Motion planning with diffusion maps
Many robotic applications require repeated, on-demand motion planning in mapped environments. In addition, the presence of other dynamic agents, such as people, often induces frequent, dynamic changes in the environment. Having a potential function that encodes pairwise cost-to-go can be useful for...
| Príomhchruthaitheoirí: | , , , , |
|---|---|
| Rannpháirtithe: | |
| Formáid: | Alt |
| Foilsithe / Cruthaithe: |
Institute of Electrical and Electronics Engineers (IEEE)
2018
|
| Rochtain ar líne: | http://hdl.handle.net/1721.1/114715 https://orcid.org/0000-0003-3756-3256 https://orcid.org/0000-0002-9838-1221 https://orcid.org/0000-0002-1648-8325 https://orcid.org/0000-0002-4621-2960 https://orcid.org/0000-0001-8576-1930 |
| _version_ | 1826214805607809024 |
|---|---|
| author | Chen, Yu Fan Liu, Shih-Yuan Liu, Miao Miller, Justin Lee How, Jonathan P |
| author2 | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics |
| author_facet | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Chen, Yu Fan Liu, Shih-Yuan Liu, Miao Miller, Justin Lee How, Jonathan P |
| author_sort | Chen, Yu Fan |
| collection | MIT |
| description | Many robotic applications require repeated, on-demand motion planning in mapped environments. In addition, the presence of other dynamic agents, such as people, often induces frequent, dynamic changes in the environment. Having a potential function that encodes pairwise cost-to-go can be useful for improving the computational speed of finding feasible paths, and for guiding local searches around dynamic obstacles. However, since storing pairwise potential can be impractical given the O(|V|²) memory requirement, existing work often needs to compute a potential function for each query to a new goal, which would require a substantial online computation. This work addresses the problem by using diffusion maps, a machine learning algorithm, to learn the map's geometry and develop a memory-efficient parametrization (O(|V|)) of pairwise potentials. Specially, each state in the map is transformed to a diffusion coordinate, in which pairwise Euclidean distance is shown to be a meaningful similarity metric. We develop diffusion-based motion planning algorithms and, through extensive numerical evaluation, show that the proposed algorithms find feasible paths of similar quality with orders of magnitude improvement in computational speed compared with single-query methods. The proposed algorithms are implemented on hardware to enable real-time autonomous navigation in an indoor environment with frequent interactions with pedestrians. |
| first_indexed | 2024-09-23T16:11:26Z |
| format | Article |
| id | mit-1721.1/114715 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T16:11:26Z |
| publishDate | 2018 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1147152022-09-29T18:52:34Z Motion planning with diffusion maps Chen, Yu Fan Liu, Shih-Yuan Liu, Miao Miller, Justin Lee How, Jonathan P Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Massachusetts Institute of Technology. Department of Mechanical Engineering Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Chen, Yu Fan Liu, Shih-Yuan Liu, Miao Miller, Justin Lee How, Jonathan P Many robotic applications require repeated, on-demand motion planning in mapped environments. In addition, the presence of other dynamic agents, such as people, often induces frequent, dynamic changes in the environment. Having a potential function that encodes pairwise cost-to-go can be useful for improving the computational speed of finding feasible paths, and for guiding local searches around dynamic obstacles. However, since storing pairwise potential can be impractical given the O(|V|²) memory requirement, existing work often needs to compute a potential function for each query to a new goal, which would require a substantial online computation. This work addresses the problem by using diffusion maps, a machine learning algorithm, to learn the map's geometry and develop a memory-efficient parametrization (O(|V|)) of pairwise potentials. Specially, each state in the map is transformed to a diffusion coordinate, in which pairwise Euclidean distance is shown to be a meaningful similarity metric. We develop diffusion-based motion planning algorithms and, through extensive numerical evaluation, show that the proposed algorithms find feasible paths of similar quality with orders of magnitude improvement in computational speed compared with single-query methods. The proposed algorithms are implemented on hardware to enable real-time autonomous navigation in an indoor environment with frequent interactions with pedestrians. Ford Motor Company 2018-04-13T17:49:17Z 2018-04-13T17:49:17Z 2016-10 2016-10 2018-03-21T17:47:54Z Article http://purl.org/eprint/type/ConferencePaper 978-1-5090-3762-9 978-1-5090-3761-2 978-1-5090-3763-6 2153-0866 http://hdl.handle.net/1721.1/114715 Chen, Yu Fan, Shih-Yuan Liu, Miao Liu, Justin Miller, and Jonathan P. How. “Motion Planning with Diffusion Maps.” 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), October 2016, Daejeon, South Korea, Institute of Electrical and Electronics Engineers (IEEE), 2016. https://orcid.org/0000-0003-3756-3256 https://orcid.org/0000-0002-9838-1221 https://orcid.org/0000-0002-1648-8325 https://orcid.org/0000-0002-4621-2960 https://orcid.org/0000-0001-8576-1930 http://dx.doi.org/10.1109/IROS.2016.7759232 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) MIT Web Domain |
| spellingShingle | Chen, Yu Fan Liu, Shih-Yuan Liu, Miao Miller, Justin Lee How, Jonathan P Motion planning with diffusion maps |
| title | Motion planning with diffusion maps |
| title_full | Motion planning with diffusion maps |
| title_fullStr | Motion planning with diffusion maps |
| title_full_unstemmed | Motion planning with diffusion maps |
| title_short | Motion planning with diffusion maps |
| title_sort | motion planning with diffusion maps |
| url | http://hdl.handle.net/1721.1/114715 https://orcid.org/0000-0003-3756-3256 https://orcid.org/0000-0002-9838-1221 https://orcid.org/0000-0002-1648-8325 https://orcid.org/0000-0002-4621-2960 https://orcid.org/0000-0001-8576-1930 |
| work_keys_str_mv | AT chenyufan motionplanningwithdiffusionmaps AT liushihyuan motionplanningwithdiffusionmaps AT liumiao motionplanningwithdiffusionmaps AT millerjustinlee motionplanningwithdiffusionmaps AT howjonathanp motionplanningwithdiffusionmaps |