Admissible Abstractions for Near-optimal Task and Motion Planning
We define an admissibility condition for abstractions expressed using angelic semantics and show that these conditions allow us to accelerate planning while preserving the ability to find the optimal motion plan. We then derive admissible abstractions for two motion planning domains with continuous...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
International Joint Conferences on Artificial Intelligence Organization
2020
|
| Online Access: | https://hdl.handle.net/1721.1/125863 |
| _version_ | 1826200770270199808 |
|---|---|
| author | Vega-Brown, William R Roy, Nicholas |
| author2 | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics |
| author_facet | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Vega-Brown, William R Roy, Nicholas |
| author_sort | Vega-Brown, William R |
| collection | MIT |
| description | We define an admissibility condition for abstractions expressed using angelic semantics and show that these conditions allow us to accelerate planning while preserving the ability to find the optimal motion plan. We then derive admissible abstractions for two motion planning domains with continuous state. We extract upper and lower bounds on the cost of concrete motion plans using local metric and topological properties of the problem domain. These bounds guide the search for a plan while maintaining performance guarantees. We show that abstraction can dramatically reduce the complexity of search relative to a direct motion planner. Using our abstractions, we find near-optimal motion plans in planning problems involving 1013 states without using a separate task planner. |
| first_indexed | 2024-09-23T11:41:11Z |
| format | Article |
| id | mit-1721.1/125863 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:41:11Z |
| publishDate | 2020 |
| publisher | International Joint Conferences on Artificial Intelligence Organization |
| record_format | dspace |
| spelling | mit-1721.1/1258632022-10-01T05:18:03Z Admissible Abstractions for Near-optimal Task and Motion Planning Vega-Brown, William R Roy, Nicholas Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory We define an admissibility condition for abstractions expressed using angelic semantics and show that these conditions allow us to accelerate planning while preserving the ability to find the optimal motion plan. We then derive admissible abstractions for two motion planning domains with continuous state. We extract upper and lower bounds on the cost of concrete motion plans using local metric and topological properties of the problem domain. These bounds guide the search for a plan while maintaining performance guarantees. We show that abstraction can dramatically reduce the complexity of search relative to a direct motion planner. Using our abstractions, we find near-optimal motion plans in planning problems involving 1013 states without using a separate task planner. 2020-06-18T14:37:51Z 2020-06-18T14:37:51Z 2018-07 2019-10-31T12:59:33Z Article http://purl.org/eprint/type/ConferencePaper 9780999241127 https://hdl.handle.net/1721.1/125863 Vega-Brown, William and Nicholas Roy. "Admissible Abstractions for Near-optimal Task and Motion Planning." Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, July 2018, Stockholm, Sweden, International Joint Conferences on Artificial Intelligence Organization, July 2018 © 2018 International Joint Conferences on Artificial Intelligence en http://dx.doi.org/10.24963/ijcai.2018/674 Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf International Joint Conferences on Artificial Intelligence Organization arXiv |
| spellingShingle | Vega-Brown, William R Roy, Nicholas Admissible Abstractions for Near-optimal Task and Motion Planning |
| title | Admissible Abstractions for Near-optimal Task and Motion Planning |
| title_full | Admissible Abstractions for Near-optimal Task and Motion Planning |
| title_fullStr | Admissible Abstractions for Near-optimal Task and Motion Planning |
| title_full_unstemmed | Admissible Abstractions for Near-optimal Task and Motion Planning |
| title_short | Admissible Abstractions for Near-optimal Task and Motion Planning |
| title_sort | admissible abstractions for near optimal task and motion planning |
| url | https://hdl.handle.net/1721.1/125863 |
| work_keys_str_mv | AT vegabrownwilliamr admissibleabstractionsfornearoptimaltaskandmotionplanning AT roynicholas admissibleabstractionsfornearoptimaltaskandmotionplanning |