Fetching the paper…

Reading the bibliography…

2017

CDDT: Fast Approximate 2D Ray Casting for Accelerated Localization

Walsh, Corey, Karaman, Sertac

Original
PDF
Post on X

Understand

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.

CDDT: Fast Approximate 2D Ray Casting for Accelerated Localization · Around

Built on

J. Bresenham. “Algorithm for Computer Control of a Digital Plotter,” IBM Systems Journal
1965
Earlier work this paper cites.
K. Perlin and E. M. Hoffert. “Hypertexture,” Computer Graphics
1989
Earlier work this paper cites.
K. Zuiderveld, A. Koning, and M. Viergever. “Acceleration of ray-casting using 3D distance transforms,” Proceedings of the SPIE
1992
Earlier work this paper cites.

Similar

D. Fox, W. Burgard, and S. Thrun. “Markov localization for mobile robots in dynamic environments,” Journal of Artificial Intelligence Research
1999
Cited alongside, same era.
S. Thrun, D. Fox, W. Burgard, and F. Dellaert. “Robust Monte Carlo Localization for Mobile Robots,” Artificial Intelligence
2001
Cited alongside, same era.
M. Pharr, and R. Fernando. “Chapter 8. Per-Pixel Displacement Mapping with Distance Functions” in GPU gems 2: Programming techniques for high-performance graphics and general-purpose computation
2005
Cited alongside, same era.

Then

P. Felzenszwalb and D. Huttenlocher. “Distance Transforms of Sampled Functions,” Theory of Computing
2012
Later among the works it cites.
J. Biswas. “Vector Map-Based, Non-Markov Localization for Long-Term Deployment of Autonomous Mobile Robots,” Ph.D. dissertation, The Robotics Inst., Carnegie Mellon Univ., Pittsburgh, PA, 2014
2014
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…