GPU Accelerated 2D and 3D Position Tracking and SLAM

Building a globally correct map of an unknown environment and localising a robot in it is a common problem in robotics. This thesis presents research on 2D and 3D position tracking, Simultaneous Localisation and Mapping (SLAM) and map building algorithms that use data from a Laser Rangefinder and a depth (RGB-D) camera. These algorithms are computationally intensive, and often require powerful computers to run in real time. In this thesis we focus on designing efficient methods to reduce the computational demands of these algorithms so they are capable of running on mobile robots with limited processing power. A key part of our approach is to develop parallel algorithms and data structures suitable for use on a mobile Graphics Processing Unit (GPU).We describe a highly parallel 2D occupancy grid Iterative Closest Point (ICP) position tracking algorithm that exploits the hardware structure of GPUs to rapidly find corresponding points and uses an occupancy map structure that can be safely modified in parallel with little synchronisation. These features allow our algorithm to run substantially faster than CPU based position tracking, even when an integrated GPU is used.This is coupled with a Graph SLAM system that is capable of producing globally consistent maps despite large errors in ICP registration. We introduce two types of loop closure constraints to allow the global map to be corrected as soon as possible, while retaining robustness to false positives in the presence of position tracking failures. Our system can generate globally consistent maps in challenging scenarios such as long featureless corridors and complex office environments. In reflection of our focus on efficiency, we employ a two step optimisation procedure operating on a tree-based graph of local maps, so only a subset of local maps need to be updated after a loop closure.A key contribution of this thesis is the fusing of this Laser Rangefinder based 2D SLAM approach into a RGB-D camera based 3D position tracking, map building and SLAM system. The approach combines the advantages of the wide field of view and precision of Laser Rangefinders, with the 3D data collection and dense data of RGB-D sensors. We introduce a regularisation term to restrict movement in degrees of freedom that are not constrained by surface geometry. We mirror the 2D Graph SLAM approach in 3D to efficiently detect loops. The resulting algorithm is able to generate dense, globally consistent 3D maps in real-time on resource constrained robots