CDDT: Fast Approximate 2D Ray Casting for Accelerated Localization
© 2018 IEEE. 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 st...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137859 |
| _version_ | 1826206104639504384 |
|---|---|
| author | Walsh, Corey H. Karaman, Sertac |
| author_facet | Walsh, Corey H. Karaman, Sertac |
| author_sort | Walsh, Corey H. |
| collection | MIT |
| description | © 2018 IEEE. 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 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. |
| first_indexed | 2024-09-23T13:24:10Z |
| format | Article |
| id | mit-1721.1/137859 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:24:10Z |
| publishDate | 2021 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1378592021-11-10T03:23:07Z CDDT: Fast Approximate 2D Ray Casting for Accelerated Localization Walsh, Corey H. Karaman, Sertac © 2018 IEEE. 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 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. 2021-11-09T13:28:52Z 2021-11-09T13:28:52Z 2018-05 2019-10-28T18:27:38Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137859 Walsh, Corey H. and Karaman, Sertac. 2018. "CDDT: Fast Approximate 2D Ray Casting for Accelerated Localization." en 10.1109/ICRA.2018.8460743 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Walsh, Corey H. Karaman, Sertac CDDT: Fast Approximate 2D Ray Casting for Accelerated Localization |
| title | CDDT: Fast Approximate 2D Ray Casting for Accelerated Localization |
| title_full | CDDT: Fast Approximate 2D Ray Casting for Accelerated Localization |
| title_fullStr | CDDT: Fast Approximate 2D Ray Casting for Accelerated Localization |
| title_full_unstemmed | CDDT: Fast Approximate 2D Ray Casting for Accelerated Localization |
| title_short | CDDT: Fast Approximate 2D Ray Casting for Accelerated Localization |
| title_sort | cddt fast approximate 2d ray casting for accelerated localization |
| url | https://hdl.handle.net/1721.1/137859 |
| work_keys_str_mv | AT walshcoreyh cddtfastapproximate2draycastingforacceleratedlocalization AT karamansertac cddtfastapproximate2draycastingforacceleratedlocalization |