Efficient path planning in deformable dense maps

Abstract

The changing belief state during a stochastic mapping process such as Simultaneous Localisation And Mapping (SLAM) poses challenges for mobile robot path planning. Existing planning algorithms are unable to handle both large volumes of spatially referenced data, which we call dense data, and the type of deformation produced by a stochastic mapping process while maintaining consistency with the belief state.

This thesis characterises the changes in belief state, termed deformation, expected from such a process by introducing three deformation metrics; the first of which monitors the distances between sample points distributed throughout the belief state. Two of the metrics are designed to detect inconsistency in the mapping process and predict the Maximum Expected Deformation (MED) using the stochastic information of the sample points. Given the MED at any point in a map, a method is presented for planning safe paths over a discrete cost map. This thesis also presents a framework for path planning that uses rigid local map representations combined with a roadmap, analogous to both Probabilistic Road Maps (PRM) and submaps in SLAM. The improvement in efficiency of the framework is verified through complexity analysis.

Results from simulations of the introduced deformation metrics demonstrate that they can not only detect but also predict local map deformation while being invariant to rigid-body motion of the belief state. Paths generated over a discrete cost map were shown to be both optimal and safe given the MED over the map.

This thesis validates that deformation monitoring and replanning management in combination with caching rigid local plans increases the efficiency of planning during SLAM by at least a factor of two. The introduced framework also demonstrated fast multiple-source, multiple-destination plan querying while maintaining consistency with dense data. Finally a novel method for continuously generating dense data from an actuated 3D laser rangefinder has been proposed. Ultimately, the management of dense data plays a key role in the efficiency of the framework for path planning during SLAM --- the major contribution of this thesis --- which has in turn removed a fundamental barrier to the increase of autonomy in contemporary mobile robotics.