β-SLAM: Simultaneous localization and grid mapping with beta distributions

Simultaneous localization and mapping (SLAM) is one of the most frequently studied problems in mobile robotics. Different map representations have been proposed in the past and a popular one are occupancy grid maps, which are particularly well suited for navigation tasks. The uncertainty in these maps is usually modeled as a single Bernoulli distribution per grid cell. This has the disadvantage that one cannot distinguish between uncertainty caused by different phenomena like missing or conflicting information. In this paper, we overcome this limitation by modeling the occupancy probabilities as random variables. Those are assumed to be beta-distributed and account for the different causes of uncertainty. Based on this map representation, we derive a SLAM algorithm, including all necessary sensor models, for building maps composed of beta-distributed random variables and using these maps for localization. Furthermore, we propose measures for quantifying uncertainty in the resulting maps and for solving navigation tasks. We evaluate our approach using real-world as well as simulation-based datasets and we compare it to a state-of-the-art SLAM algorithm for building classical grid maps.     

Occupancy Grid Learning Using Contextual Forward Modelling

A mode versus clarity dilemma exists in occupancy grid based robotic mapping. This arises as two general approaches have emerged in the domain with diametric operational modes and differing representational abilities; the inverse and the forward approach. Their classification relates to the sensory model employed by the approaches. The inverse approach is characterised by an ability to construct a map in real time. This ability comes at the cost of reduced representational clarity however. The forward approach is capable of producing more accurate maps but requires all sensory data a priori. This work investigates if sub dividing the mapping problem into its constituent elements of sensor data evaluation and representation may facilitate improved real time map generation. ConForM (Contextual Forward Modelling) is presented as a technique for spatial perception and map building which addresses this problem which embodies this approach. Results from in-depth empirical evaluation illustrate the associated improvement in map quality resultant from the technique.     

Outdoor Localization Using Stereo Vision Under Various Illumination Conditions

We present a mobile robot localization method using only a stereo camera. Vision-based localization in outdoor environments is a challenging issue because of extreme changes in illumination. To cope with varying illumination conditions, we use two-dimensional occupancy grid maps generated from three-dimensional point clouds obtained by a stereo camera. Furthermore, we incorporate salient line segments extracted from the ground into the grid maps. The grid maps are not significantly affected by illumination conditions because occupancy information and salient line segments can be robustly obtained. On the grid maps, a robot's poses are estimated using a particle filter that combines visual odometry and map matching. We use edge-point-based stereo simultaneous localization and mapping to obtain simultaneously occupancy information and robot ego-motion estimation. We tested our method under various illumination and weather conditions, including sunny and rainy days. The experimental results showed the effectiveness and robustness of the proposed method. Our method enables localization under extremely poor illumination conditions, which are challenging for even existing state-of-the-art methods.     

Map merging for multiple robots using Hough peak matching

Navigation in a GPS-denied environment is an essential requirement for increased robotics autonomy. While this is in some sense solved for a single robot, the next challenge is to design algorithms for a team of robots to be able to map and navigate efficiently.The key requirement for achieving this team autonomy is to provide the robots with a collaborative ability to accurately map an environment. This problem is referred to as cooperative simultaneous localization and mapping (SLAM). In this research, the mapping process is extended to multiple robots with a novel occupancy grid map fusion algorithm. Map fusion is achieved by transforming individual maps into the Hough space where they are represented in an abstract form. Properties of the Hough transform are used to find the common regions in the maps, which are then used to calculate the unknown transformation between the maps.Results are shown from tests performed on benchmark datasets and real-world experiments with multiple robotic platforms.     

Autonomous vision-based robotic exploration and mapping using hybrid maps and particle filters

This paper addresses the problem of exploring and mapping an unknown environment using a robot equipped with a stereo vision sensor. The main contribution of our work is a fully automatic mapping system that operates without the use of active range sensors (such as laser or sonic transducers), can operate on-line and can consistently produce accurate maps of large-scale environments. Our approach implements a Rao-Blackwellised particle filter (RBPF) to solve the simultaneous localization and mapping problem and uses efficient data structures for real-time data association, mapping, and spatial reasoning. We employ a hybrid map representation that infers 3D point landmarks from image features to achieve precise localization, coupled with occupancy grids for safe navigation. We demonstrate two exploration approaches, one based on a greedy strategy and one based on an iteratively deepening strategy. This paper describes our framework and implementation, and presents our exploration method, and experimental results illustrating the functionality of the system.     

Using occupancy grids for mobile robot perception and navigation

An approach to robot perception and world modeling that uses a probabilistic tesselated representation of spatial information called the occupancy grid is reviewed. The occupancy grid is a multidimensional random field that maintains stochastic estimates of the occupancy state of the cells in a spatial lattice. To construct a sensor-derived map of the robot's world, the cell state estimates are obtained by interpreting the incoming range readings using probabilistic sensor models. Bayesian estimation procedures allow the incremental updating of the occupancy grid, using readings taken from several sensors over multiple points of view. The use of occupancy grids from mapping and for navigation is examined. Operations on occupancy grids and extensions of the occupancy grid framework are briefly considered     

Using Real-Time Stereo Vision for Mobile Robot Navigation

This paper describes a working vision-based mobile robot that navigates and autonomously explores its environment while building occupancy grid maps of the environment. We present a method for reducing stereo vision disparity images to two-dimensional map information. Stereo vision has several attributes that set it apart from other sensors more commonly used for occupancy grid mapping. We discuss these attributes, the errors that some of them create, and how to overcome them. We reduce errors by segmenting disparity images based on continuous disparity surfaces to reject spikes caused by stereo mismatches. Stereo vision processing and map updates are done at 5 Hz and the robot moves at speeds of 300 cm/s.     

Building maps of indoor environments by merging line segments extracted from registered laser range scans

The recent trend of deploying mobile robots in large indoor environments calls for development of efficient map representation techniques. Compared to the more common occupancy grid representation, maps built with line segments are more compact and scale well with the environment size. In this paper, we propose an offline method for building maps of indoor environments using line segments extracted from registered laser range scans. At the core of this method lies a new formulation for identifying and then merging into one, all line segments that represent the same planar surface in the environment. Two successive steps of density-based clustering, applied on the extracted segments, enable us to delineate the segments that are in close proximity to each other and hence represent the same surface. The proposed method has accurately built maps of a wide variety of indoor environments, both real and simulated. Compared to two other similar methods, it has generally produced better maps. We also propose ways by which the goodness of the produced maps, in terms of how closely they resemble the ground truth, can be assessed.     

A Simultaneous Localization and Mapping Algorithm in Complex Environments: SLASEM

In this paper we present an algorithm for the application of simultaneous localization and mapping in complex environments. Instead of building a grid map or building a feature map with a small number of the obstacles' geometric parameters, the proposed algorithm builds a sampled environment map (SEM) to represent a complex environment with a set of environment samples. To overcome the lack of one-toone correspondence between environment samples and raw observations, the signed orthogonal distance function is proposed to be used as the observation model. A method considering geometric constraints is presented to remove redundant environment samples from the SEM. We also present a method to improve the SEM's topological consistency by using corner constraints. The proposed algorithm has been verified in a simulation and an indoor experiment. The results show that the algorithm can localize the robot and build a complex map effectively.     

Learning Occupancy Grid Maps with Forward Sensor Models

This article describes a new algorithm for acquiring occupancy grid maps with mobile robots. Existing occupancy grid mapping algorithms decompose the high-dimensional mapping problem into a collection of one-dimensional problems, where the occupancy of each grid cell is estimated independently. This induces conflicts that may lead to inconsistent maps, even for noise-free sensors. This article shows how to solve the mapping problem in the original, high-dimensional space, thereby maintaining all dependencies between neighboring cells. As a result, maps generated by our approach are often more accurate than those generated using traditional techniques. Our approach relies on a statistical formulation of the mapping problem using forward models. It employs the expectation maximization algorithm for searching maps that maximize the likelihood of the sensor measurements.     

RMAP: a rectangular cuboid approximation framework for 3D environment mapping

This paper presents a rectangular cuboid approximation framework (RMAP) for 3D mapping. The goal of RMAP is to provide computational and memory efficient environment representations for 3D robotic mapping using axis aligned rectangular cuboids (RC). This paper focuses on two aspects of the RMAP framework: (i) An occupancy grid approach and (ii) A RC approximation of 3D environments based on point cloud density. The RMAP occupancy grid is based on the Rtree data structure which is composed of a hierarchy of RC. The proposed approach is capable of generating probabilistic 3D representations with multiresolution capabilities. It reduces the memory complexity in large scale 3D occupancy grids by avoiding explicit modelling of free space. In contrast to point cloud and fixed resolution cell representations based on beam end point observations, an approximation approach using point cloud density is presented. The proposed approach generates variable sized RC approximations that are memory efficient for axis aligned surfaces. Evaluation of the RMAP occupancy grid and approximation approach based on computational and memory complexity on different datasets shows the effectiveness of this framework for 3D mapping.     

Bridging the gap between feature- and grid-based SLAM

One important design decision for the development of autonomously navigating mobile robots is the choice of the representation of the environment. This includes the question of which type of features should be used, or whether a dense representation such as occupancy grid maps is more appropriate. In this paper, we present an approach which performs SLAM using multiple representations of the environment simultaneously. It uses reinforcement to learn when to switch to an alternative representation method depending on the current observation. This allows the robot to update its pose and map estimate based on the representation that models the surrounding of the robot in the best way. The approach has been implemented on a real robot and evaluated in scenarios, in which a robot has to navigate in- and outdoors and therefore switches between a landmark-based representation and a dense grid map. In practical experiments, we demonstrate that our approach allows a robot to robustly map environments which cannot be adequately modeled by either of the individual representations.     

Local map-based exploration for mobile robots

For an accurate and efficient exploration, a local map-based exploration strategy is proposed. Segmented frontiers and relative transformations constitute a tree structure; using frontier segmentation and a local map management method, a robot can expand the mapped environment by moving along the tree structure. Although this local map-based exploration method uses only local maps and adjacent node information, mapping completion and efficiency can be greatly improved by merging and updating the frontier nodes. Simulation results demonstrate that the computational time does not increase during the exploration process, or when the resulting map becomes large. Additionally, the resulting path is effective in reducing the uncertainty in simultaneous localization and mapping or localization because of the loop-inducing characteristics from the child node to the parent node.     

Large-Scale SLAM Building Conditionally Independent Local Maps: Application to Monocular Vision

Simultaneous localization and mapping (SLAM) algorithms based on local maps have been demonstrated to be well suited for mapping large environments as they reduce the computational cost and improve the consistency of the final estimation. The main contribution of this paper is a novel submapping technique that does not require independence between maps. The technique is based on the intrinsic structure of the SLAM problem that allows the building of submaps that can share information, remaining conditionally independent. The resulting algorithm obtains local maps in constant time during the exploration of new terrain and recovers the global map in linear time after simple loop closures without introducing any approximations besides the inherent extended Kalman filter linearizations. The memory requirements are also linear with the size of the map. As the algorithm works in a covariance form, well-known data-association techniques can be used in the usual manner. We present experimental results using a handheld monocular camera, building a map along a closed-loop trajectory of 140 m in a public square, with people and other clutter. Our results show that the combination of conditional independence, which enables the system to share the camera and feature states between submaps, and local coordinates, which reduce the effects of linearization errors, allow us to obtain precise maps of large areas with pure monocular SLAM in real time.      

Adaptive occupancy grid mapping with clusters

In this article, we describe an algorithm for acquiring occupancy grid maps with mobile robots. The standard occupancy grid mapping developed by Elfes and Moravec in the mid-1980s decomposes the high-dimensional mapping problem into many one-dimensional estimation problems, which are then tackled independently. Because of the independencies between neighboring grid cells, this often generates maps that are inconsistent with the sensor data. To overcome this, we propose a cluster that is a set of cells. The cells in the clusters are tackled dependently with another occupancy grid mapping with an expectation maximization (EM) algorithm. The occupancy grid mapping with an EM algorithm yields more consistent maps, especially in the cluster. As we use the mapping algorithm adaptively with clusters according to the sensor measurements, our mapping algorithm is faster and more accurate than previous mapping algorithms. This work was presented in part at the 10th International Symposium on Artificial Life and Robotics, Oita, Japan, February 4–6, 2005     

Loop-closing: A typicality approach

Loop-closing has long been identified as a critical issue when building maps from local observations. Topological mapping methods abstract the problem of how loops are closed from the problem of how to determine the metrical layout of places in the map and how to deal with noisy sensors.The typicality problem refers to the identification of new classes in a general classification context. This typicality concept is used in this paper to help a robot acquire a topological representation of the environment during its exploration phase. The problem is addressed using the INCA statistic which follows a distance-based approach.In this paper we describe a place recognition approach based on match testing by means of the INCA test. We describe the theoretical basis of the approach and present extensive experimental results performed in both a simulated and a real robot-environment system; Behaviour Based philosophy is used to construct the whole control architecture. Obtained results show the validity of the approach.     

Autonomous Exploration with Exact Inverse Sensor Models

This paper is focused on probabilistic occupancy grid mapping and motion planning such that a robot may build a map and explore a target area autonomously in real time. The desired path of the robot is developed in an optimal fashion to maximize the information gain from the sensor measurements on its path, thereby increasing the accuracy and efficiency of mapping, while explicitly considering the sensor limitations such as the maximum sensing range and viewing angle. Most current exploration techniques require frequent human intervention, often developed for omnidirectional sensors with infinite range. The proposed research is based on realistic assumptions on sensor capabilities. The unique contribution is that the mapping and autonomous exploration techniques are systematically developed in a rigorous, probabilistic formulation. The mapping approach exploits the probabilistic properties of the sensor and map explicitly, and the autonomous exploration is designed to maximize the expected map information gain, thereby improving the efficiency of the mapping procedure and the quality of the map substantially. The efficacy of the proposed optimal approach is illustrated by both numerical simulations and experimental results.     

Mapping multiple gas/odor sources in an uncontrolled indoor environment using a Bayesian occupancy grid mapping based method

In this paper we address the problem of autonomously localizing multiple gas/odor sources in an indoor environment without a strong airflow. To do this, a robot iteratively creates an occupancy grid map. The produced map shows the probability each discrete cell contains a source. Our approach is based on a recent adaptation (Jakuba, 2007) [16] to traditional Bayesian occupancy grid mapping for chemical source localization problems. The approach is less sensitive, in the considered scenario, to the choice of the algorithm parameters. We present experimental results with a robot in an indoor uncontrolled corridor in the presence of different ejecting sources proving the method is able to build reliable maps quickly (5.5 minutes in a 6 m×2.1 m area) and in real time.     

一种低功耗程控滤波器的设计

针对目前移动机器人同时定位与地图创建(SLAM)研究中多采用激光雷达或超声环作为测距传感器导致系统复杂、成本高的问题,提出了一种利用舵机带动单超声传感器扫描的低成本设计方案。在高斯超声模型基础上,利用贝叶斯公式对栅格地图进行概率更新,并结合Sobel边缘检测算法提取特征点,实现了由不确定的移动机器人坐标系向固定的以环境特征点为原点的全局环境坐标系的转换及全局定位,为在相同环境下通过重复实验进行多地图融合研究奠定了基础。该低成本移动机器人设计的有效性通过实验得以验证。