Cartographer
Cartographer
1.0 Introduction
Google Cartographer is a project that was originally a Google in-house project that has now become open source. The mission statement of Google Cartographer is to advance Simultaneous Localization and Mapping (SLAM) as a technology, with a focus on Light Detection and Ranging (LiDAR) SLAM. The majority of work done for the project is done by the original Google group, though some newer developers have worked on the project since it went open source.
Cartographer has two main purposes: 1) to provide localization of a device on a virtual map and, 2) to generate (or update) that very same map. The system requires integration with a robotics platform to provide sensor input, but once connected, the system can obtain 2D or 3D maps of a local area. The localization component involves computing the trajectory of a sense enabled device through a given metric space. The input to the system is sensor data, and the output is the best estimate of the trajectory of the device that provided the sensor readings. This is a probabilistic process compare a sensor reading with the base map in an attempt to find a high probability match, thus indicating a specific location and pose for the device.
Additionally, cartographer relies on a module to take sensor readings and integrate a series of these into a 2D or 3D map that attempts to minimize the inconsistencies created by the various readings taken at different time instances from different locations and poses. The system for localization is by necessity a near-real-time system. The processing power of the device requiring SLAM is often a limiting factor in the computations for localization can be significant.
Project
Team
Supervisors
2.0 Stakeholder Analysis
2.1 Stakeholder Assessment
This systems primary stakeholders are the users of the system, without them, no other stakeholder would have standing. These stakeholders are most concerned about system performance and availability as SLAM is a mission critical feature for an autonomous device.
If we consider the key end user as a robotics researchers or vendor who utilize the Cartographer system for SLAM as part of a larger autonomy package for a given robot, this leads to some more obvious business goals. Cartographer has been integerated with several platforms like ROS, TurtleBot, Toyota HSR and Fetch. ROS is by far the most advanced and well used integration. Consideration of the integrations with robotics platforms indicates a wide range of potential stakeholders.
Role | Concerns | Instances |
Acquirers | Oversee the procurement of the system or product | Robotics hardware vendor |
Assessors | Oversee the system’s conformance to standards and legal regulation | Regulatory compliance officer |
Communicators | Explain the system to other stakeholders via its documentation and training materials | Technical writers for OEM platform vendors, Cartographer Google Group members |
Developers | Construct and deploy the system from specifications (or lead the teams that do this) | Google dev team, open source providers, robotics integration platform devs |
Maintainers | Manage the evolution of the system once it is operational | Hardware vendors who include Cartographer as COTS software for robotics systems |
Production Engineers | Design, deploy, and manage the hardware and software environments in which the system will be built, tested, and run | Robotics hardware engineers, SIL/HIL test writers |
Suppliers | Build and/or supply the hardware, software, or infrastructure on which the system will run | ROS/TurtleBot/Toyota HSR |
Support Staff | Provide support to users for the product or system when it is running | Robotics platform vendor, integration vendors (ROS/TurtleBot/Toyota HSR) |
System | Administrators Run the system once it has been deployed | OEM robotics vendor |
Testers | Test the system to ensure that it is suitable for use | SIL/HIL tester |
Users | Define the system's functionality and ultimately make use of it | Robotics researcher, hobbyists, OEM automotic sensor vendor |
*Stakeholder Assessment Table*
2.2 Business Goals
The developers clearly indicate the focus of Cartographer and these can be considered excellent business goals.
Advancing and democratizing SLAM as a technology
Provide 2D and 3D SLAM to robotics researchers and developers
Heavily focused on LiDAR SLAM
Support multiple sensors and platforms
Enable lifelong mapping
Enable localizing in a pre-existing maps
Current work
Current work on the platform as described by the development team in their open house slides provides an insight into the business goals of the project.
Cloud-Based Mapping
Multi agent collaborative mapping
GPS support
Improve test coverage
Insight into the aspriration of the development team is available from a review of the main active open projects in the repository:
Improve multiple trajectory handling for mulitiple robots with potentially concurrent trajectories. RFC Project 9
Add the ability to incorporate NavSatFix (GPS) data into the ROS integration to reduce drift RFC Project 7
Improve the accessibility of map data in the ROS integration by allowing pbstream files to be created RFC Project 6
In the GitHub documentation, the development team exposes much of their technical aspirations in the form of these Request for Comment (RFCs) which are a controlled avenue for bringing in new functionality to the code base. The development team identified the following projects for consideration. They largely fall under the Managing Market Position standard business goal category. This has to do with the business objective of improving the quality and functionality of the SLAM system with respect to other industry players.
Want to use Cartographer to support cloud based collaborative mapping
Want to allow Cartographer to use gRPC (an open source remote procedure call system that can exchange data better between Cartographer nodes)
Change to using Proto3 instead of Proto2 as a protocol buffer
Improve readability by refactoring the codebase to eliminate the redundant term 'sparse-pose'
Create a public API
Simplify the existing API by unifying redundant TrajectoryBuilder implementations
Optimize PoseGraphInterface to reduce technical debt incurred by moving to gRPC cloud architecture
Reduce overhead and generation of redundant map data by changing the serving location in ROS to a pbstream file
Develop customizable collators to allow agents to be offline without locking up the collation system
Improve the ability to handle multiple trajectories across multiple ROS data bags to improve collaborative mapping performance
Improve technical documentation to expose more existing features to users
Dominant Business Goals
From all of the documentation surveyed we feel that the dominant business goals for the Cartographer project are:
Facilitate cloud based SLAM using the existing system with remote co-ordination or multiple trajectories
Enable GPS sensor data fusion
Enhance usability for researchers by simplifying interfaces
Improve interoperability between multiple platforms using ROS
Improve code readability before issuing 1.0 version and public API
3.0 Architecturally Significant Requirements
Architecturally Significant Requirements or ASRs are project requirements that if absent, would have a profound impact on the project outcomes. An ASR necessarily has a high business value.
ASRs can be categorized into one of the following three areas: 1. Functional Requirement - how the system must behave or react to stimulus 2. Quality Attribute Requirement - a qualification of the functional requirement 3. Constraint - a design decision with no degrees of freedom
Listing of ASRs
We considered the incoming business goal analysis as well as a comprehensive review of the documentation and online commentary sources to develop this list of ASRs for the Cartographer project. The system is meant to be implemented on mobile computing hardware, largely for researchers, so this playing an important part in our selection process.
Interface using a Publish/Subscribe pattern with downstream consumers/creators of the data (ROS, etc.)
Operate such that performance can be tuned to deliver trajectory projections, as messages in near real time
Be able to readily access and process data from COTS sensor arrays and other system inputs
Create an abstractable design that can be used in multiple environments and moved between said environments
Allow the software to be version controlled during the course of large scale deployment
Changes to the software can be tested on the fly to allow public involvement not to interfere with code integrity
Mapping data should be saved in a reasonable manner
Algorithm must be able to maintain the relative position of the sensor accurately
Code must be easy to understand in order to be modifiable by other developers
It should openly support multiple sensors and platforms
Algorithm must be able to optimize both generated and visualized floor plans in real-time
Hardware expectations : 64bit CPU, ideally a core i7, to avoid libeigen alignment problems
Algorithms implemented must achieve real-time loop closure
2D and 3D mapping algorithms should both be efficient
Quality Attribute Scenarios
QAS are used to quantify the qualitative nature of the attribute to be able to measure success. They require;
Source
Stimulus
Environment
Artifact
Response
Response Measure
Performance
Scenario name | Process Position Data |
Business Goals | Effective algorithm for calculating position, pose and trajectory of a mobile robot |
Quality Attributes | Performance |
Stimulus | Deploy the device in operating status |
Stimulus Source | User needing localization and hardware request |
Response | Process data from sensor and sending back mapping response |
Response Measure | Mean accuracy <= 5mm |
Interoperability
Scenario name | Cross-Platform Communication |
Business Goals | Achieve inter-platform communication |
Quality Attributes | Interoperability |
Stimulus | Need for an alternate or novel platform to be able to utilize the system |
Stimulus Source | User implementing on the other paltform, software based |
Response | Able to read and write incoming and outgoing data in message form |
Response Measure | Successfully send and receive data message or enable error correcting algorithms on failure |
Usability
Scenario name | Save map to image |
Business Goals | Whe system ceased operation, there must be an algorithm to store the resulting map to an accessible image. |
Quality Attributes | Usability |
Stimulus | Need from user to save the map to the computer |
Stimulus Source | User stops the system and wants to view the map |
Response | Able to save the resulting map had so far and output a recognizable format |
Response Measure | Successfully save the map to the local machine or enable error handler |
Listing of QASs
As this system is a real time or near real time system, attributes like performance and usability were important. Interoperability and maintainability were also key issues which address the 'Advancing and democratizing SLAM as a technology' goal. It is not possible to draw a 1:1 relationship between goal and these QASs, as many address several business goals simultaneously. Availability and Security play a role, but as the systems are usually used with other systems that address these areas as a group, these were not dominant in our analysis.
Usability
When the system is in running mode, localization is delivered as a discrete message to the subscribing system in a format that results in a successful interpretation by the client device. Technical Complexity - medium : Business Priority - medium
When the system has ceased operation, the resulting map created by the algorithm must be stored as an image. The map can be veiwed on any jpeg viewed. Technical Complexity - medium : Business Priority - high
Interoperability
When completing a build of the project, the build should be self-contained and deployable on multiple environments. Compatible with advertised ROS distributions at a minimum. Technical Complexity - high : Business Priority - high
Modifiability
Whenever the code base is being modified, by a development team, there will be versioning on the modifications. Each code change will have a separate version associated with it. Technical Complexity - low : Business Priority - low
Performance
When the system is in running mode, the deployable position must be within 5mm of the algorithms calculated position. Technical Complexity - high : Business Priority - high
When an client of the system requests a localization or trajectory approximation, based on sensor data, the system will provide a valid response, with an estimate of error in the approximation, in less than 500 ms. Technical Complexity - high : Business Priority - medium
Configurability
When designing an environment to deploy the project to, the sensor chosen must be modular, replaceable and accessible to designers to allow for flexibility in design. Compatible with all COTS as well as custom laser range sensors. Technical Complexity - low : Business Priority - high
Maintainability
When a developer submits a change to the code, the project shall be tested to ensure the change meets a set of testing parameters. The change passes all automated testing parameters. Technical Complexity - medium : Business Priority - high
Utility Tree
4.0 Module View
This document presents Team 2's recent work examining the architecture of the open source Cartographer project. We provide a module view presentation as envisioned by the Carnegie Mellon Software Engineering Institute.
Module Uses View
Element Catalog
The following section presents the 9 major modules of the Cartographer system. We chose this architectural view as it presents the core components of the system. The designers did an excellent job of segmenting the code base into folders, which we follow as we present the various elements of the system shown above.
Common
Common is primarily used for core functionalities such as object definitions, LUA integration and ensuring concurrency. There are also helper functions and cartographer port definitions.
Ground Truth
Ground Truth contains machine learning that is core to the mapping algorithm. The code compares the current position to the position generated during the last loop and calculates the distance travelled.
Internal
Internal has the helper functions and header files needed for Mapping, Mapping 2d, and Mapping 3d. Local trajectory builders for the three Mapping folders are also included.
IO
I/O contains code to draw graphical representations of the programs actions during runtime. It also has filestream objects and other things for saving this information to memory.
Mapping
Mapping is where the calculations for things such as pose, trajectory, and location probability are done. Mapping also builds the map using all the information from other files.
Mapping 2d
Mapping 2D has similar functions to the mapping folder, although the calculations are only done in two dimensions. It creates a 2D submap and pose map as helper steps for the mapping folder.
Mapping 3d
Mapping 3D provides functionality to create 3D pose maps and 3D submaps, as well as testing ranges in 3D space compared to the previous scans.
Sensor
Sensor is used to take in the sensor information and turn it into variables that can be used in other functions. This includes things such as range, map position with respect to time, calculating trajectory and establishing any landmarks that can be used for position tracking.
Transform
Transform uses Eigenvalues and matrix algebra to get information from the maps.
Context Diagram
The following diagram shows the context for the operation of Cartographer. The main application has bi-directional flow from the hardware (mobile robot typically) which in turn takes input data from both the lidar sensor and the ground truthing odometry sensor.
System output is the area map, as well as providing trajectory (location, pose and rate of change of each) continuously in real time to the ROS client. These data artifacts can be packaged and reused as base maps for other mobile devices as if they were created by the using system.
Behaviour Diagrams
We selected two critical QASs to examine using behaviour diagrams. These QAS are presented below for clarity.
Quality Attribute - Performance
Performance is a critical QAS, as the mobile devices implementing Cartographer need to be able to localize faster than they can actually locomote themselves. This requires the accuracy of the positioning to be sufficiently high to allow confidence before sending motion command to the robots actuators.
Scenario name | Process Position Data |
Business goals | Effective algorithms for calculating position, pose and trajectory of a mobile robot |
Quality attribute | Performance |
Stimulus | Deploy the device in operating status |
Stimulus source | User needing localization, hardware request |
Response | Processing data from sensor and sending back mapping response |
Response measure | Position mean accuracy |
Performance - Use Case Diagram
Performance - Sequence Diagram
Quality Attribute - Interoperability
Interoperability is another important quality attribute that is addressed by Cartographer’s architecture. The core functionality should be able to be implemented by a variety of devices running a variety of client software. ROS is the dominate client platform, but there are many others in use, and will likely be more as hardware evolves. Without cross platform interoperability, the utility of the open source project is significantly reduced.
Scenario name | Multiplatform Interoperability |
Business goals | Achieve inter-platform communication |
Quality attribute | Interoperability |
Stimulus | Need to have an alternate or novel platform to be able to utilize the system |
Stimulus source | User implementing other platform, software based |
Response | Can read and write incoming and outgoing messages |
Response measure | Successfully receive and send message or enable error correcting algorithms on failure |
Interoperability - Sequence Diagram
Interfaces
We provide two interfaces that are critical to the overall system; the ROS (mobile client) interface and the mapping interface.
ROS Interface
Mapping Interface
Rationale
Cartographer is a mathematically complex program that needs to be capable of being modified by a large number of developers. This is a function of the user base who are are typically researching and building custom robotics systems and architectures to support them. Cartographer’s design aims for high cohesion, in order to make the code easily modifiable by a diverse group of developers. By keeping the modules within well defined boundaries it is easy to find the code associated with a quality attribute.
Cartographer is built around nine core modules. One of Cartographer’s key modules is called Common. It is dedicated to structures and functions with shared usage throughout the system. Cartographer does not aim for cohesion is it’s Common module. Performance is assisted by providing common programming objects, such as queues, in performance empathetic versions. Objects that work well with concurrency are prevalent throughout Common. By offering performance emphasised objects, Cartographer makes it easy for developers to program in a manner that achieves their performance goals.
Additionally, the Common module is used to prevent copies of code that perform the same task from proliferating in the codebase. The downside to Common is it is difficult to gauge whether a functionality is part of it from just the functionalities description. Common also provides generic functions used throughout the system and LUA integration.
Configurability is an important quality attribute, and Cartographer is architected around this concept. Configurability is enabled through a number of LUA scripts. LUA was chosen as it is easy a relatively simple language in which to perform high level changes. The LUA scripts add a degree of abstraction so a user can alter Cartographer without needing to alter the more complex C++ source code. The changes that can be provided through the configurablitty scripts are limited to common options the developers chose to provide. More complex changes to Cartographer are somewhat supported through the cohesion of the modules and robust documentation that supports the project.
The following four modules; Internal, Mapping, Mapping 2D, and Mapping 3D are tightly coupled. Due to different approaches required for 2D and 3D mapping within Cartographer, as well as the ideology that not all systems will require both types, the mapping module has been segmented by dimension rank. This split increases the cohesion of the individual modules and supports modifiability. The downside to this architectural choice, splitting the Mapping module into three distinct modules is that it can be unclear where each component located. From a general perspective Mapping contains functions that are common to both 2D and 3D implementations and anything specific to either type of mapping is put in its perspective folder.
Internal contains helper functions and structures used throughout mapping while also containing connections to Sensor which captures the input data required as feedstock to the mapping process. Internal provides greater cohesion for functions that would otherwise be gathered in the Common module. As such, the choice to segregate Internal is effective at increasing the modifiability of the code.
The Transform module, which provides unit conversions and transformations of vectors and matrices, is also strongly coupled to the mapping functions as these are key to the mapping process itself. While Transform may be tightly coupled to the mapping modules, it is also tightly coupled to the IO module.
The IO, and Transform Libraries are very tightly coupled and act as a conduit for the output of all the mapping modules. As maps are created the data is interpreted through Transform. Once passed through Transform, data is changed into a graphical form as a voxel map and saved through the IO module. IO acts as the graphical output for the mapping functions. While IO is a somewhat generic name choice for a module, it is appropriate in this case as all of Cartographer’s output passes through this module. One exception to the inferred purpose of the IO module, is that Cartographer’s primary input is handled through the Sensor module, not IO.
Sensor is a module that controls the data inputs into the program. LiDar and odometry information supplied via ROS (or other mobile client) comes into the rest of Cartographer via this module. Sensor abstracts the physical information provided to it into data which can be read by the rest of Cartographer. Sensor is key to Cartographers interoperability QA goals as it changes input from something sensor specific, into a format readable by Cartographer’s data processing modules. Cartographer’s interoperability is so strongly defined at this specific part of the system architecture, we can say that any implementation that can provide data in a way which Sensor can interpret and which can run Cartographer’s code has access to the the entire Cartographer system.
5.0 Component and Connector View
Voxel Filter Pipeline
Voxel Filter Pipeline, which is between the input of LiDAR data and the submap generator component, acts as the primary data input pipeline in cartographer. The input of the voxel filter consists of one three dimensional float vector marking the origin and two point cloud structures marking hits or misses from the scanner. Point clouds are a grouping of three dimensional vectors defined by floats. The filter itself takes in three integers as modifiers that change the output. These modifiers are the max length of the voxels edge, the minimum number of points that must pass through this filter, and the max range the vector can be from the origin to pass through the filter. If the minimum number of points is not met, the max length is increased until the minimum can be met. After passing through the filter, the result is a hits point cloud and a misses points cloud with all the vectors that met the filters criteria.
Submap Generator Pipeline
The Submap Generator Pipeline deals with the submap generation and the Ceres scan matching algorithm. The pipeline is placed after the voxel filtered point clouds are created and acts as the map builder for Cartographer. The input from the voxel filter pipeline is point clouds outputted from the Voxel Filter pipeline. This pipeline also takes in the pose from the pose extrapolator pipeline which is stored as a Rigid3d data type. Rigid3d consists of two main parts, a three dimensional vector with the data stored in doubles, as well as a quaternion that also has its data points stored as doubles. A quaternion is a representation that makes spatial rotation calculations fast and efficient. From a data type perspective, they can be thought of as a 2 x 2 matrix of complex numbers, or typically represented for computation, as a 4 x 4 real matrix.
Inside the filter, the point clouds are matched onto the submaps and a new pose is sent to the pose extrapolator pipeline as a poseGraph structure, this is the pipelines output. The poseGraph structure consists of a submap ID and node ID, as well as a rigid3d structure with translation and rotation weights added on.
Pose Extrapolator Pipeline
The pose extrapolator pipeline takes information from Ceres the Odometry to infer position and orientation at a time. The robotic odometry sends the pipeline the current system time as a 64 bit integer as well as a Rigid3d structure of its pose calculated by the robots delta position. The Ceres scan matching algorithm also sends the pose that was used during its last calculation as another source of input for this pipeline. Using both of these pose inputs, the extrapolator checks to make sure that the information is valid, and infers pose if one of the two seem invalid based on previous pose extrapolations. The output is sent the Ceres scan matching pipeline as a Rigid3d structure.
Element Catalog
Laser Range Data
This filter element represents a hardware source of data, in our case a LiDaR sensor module. This device reports time stamped point clouds of data in either 1, 2 or 3D. In some cases 1 or 2D devices are oscillated or swept across an area to create higher dimensional views. In any case, the data set is referenced from a device origin, and is a series of time stamped, ray tracing, distance to return measurements (laser hit something solid) along any number of vectors originating from the origin and radiating into spatial areas of interest.
http://velodynelidar.com/hdl-64e.html
This data format is a function of the mechanism of collection, but can be used to generate point clouds for series of instants in time as shown in the sample image above, created from a rotating line scanner with 64 discrete points or rays. Rotation frequency of the device is relevant and therefore corrections for the moving origin are required to compensate for robot motion. Also notice the shadow cast by the person near the center of the point cloud.
Voxel Filter
The voxel filter element takes the incoming range data and converts it to a sparse point cloud. Returns beyond a certain range or distance are trimmed to reduce the overall point cloud size to aid in achieving real time performance. The sparse point cloud is then binned in coarse resolution voxels. If there are sufficiently high number of returns in a given voxel, it is considered solid, not enough points, empty space. These control criteria can be specified via the LUA dictionary. Voxel size is also adjustable to allow performance to be tuned dynamically.
Excellent video link showing progressive build - https://www.youtube.com/watch?v=dTTrCQuamPk
Cartographer uses a coarse voxel filter for fast localization and loop closure as well as a higher resolution voxel representation for display and refinement of the global map. A sample image of a sparse (much empty space) voxel map is shown above for reference.
Ceres Scan Matching
Ceres Scan Matching filter element is a third party library that implements spatial matching algorithms. It can take a voxel submap and find the highest probability location and orientation or pose estimate for that given submap. Due to the successive scan nature of the process, the next submap is highly overlapping typically, so that the maps, once matched and located with one another create a self seeding composite map or current map.
To assist in successfully locating a given set of scan data, a high fidelity estimate of the pose origin of that particular scan data set is very useful in reducing convergence time in the Ceres matching logic. This estimate is based on where the odometry component expects the scan at a given time to have originated. The better the estimate, the faster the match time.
Submaps
Submaps are individual voxel maps that show the probability that a voxel is occupied or more technically; a regular probability grid where each discrete grid location represents the probability that the corresponding physical grid location is occupied or empty, in reality.
When several submaps are aggregated together or properly aligned with respect to each other, they provide multiple estimates on voxel occupancy. These multiple probabilities are again aggregated to create the current map, or the collective best estimate of the available scans of the surrounding surface area.
Currently, the Cartographer group is moving to allow the combination of multiple sources of submaps to be used to create a common current map. This would allow multiple agents to complete SLAM collectively. This is visible by the gRPC code being morphed into the codebase.
Robotic Odometry
The robot odometry is a combination of spatially aware sensors. Often a set of rotary encoders to map wheel based motion. An IMU is also integrated to provide relative change in inertial forces as well as provide a consistent gravity vector to help estimate pose. These aggregate data are forwarded to the pose extrapolator and onto the scan matching components to aid in better estimating the origin location of the scan data in the composite submap structure and hence better predicting the submap location and orientation.
Pose Extrapolator
This filter element takes data from robotic odometry component and uses this ground truth data to extrapolate the robot pose - location and orientation of the device as well as the range sensor. It also is updated from the scan matching functions and provides updated pose estimates for future scan matching by the Ceres component.
Context Diagram
The following diagram shows the context for the dataflow of Cartographer. The system has two main inputs, Laser Range Data and Robotic Odometry Data. Each of the inputs move through a pipeline which accepts some feedback from other pipelines as seen below.
The dataflow is relatively convoluted, but can be abstracted to follow a pattern as above. Output from this process is the area map, as well as providing trajectory (location, pose and rate of change of each) continuously in real time to the ROS client.
Interface Documentation
Voxel Grid Interface
Identity
SubmapGenerator
Resources
Syntax:
Submap SubmapGenerator(PointCloud pointCloud) ~ or;
Submap SubmapGenerator(TimedPointCloud timedPointCloud)
Semantics
Pre-Condition: Takes in point clouds which are formed by a set of ray tracing range data coming from LiDaR sensor. Timed point cloud is a point cloud with seconds since the last point was acquired stores as the last point.
Post-Condition: Each point cloud is placed on a voxel grid that says where it is in relation to the other point clouds. When enough point clouds have been placed submaps can be generated.
Datatype
Point Cloud is a collection of three dimensional vectors. Each vector has three floats that store the X, Y, and Z coordinates. The timedPointCloud contains a fourth float that has time since last point was acquired.
Error Handling
Compares point clouds to others on the voxel grid and can change other point clouds grid location if needed once more data has shown it to be placed the the wrong grid.
Rationale
The interface was designed to be updated based on data coming in from the voxel filter so that outlying data can be smoothed out and a proper submap can be created.
Adaptive Voxel Filter Interface
Identity
VoxelFilter
Resources
Syntax
PointCloud AdaptivelyVoxelFiltered(const proto::AdaptiveVoxelFilterOption& options, const PointCloud& point_cloud)
Semantics
Pre-condition:Takes in filter options which are stored as a proto message and takes in point cloud which is formed by a set of range data coming from sensors.
Post-condition: After running through the function the original variables won’t change, but the function returns a new filtered point cloud which is based on user’s options such as maximum voxel edge and minimum number of scan points in each cell.
Datatype
Point Cloud is a collection of three dimensional vectors. Each vector has three floats that store the X, Y, and Z coordinates. Options is a proto structure that contains max_length, min_num_points, and max_range which are stored as doubles.
Error Handling
It uses some conditional statements to handle the errors on point cloud, and if any error occurs it will return the original point cloud.
Rationale
Before a set of sensor data(point cloud) can be inserted into the voxel grid, cartographer runs a real-time voxel filter on this data to make the voxels stay at a consistent size. This improves the voxel grid creation which improves the accuracy of the submap when enough data has been gathered.
Variability Guide
Robots are not always going to be looking at the inside of a lab full of squared off edges and solid walls that provide clear edges to build a map from. In the field, robots need to be able to generate maps with obstacles such a rising slopes or lack of defined edges on the area being mapped. Due to the difference in various terrains that robots operate in Cartographer needs to be able to sort the incoming data in a way that still performs when in any of the possible terrains. Another issue is that the robots orientation or position changes in no clear pattern to Cartographer as they may be human controlled. Placing the data into a submap grid greatly improves the variability of the overall system in both of these situations as data can be compared to only certain grids.
Another form of variability is language variability. ROS is the most common implementation of the Cartographer controller and is written in C++ like Cartographer is. However, other implementations that interface with the Cartographer SLAM service do so via another platform and some of which are written in languages other than C++. To accommodate this variability, in support of the interoperability QAS presented in M3 the developers implemented protocol buffers to create a simple way to maintain a simple, XML like format of global data types. Then at compile time a precompiler is run to generate the language specific classes and header files, which are then compiled with the existing codebase, which references these data structures.
Rationale
Cartographer employs a variety of data types to support good information flow. Our C&C view of Cartographer covers 3 pipelines that are core to Cartographer. Cartographer also aims to address performance and interoperability goals with its data flow design.
Cartographer addresses performance concerns by allowing different systems to run concurrently. LiDAR data can be gathered, but the actual processing can be delayed by the system until an appropriate amount of data is present. In Cartographers Submaps component small maps are collected until all of the submaps can be assembled with reasonable confidence, by the Ceres Problem Solver, into a single map. By deferring the final assembly of the map until all the submaps are correctly assembled or positioned, the processing time spent by Ceres is reduced. In order to increase simplicity of mapping, the maps are filtered, in the Voxel Filter, to lower resolution. This optimization helps Cartographer run in real time.
Interoperability goals in Cartographer are key to Cartographers design. Proto is used in Cartography to mark up data types in a platform independent way. Other languages can access proto structures as needed which helps lower coupling in Cartographer. Data from sensors is passed through ROS allowing a standardization of sensor input. Cartographer is designed to handle basic sensor data from the OS in order to work with a variety of sensors appropriately.
In our Context Diagram three major pipelines are outlined. Pipeline 1 handles data coming in from the Lidar sensors, going through the Voxel Filter, and exiting towards Submaps, Pose, and Ceres. Pipeline 2 covers data coming from Robotic Odometry, Ceres, and the Voxel Filter which is then stored in Pose for use in Submaps and Ceres. Finally, Pipeline 3 Covers the transition of information from Ceres to Submaps and the various inputs to both.
Voxel Filter Pipeline, which is between the input of LiDAR data and the submap generator component, acts as the primary data input pipeline in cartographer. The Voxel Filter takes in a collection of points in 3D space that represent the laser’s hits as well as the origin, from which the lasers are shot. The filter then performs a process similar to clustering in order to group points into voxels. The voxel maps created are fed into storage and more processing in the Submap Generator Pipeline.
In the Submap Generator Data is fed into Submaps from the Voxel Filter, these submaps are stored for future use. Pose information from the Pose Extrapolator Pipeline is also stored within the Ceres Scan Matching. Ceres takes in Submaps from the voxel filter and pose information. Ceres aims to find how all the submaps align and outputs its submap organization into submaps for storage.
The pose extrapolator pipeline aims to place the robot in the 3D maps it has created at a distinct time. Data concerning the robots movement is taken from Robotic Odometry as well as map information from Ceres. This Pose information is then sent to Ceres and Submaps for their use.
As seen in M3’s module view the data dependencies in Cartographer are numerable and complex. Tracing dataflow in Cartographer is quite difficult and does not support modifiability. As stated above the dataflow design instead aims to be fast and abstracted. Cartographer itself is not the area where modifiability is expressed, rather this is implemented in the ROS (or other platform) interface.
Related Views
Please see the following additional views relevant to the project:
Return to: Introduction
6.0 Code Quality Review
This code quality review serves to determine how well Cartographers code base conforms to best practices and the impacts of deviations from those on the Quality Attributes the user base cares about.
Generally, the Cartographer code base is very dense. They use protocol buffers to template many of the structures to improve interoperability. However, this comes at a cost of readability. Additionally, it is an implementation of a specific geometric algorithm coupled with some unique statistical inference. Additionally, the project group is actively transforming the key 2D and 3D libraries while simultaneously folding in gRPC structures to allow for multi agent SLAM.
We decided to analyze the code base using several of the tools as some were better than others and produced different inferences into the quality of the overall codebase.
Tools Used
We used several tools to assess code quality. First, we used Understand as it was previously used to help with the Module and C&C milestones. This program has static code analysis built in and worked to show us some code smells and identify areas of potential technical debt.
Additionally we used SonarQube, which was very challenging to use. Several of our team members attempted to get it to run. Only one was even moderately successful, however this was on a local instance, so we are not able to share it for review like a cloud account.
CodeScene was used extensively as well as the CLI based cpplint. The results from all of these four tools is summarized after each is presented individually in the sections below. The summaries include a brief description of the tool, what is could look for, what it did not find some of the key findings.
Understand
Understand is a static software analysis tool that was used in the earlier phases of the project, while not used as a comprehensive tool to evaluate code quality, it does have one interesting quality tool called Metrics Treemap a form of heat map, in these maps a gradient of color is applied across a segmentation map. The characteristic being examined is most expressed when the color is dark and the segment size can also be selected; by file, by class, etc.
The maps shown in this section show the entire library build, with Cartographer shown highlighted in yellow. In many key metrics (line count, max cyclomatic, etc.) we found that the Cartographer code had better metrics than most included libraries, indicating that it was low in technical debt.
One area where it did show issue was in commenting. When we analyzed the ratio of comment to code and looked at Cartographer and ROS combined, we found quantitative support from what we had noted in the codebase qualitatively; a pronounced lack of comments. Commenting was widely variable and often insufficient to understand even the purpose of the class, let alone the inner workings.
However, the metric used in Understand can be misleading as much of the comments showing below as well commented below (green) are simply license header comment blocks. See the Technical Debt section for more discussion.
]
Understand also had another tool called CodeCheck that performs static analysis. We used this to identify code smells. We ran this tool on a subset of the code base; the cartographer source proper, not including any of the ROS code or math libraries.
The results showed lots of uncommented variables, many defined by unused identifiers and also lots of magic numbers (numeral literals with little reference as to the reason for their selection). This lack of commenting negatively impacts the maintainability QAS described in previous milestones.
CodeScene
CodeScene is a behavioral code analysis tool written in Clojure. Instead of doing traditional static analysis, it looks for patterns in version control data to understand the history and evolution of a code base: unravelling things like hotspots, temporal coupling as well as complexity trends.
Hotspots
A hotspot is complicated code that a developer has to work with often. In CodeScene, hotspots are calculated from two different data sources:
Lines of code in each file as a proxy for complexity
Change frequency of each file as a proxy for the effort one has spent on that code
The following image shows the hotspot analysis for Cartographer:
Each large, blue circle represents a package in Cartographer. The packages in the figure follow the directory structure of Cartographer. Inside each package, source code files can be found. The biggest circles in darkest red are the top hotspots in the codebase. In other words, pose_graph_2d and pose_graph_3d are the two modules to which most of development activities tend to be located.
Temporal Coupling
Temporal coupling means that two (or more) modules change together over time. CodeScene provides several different metrics for temporal coupling. The tool considers two modules coupled in time if they;
are modified in the same commit, or
are modified by the same programmer within a specific period of time, or
refer to the same Ticket ID in their commit messages.
The following figure shows the temporal coupling for Cartographer:
The pose_graph_2d.cc and pose_graph_3d.cc have the highest sum of couplings - 656 and 654. If looking at the temporal coupling by commits, these two modules have very high degree of coupling: 82%, and the number of average revisions even reaches to 150. If looking at the temporal coupling across commits, the degree of coupling between these two modules is 83% and the number of average revisions is 117.
This tool helped us zero in on potential areas for technical debt as it tends to accumulate in proportion to code rework. When we examine pose_graph_2d.cc and pose_graph_3d.cc we notice one thing; lots of comments compared to the rest of the code base. These comments are instructional, bread crumbs for other developers that indicate that the code can be challenging to understand. All the commits, over time, motivated the developers to add these helpful in code artifacts, which based on the lack of comments elsewhere, indicates this as any area to investigate for issues.
Complexity Trends
Complexity trends are used to get more information around hotspots. A complexity trend is calculated by fetching each historic version of a hotspot and calculating the code complexity of those historic versions.
The figures above show the complexity trends of pose_graph_2d and pose_graph_3d respectively, starting in mid 2016. It paints a worrisome picture since the complexity has started to grow rapidly since April 2017.
As evident by the Complexity/Lines of Code ratio shown in figures above, the ratio is always over 2.0 for both modules even though there are some modifications somewhere between April to November in 2017. This ratio indicates that the code in the hotspots - pose_graph_2d.cc and pose_graph_3d.cc - may be overly challenging to understand, which negatively impacts modifiability, a key QA for this project.
SonarQube
SonarQube is an enterprise solution to code quality analysis. SonarQube offers insight into Code Smells, Bugs, Debt, Testing Coverage, and Duplicated Sections of code. SonarQube markets itself as a continuously updating version of other tools, but it is a much more robust tool then that. SonarQube is made of two main pieces, a server and a scanner, making it a
lot more complex than other tools to get up and running.
The server for SonarQube is a Java based system made to allow web distribution of results. The server is a robust platform which offers security, code quality report tracking, and multiple projects. It is reasonably easy to configure the server once its PATH variables are added. The server also supports a variety of plugins to offer greater versatility. Plugins can be added through drag and drop and then a restart of the server, making install relatively simple. Finally as the server is in Java it works on Windows, Linux, and Mac.
The SonarQube scanner is a client side way of publishing results to the server. Some configuration is required in order allow the scanner to talk to the server, but it is simple in a local environment. Our issue with this tool for our project is that it does not support the C++ that our project is made of primarily.
CXX is a open source plugin that offers C/C++ support. One of the issues with CXX is that it does not actually do any code sniffing on its own. CXX purely acts as a tool to decode other tools output, like CPPCheck. We found our best solution was too output results from CPPCheck and then too use scanner as a way of publishing them. Configuring scanner in this way proved very difficult as it was not undocumented. As CPPCheck is not a very special code checker our attempt at SonarQube was left here.
In the end SonarQube proved to be a powerful tool with huge upfront cost. In a work environment where employees are very spread out it would offer a unique solution through its web interface. If SonarQube is configured extensively it is the most powerful tool as it can consolidate information from other tools, but out of the box it proves a little lacking.
It is worth noting that SonarQube was very effective at checking python code of which there is around 200 lines of in our project. While not key to our projects overall quality a small analysis of the python report is done below.
From above we can see that there were no bugs or vulnerabilities where found with the built in SonarQube quality profile, other profiles can be added as plugins as described above. As we did not run any batch testing our coverage is 0%. First taking a look at code smells we can see there are 8 smells present.
Those 8 smells are rated by Severity, Personnel Assignment, and time to complete. A number of other metrics to organize the smells are also available on the left. This provides a effective way for teams to look code smells. The Debt rating of ‘1h’ acts as a tracker of how much time would be needed to completely rectify the code to SonarQube standards. Finally Duplicated lines shows what sections are repeats and could be changed to functions.
Cpplint
Cpplint is an open source automated source code analyze tool written in Python script that can flag programming errors, bugs, stylistic errors, and suspicious constructs. This tool was first developed by Google in 2009. The ultimate goal of Cpplint is to make sure C++ code file follows Google’s C++ coding style guide.
We ran this tool on an Anaconda environment with python version 2.7 installed. By using prewritten Windows batch file we recursively ran this python tool on each of the cpp and header files and stored the results for each module. Results are presented in a textual format, as seen in the screenshot below;
After finished analyzing code file, it will return total error number found in this code file along with the full paths, including which lines are they and suggestions of how should they be fixed. It also gives issue type, for example it will add [build/include_what_you_use] when it found missing #include guard, and confidence scores ranging from one to five. Where five means that the tool is very certain of the problem and one refers to issues that could be a legitimate construct.
From the results we have, we see a numerous error reports found for each module that most of them are having style problem with #ifndef header guard and some #include guards. But also a major issue is there is some unapproved C++11 headers such as and which we think it could to be easily turned into technical debt. There is also some less important coding style issues such as, redundant semicolons after curly bracket or lines exceeding 80 characters in length.
Having source code before built examined and analyzed by such simple lint-like tool, although there could be many errors made due to the dependencies not being built and recognized, we still think it is showing some of the aspect of their coding quality and helped us to inspect the architecture more carefully in terms of the potential for technical debt.
Cumulative Summary of Results
We reviewed several tools to pull in a wide range of analysis of code quality. We found that lacking of comments was reported by Understand which can leads to negatively impacts the maintainability. With the experience of CodeScence, we found that pose_graph_2d.cc and pose_graph_3d are the two modules which change most frequently and the most challenging to understand, this may also lead to poor maintainability. We run a small analysis on SonarQube, based on the report we generated, the overall quality is good but still have minor problems like code smells and duplicated lines. Last but not least, coding style issues were found by Cpplint and this produced similar results to the output of the CodeCheck from Understand.
From this we concluded the most significant code quality issues were lacking of commenting, and coding style issues because they can lead to negative repercussions on the maintainability QAS that are important to the system users.
Technical Debt
The following section presents our findings on the technical debt accumulated in the Cartographer code base. The project is a Google codebase turned Open Source. As such it has excellent code quality, although as noted above is very dense and challenging to read. This is in part to it being a complicated geometric algorithm, but is not helped by almost a complete lack of comments, not including license headers.
Technical debt is an implied rework cost stemming from choosing a relatively easy to implement solution now rather than using a more time consuming to produce, but inherently more efficient approach. In our case lack of commenting negatively impacted the modifiability QAS’s associated with this project.
Analysis of Potential Debt
Although it was challenging to find significant technical debt is a mature Google project, the following sections present our findings on the technical debt of Cartographer.
Lack of Inline Documentation - Comments
One key area of potential technical debt, was inline documentation. Comments were ineffective at transmitting the intent of the developers in many cases. While a deep understanding of the geometric algorithms is a requirement, even comments to indicate the purpose of a file seem to be subservient to the obligatory Apache ULA banner.
Our analysis with various static code quality tools found that ratios were both inconsistent and very low. File size was quite low for many files and any acceptably high comment to code ratios were often attributable to the licensing banner. It would be better to use a tool that took into consideration if the comments were at the beginning of the file and also if they were nearly identical to other file headers, therefore conveying little specific meaning about the individual files. An example file (ceres_pose.cc) of a typical commenting gap, with the licence header issue illustrated as well.
Google’s own style guide for C++ had this to say about comments;
"Though a pain to write, comments are absolutely vital to keeping our code readable. The following rules describe what you should comment and where. But remember: while comments are very important, the best code is self-documenting. Giving sensible names to types and variables is much better than using obscure names that you must then explain through comments.
When writing your comments, write for your audience: the next contributor who will need to understand your code. Be generous — the next one may be you!"
https://google.github.io/styleguide/cppguide.html#Comments
Clearly, if comments are vital, including none in a file is not meeting the expectations of the guidelines and is clearly technical debt worth addressing. This assessment was supported by the code smells identified in our code quality inspections. Many issues were noted for failing to document variables and numeric literal choices. This negatively impact the maintainability of the code base and was apparent throughout our entire assessment of this open source project released into the wild from Google Labs.
Refactoring Candidates
The figure above shows a list of prioritized refactoring targets for Cartographer. It is clearly that pose_graph_2d.cc and pose_graph_3d.cc are two refactoring targets with the top priority. As mentioned above, it is not hard to see why it is important to refactor these two modules:
These two modules are the top hotspots in Cartographer meaning that lots of effort is put into implementing these two modules
These two modules are highly coupled with high numbers of average revisions by commits or across commits
The Complexity/Lines of Code ratio is always 2.0 even though there were fluctuations somewhere in time.
Followed by pose_graph_2d.cc and pose_graph_3d.cc, there are other modules needed to be refactored, such as constraint_builder_3d.cc. Among these refactoring targets, the code complexity of some modules starts to rise as shown by the flag of complexity trend warning. In other words, when developing modules, such as local_trajectory_builder_3d.cc, it is important to refactor the code at the same time.
Design Tradeoffs Identified
Cartographer is a big piece of software, and as such several design tradeoffs were made. While Cartographer is open source, it started as a Google inhouse project and has a relatively strong foundation because of this. The first design trade off involves an increase of quality and complexity.
The first tradeoff identified by our team involved protocol buffer. Protocol buffers are Google's language-neutral, platform-neutral, extensible mechanism for serializing structured data. By implementing protobuf the project's interoperability is increased greatly by allowing data structures to be easily passed between languages and platforms. The downside of this is that proto buffer needs to be implemented project wide. Changing proto files is straight forward but building all of them originally would take time. This tradeoff offers increased interoperability at the cost of code complexity.
Another major tradeoff identified involves Google Remote Procedure Call (gRPC). This allows interoperability of clients running on various mobile platforms (as is often the case with mobile robots). This abstraction lets multiple agents work together on a mapping objective.
Originally gRPC was not implemented, but it was added to the project further in. Initially building the project without gRPC would be simpler, but it is more work to add a functionality late. This tradeoff was made to help the project get off the ground.
The final tradeoff that our team has identified is the splitting of the 2D and 3D mapping. Originally they were separated into two folders, which we believe is because they implemented only the 2D mapping first before moving to 3D. Laying out the code in such a way would make it very easy to check and work on originally. Recently the developers have been combing the two folders into a single one and merging the files to have 2D and 3D functionality. This is similar to the gRPC in the sense that it was done to reduce complexity while the code base was being established but has created technical debt that had to be fixed at a later date.
7.0 Conclusion
Cartographer is an interesting program that furthers LiDAR SLAM as a technology. Cartogropher's main goal of advancing SLAM as a technology. Our team looked at architecturally significant requirements in relation to Cartographer and then focused in on performance and usability as the main goals after that examination. Since this two quality attributes are the most import for a real time system. In examination of Cartographers the modules, we found that Cartographer is built around nine core modules which are tightly bound together. Looking at the core components, we found 3 pipelines that are core to Cartographer. This project offered alot of insight into how enterprise software is built.
8.0 References
[1] Google LLC, "Introducing Cartographer", Google Open Source Blog, 2016. [online]. Available: https://opensource.googleblog.com/2016/10/introducing-cartographer.html. [Accessed: 21- Jan- 2018].
[2] Google LLC, "Cartographer ROS for the Toyota HSR", GitHub, 2018. [online]. Available: https://github.com/googlecartographer/cartographer_toyota_hsr. [Accessed: 20- Jan- 2018].
[3] Wolfgang Hess and Damon Kohler and Holger Rapp and Daniel Andor, "Real-Time Loop Closure in 2D LIDAR SLAM", Research at Google, 2016. [online]. Available: https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/45466.pdf. [Accessed: 21- Jan- 2018].
[4] Open Source Robotics Foundation, "About ROS", ROS.org, 2018. [online]. Available: http://www.ros.org/about-ros/. [Accessed: 21- Jan- 2018].
[5] Google LLC, "open house slides", GitHub, 2018. [online]. Available: https://github.com/googlecartographer/cartographer/projects. [Accessed: 21- Jan- 2018].
[6] Google LLC, "Improved handling of multiple trajectories and bags in the offline node (RFC 0009)", GitHub, 2018. [online]. Available: https://github.com/googlecartographer/cartographer/projects/9. [Accessed: 21- Jan- 2018].
[7] Google LLC, "NavSatFix (GPS) Support in Cartographer ROS (RFC 0007)", GitHub, 2018. [online]. Available: https://github.com/googlecartographer/cartographer/projects/8. [Accessed: 21- Jan- 2018].
[8] Google LLC, "Serve ROS map from a pbstream file (RFC 0006)", GitHub, 2018. [online]. Available: https://github.com/googlecartographer/cartographer/projects/7. [Accessed: 21- Jan- 2018].
[9] The Cartograoher Authors, "System Requirements", Read the Docs, 2016. [oneline]. Avaiable: https://google-cartographer.readthedocs.io/en/latest/#system-requirements. [Accessed: 21- Jan- 2018].
[10] SonarSource S.A, "SonarQube C++ plugin (Community)", GitHub, 2018. [online]. Avaiable: https://github.com/SonarOpenCommunity/sonar-cxx. [Accessed: 20- Mar- 2018].
[11] Google LLC, "Google C++ Style Guide", GitHub, 2018. [online]. Avaiable: https://google.github.io/styleguide/cppguide.html. [Accessed: 20- Mar- 2018].
[12] Google LLC, "Protocol Buffers", Google Developers, 2018. [online]. Avaiable: https://developers.google.com/protocol-buffers/. [Accessed: 21- Mar- 2018].
[13] Google Inc, "A high performance, open-source universal RPC framework", GRPC, 2018. [online]. Avaiable: https://grpc.io/. [Accessed: 20- Mar- 2018].
Last updated
