FFRob: Leveraging symbolic planning for efficient task and motion planning
© 2017, © The Author(s) 2017. Mobile manipulation problems involving many objects are challenging to solve due to the high dimensionality and multi-modality of their hybrid configuration spaces. Planners that perform a purely geometric search are prohibitively slow for solving these problems because...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
SAGE Publications
2021
|
| Online Access: | https://hdl.handle.net/1721.1/134878 |
| _version_ | 1811075747835543552 |
|---|---|
| author | Garrett, Caelan Reed Lozano-Pérez, Tomás Kaelbling, Leslie Pack |
| author_facet | Garrett, Caelan Reed Lozano-Pérez, Tomás Kaelbling, Leslie Pack |
| author_sort | Garrett, Caelan Reed |
| collection | MIT |
| description | © 2017, © The Author(s) 2017. Mobile manipulation problems involving many objects are challenging to solve due to the high dimensionality and multi-modality of their hybrid configuration spaces. Planners that perform a purely geometric search are prohibitively slow for solving these problems because they are unable to factor the configuration space. Symbolic task planners can efficiently construct plans involving many variables but cannot represent the geometric and kinematic constraints required in manipulation. We present the FFRob algorithm for solving task and motion planning problems. First, we introduce extended action specification (EAS) as a general purpose planning representation that supports arbitrary predicates as conditions. We adapt existing heuristic search ideas for solving strips planning problems, particularly delete-relaxations, to solve EAS problem instances. We then apply the EAS representation and planners to manipulation problems resulting in FFRob. FFRob iteratively discretizes task and motion planning problems using batch sampling of manipulation primitives and a multi-query roadmap structure that can be conditionalized to evaluate reachability under different placements of movable objects. This structure enables the EAS planner to efficiently compute heuristics that incorporate geometric and kinematic planning constraints to give a tight estimate of the distance to the goal. Additionally, we show FFRob is probabilistically complete and has a finite expected runtime. Finally, we empirically demonstrate FFRob’s effectiveness on complex and diverse task and motion planning tasks including rearrangement planning and navigation among movable objects. |
| first_indexed | 2024-09-23T10:11:14Z |
| format | Article |
| id | mit-1721.1/134878 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T10:11:14Z |
| publishDate | 2021 |
| publisher | SAGE Publications |
| record_format | dspace |
| spelling | mit-1721.1/1348782021-10-28T04:34:00Z FFRob: Leveraging symbolic planning for efficient task and motion planning Garrett, Caelan Reed Lozano-Pérez, Tomás Kaelbling, Leslie Pack © 2017, © The Author(s) 2017. Mobile manipulation problems involving many objects are challenging to solve due to the high dimensionality and multi-modality of their hybrid configuration spaces. Planners that perform a purely geometric search are prohibitively slow for solving these problems because they are unable to factor the configuration space. Symbolic task planners can efficiently construct plans involving many variables but cannot represent the geometric and kinematic constraints required in manipulation. We present the FFRob algorithm for solving task and motion planning problems. First, we introduce extended action specification (EAS) as a general purpose planning representation that supports arbitrary predicates as conditions. We adapt existing heuristic search ideas for solving strips planning problems, particularly delete-relaxations, to solve EAS problem instances. We then apply the EAS representation and planners to manipulation problems resulting in FFRob. FFRob iteratively discretizes task and motion planning problems using batch sampling of manipulation primitives and a multi-query roadmap structure that can be conditionalized to evaluate reachability under different placements of movable objects. This structure enables the EAS planner to efficiently compute heuristics that incorporate geometric and kinematic planning constraints to give a tight estimate of the distance to the goal. Additionally, we show FFRob is probabilistically complete and has a finite expected runtime. Finally, we empirically demonstrate FFRob’s effectiveness on complex and diverse task and motion planning tasks including rearrangement planning and navigation among movable objects. 2021-10-27T20:09:37Z 2021-10-27T20:09:37Z 2018 2019-06-04T15:12:24Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/134878 en 10.1177/0278364917739114 International Journal of Robotics Research Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf SAGE Publications arXiv |
| spellingShingle | Garrett, Caelan Reed Lozano-Pérez, Tomás Kaelbling, Leslie Pack FFRob: Leveraging symbolic planning for efficient task and motion planning |
| title | FFRob: Leveraging symbolic planning for efficient task and motion planning |
| title_full | FFRob: Leveraging symbolic planning for efficient task and motion planning |
| title_fullStr | FFRob: Leveraging symbolic planning for efficient task and motion planning |
| title_full_unstemmed | FFRob: Leveraging symbolic planning for efficient task and motion planning |
| title_short | FFRob: Leveraging symbolic planning for efficient task and motion planning |
| title_sort | ffrob leveraging symbolic planning for efficient task and motion planning |
| url | https://hdl.handle.net/1721.1/134878 |
| work_keys_str_mv | AT garrettcaelanreed ffrobleveragingsymbolicplanningforefficienttaskandmotionplanning AT lozanopereztomas ffrobleveragingsymbolicplanningforefficienttaskandmotionplanning AT kaelblinglesliepack ffrobleveragingsymbolicplanningforefficienttaskandmotionplanning |