Efficient simultaneous localisation and mapping in large and complex environments

• Autores: Cesar Dario Cadena Lerma
• Directores de la Tesis: José Neira Parra (dir. tes.)
• Lectura: En la Universidad de Zaragoza ( España ) en 2011
• Idioma: español
• Tribunal Calificador de la Tesis: Alberto Sanfeliu Cortés (presid.) , Juan Domingo Tardos Solano (secret.) , Nicholas Roy (voc.) , Javier González Jimenez (voc.) , Paul A. Newman (voc.)
• Enlaces
  • Tesis en acceso abierto en: Zaguán
• Resumen

  • Finding its way in the environment in which a robot operates is a basic problem to solve for true autonomy. There are two main aspects to this problem, known as Simultaneous Localization and Mapping (SLAM): (1) the continuous problem of estimating the location of elements of interest for the robot, and (2) the discrete problem of finding correspondences between measurements of the sensor that the robot uses to perceive its environment and the elements already in the map. In this thesis we address these two aspects of SLAM.

    The estimation problem is classically solved with a filtering approach with satisfactory solutions for environments of limited size. But as the operating environments grow, basic filtering approaches become no more an option because of high computational cost and loss of precision. There has been great progress in advancing filtering algorithms in this sense. In this thesis we intend to push filtering algorithms further forward. We propose a highly scalable filtering algorithm, also conceptually simple to implement. The Combined Filter SLAM algorithm (CF SLAM) is a judicious combination of Extended Kalman (EKF) and Extended Information Filters (EIF) that can be used to execute highly efficient SLAM in large environments.

    CF SLAM is always more efficient than any other EKF or EIF algorithm: filter updates can be executed in as low as O(log n) as compared with the linear cost of the currently most efficient filtering algorithms. In the worst cases, updates are executed in linear time for CF SLAM as compared with the quadratic cost for all others. In addition to its computational cost savings, CF SLAM does not include approximations (apart from linearisations) and require only linear memory with respect to the size of the environment.

    The estimation process in SLAM is subordinated to the constraints imposed by the detected correspondences between sensor observations, and thus the algorithm that solves the correspondence must be robust. This problem is usually denominated the data association problem. In this thesis, we address a central data association problem: detecting that the robot is revisiting a previously visited place. This problem is known as loop closing or place recognition.

    We propose a place recognition algorithm for SLAM systems that works with image and 3D sensors. Our algorithm considers both appearance and geometric information of points of interest in the image and 3D data. Both near and far scene points provide information for the recognition process. Hypotheses about loop closings are generated using a fast appearance technique based on the bag-of-words (BoW) method. Our main contribution is in the verification stage, using conditional random fields (CRFs). We build on CRF-matching with two main novelties: we use both image and 3D geometric information, and we carry out inference on a minimum Spanning Tree (MST), instead of a densely connected graph. Our results show that MSTs provide an adequate representation of the problem, with the additional advantages that exact inference is possible and the computational cost of the inference process is limited.

    We evaluate our proposals in a several publicly available datasets of indoor and outdoor static and dynamic urban environments, using stereo cameras and 3D laser sensors. We compare with other methods in the state of the art to illustrate the improvements in computational cost and robustness of the methods proposed.