Abstract-This paper provides a new solution to the simultaneous localization and mapping (SLAM) problem with six degrees of freedom. A fast variant of the Iterative Closest Points (ICP) algorithm registers 3D scans taken by a mobile robot into a common coordinate system and thus provides relocalization. Hereby, data association is reduced to the problem of searching for closest points. Approximation algorithms for this searching, namely, approximate kd-trees and box decomposition trees, are presented and evaluated in this paper. A solution to 6D SLAM that considers all free parameters in the robot pose is built based on 3D scan matching. Digital 3D models of the environment are needed in rescue and inspection robotics, facility management and architecture. The problem of automatic environment sensing and modeling is complex, because a number of fundamental scientific issues are involved. This paper focusses on how to create a consistent 3D scene into a common coordinate system from multiple scans. The proposed algorithms allow to digitize large environments fast and reliably without any intervention and to solve the simultaneous localization and mapping (SLAM) problem. Finally, robot motion on natural outdoor surfaces has to cope with changes in yaw, pitch and roll angles, turning pose estimation as well as scan matching or registration into a problem in six mathematical dimensions. This paper presents a new solution to the SLAM problem with six degrees of freedom (6D SLAM). A fast variant of the iterative closest points (ICP) algorithm registers the 3D scans into a common coordinate system and relocalizes the robot. Computation time is reduced by two new methods: First, we reduce the 3D data, i.e., we compute point clouds that approximate the scanned 3D surface and contain only a small fraction of that original 3D point cloud. Second, we present a fast approximation of the corresponding point for the ICP algorithm. Several approximation methods are evaluated in this paper. These extensions of ICP result in a fast and robust algorithm for generating overall consistent 3D maps, using global error minimization. In previous work we developed the 6D SLAM algorithm [20] , [27] . This paper's main contribution is to evaluate the approximate data association to speed up the algorithm. The rest of the paper is organized as follows: Section II discusses the state of the art in 3D mapping. Then we present the used 3D laser scanner and the mobile robot. Section IV describes scan matching and pose estimation, followed by the application of closest point approximation in the data
Using an approximate kd-tree decreases the computational time of ICP REF .
6D SLAM with approximate data association
ICAR '05. Proceedings., 12th International Conference on Advanced Robotics, 2005.
ICAR '05. Proceedings., 12th International Conference on Advanced Robotics, 2005.
Mathematics