Although recent advances have improved the space of tasks a robot can address, robots still struggle with complicated tasks involving long sequences of actions. For example, a robot tasked with cleaning a room must decide both what objects to grab and in which order, as well as how to grasp them and where to place them. The combination of geometric constraints—where to place objects and how to move them—with combinatorial complexity—which objects to move and in which order—creates enormous practical and computational challenges. Problems like this, known as task and motion planning problems, cannot be directly solved using conventional motion planning or task planning techniques.
We showed that a broad class of task and motion planning problems—those with piecewise-analytic constraints—can be solved using a domain-independent planner. Our planner is probabilistically complete and asymptotically optimal; to our knowledge, it is the first planner with these properties capable of addressing such a broad family of problems. We have also shown a generalization to stochastic planning problems. Although our planner works well for small problems, it scales very poorly with problem size. This work suggests that the fundamental challenge for these problems is computational, and that the task planner is essential only for its computational efficiency.
We argue that abstraction is the key to making planning tractable in practice. If we can construct and solve a high-level approximation of a problem, we can use that approximate solution to guide the search for a solution to the underlying problem. We have adopted angelic semantics as a language for describing abstraction, and have presented an admissibility condition for angelic abstractions that allows us to accelerate planning while preserving the ability to find the optimal primitive motion plan. We have demonstrated this approach on a legged manipulator in both known and partially-known environments.
In our ongoing work, we are simplifying the process of synthesizing abstractions and specifying problems, with an aim to use machine learning to take planning and control beyond the bounds of what we can hand-engineer. We are also working to apply our abstraction techniques to nondeterministic, partially-observable, or multi-agent domains.