An Efficient Localization Algorithm Based on Vector Matching for Mobile Robots Using Laser Range Finders

This paper describes an efficient localization algorithm based on a vector-matching technique for mobile robots with laser range finders. As a reference the method uses a map with line-segment vectors, which can be built from a CAD layout of the indoor environment. The contribution of this work lies in the overall localization process. First, the proposed sequential segmentation method enables efficient vector extraction from scanned data. Second, a reliable and efficient vector-matching technique is proposed. Finally, a cost function suitable for vector-matching is proposed for nonlinear pose estimation with solutions for both nonsingular and singular cases. Simulation results show that the proposed localization method works reliably even in a noisy environment. The algorithm was implemented for our wheelchair-based mobile robot and evaluated in a 135 m long corridor environment. Categories (3), (6).     

基于人工路标的易部署室内机器人全局定位系统

在一些布局易变或存在较多动态障碍物的室内,移动机器人的全局定位依然面临较大的应用挑战.针对这类场景,实现了一种新的基于人工路标的易部署室内机器人全局定位系统.该系统将人工路标粘贴在不易被遮挡的天花板上来作为参照物,仅依赖一个摄像头即能实现稳定的全局定位.整个系统根据具体的功能分为地图构建和全局定位两个过程.在地图构建过程中,系统使用激光SLAM算法所输出的位姿估计结果为基准,根据相机对路标点的观测信息来自动估计人工路标点在全局坐标系中的位姿,建立人工路标地图.而在全局定位过程中,该系统则是根据相机对地图中已知位姿的人工路标点的观测信息,结合里程计与IMU融合的预积分信息来对位姿进行实时估计.充分的实验测试表明,机器人在该系统所部署范围内运行的定位误差稳定在10 cm以内,且运行过程可以保证实时位姿输出,满足典型实际室内移动机器人全局定位的应用需求.     

How to localize humanoids with a single camera?

In this paper, we propose a real-time vision-based localization approach for humanoid robots using a single camera as the only sensor. In order to obtain an accurate localization of the robot, we first build an accurate 3D map of the environment. In the map computation process, we use stereo visual SLAM techniques based on non-linear least squares optimization methods (bundle adjustment). Once we have computed a 3D reconstruction of the environment, which comprises of a set of camera poses (keyframes) and a list of 3D points, we learn the visibility of the 3D points by exploiting all the geometric relationships between the camera poses and 3D map points involved in the reconstruction. Finally, we use the prior 3D map and the learned visibility prediction for monocular vision-based localization. Our algorithm is very efficient, easy to implement and more robust and accurate than existing approaches. By means of visibility prediction we predict for a query pose only the highly visible 3D points, thus, speeding up tremendously the data association between 3D map points and perceived 2D features in the image. In this way, we can solve very efficiently the Perspective-n-Point (PnP) problem providing robust and fast vision-based localization. We demonstrate the robustness and accuracy of our approach by showing several vision-based localization experiments with the HRP-2 humanoid robot.     

Global localization for mobile robots using reference scan matching

This paper presents a new approach based on scan matching for global localization with a metric-topological hybrid world model. The proposed method aims to estimate relative pose to the most likely reference site by matching an input scan with reference scans, in which topological nodes are used as reference sites for pose hypotheses. In order to perform scan matching we apply the spectral scan matching (SSM) method that utilizes pairwise geometric relationships (PGR) formed by fully interconnected scan points. The SSM method allows the robot to achieve scan matching without using an initial alignment between two scans and geometric features such as corners, curves, or lines. The localization process is composed of two stages: coarse localization and fine localization. Coarse localization with 2D geometric histogram constructed from the PGR is fast, but not precise sufficiently. On the other hand, fine localization using the SSM method is comparatively slow, but more accurate. This coarse-to-fine framework reduces the computational cost, and makes the localization process reliable. The feasibility of the proposed methods is demonstrated by results of simulations and experiments.     

基于扫描匹配的室外环境SLAM 方法

针对室外环境中的机器人“绑架”问题,提出了基于地图匹配的SLAM方法．该方法舍弃了机器人里程计信息, 只利用局部地图和全局地图的图形相关性进行机器人定位．方法的核心是多重估计数据关联,并将奇异值分解应用到机器人位姿计算中．利用Victoria Park数据集将本算法与基于扩展卡尔曼滤波器的方法进行比较,实验结果证明了本文提出的算法的有效性．     

Trajectory-Based Place-Recognition for Efficient Large Scale Localization

Place recognition is a core competency for any visual simultaneous localization and mapping system. Identifying previously visited places enables the creation of globally accurate maps, robust relocalization, and multi-user mapping. To match one place to another, most state-of-the-art approaches must decide a priori what constitutes a place, often in terms of how many consecutive views should overlap, or how many consecutive images should be considered together. Unfortunately, such threshold dependencies limit their generality to different types of scenes. In this paper, we present a placeless place recognition algorithm using a novel match-density estimation technique that avoids heuristically discretizing the space. Instead, our approach considers place recognition as a problem of continuous matching between image streams, automatically discovering regions of high match density that represent overlapping trajectory segments. The algorithm uses well-studied statistical tests to identify the relevant matching regions which are subsequently passed to an absolute pose algorithm to recover the geometric alignment. We demonstrate the efficiency and accuracy of our methodology on three outdoor sequences, including a comprehensive evaluation against ground-truth from publicly available datasets that shows our approach outperforms several state-of-the-art algorithms for place recognition. Furthermore we compare our overall algorithm to the currently best performing system for global localization and show how we outperform the approach on challenging indoor and outdoor datasets.     

Observation‐driven Bayesian Filtering for Global Location Estimation in the Field Area

Global localization has long been considered one of the most important but also one of the most challenging localization problems for mobile robots. Current studies of global localization in the literature are mainly based on the Bayesian filtering technique, which can provide an elegant statistical framework for uncertainty management and multisensory fusion. However, the majority of implementations of Bayesian filters for global localization obey the same update rules in such a location‐driven sense that they guess the robot location first and then adjust the guess by incorporating the current observation data. This leads to some problematic consequences in that the system suffers from great computational load in a large application area and it cannot recover from localization failure. To overcome the above limitations, this paper deviates from the conventional update rules of Bayes filters and proposes a new approach: the observation‐driven Bayes filters (OD‐BFs). As the name implies, OD‐BFs estimate the robot state just according to the most recent observations and then adjust the estimate by incorporating the dead‐reckoning information. We further implement an observation‐driven Bayes filter to globally estimate the robot pose in the field area. This global localization system features an effective pose estimation framework that can operate with a large amount of point data in a coarse‐to‐fine manner. Sufficient experiments were carried out to determine both the advantages and the disadvantages of our OD‐BF localization approaches compared with previous ones.     

Linear-time robot localization and pose tracking using matching signatures

A feature-based method for global localization of mobile robot using a concept of matching signatures is presented. A group of geometric features, their geometric constraints invariant to frame transform, and location dependent constraints, together are utilized in defining signature of a feature. Plausible global poses are found out by matching signatures of observed features with signatures of global map features. The concept of matching signatures is so developed that the proposed method provides a very efficient solution for global localization. Worst-case complexity of the method for estimating and verifying global poses is linear with the size of global reference map. It will also be shown that with the approach of random sampling the proposed algorithm becomes linear with both the size of global map and number of observed features. In order to avoid pose ambiguity, simultaneous tracking of multiple pose hypotheses staying within the same framework of the proposed method is also addressed. Results obtained from simulation as well as from real world experiment demonstrate the performance and effectiveness of the method.     

基于激光测距的环境地图动态创建技术研究

本文主要研究完全未知结构化环境下的移动机器人二维地图构建与标图技术。本文以激光测距仪为环境探测传感器,采用几何特征法创建地图。对局部地图创建中的区域分割方法进行了改进,提出了基于线性阈值法的区域分割方法;给出了基于相关线段和线段缓冲区的全局地图创建方法。实验结果表明：本方法实现了基于实时的激光测距数据的局部地图动态创建和全局地图的实时更新,算法有效且可行。     

Globally Optimal Estimates for Geometric Reconstruction Problems

We introduce a framework for computing statistically optimal estimates of geometric reconstruction problems. While traditional algorithms often suffer from either local minima or non-optimality—or a combination of both—we pursue the goal of achieving global solutions of the statistically optimal cost-function. Our approach is based on a hierarchy of convex relaxations to solve non-convex optimization problems with polynomials. These convex relaxations generate a monotone sequence of lower bounds and we show how one can detect whether the global optimum is attained at a given relaxation. The technique is applied to a number of classical vision problems: triangulation, camera pose, homography estimation and last, but not least, epipolar geometry estimation. Experimental validation on both synthetic and real data is provided. In practice, only a few relaxations are needed for attaining the global optimum.     

基于点线特征融合的视觉惯性SLAM算法

针对目前视觉SLAM方法鲁棒性差、耗时高,使系统定位不够精确的问题,提出了一种基于点线特征融合的视觉惯性SLAM算法。首先通过短线剔除和近似线段合并策略改进LSD（line segment detection）提取质量,以提高线特征检测的速率和准确度;然后在后端优化中有效融合了点、线和IMU数据,建立最小化目标函数进行优化,得到更精确的相机位姿;最后在EuRoC数据集和现实走廊场景进行了实验验证。实验表明,所提算法可以有效提升线特征提取的质量和速度,同时有效提高了SLAM系统的定位精度,获得更为丰富的点线结构地图。     

Robust mapping and localization in indoor environments

Conventional localization methods have been developed for indoor static environments such as the home environment. In dynamic environments such as factories and warehouses, however, it is difficult to estimate the accurate robot pose. Therefore, we propose a novel approach for the estimation of the robot pose in a dynamic or large environment for which fixed features are used. In the proposed method, a ceiling-feature map is built using an upward-looking monocular camera. This map is created accurately from the robot pose using a laser scanner and an estimation based on the iterative closest point method. The ceiling-feature map consists of features such as lamps and the FREAK, and its creation can be more accurate if the sliding-window technique and bundle-adjustment schemes are used. During the post-mapping navigation, the robot pose is estimated using the Monte Carlo localization method based on the ceiling-feature map. In dynamic experiments, the proposed method shows a high repeatability and stability in real-world conditions and applications.     

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

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

Metric embedding of view-graphs

Most recent robotic systems, capable of exploring unknown environments, use topological structures (graphs) as a spatial representation. Localization can be done by deriving an estimate of the global pose from landmark information. In this case navigation is tightly coupled to metric knowledge, and hence the derived control method is mainly pose-based. Alternative to continuous metric localization, it is also possible to base localization methods on weaker constraints, e.g. the similarity between images capturing the appearance of places or landmarks. In this case navigation can be controlled by a homing algorithm. Similarity based localization can be scaled to continuous metric localization by adding additional constraints, such as alignment of depth estimates. We present a method to scale a similarity based navigation system (the view-graph-model) to continuous metric localization. Instead of changing the landmark model, we embed the graph into the three dimensional pose space. Therefore, recalibration of the path integrator is only possible at discrete locations in the environment. The navigation behavior of the robot is controlled by a homing algorithm which combines three local navigation capabilities, obstacle avoidance, path integration, and scene based homing. This homing scheme allows automated adaptation to the environment. It is further used to compensate for path integration errors, and therefore allows to derive globally consistent pose estimates based on “weak” metric knowledge, i.e. knowledge solely derived from odometry. The system performance is tested with a robotic setup and with a simulated agent which explores a large, open, and cluttered environment. This work is part of the GNOSYS (FP6-003835-GNOSYS) project, supported by the European Commission.     

Robust camera pose and scene structure analysis for service robotics

Successful path planning and object manipulation in service robotics applications rely both on a good estimation of the robot’s position and orientation (pose) in the environment, as well as on a reliable understanding of the visualized scene. In this paper a robust real-time camera pose and a scene structure estimation system is proposed. First, the pose of the camera is estimated through the analysis of the so-called tracks. The tracks include key features from the imaged scene and geometric constraints which are used to solve the pose estimation problem. Second, based on the calculated pose of the camera, i.e. robot, the scene is analyzed via a robust depth segmentation and object classification approach. In order to reliably segment the object’s depth, a feedback control technique at an image processing level has been used with the purpose of improving the robustness of the robotic vision system with respect to external influences, such as cluttered scenes and variable illumination conditions. The control strategy detailed in this paper is based on the traditional open-loop mathematical model of the depth estimation process. In order to control a robotic system, the obtained visual information is classified into objects of interest and obstacles. The proposed scene analysis architecture is evaluated through experimental results within a robotic collision avoidance system.     

Robust vision-based localization by combining an image-retrieval system with Monte Carlo localization

In this paper, we present a vision-based approach to mobile robot localization that integrates an image-retrieval system with Monte Carlo localization. The image-retrieval process is based on features that are invariant with respect to image translations and limited scale. Since it furthermore uses local features, the system is robust against distortion and occlusions, which is especially important in populated environments. To integrate this approach with the sample-based Monte Carlo localization technique, we extract for each image in the database a set of possible viewpoints using a two-dimensional map of the environment. Our technique has been implemented and tested extensively. We present practical experiments illustrating that our approach is able to globally localize a mobile robot, to reliably keep track of the robot's position, and to recover from localization failures. We furthermore present experiments designed to analyze the reliability and robustness of our approach with respect to larger errors in the odometry.     

Mobile Robot Self-Localization without Explicit Landmarks

Localization is the process of determining the robot's location within its environment. More precisely, it is a procedure which takes as input a geometric map, a current estimate of the robot's pose, and sensor readings, and produces as output an improved estimate of the robot's current pose (position and orientation). We describe a combinatorially precise algorithm which performs mobile robot localization using a geometric model of the world and a point-and-shoot ranging device. We also describe a rasterized version of this algorithm which we have implemented on a real mobile robot equipped with a laser rangefinder we designed. Both versions of the algorithm allow for uncertainty in the data returned by the range sensor. We also present experimental results for the rasterized algorithm, obtained using our mobile robots at Cornell. Received November 15, 1996; revised January 13, 1998.     

可移动机器人的马尔可夫自定位算法研究

马尔可夫定位算法是利用机器人运动环境中的概率密度分布进行定位的方法.使用该 方法机器人可在完全不知道自己位置的情况下通过传感器数据和运动模型来估计自己的位置. 但是,在研究中发现它还存在一些问题,如概率减小到零后就无法恢复.对只有距离传感器的机 器人在对称的环境中仅仅采用该算法就无法确定位置.为了解决这些问题,文中给出了修正算 法,并建议在机器人上装上方向仪(如指南针或陀螺仪等),然后利用定义的一个角度高斯分布 函数来构造新的机器人感知模型.在此基础上详细地阐述了一种新的自定位技术.最后,采用仿 真程序验证了机器人在对称环境中运动时这一新算法的可行性.     

A Computational Geometry Approach for Localization and Tracking in GPS‐denied Environments*

Localization and tracking of vehicles is still an important issue in GPS‐denied environments (both indoors and outdoors), where accurate motion is required. In this work, a localization system based on the random disposition of LiDAR sensors (which share a partially common field of view) and on the use of the Hausdorff distance is addressed. The proposed system uses the Hausdorff distance to estimate both the position of the LiDAR sensors and the pose of the vehicle as it drives within the environment. Our approach is not restricted to the number of LiDAR sensors (the estimation procedure is asynchronous), the number of vehicles (it is a multidimensional approach), or the nature of the environment. However, it is implemented in open spaces, limited by the range of the LiDAR sensors and the geometry of the vehicle. An empirical analysis of the presented approach is also included here, showing that the error in the localization estimation remains bounded in approximately 50 cm. Real‐time experimentation as validation of the proposed localization and tracking techniques as well as the pros and cons of our proposal are also shown in this work.