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: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2022
|
| Online Access: | https://hdl.handle.net/1721.1/137859.2 |
| _version_ | 1826207564495323136 |
|---|---|
| author | Walsh, Corey H. Karaman, Sertac |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science 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:51:31Z |
| format | Article |
| id | mit-1721.1/137859.2 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:51:31Z |
| publishDate | 2022 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/137859.22022-01-07T18:33:46Z CDDT: Fast Approximate 2D Ray Casting for Accelerated Localization Walsh, Corey H. Karaman, Sertac Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems © 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. 2022-01-07T18:33:45Z 2021-11-09T13:28:52Z 2022-01-07T18:33:45Z 2018-05 2019-10-28T18:27:38Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137859.2 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/octet-stream 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.2 |
| work_keys_str_mv | AT walshcoreyh cddtfastapproximate2draycastingforacceleratedlocalization AT karamansertac cddtfastapproximate2draycastingforacceleratedlocalization |