Category Archives: Mobile Robot Mapping

Grid maps extended with confidence information

Ali-akbar Agha-mohammadi, Eric Heiden, Karol Hausman, Confidence-rich grid mapping,. The International Journal of Robotics Research, 38(12–13), 1352–1374, DOI: 10.1177/0278364919839762.

Representing the environment is a fundamental task in enabling robots to act autonomously in unknown environments. In this work, we present confidence-rich mapping (CRM), a new algorithm for spatial grid-based mapping of the 3D environment. CRM augments the occupancy level at each voxel by its confidence value. By explicitly storing and evolving confidence values using the CRM filter, CRM extends traditional grid mapping in three ways: first, it partially maintains the probabilistic dependence among voxels; second, it relaxes the need for hand-engineering an inverse sensor model and proposes the concept of sensor cause model that can be derived in a principled manner from the forward sensor model; third, and most importantly, it provides consistent confidence values over the occupancy estimation that can be reliably used in collision risk evaluation and motion planning. CRM runs online and enables mapping environments where voxels might be partially occupied. We demonstrate the performance of the method on various datasets and environments in simulation and on physical systems. We show in real-world experiments that, in addition to achieving maps that are more accurate than traditional methods, the proposed filtering scheme demonstrates a much higher level of consistency between its error and the reported confidence, hence, enabling a more reliable collision risk evaluation for motion planning.

Interesting account of robots that have non-rich sensors but have to do mapping and other modern stuff

Ma, F., Carlone, L., Ayaz, U., & Karaman, S. Sparse depth sensing for resource-constrained robots. The International Journal of Robotics Research, 38(8), 935 DOI: 10.1177/0278364919850296.

We consider the case in which a robot has to navigate in an unknown environment, but does not have enough on-board power or payload to carry a traditional depth sensor (e.g., a 3D lidar) and thus can only acquire a few (point-wise) depth measurements. We address the following question: is it possible to reconstruct the geometry of an unknown environment using sparse and incomplete depth measurements? Reconstruction from incomplete data is not possible in general, but when the robot operates in man-made environments, the depth exhibits some regularity (e.g., many planar surfaces with only a few edges); we leverage this regularity to infer depth from a small number of measurements. Our first contribution is a formulation of the depth reconstruction problem that bridges robot perception with the compressive sensing literature in signal processing. The second contribution includes a set of formal results that ascertain the exactness and stability of the depth reconstruction in 2D and 3D problems, and completely characterize the geometry of the profiles that we can reconstruct. Our third contribution is a set of practical algorithms for depth reconstruction: our formulation directly translates into algorithms for depth estimation based on convex programming. In real-world problems, these convex programs are very large and general-purpose solvers are relatively slow. For this reason, we discuss ad-hoc solvers that enable fast depth reconstruction in real problems. The last contribution is an extensive experimental evaluation in 2D and 3D problems, including Monte Carlo runs on simulated instances and testing on multiple real datasets. Empirical results confirm that the proposed approach ensures accurate depth reconstruction, outperforms interpolation-based strategies, and performs well even when the assumption of a structured environment is violated.

Grid maps with confidence levels

Agha-mohammadi, A., Heiden, E., Hausman, K., & Sukhatme, G., Confidence-rich grid mapping, The International Journal of Robotics Research, DOI: 10.1177/0278364919839762.

Representing the environment is a fundamental task in enabling robots to act autonomously in unknown environments. In this work, we present confidence-rich mapping (CRM), a new algorithm for spatial grid-based mapping of the 3D environment. CRM augments the occupancy level at each voxel by its confidence value. By explicitly storing and evolving confidence values using the CRM filter, CRM extends traditional grid mapping in three ways: first, it partially maintains the probabilistic dependence among voxels; second, it relaxes the need for hand-engineering an inverse sensor model and proposes the concept of sensor cause model that can be derived in a principled manner from the forward sensor model; third, and most importantly, it provides consistent confidence values over the occupancy estimation that can be reliably used in collision risk evaluation and motion planning. CRM runs online and enables mapping environments where voxels might be partially occupied. We demonstrate the performance of the method on various datasets and environments in simulation and on physical systems. We show in real-world experiments that, in addition to achieving maps that are more accurate than traditional methods, the proposed filtering scheme demonstrates a much higher level of consistency between its error and the reported confidence, hence, enabling a more reliable collision risk evaluation for motion planning.

Aligning maps of different modalities, coverage and scale

Gholami Shahbandi, S. & Magnusson M., 2D map alignment with region decomposition, Auton Robot (2019) 43: 1117, DOI: 10.1007/s10514-018-9785-7.

In many applications of autonomous mobile robots the following problem is encountered. Two maps of the same environment are available, one a prior map and the other a sensor map built by the robot. To benefit from all available information in both maps, the robot must find the correct alignment between the two maps. There exist many approaches to address this challenge, however, most of the previous methods rely on assumptions such as similar modalities of the maps, same scale, or existence of an initial guess for the alignment. In this work we propose a decomposition-based method for 2D spatial map alignment which does not rely on those assumptions. Our proposed method is validated and compared with other approaches, including generic data association approaches and map alignment algorithms. Real world examples of four different environments with thirty six sensor maps and four layout maps are used for this analysis. The maps, along with an implementation of the method, are made publicly available online.

Predicting the structure of indoor environments for mobile robots

Matteo Luperto, Francesco Amigoni, Predicting the global structure of indoor environments: A constructive machine learning approach, Autonomous Robots, April 2019, Volume 43, Issue 4, pp 813–835, DOI: 10.1007/s10514-018-9732-7.

Consider a mobile robot exploring an initially unknown school building and assume that it has already discovered some corridors, classrooms, offices, and bathrooms. What can the robot infer about the presence and the locations of other classrooms and offices and, more generally, about the structure of the rest of the building? This paper presents a system that makes a step towards providing an answer to the above question. The proposed system is based on a generative model that is able to represent the topological structures and the semantic labeling schemas of buildings and to generate plausible hypotheses for unvisited portions of these environments. We represent the buildings as undirected graphs, whose nodes are rooms and edges are physical connections between them. Given an initial knowledge base of graphs, our approach, relying on constructive machine learning techniques, segments each graph for finding significant subgraphs and clusters them according to their similarity, which is measured using graph kernels. A graph representing a new building or an unvisited part of a building is eventually generated by sampling subgraphs from clusters and connecting them.

A probabilistically rigurous formulation of the estimation of grid maps in dynamic scenarios, and a nice review and state-of-the-art of grid maps, both for static and dynamic scenarios

Dominik Nuss, Stephan Reuter, Markus Thom, Ting Yuan, Gunther Krehl, Michael Maile, Axel Gern, and Klaus Dietmayer, A random finite set approach for dynamic occupancy grid maps with real-time application, The International Journal of Robotics Research
Vol 37, Issue 8, pp. 841 – 866, DOI: 10.1177/0278364918775523.

Grid mapping is a well-established approach for environment perception in robotic and automotive applications. Early work suggests estimating the occupancy state of each grid cell in a robot’s environment using a Bayesian filter to recursively combine new measurements with the current posterior state estimate of each grid cell. This filter is often referred to as binary Bayes filter. A basic assumption of classical occupancy grid maps is a stationary environment. Recent publications describe bottom-up approaches using particles to represent the dynamic state of a grid cell and outline prediction-update recursions in a heuristic manner. This paper defines the state of multiple grid cells as a random finite set, which allows to model the environment as a stochastic, dynamic system with multiple obstacles, observed by a stochastic measurement system. It motivates an original filter called the probability hypothesis density / multi-instance Bernoulli (PHD/MIB) filter in a top-down manner. The paper presents a real-time application serving as a fusion layer for laser and radar sensor data and describes in detail a highly efficient parallel particle filter implementation. A quantitative evaluation shows that parameters of the stochastic process model affect the filter results as theoretically expected and that appropriate process and observation models provide consistent state estimation results.

A parallel implementation of a new probabilistic filter for occupancy grid maps that deals with non-static environments

Dominik Nuss, Stephan Reuter, Markus Thom, …, A random finite set approach for dynamic occupancy grid maps with real-time application, The International Journal of Robotics Research DOI: 10.1177/0278364918775523.

Grid mapping is a well-established approach for environment perception in robotic and automotive applications. Early work suggests estimating the occupancy state of each grid cell in a robot’s environment using a Bayesian filter to recursively combine new measurements with the current posterior state estimate of each grid cell. This filter is often referred to as binary Bayes filter. A basic assumption of classical occupancy grid maps is a stationary environment. Recent publications describe bottom-up approaches using particles to represent the dynamic state of a grid cell and outline prediction-update recursions in a heuristic manner. This paper defines the state of multiple grid cells as a random finite set, which allows to model the environment as a stochastic, dynamic system with multiple obstacles, observed by a stochastic measurement system. It motivates an original filter called the probability hypothesis density / multi-instance Bernoulli (PHD/MIB) filter in a top-down manner. The paper presents a real-time application serving as a fusion layer for laser and radar sensor data and describes in detail a highly efficient parallel particle filter implementation. A quantitative evaluation shows that parameters of the stochastic process model affect the filter results as theoretically expected and that appropriate process and observation models provide consistent state estimation results.

Dynamic and efficient occupancy mapping

Vitor Guizilini and Fabio Ramos, Towards real-time 3D continuous occupancy mapping using Hilbert maps, The International Journal of Robotics Research
Vol 37, Issue 6, pp. 566 – 584, DOI: 10.1177/0278364918771476.

The ability to model the surrounding space and determine which areas are occupied is of key importance in many robotic applications, ranging from grasping and manipulation to path planning and obstacle avoidance. Occupancy modeling is often hindered by several factors, such as: real-time constraints, that require quick updates and access to estimates; quality of available data, that may contain gaps and partial occlusions; and memory requirements, especially for large-scale environments. In this work we propose a novel framework that elegantly addresses all these issues, by producing an efficient non-stationary continuous occupancy function that can be efficiently queried at arbitrary resolutions. Furthermore, we introduce techniques that allow the learning of individual features for different areas of the input space, that are better able to model its contained information and promote a higher-level understanding of the observed scene. Experimental tests were conducted on both simulated and real large-scale datasets, showing how the proposed framework rivals current state-of-the-art techniques in terms of computational speed while achieving a substantial decrease (of orders of magnitude) in memory requirements and demonstrating better interpolative powers, that are able to smooth out sparse and noisy information.

A standard format for robotic maps

F. Amigoni et al, A Standard for Map Data Representation: IEEE 1873-2015 Facilitates Interoperability Between Robots, IEEE Robotics & Automation Magazine, vol. 25, no. 1, pp. 65-76, DOI: 10.1109/MRA.2017.2746179.

The availability of environment maps for autonomous robots enables them to complete several tasks. A new IEEE standard, IEEE 1873-2015, Robot Map Data Representation for Navigation (MDR) [15], sponsored by the IEEE Robotics and Automation Society (RAS) and approved by the IEEE Standards Association Standards Board in September 2015, defines a common representation for two-dimensional (2-D) robot maps and is intended to facilitate interoperability among navigating robots. The standard defines an extensible markup language (XML) data format for exchanging maps between different systems. This article illustrates how metric maps, topological maps, and their combinations can be represented according to the standard.

Resampling point clouds to reduce their size without compromising their utility for the tasks that use them

S. Chen, D. Tian, C. Feng, A. Vetro and J. Kovačević, Fast Resampling of Three-Dimensional Point Clouds via Graphs, IEEE Transactions on Signal Processing, vol. 66, no. 3, pp. 666-681, DOI: 10.1109/TSP.2017.2771730.

To reduce the cost of storing, processing, and visualizing a large-scale point cloud, we propose a randomized resampling strategy that selects a representative subset of points while preserving application-dependent features. The strategy is based on graphs, which can represent underlying surfaces and lend themselves well to efficient computation. We use a general feature-extraction operator to represent application-dependent features and propose a general reconstruction error to evaluate the quality of resampling; by minimizing the error, we obtain a general form of optimal resampling distribution. The proposed resampling distribution is guaranteed to be shift-, rotation- and scale-invariant in the three-dimensional space. We then specify the feature-extraction operator to be a graph filter and study specific resampling strategies based on all-pass, low-pass, high-pass graph filtering and graph filter banks. We validate the proposed methods on three applications: Large-scale visualization, accurate registration, and robust shape modeling demonstrating the effectiveness and efficiency of the proposed resampling methods.