Determining the Robot-to-Robot Relative Pose Using Range-only Measurements

    A bird's-eye view of the two robots moving on the ground. In our experiments, visual markers are placed on top of the robots for tracking their motions from an overhead camera.
    In this work, we address the problem of determining the relative pose of pairs robots that move on a plane while measuring the distance to each other. We have proved that the minimum number of distance measurements required for computing the 3 degrees of freedom relative pose is 3. In this case, we have shown that there exist at most 6 solutions. In order to disambiguate them, additional distance measurements are necessary. We have further shown that given 4 distance measurements there exist at most 4 solutions. Finally, we have proved that 5 distance measurements are sufficient for uniquely determining the vehicles' relative pose.

    Sponsor: NSF, UMN Researchers: Xun Zhou, Prof. Stergios Roumeliotis

    Multi-robot SLAM with Unknown Initial Correspondence

    Global map created by two robots.

    Two Pioneer robots performing SLAM.
    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.

    Sponsor: NSF, UMN Researchers: Xun Zhou, Prof. Stergios Roumeliotis