Results and Conclusions

The algorithms have been applied to data collected in the Mathies Mine after the robot returned. Table I summarizes the results for the 3D scan matching and 6D SLAM. It is shown that using approximate $k$d-tree search decreases the running time of the proposed scan matching algorithms about 15%. Nevertheless, the main speedup is reached by the data reduction, resulting in a real-time capable ICP algorithm. The 6D SLAM algorithm can be used on an inspection robot for mines, the time needed for global consistent registration roughly corresponds to the time, needed to drive to the next scanning pose.

Table I: Computing time and number of ICP iterations to align two 3D scans (Pentium-IV-2400). The time values, excluding the brute force, and the number of iterations are averages over 48 3D scans. In addition the computing time for the SLAM algorithm (simultaneous matching) is given.

points used	time	# ICP iterations
all points & brute force search	4 h 25 min	45
all points & $k$D-tree	6.8 sec	45
all points & Apx-$k$D-tree	5.9 sec	45
reduced points & Apx-$k$D-tree	$<$0.62 sec	42
3D SLAM with		42 (step 1)
reduced points & Apx-$k$D-tree	52 sec	497 (step 3)

Fig. 6 shows the result of the Mathies Mine mapping. The top plot shows the 2D map, i.e., $xz$-map, where $z$ is the depth axis. The bottom part shows the elevation, i.e., the $xy$-map. The Groundhog robot had to overbear a height of 4 meters during its 250 meter long autonomous drive.

To visualize the scanned 3D data, a viewer program based on OPENGL has been implemented. The task of this program is to project the 3D scene to the image plane, i.e., the monitor, such that the data can be drawn and inspected from every perspective. Fig. 2 and 4 show rendered 3D scans. A video of all matched 3D scans is available for download at www.ais.fraunhofer.de/ARC/3D/mine/. C This paper has presented a new solution to the simultaneous localization and mapping (SLAM) problem with six degrees of freedom. Based on the ICP algorithm the registration error is globally spread over all 3D scans and thus minimized. The presented algorithms are significant speeded up with data reduction that maintains the surface structure and with approximate $k$d-tree for closest point search.