FFRob: An Efficient Heuristic for Task and Motion Planning
Manipulation problemsinvolvingmany objects present substantial challenges for motion planning algorithms due to the high dimensionality and multi-modality of the search space. Symbolic task planners can efficiently construct plans involving many entities but cannot incorporate the constraints from g...
Main Authors: | , , |
---|---|
Other Authors: | |
Format: | Article |
Language: | en_US |
Published: |
Springer Cham
2017
|
Online Access: | http://hdl.handle.net/1721.1/112348 https://orcid.org/0000-0002-6474-1276 https://orcid.org/0000-0002-8657-2450 https://orcid.org/0000-0001-6054-7145 |
_version_ | 1811087497823780864 |
---|---|
author | Garrett, Caelan Reed Lozano-Perez, Tomas Kaelbling, Leslie P |
author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Garrett, Caelan Reed Lozano-Perez, Tomas Kaelbling, Leslie P |
author_sort | Garrett, Caelan Reed |
collection | MIT |
description | Manipulation problemsinvolvingmany objects present substantial challenges for motion planning algorithms due to the high dimensionality and multi-modality of the search space. Symbolic task planners can efficiently construct plans involving many entities but cannot incorporate the constraints from geometry and kinematics. In this paper, we show how to extend the heuristic ideas from one of the most successful symbolic planners in recent years, the FastForward (FF) planner, to motion planning, and to compute it efficiently. We use a multi-query roadmap structure that can be conditionalized to model different placements of movable objects. The resulting tightly integrated planner is simple and performs efficiently in a collection of tasks involving manipulation of many objects. |
first_indexed | 2024-09-23T13:46:45Z |
format | Article |
id | mit-1721.1/112348 |
institution | Massachusetts Institute of Technology |
language | en_US |
last_indexed | 2024-09-23T13:46:45Z |
publishDate | 2017 |
publisher | Springer Cham |
record_format | dspace |
spelling | mit-1721.1/1123482022-09-28T16:08:44Z FFRob: An Efficient Heuristic for Task and Motion Planning Garrett, Caelan Reed Lozano-Perez, Tomas Kaelbling, Leslie P Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Garrett, Caelan Reed Lozano-Perez, Tomas Kaelbling, Leslie P Manipulation problemsinvolvingmany objects present substantial challenges for motion planning algorithms due to the high dimensionality and multi-modality of the search space. Symbolic task planners can efficiently construct plans involving many entities but cannot incorporate the constraints from geometry and kinematics. In this paper, we show how to extend the heuristic ideas from one of the most successful symbolic planners in recent years, the FastForward (FF) planner, to motion planning, and to compute it efficiently. We use a multi-query roadmap structure that can be conditionalized to model different placements of movable objects. The resulting tightly integrated planner is simple and performs efficiently in a collection of tasks involving manipulation of many objects. National Science Foundation (U.S.) (Grant No. 019868) United States. Office of Naval Research. Multidisciplinary University Research Initiative (grant N00014-09-1-1051) United States. Air Force. Office of Scientific Research (grant AOARD-104135) Singapore. Ministry of Education 2017-12-01T22:22:26Z 2017-12-01T22:22:26Z 2015-04 Article http://purl.org/eprint/type/ConferencePaper 978-3-319-16594-3 978-3-319-16595-0 1610-7438 1610-742X http://hdl.handle.net/1721.1/112348 Garrett, Caelan Reed, et al. “FFRob: An Efficient Heuristic for Task and Motion Planning.” Algorithmic Foundations of Robotics XI, edited by H. Levent Akin et al., vol. 107, Springer International Publishing, 2015, pp. 179–95. https://orcid.org/0000-0002-6474-1276 https://orcid.org/0000-0002-8657-2450 https://orcid.org/0000-0001-6054-7145 en_US http://dx.doi.org/10.1007/978-3-319-16595-0_11 Algorithmic Foundations of Robotics XI Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer Cham MIT Web Domain |
spellingShingle | Garrett, Caelan Reed Lozano-Perez, Tomas Kaelbling, Leslie P FFRob: An Efficient Heuristic for Task and Motion Planning |
title | FFRob: An Efficient Heuristic for Task and Motion Planning |
title_full | FFRob: An Efficient Heuristic for Task and Motion Planning |
title_fullStr | FFRob: An Efficient Heuristic for Task and Motion Planning |
title_full_unstemmed | FFRob: An Efficient Heuristic for Task and Motion Planning |
title_short | FFRob: An Efficient Heuristic for Task and Motion Planning |
title_sort | ffrob an efficient heuristic for task and motion planning |
url | http://hdl.handle.net/1721.1/112348 https://orcid.org/0000-0002-6474-1276 https://orcid.org/0000-0002-8657-2450 https://orcid.org/0000-0001-6054-7145 |
work_keys_str_mv | AT garrettcaelanreed ffrobanefficientheuristicfortaskandmotionplanning AT lozanopereztomas ffrobanefficientheuristicfortaskandmotionplanning AT kaelblinglesliep ffrobanefficientheuristicfortaskandmotionplanning |