Adaptive occupancy grid mapping with measurement and pose uncertainty

[摘要] ENGLISH ABSTRACT: In this thesis we consider the problem of building a dense and consistent map of a mobile robot'senvironment that is updated as the robot moves. Such maps are vital for safe and collision-free navigation.Measurements obtained from a range sensor mounted on the robot provide information on the structureof the environment, but are typically corrupted by noise. These measurements are also relative to therobot's unknown pose (location and orientation) and, in order to combine them into a world-centric map,pose estimation is necessary at every time step. A SLAM system can be used for this task. However,since landmark measurements and robot motion are inherently noisy, the pose estimates are typicallycharacterized by uncertainty. When building a map it is essential to deal with the uncertainties in rangemeasurements and pose estimates in a principled manner to avoid overconfidence in the map.A literature review of robotic mapping algorithms reveals that the occupancy grid mapping algorithmis well suited for our goal. This algorithm divides the area to be mapped into a regular lattice of cells(squares for 2D maps or cubes for 3D maps) and maintains an occupancy probability for each cell.Although an inverse sensor model is often employed to incorporate measurement uncertainty into sucha map, many authors merely state or depict their sensor models. We derive our model analytically anddiscuss ways to tailor it for sensor-specific uncertainty.One of the shortcomings of the original occupancy grid algorithm is its inability to convey uncertainty inthe robot's pose to the map. We address this problem by altering the occupancy grid update equationto include weighted samples from the pose uncertainty distribution (provided by the SLAM system).The occupancy grid algorithm has been criticized for its high memory requirements. Techniques havebeen proposed to represent the map as a region tree, allowing cells to have different sizes depending onthe information received for them. Such an approach necessitates a set of rules for determining when acell should be split (for higher resolution in a local region) and when groups of cells should be merged(for lower resolution). We identify some inconsistencies that can arise from existing rules, and adaptthose rules so that such errors are avoided.We test our proposed adaptive occupancy grid algorithm, that incorporates both measurement and poseuncertainty, on simulated and real-world data. The results indicate that these uncertainties are includedeffectively, to provide a more informative map, without a loss in accuracy. Furthermore, our adaptivemaps need far fewer cells than their regular counterparts, and our new set of rules for deciding whento split or merge cells significantly improves the ability of the adaptive grid map to mimic its regularcounterpart.

[发布机构] Stellenbosch University