Sampling-based methods for factored task and motion planning
Abstract
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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Oct 10, 2018
- Source ID
- 10.1177/0278364918802962
Entities
People
- Caelan Reed Garrett
- Leslie P. Kaelbling
- Tomas Lozano-Pérez
Organizations
- Air Force Office of Scientific Research
- Massachusetts Institute of Technology
- National Science Foundation
- Office of Naval Research