CDDT: Fast Approximate 2D Ray Casting for Accelerated Localization
This addresses the problem of real-time localization for resource-constrained autonomous robots, offering a significant speedup over existing methods.
The paper tackles the computational expense of ray casting in robot localization by introducing the Compressed Directional Distance Transform, which achieves near constant time performance with two orders of magnitude less memory and precomputation than a 3D lookup table, enabling a particle filter to run at 40Hz with 2500 particles on a single CPU thread.
Localization is an essential component for autonomous robots. A well-established localization approach combines ray casting with a particle filter, leading to a computationally expensive algorithm that is difficult to run on resource-constrained mobile robots. We present a novel data structure called the Compressed Directional Distance Transform for accelerating ray casting in two dimensional occupancy grid maps. Our approach allows online map updates, and near constant time ray casting performance for a fixed size map, in contrast with other methods which exhibit poor worst case performance. Our experimental results show that the proposed algorithm approximates the performance characteristics of reading from a three dimensional lookup table of ray cast solutions while requiring two orders of magnitude less memory and precomputation. This results in a particle filter algorithm which can maintain 2500 particles with 61 ray casts per particle at 40Hz, using a single CPU thread onboard a mobile robot.