Multi-Robot SLAM with Unknown Initial Covariance

  • NSF
  • Motivation
  • One of the most challenging problems in autonomous vehicle navigation is to maintain accurate knowledge of the position of the vehicles. When robots operate within unmapped areas or when absolute positioning information is not available, achieving accurate localization requires that they create and maintain a precise map of their surroundings. This is commonly referred to as Simultaneous Localization and Mapping (SLAM). In order to increases the accuracy and efficiency when mapping large areas, it is often necessary for multiple robots to participate in this task. A prerequisite for multi-robot cooperation is know their relative transformation. In this project, we consider the problem of joining maps created by different robots where their relative robot-to-robot transformation is initially unknown.
  • Summary
  • This work presents a new approach to the multi-robot map-alignment problem that enables teams of robots to build joint maps without initial knowledge of their relative poses. The key contribution of this work is an optimal algorithm for merging (not necessarily overlapping) maps that are created by different robots independently. Relative pose measurements between pairs of robots are processed to compute the coordinate transformation between any two maps. Noise in the robot-to-robot observations, propagated through the map-alignment process, increases the error in the position estimates of the transformed landmarks, and reduces the overall accuracy of the merged map. When there is overlap between the two maps, landmarks that appear twice provide additional information, in the form of constraints, which increases the alignment accuracy. Landmark duplicates are identified through a fast nearest neighbor matching algorithm. In order to reduce the computational complexity of this search process, a kd-tree is used to represent the landmarks in the original map. The criterion employed for matching any two landmarks is the Mahalanobis distance. As a means of validation, we present experimental results obtained from two robots mapping an area of 4,800 square meters.
  • Experiments
  • The experiments took place in the main building of our department. Two Pioneer 3 robots are used to map an area of size ~ 4,800 square meters. Each robot carries a SICK LMS200 for detecting corner features in the environment and a PointGrey color camera with a RemoteReality NetVision360 omnidirectional lens. A colored cylinder was placed on top of each omnidirectional camera. Robot-to-Robot measurements were acquired through the omnidirectional camera by means of tracking the colored cylinder.
    The two robots start their mapping tasks at two different locations. The relative pose between the two robots is unknown. Initially, each robot maps the floor independently. Their maps are shown in the following figures.
    Map of robot 1 before meeting robot 2:

    Map of robot 2 before meeting robot 1:
    At some point the two robots meet each other, and measure their relative distance and bearing. From these measurements, their relative transformation is determined. The map of robot 2 is transformed to the frame of the reference of robot 1. The errors in the inter-robot measurements introduce error in the relative transformation. Therefore, the transformed landmark uncertainty is increased.
    Merged map before matching duplicate landmarks:
    To reduce the merged map uncertainty, we employ a Nearest Neighbor test algorithm to identify and merge duplicated landmarks. The merged map is updated by imposing collocation constraints on duplicated landmarks. It is shown that the accuracy of the map is significantly increased.
    Merged map after matching and eliminating duplicate landmarks:
    Once the merging process is completed, the two robots continue to perform SLAM as a single system in a centralized fashion.
    Two robots SLAM:
  • Relevant Publications
  • C1. X. S. Zhou and S. I. Roumeliotis, "Multi-robot SLAM with unknown initial correspondence: The robot rendezvous case," in Proceedings of IEEE International Conference on Intelligent Robots and Systems, Beijing, China, Oct. 9 - 15 2006. pp. 1785-1792 (pdf).