Sampling-based methods for factored task and motion planning
This paper presents a general-purpose formulation of a large class of discrete-time planning problems, with hybrid state and control-spaces, as factored transition systems. Factoring allows state transitions to be described as the intersection of several constraints each affecting a subset of the st...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
SAGE Publications
2020
|
| Online Access: | https://hdl.handle.net/1721.1/124490 |
| _version_ | 1826206687166464000 |
|---|---|
| author | Garrett, Caelan Reed Lozano-Pérez, Tomás 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-Pérez, Tomás Kaelbling, Leslie P |
| author_sort | Garrett, Caelan Reed |
| collection | MIT |
| description | This paper presents a general-purpose formulation of a large class of discrete-time planning problems, with hybrid state and control-spaces, as factored transition systems. Factoring allows state transitions to be described as the intersection of several constraints each affecting a subset of the state and control variables. Robotic manipulation problems with many movable objects involve constraints that only affect several variables at a time and therefore exhibit large amounts of factoring. We develop a theoretical framework for solving factored transition systems with sampling-based algorithms. The framework characterizes conditions on the submanifold in which solutions lie, leading to a characterization of robust feasibility that incorporates dimensionality-reducing constraints. It then connects those conditions to corresponding conditional samplers that can be composed to produce values on this submanifold. We present two domain-independent, probabilistically complete planning algorithms that take, as input, a set of conditional samplers. We demonstrate the empirical efficiency of these algorithms on a set of challenging task and motion planning problems involving picking, placing, and pushing. Keywords: task and motion planning; manipulation planning; AI reasoning |
| first_indexed | 2024-09-23T13:36:41Z |
| format | Article |
| id | mit-1721.1/124490 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:36:41Z |
| publishDate | 2020 |
| publisher | SAGE Publications |
| record_format | dspace |
| spelling | mit-1721.1/1244902022-09-28T15:02:11Z Sampling-based methods for factored task and motion planning Garrett, Caelan Reed Lozano-Pérez, Tomás Kaelbling, Leslie P Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory This paper presents a general-purpose formulation of a large class of discrete-time planning problems, with hybrid state and control-spaces, as factored transition systems. Factoring allows state transitions to be described as the intersection of several constraints each affecting a subset of the state and control variables. Robotic manipulation problems with many movable objects involve constraints that only affect several variables at a time and therefore exhibit large amounts of factoring. We develop a theoretical framework for solving factored transition systems with sampling-based algorithms. The framework characterizes conditions on the submanifold in which solutions lie, leading to a characterization of robust feasibility that incorporates dimensionality-reducing constraints. It then connects those conditions to corresponding conditional samplers that can be composed to produce values on this submanifold. We present two domain-independent, probabilistically complete planning algorithms that take, as input, a set of conditional samplers. We demonstrate the empirical efficiency of these algorithms on a set of challenging task and motion planning problems involving picking, placing, and pushing. Keywords: task and motion planning; manipulation planning; AI reasoning NSF (Grants 1420316, 1523767, and 1723381) AFOSR (Grant FA9550-17-1-0165) ONR (Grant N00014-14-1-0486) 2020-04-06T14:34:53Z 2020-04-06T14:34:53Z 2018-10-10 2019-06-04T15:08:50Z Article http://purl.org/eprint/type/JournalArticle 0278-3649 1741-3176 https://hdl.handle.net/1721.1/124490 Garrett, Caelan Reed, Lozano-Pérez, Tomás and Kaelbling, Leslie Pack. "Sampling-based methods for factored task and motion planning." International Journal of Robotics Research 37, 13/14 (December 2018): 1796-1825 © The Author(s) 2018. en http://dx.doi.org/10.1177/0278364918802962 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 P Sampling-based methods for factored task and motion planning |
| title | Sampling-based methods for factored task and motion planning |
| title_full | Sampling-based methods for factored task and motion planning |
| title_fullStr | Sampling-based methods for factored task and motion planning |
| title_full_unstemmed | Sampling-based methods for factored task and motion planning |
| title_short | Sampling-based methods for factored task and motion planning |
| title_sort | sampling based methods for factored task and motion planning |
| url | https://hdl.handle.net/1721.1/124490 |
| work_keys_str_mv | AT garrettcaelanreed samplingbasedmethodsforfactoredtaskandmotionplanning AT lozanopereztomas samplingbasedmethodsforfactoredtaskandmotionplanning AT kaelblinglesliep samplingbasedmethodsforfactoredtaskandmotionplanning |