Sampling-Based Methods for Factored Task and Motion Planning
This work addresses the challenge of efficient planning in robotics for tasks like picking, placing, and pushing, but it is incremental as it builds on existing sampling-based methods with a new theoretical framework.
The paper tackles the problem of solving complex robotic manipulation tasks with many movable objects by formulating them as factored transition systems, and it presents two domain-independent, probabilistically complete planning algorithms that demonstrate empirical efficiency on challenging task and motion planning problems.
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.