An Efficient Data Association Approach to Simultaneous Localization and Map Building

Abstract

In this paper we present an efficient integer programming (IP) based data association approach to simultaneous localization and mapping (SLAM). In this approach, the feature-based SLAM data association problem is formulated as a 0-1 IP problem. The IP problem is approached by first solving a relaxed linear programming (LP) problem. Based on the optimal LP solution, a suboptimal solution to the IP problem is then obtained by applying an iterative heuristic greedy rounding (IHGR) procedure. Unlike the traditional nearest-neighbor (NN) algorithm, the proposed algorithm deals with the global matching between existing features and measurements of each scan and is more robust for an environment of high-density features (the feature number is high and the distances between features are often very close) which is usually the case in outdoor applications. Detailed simulation and experimental studies show that the proposed IHGR-based algorithm has moderate computational requirement and offers a better performance with higher successful rate of SLAM for complex environments of high density of features than the NN algorithm.