Todor Stoyanov
Reliable Autonomous Navigation in Semi-Structured Environments using the Three-Dimensional Normal Distributions Transform (3D-NDT)

This thesis is concerned with autonomous navigation of a robotic vehicle in a semi-structured environment. Starting from the low-level problem of range sensing and moving on to more complex tasks like spatial representation, registration and mapping, path planning and following, this dissertation aims at providing a consistent picture of an autonomous navigation system.

A unifying concept throughout this work is the use of the Three-Dimensional Normal Distributions Transform (3D-NDT) as a base for modeling space. The 3D-NDT is a compact, yet expressive means of modeling the environment, using a set of Gaussian probability density functions. Closely related to Gaussian Mixture Models (GMMs), the 3D-NDT can adequately model semi-structured indoor or natural environments. Unlike GMMs however, the 3D-NDT can be constructed very rapidly from 3D sensor data, making it ideal for use in time-critical algorithms, often necessary for successful autonomous navigation.

One of the contributions of this dissertation is a method for comparison of spatial representation models. The proposed method is used on a large benchmarking data set, demonstrating the accuracy and expressive power of the 3D-NDT. The proposed methodology is modified and used to compare the accuracy of four 3D range sensors in complex operational scenarios. A central task in robotics is that of \textit{registering} range measurements in a consistent model of the environment. In an important contribution, we propose a registration algorithm which operates directly on the 3D-NDT representations of the raw point cloud data. Using the compactness and expressive power of the 3D-NDT, accurate registration results are obtained at run times, an order of magnitude faster then those of current algorithms. Algorithms to choose a good starting position for registration and to estimate the match covariance are also presented, paving the way to future 3D-NDT-based simultaneous localization and mapping (SLAM) solutions. This dissertation also makes a contribution to another essential component of an autonomous navigation system --- namely the planning and safe execution of a drivable path. A traversability analysis technique, based on the 3D-NDT, is proposed and used in a modified wavefront path planner to produce safe paths in complex 3D environments. Finally, the proposed traversability analysis algorithm is used for obstacle detection and avoidance.

Thesis: [PDF (14.0MB)].
  AUTHOR = {Stoyanov, Todor},
  TITLE = {Reliable Autonomous Navigation in Semi-Structured Environments using the Three-Dimensional Normal Distributions Transform (3D-NDT)},
  YEAR = {2012},