T. Bailey, E.M. Nebot, J.K. Rosenblatt and H.F. Durrant-Whyte

Data Association for Mobile Robot Navigation:
A Graph Theoretic Approach

IEEE International Conference on Robotics and Automation, 2000


 

Description

This paper presents a batch validation gating algorithm based on the Maximum Common Subgraph (MCS) search. This algorithm is a forerunner to the CCDA algorithm presented in my PhD thesis, which supercedes it. There are two main differences between this MCS approach and the CCDA. First, MCS does not include vehicle pose information, while CCDA uses pose information (if available) as additional constraints. Second, the MCS constraints are defined by euclidean bounds, while the CCDA bounds involve stochastic gating (ie., Chi-square bounds).
 

Abstract

Data association is the process of relating features observed in the environment to features viewed previously or to features in a map. Correct feature association is essential for mobile robot navigation as it allows the robot to determine its location relative to the features it observes. This paper presents a graph theoretic method that is applicable to data association problems where the features are observed via a batch process. Batch observations (e.g., scanning laser, radar, video) detect a set of features simultaneously or with sufficiently small temporal difference that, with motion compensation, the features can be represented with precise relative coordinates. This data association method is described in the context of two possible navigation applications: metric map building with simultaneous localisation, and topological map based localisation.

Experimental results are presented using an indoor mobile robot with a 2D scanning laser sensor. Given two scans from different unknown locations, the features common to both scans are mapped to each other and the relative change in pose (position and orientation) of the vehicle between the two scans is obtained.

Download

Full paper [pdf] (398 kb, 6 pages)


[Tim's Homepage]