A new approach to solve SLAM challenges by relative map filter

In this paper we propose a new approach to solve some challenges in the simultaneous localization and mapping (SLAM) problem based on the relative map filter (RMF). This method assumes that the relative distances between the landmarks of relative map are estimated fully independently. This considerably reduces the computational complexity to average number of landmarks observed in each scan. To solve the ambiguity that may happen in finding the absolute locations of robot and landmarks, we have proposed two separate methods, the lowest position error (LPE) and minimum variance position estimator (MVPE). Another challenge in RMF is data association problem where we also propose an algorithm which works by using motion sensors without engaging in their cumulative error. To apply these methods, we switch successively between the absolute and relative positions of landmarks. Having a sufficient number of landmarks in the environment, our algorithm estimates the positions of robot and landmarks without using motion sensors and kinematics of robot. Motion sensors are only used for data association. The empirical studies on the proposed RMF-SLAM algorithm with the LPE or MVPE methods show a better accuracy in localization of robot and landmarks in comparison with the absolute map filter SLAM.     

Learning to select distinctive landmarks for mobile robot navigation

In landmark-based navigation systems for mobile robots, sensory perceptions (e.g., laser or sonar scans) are used to identify the robot’s current location or to construct internal representations, maps, of the robot’s environment. Being based on an external frame of reference (which is not subject to incorrigible drift errors such as those occurring in odometry-based systems), landmark-based robot navigation systems are now widely used in mobile robot applications.The problem that has attracted most attention to date in landmark-based navigation research is the question of how to deal with perceptual aliasing, i.e., perceptual ambiguities. In contrast, what constitutes a good landmark, or how to select landmarks for mapping, is still an open research topic. The usual method of landmark selection is to map perceptions at regular intervals, which has the drawback of being inefficient and possibly missing ‘good’ landmarks that lie between sampling points.In this paper, we present an automatic landmark selection algorithm that allows a mobile robot to select conspicuous landmarks from a continuous stream of sensory perceptions, without any pre-installed knowledge or human intervention during the selection process. This algorithm can be used to make mapping mechanisms more efficient and reliable. Experimental results obtained with two different mobile robots in a range of environments are presented and analysed.     

一种用于未知环境探索的可动态配置路标系统

研究了移动机器人探索未知环境所面临的定位问题．针对在某些未知环境中难以可靠提取自然路标、 并且存在数据关联难题的实际情况,提出了一种可以根据定位需要进行动态配置的路标系统,设计并实现了可以动 态配置的路标、路标投放装置、路标探测装置,能够在探索未知环境的过程中动态在线配置路标以辅助完成机器人 定位与对环境的探索．可动态配置路标具有成本低、体积小、能耗低的特点,便于携带与动态配置,实验结果证明 了这种路标系统在未知环境探索中的有效性．     

Fully automatic expression-invariant face correspondence

We consider the problem of computing accurate point-to-point correspondences among a set of human face scans with varying expressions. Our fully automatic approach does not require any manually placed markers on the scan. Instead, the approach learns the locations of a set of landmarks present in a database and uses this knowledge to automatically predict the locations of these landmarks on a newly available scan. The predicted landmarks are then used to compute point-to-point correspondences between a template model and the newly available scan. To accurately fit the expression of the template to the expression of the scan, we use as template a blendshape model. Our algorithm was tested on a database of human faces of different ethnic groups with strongly varying expressions. Experimental results show that the obtained point-to-point correspondence is both highly accurate and consistent for most of the tested 3D face models.     

Scan matching SLAM in underwater environments

This paper proposes a pose-based algorithm to solve the full simultaneous localization and mapping problem for autonomous underwater vehicle (AUV) navigating in unknown and possibly unstructured environments. The proposed method first estimates the local path traveled by the robot while forming the acoustic image (scan) with range data coming from a mono-beam rotating sonar head, providing position estimates for correcting the distortions that the vehicle motion produces in the scans. Then, consecutive scans are cross-registered under a probabilistic scan matching technique for estimating the displacements of the vehicle including the uncertainty of the scan matching result. Finally, an augmented state extended Kalman filter estimates and keeps the registered scans poses. No prior structural information or initial pose are considered. The viability of the proposed approach has been tested reconstructing the trajectory of a guided AUV operating along a 600 m path within a marina environment.     

Omnivision-based KLD-Monte Carlo Localization

Mobile robots operating in real and populated environments usually execute tasks that require accurate knowledge on their position. Monte Carlo Localization (MCL) algorithms have been successfully applied for laser range finders. However, vision-based approaches present several problems with occlusions, real-time operation, and environment modifications. In this article, an omnivision-based MCL algorithm that solves these drawbacks is presented. The algorithm works with a variable number of particles through the use of the Kullback–Leibler divergence (KLD). The measurement model is based on an omnidirectional camera with a fish-eye lens. This model uses a feature-based map of the environment and the feature extraction process makes it robust to occlusions and changes in the environment. Moreover, the algorithm is scalable and works in real-time. Results on tracking, global localization and kidnapped robot problem show the excellent performance of the localization system in a real environment. In addition, experiments under severe and continuous occlusions reflect the ability of the algorithm to localize the robot in crowded environments.     

Map Management for Efficient Simultaneous Localization and Mapping (SLAM)

The solution to the simultaneous localization and map building (SLAM) problem where an autonomous vehicle starts in an unknown location in an unknown environment and then incrementally build a map of landmarks present in this environment while simultaneously using this map to compute absolute vehicle location is now well understood. Although a number of SLAM implementations have appeared in the recent literature, the need to maintain the knowledge of the relative relationships between all the landmark location estimates contained in the map makes SLAM computationally intractable in implementations containing more than a few tens of landmarks. This paper presents the theoretical basis and a practical implementation of a feature selection strategy that significantly reduces the computation requirements for SLAM. The paper shows that it is indeed possible to remove a large percentage of the landmarks from the map without making the map building process statistically inconsistent. Furthermore, it is shown that the computational cost of the SLAM algorithm can be reduced by judicious selection of landmarks to be preserved in the map.     

Three‐dimensional localization for the MagneBike inspection robot

The MagneBike inspection robot is a climbing robot equipped with magnetic wheels. The robot is designed to drive on three‐dimensional (3D) complexly shaped pipe structures; therefore it is necessary to provide 3D visualization tools for the user, who remotely controls the robot out of sight. The localization system is required to provide a 3D map of the unknown environment and the 3D location of the robot in the environment's map. The localization strategy proposed in this paper consists of combining 3D odometry with 3D scan registration. The odometry model is based on wheel encoders and a three‐axis accelerometer. Odometry enables the tracking of the robot trajectory between consecutive 3D scans and is used as a prior for the scan matching algorithm. The 3D scan registration facilitates the construction of a 3D map of the environment and refines the robot position computed with odometry. This paper describes in detail the implementation of the localization concept. It presents the lightweight, small‐sized 3D range finder that has been developed for the MagneBike. It also proposes an innovative 3D odometry model that estimates the local surface curvature to compensate for the absence of angular velocity inputs. The different tools are characterized in detail based on laboratory and field experiments. They show that the localization concepts reliably track the robot moving in the specific application environment. We also describe various techniques to optimize the 3D scanning process, which is time consuming, and to compensate for the identified limitations. These techniques are useful inputs for the future automatization of the robot's control and optimization of its localization process. © 2010 Wiley Periodicals, Inc.     

Effective cubature FastSLAM: SLAM with Rao-Blackwellized particle filter and cubature rule for Gaussian weighted integral

Simultaneous localization and mapping (SLAM) is a key technology for mobile robot autonomous navigation in unknown environments. While FastSLAM algorithm is a popular solution to the large-scale SLAM problem, it suffers from two major drawbacks: one is particle set degeneracy due to lack of measurements in proposal distribution of particle filter; the other is errors accumulation caused by inaccurate linearization of the nonlinear robot motion model and the environment measurement model. To overcome the problems, a new Jacobian-free cubature FastSLAM (CFastSLAM) algorithm is proposed in this paper. The main contribution of the algorithm lies in the utilization of third-degree cubature rule, which calculates the nonlinear transition density of Gaussian prior more accurately, to design an optimal proposal distribution of the particle filter and to estimate the Gaussian densities of the feature landmarks. On the basis of Rao-Blackwellized particle filter, the proposed algorithm is comprised by two main parts: in the first part, a cubature particle filter (CPF) is derived to localize the robot; in the second part, a set of cubature Kalman filters is used to estimate environment landmarks. The performance of the proposed algorithm is investigated and compared with that of FastSLAM2.0 and UFastSLAM in simulations and experiments. Results verify that the CFastSLAM improves the SLAM performance.     

基于二次栅格扫描的无线传感器网络定位算法

为了提高无线传感器网络的定位精度,在栅格扫描算法的基础上提出了一种基于二次栅格扫描的无线传感器网络定位算法.利用未知节点与两跳范围内的锚节点的连通性约束信息,在近节点对未知节点进行栅格扫描得到其初始位置估计的基础上,引入远节点对未知节点再次进行栅格扫描,从而提高定位精度.算法增加了远节点栅格扫描的计算量,但不需要额外地增加节点的硬件功能.仿真结果表明,与仅利用近节点的栅格扫描算法相比,该算法在锚节点密度增大的过程中可以更快地提高定位精度.     

Optimal landmark selection for triangulation of robot position

A mobile robot can identify its own position relative to a global environment model by using triangulation based on three landmarks in the environment. It is shown that this procedure may be very sensitive to noise depending on spatial landmark configuration, and relative position between robot and landmarks. A general analysis is presented which permits prediction of the uncertainty in the triangulated position.

In addition an algorithm is presented for automatic selection of optimal landmarks. This algorithm enables a robot to continuously base its position computation on the set of available landmarks, which provides the least noise sensitive position estimate. It is demonstrated that using this algorithm can result in more than one order of magnitude reduction in uncertainty.     

一种新颖的基于两个特征点的室内移动机器人定位方法

提出了一种新颖的基于两个特征点的室内移动机器人定位方法。与已有的几何位姿估计方法或航标匹配方法不同，该方法不需要人工航标，也不需要准确的环境地图，只需一幅由传统的CCD相机拍摄的图像。从机器人接近的目标上选取相对于地面等高的两个点作为两个特征点。基于这两点建立一个目标坐标系。在相机平视且这两个特征点与相机投影中心相对于地面不是恰好等高的条件下，就可以根据这两个特征点在图像中的坐标确定机器人相对于目标坐标系的位置和运动方向。该方法非常灵活，适用范围广，可以大大简化机器人定位问题。试验结果表明这一新的方法不仅简单灵活而且具有很高的定位精度。     

Super 4PCS Fast Global Pointcloud Registration via Smart Indexing

Data acquisition in large‐scale scenes regularly involves accumulating information across multiple scans. A common approach is to locally align scan pairs using Iterative Closest Point (ICP) algorithm (or its variants), but requires static scenes and small motion between scan pairs. This prevents accumulating data across multiple scan sessions and/or different acquisition modalities (e.g., stereo, depth scans). Alternatively, one can use a global registration algorithm allowing scans to be in arbitrary initial poses. The state‐of‐the‐art global registration algorithm, 4PCS, however has a quadratic time complexity in the number of data points. This vastly limits its applicability to acquisition of large environments. We present Super 4PCS for global pointcloud registration that is optimal, i.e., runs in linear time (in the number of data points) and is also output sensitive in the complexity of the alignment problem based on the (unknown) overlap across scan pairs. Technically, we map the algorithm as an ‘instance problem’ and solve it efficiently using a smart indexing data organization. The algorithm is simple, memory‐efficient, and fast. We demonstrate that Super 4PCS results in significant speedup over alternative approaches and allows unstructured efficient acquisition of scenes at scales previously not possible. Complete source code and datasets are available for research use at http://geometry.cs.ucl.ac.uk/projects/2014/super4PCS/ .     

Visual Navigation in Natural Environments: From Range and Color Data to a Landmark-Based Model

This paper concerns the exploration of a natural environment by a mobile robot equipped with both a video color camera and a stereo-vision system. We focus on the interest of such a multi-sensory system to deal with the navigation of a robot in an a priori unknown environment, including (1) the incremental construction of a landmark-based model, and the use of these landmarks for (2) the 3-D localization of the mobile robot and for (3) a sensor-based navigation mode.For robot localization, a slow process and a fast one are simultaneously executed during the robot motions. In the modeling process (currently 0.1 Hz), the global landmark-based model is incrementally built and the robot situation can be estimated from discriminant landmarks selected amongst the detected objects in the range data. In the tracking process (currently 4 Hz), selected landmarks are tracked in the visual data; the tracking results are used to simplify the matching between landmarks in the modeling process.Finally, a sensor-based visual navigation mode, based on the same landmark selection and tracking, is also presented; in order to navigate during a long robot motion, different landmarks (targets) can be selected as a sequence of sub-goals that the robot must successively reach.     

Omnidirectional vision scan matching for robot localization in dynamic environments

The localization problem for an autonomous robot moving in a known environment is a well-studied problem which has seen many elegant solutions. Robot localization in a dynamic environment populated by several moving obstacles, however, is still a challenge for research. In this paper, we use an omnidirectional camera mounted on a mobile robot to perform a sort of scan matching. The omnidirectional vision system finds the distances of the closest color transitions in the environment, mimicking the way laser rangefinders detect the closest obstacles. The similarity of our sensor with classical rangefinders allows the use of practically unmodified Monte Carlo algorithms, with the additional advantage of being able to easily detect occlusions caused by moving obstacles. The proposed system was initially implemented in the RoboCup Middle-Size domain, but the experiments we present in this paper prove it to be valid in a general indoor environment with natural color transitions. We present localization experiments both in the RoboCup environment and in an unmodified office environment. In addition, we assessed the robustness of the system to sensor occlusions caused by other moving robots. The localization system runs in real-time on low-cost hardware.     

Occlusions as a guide for planning the next view

A strategy for acquiring 3-D data of an unknown scene, using range images obtained by a light stripe range finder is addressed. The foci of attention are occluded regions, i.e., only the scene at the borders of the occlusions is modeled to compute the next move. Since the system has knowledge of the sensor geometry, it can resolve the appearance of occlusions by analyzing them. The problem of 3-D data acquisition is divided into two subproblems due to two types of occlusions. An occlusion arises either when the reflected laser light does not reach the camera or when the directed laser light does not reach the scene surface. After taking the range image of a scene, the regions of no data due to the first kind of occlusion are extracted. The missing data are acquired by rotating the sensor system in the scanning plane, which is defined by the first scan. After a complete image of the surface illuminated from the first scanning plane has been built, the regions of missing data due to the second kind of occlusions are located. Then, the directions of the next scanning planes for further 3-D data acquisition are computed     

Range-only SLAM with indistinguishable landmarks; a constraint programming approach

This paper deals with the simultaneous localization and mapping problem (SLAM) for a robot. The robot has to build a map of its environment while localizing itself using a partially built map. It is assumed that (i) the map is made of point landmarks, (ii) the landmarks are indistinguishable, (iii) the only exteroceptive measurements correspond to the distance between the robot and the landmarks. This paper shows that SLAM can be cast into a constraint network the variables of which being trajectories, digraphs and subsets of \(\mathbb {R}^{n}.\) Then, we show how constraint propagation can be extended to deal with such generalized constraint networks. As a result, due to the redundancy of measurements of SLAM, we demonstrate that a constraint-based approach provides an efficient backtrack-free algorithm able to solve our SLAM problem in a guaranteed way.     

2D‐D Lifting for Shape Reconstruction

We present an algorithm for shape reconstruction from incomplete 3D scans by fusing together two acquisition modes: 2D photographs and 3D scans. The two modes exhibit complementary characteristics: scans have depth information, but are often sparse and incomplete; photographs, on the other hand, are dense and have high resolution, but lack important depth information. In this work we fuse the two modes, taking advantage of their complementary information, to enhance 3D shape reconstruction from an incomplete scan with a 2D photograph. We compute geometrical and topological shape properties in 2D photographs and use them to reconstruct a shape from an incomplete 3D scan in a principled manner. Our key observation is that shape properties such as boundaries, smooth patches and local connectivity, can be inferred with high confidence from 2D photographs. Thus, we register the 3D scan with the 2D photograph and use scanned points as 3D depth cues for lifting 2D shape structures into 3D. Our contribution is an algorithm which significantly regularizes and enhances the problem of 3D reconstruction from partial scans by lifting 2D shape structures into 3D. We evaluate our algorithm on various shapes which are loosely scanned and photographed from different views, and compare them with state‐of‐the‐art reconstruction methods.     

Simultaneous localization and mapping using the Geometric Projection Filter and correspondence graph matching

A common way of localization in robotics is using triangulation on a system composed of a sensor and some landmarks (which can be artificial or natural). First, when no identifying marks are set on the landmarks, their identification by a robust algorithm is a complex problem which may be solved using correspondence graphs. Secondly, when the localization system has no a priori information about its environment, it has to build its own map in parallel with estimating its position, a problem known as simultaneous localization and mapping (SLAM). Recent works have proposed to solve this problem based on building a map made of invariant features. This paper describes the algorithms and data structure needed to deal with landmark matching, robot localization and map building in a single efficient process, unifying the previous approaches. Experimental results are presented using an outdoor robot car equipped with a two-dimensional scanning laser sensor.     

Constructing the generalized local Voronoi diagram from laser rangescanner data

We consider the problem of building local free space representation by a circular-base robot, operating in an unknown bounded planar environment populated by obstacles of arbitrary shape. In the unknown environment, the robot depends on its sensors; in our case, this is the laser range scanner. A new structure is represented, termed the generalized local Voronoi diagram (GLVD), constructed directly from sensory data, obtained from an observation of the local environment, that is from the visible region, GLVD is obtained by deleting some edges from the ordinary Voronoi diagram, which is generated by the measured scanned points from the visible region. Crucial for the acquisition of the GLVD is the clusterization of the scanned points. Clusterization means grouping of the scanned points into distinct clusters, each having a specific property, e.g., for a particular point in the cluster, the nearest neighboring point should not lie further than a prescribed distance away. The relevant part of GLVD, the portion of GLVD which is in accordance with the generalized Voronoi diagram of the environment, is determined. Eventual differences between these two structures are discussed and experimental results are presented. With the superposition of several GLVDs we show that this structure can be used to construct a global map of the environment, for which the position and the orientation of the robot is needed