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 dtrees and approximate bdtrees. Finally, we reproduce results from a robot run given in [27] 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 dtree outperforms the bdtree. 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 bdtree is faster than the dtree. 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
http://www.ais.fraunhofer.de/ARC/3D/6D/
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. & Dtree  12 min 23 s  2080 
all pts. & ApxDtree  10 min 1 s  2080 
red. pts. & ApxDtree  1 min 32 s  2176 
6D SLAM with  
reduced pts. & ApxDtree  38 min  16000 
