Description

This thesis is primarily concerned with two aspects of the [feature-based] SLAM problem. First, it addresses data association, which previously has been dominated by methods inherited from the target-tracking literature. It is shown that processing associations as a batch, rather than sequentially, greatly improves robustness - especially when the vehicle location is very uncertain. A graph-theoretic data association method, Combined Constraint Data Association (CCDA), provides a practical and efficient implementation of batch validation gating. Second, the thesis presents a new submap framework, Network Coupled Feature Maps (NCFM), which permits efficient computation of SLAM, and addresses the problem of consistency in the presence of cumulative non-linearities.

NCFM and CCDA are complementary concepts and are shown to facilitate reliable data association in very difficult circumstances. Particularly, the combined use of NCFM and CCDA addresses the problem of detecting and closing large loops with SLAM when the accumulated vehicle uncertainty is extreme.

Abstract

This thesis addresses the issues of scale for practical implementations of simultaneous localisation and mapping (SLAM) in extensive outdoor environments. Building an incremental map while also using it for localisation is of prime importance for mobile robot navigation but, until recently, has been confined to small-scale, mostly indoor, environments. The critical problems for large-scale implementations are as follows. First, data association— finding correspondences between map landmarks and robot sensor measurements—becomes difficult in complex, cluttered environments, especially if the robot location is uncertain. Second, the information required to maintain a consistent map using traditional methods imposes a prohibitive computational burden as the map increases in size. And third, the mathematics for SLAM relies on assumptions of small errors and near-linearity, and these become invalid for larger maps.

In outdoor environments, the problems of scale are exacerbated by complex structure and rugged terrain. This can impede the detection of stable discrete landmarks, and can degrade the utility of motion estimates derived from wheel-encoder odometry. This thesis presents the following contributions for large-scale SLAM. First, a batch data association method called combined constraint data association (CCDA) is developed, which permits robust association in cluttered environments even if the robot pose is completely unknown. Second, an alternative to feature-based data association is presented, based on correlation of unprocessed sensor data with the map, for environments that don’t contain easily detectable discrete landmarks. Third, methods for feature management are presented to control the addition and removal of map landmarks, which facilitates map reliability and reduces computation. Fourth, a new map framework called network coupled feature maps (NCFM) is introduced, where the world is divided into a graph of connected submaps. This map framework is shown to solve the problems of consistency and tractability for very large-scale SLAM.

The theoretical contributions of this thesis are demonstrated with a series of practical implementations using a scanning range laser in three different outdoor environments. These include: sensor-based dead reckoning, which is a highly accurate alternative to odometry for rough terrain; correlation-based localisation using particle filter methods; and NCFM SLAM over a region greater than 50000 square metres, and including trajectories with large loops.

Download

Full thesis [pdf] (9,276 kb, 212 pages)