Category Archives: Mobile Robot Mapping

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.

Using deep learning for extracting features from range data

Y. Liao, S. Kodagoda, Y. Wang, L. Shi and Y. Liu, Place Classification With a Graph Regularized Deep Neural Network, IEEE Transactions on Cognitive and Developmental Systems, vol. 9, no. 4, pp. 304-315, DOI: 10.1109/TCDS.2016.2586183.

Place classification is a fundamental ability that a robot should possess to carry out effective human-robot interactions. In recent years, there is a high exploitation of artificial intelligence algorithms in robotics applications. Inspired by the recent successes of deep learning methods, we propose an end-to-end learning approach for the place classification problem. With deep architectures, this methodology automatically discovers features and contributes in general to higher classification accuracies. The pipeline of our approach is composed of three parts. First, we construct multiple layers of laser range data to represent the environment information in different levels of granularity. Second, each layer of data are fed into a deep neural network for classification, where a graph regularization is imposed to the deep architecture for keeping local consistency between adjacent samples. Finally, the predicted labels obtained from all layers are fused based on confidence trees to maximize the overall confidence. Experimental results validate the effectiveness of our end-to-end place classification framework in which both the multilayer structure and the graph regularization promote the classification performance. Furthermore, results show that the features automatically learned from the raw input range data can achieve competitive results to the features constructed based on statistical and geometrical information.

Experimental comparison of methods for merging line segments in line-segment-based maps for mobile robots

Francesco Amigoni, Alberto Quattrini Li, Comparing methods for merging redundant line segments in maps, Robotics and Autonomous Systems, Volume 99, 2018, Pages 135-147, DOI: 10.1016/j.robot.2017.10.016.

Map building of indoor environments is considered a basic building block for autonomous mobile robots, enabling, among others, self-localization and efficient path planning. While the mainstream approach stores maps as occupancy grids of regular cells, some works have advocated for the use of maps composed of line segments to represent the boundary of obstacles, leveraging on their more compact size. In order to limit both the growth of the corresponding data structures and the effort in processing these maps, a number of methods have been proposed for merging together redundant line segments that represent the same portion of the environment. In this paper, we experimentally compare some of the most significant methods for merging line segments in maps by applying them to publicly available data sets. At the end, we propose some guidelines to choose the appropriate method.

Qualitative maps for mobile robots

Jennifer Padgett, Mark Campbell, Probabilistic qualitative mapping for robots, Robotics and Autonomous Systems, Volume 98, 2017, Pages 292-306, DOI: 10.1016/j.robot.2017.09.013.

A probabilistic qualitative relational mapping (PQRM) algorithm is developed to enable robots to robustly map environments using noisy sensor measurements. Qualitative state representations provide soft, relative map information which is robust to metrical errors. In this paper, probabilistic distributions over qualitative states are derived and an algorithm to update the map recursively is developed. Maps are evaluated for convergence and correctness in Monte Carlo simulations. Validation tests are conducted on the New College dataset to evaluate map performance in realistic environments.

Taking into account explicitly the dynamics of the environment, and in particular the diverse frequencies of changes, for mobile robot mapping

T. Krajník, J. P. Fentanes, J. M. Santos and T. Duckett, FreMEn: Frequency Map Enhancement for Long-Term Mobile Robot Autonomy in Changing Environments, IEEE Transactions on Robotics, vol. 33, no. 4, pp. 964-977, DOI: 10.1109/TRO.2017.2665664.

We present a new approach to long-term mobile robot mapping in dynamic indoor environments. Unlike traditional world models that are tailored to represent static scenes, our approach explicitly models environmental dynamics. We assume that some of the hidden processes that influence the dynamic environment states are periodic and model the uncertainty of the estimated state variables by their frequency spectra. The spectral model can represent arbitrary timescales of environment dynamics with low memory requirements. Transformation of the spectral model to the time domain allows for the prediction of the future environment states, which improves the robot’s long-term performance in changing environments. Experiments performed over time periods of months to years demonstrate that the approach can efficiently represent large numbers of observations and reliably predict future environment states. The experiments indicate that the model’s predictive capabilities improve mobile robot localization and navigation in changing environments.

Interesting review of approaches to visually detect loop closings in robotics, and a novel, very efficient method that is independent on the image representation and based on not using the typical l2 norm (least squares), which leads to dense optimization problems

Yasir Latif, Guoquan Huang, John Leonard, José Neira, Sparse optimization for robust and efficient loop closing, Robotics and Autonomous Systems, Volume 93, July 2017, Pages 13-26, ISSN 0921-8890,DOI: 10.1016/j.robot.2017.03.016.

It is essential for a robot to be able to detect revisits or loop closures for long-term visual navigation. A key insight explored in this work is that the loop-closing event inherently occurs sparsely, i.e., the image currently being taken matches with only a small subset (if any) of previous images. Based on this observation, we formulate the problem of loop-closure detection as a sparse, convex
ℓ 1 -minimization problem. By leveraging fast convex optimization techniques, we are able to efficiently find loop closures, thus enabling real-time robot navigation. This novel formulation requires no offline dictionary learning, as required by most existing approaches, and thus allows online incremental operation. Our approach ensures a unique hypothesis by choosing only a single globally optimal match when making a loop-closure decision. Furthermore, the proposed formulation enjoys a flexible representation with no restriction imposed on how images should be represented, while requiring only that the representations are “close” to each other when the corresponding images are visually similar. The proposed algorithm is validated extensively using real-world datasets.