This section focuses on three aspects. Firstly, we evaluate the quality of scan matching with approximate nearest neigbour search. Secondly, we investigate the performance of approximate d-trees and approximate bd-trees. Finally, we reproduce results from a robot run given in  to demonstrate the general performance of the approach.
To evaluate the quality of the scan matching we restrict the problem to three degrees of freedom. We acquired two 3D scans and measured the pose shift by a reference system, i.e., a meter rule. Fig. (bottom) shows the starting poses from which a correct scan matching is possible. Fig. indicates the initial positions that result in a correct scan matching for different values of and the bucket size . Comparing the figures, we conclude that the approximation does not significantly influence the scan matching, due to the large numer of used points and to the iterative nature of the algorithm.
The performance of the proposed tree search is given in Fig. and . In case of no approximation (Fig. ) the d-tree outperforms the bd-tree. The optimal time is reached with 10 points per bucket. In case of approximation, only in a few cases, i.e., 18 out of 124 experiments, the bd-tree is faster than the d-tree. Nevertheless, one notices that with increasing the computation time for the scan matching is reduced drastically (up to a factor of 2).
The proposed algorithms have been applied to a data set acquired
on the Fraunhofer Campus Birlinghoven campus. 32 3D scans, each
containing 302820 (721 420) range data points, were
taken by the mobile robot Kurt3D. The robot had to cope with a
height difference between the two buildings of 1.05 meter,
covered, in the first case, by a sloped driveway in open outdoor
terrain, and, in the second case, by a ramp of 12 inside
the building. The 3D model was computed after acquiring all 3D
scans. Table summarizes the computation time
of our 6D SLAM algorithms. Refer to the website
for a computed animation and video through the scanned 3D scene. Furthermore, the algorithms have been evaluated at the RoboCup Rescue 2004 competition in Lisbon and precise, reliable, on time 3D maps have been generated (see http://www.ais.fhg.de/ARC/kurt3D/rr.html).
|points & search method||time||iter.|
|all pts. & brute force||144 h 5 min||2080|
|all pts. & D-tree||12 min 23 s||2080|
|all pts. & Apx-D-tree||10 min 1 s||2080|
|red. pts. & Apx-D-tree||1 min 32 s||2176|
|6D SLAM with|
|reduced pts. & Apx-D-tree||38 min||16000|