Authors: Caelan Garrett, Tomas Lozano-Perez, Leslie Kaelbling
There has been a great deal of progress in developing probabilistically complete methods that move beyond motion planning to multi-modal problems including various forms of task planning. This paper presents a general-purpose formulation of a large class of discrete-time planning problems, with continuous or hybrid state and action spaces. The formulation characterizes conditions on the submanifolds in which solutions lie and connects those conditions to conditional samplers that must be provided as part of a problem specification and to a general charac- terization of robust feasibility. We present domain-independent sample-based planning algorithms and show that they are both probabilistically complete and computationally efficient on a set of challenging benchmark problems.