This paper presents a general-purpose formulation of a large class ofdiscrete-time planning problems, with hybrid state and control-spaces, asfactored transition systems. Factoring allows state transitions to be describedas the intersection of several constraints each affecting a subset of the stateand control variables. Robotic manipulation problems with many movable objectsinvolve constraints that only affect several variables at a time and thereforeexhibit large amounts of factoring. We develop a theoretical framework forsolving factored transition systems with sampling-based algorithms. Theframework characterizes conditions on the submanifold in which solutions lie,leading to a characterization of robust feasibility that incorporatesdimensionality-reducing constraints. It then connects those conditions tocorresponding conditional samplers that can be composed to produce values onthis submanifold. We present two domain-independent, probabilistically completeplanning algorithms that take, as input, a set of conditional samplers. Wedemonstrate the empirical efficiency of these algorithms on a set ofchallenging task and motion planning problems involving picking, placing, andpushing.
展开▼
