Efficiency and Abstraction in Task and Motion Planning




Nick Roy
AeroAstro / CSAIL
Thesis title: Efficiency and Abstraction in Task and Motion Planning
By: William Vega-Brown
Date: December 4, 2019
Time: 1:00 PM EST
Location: 3-133

Modern robots are capable of complex and highly dynamic behaviors, yet the decision-making algorithms that drive them struggle to solve problems involving complex behaviors like manipulation. The combination of continuous and discrete dynamics involved in contact creates severe computational challenges, and while there has been significant recent progress in overcoming this computational intractability, most known approaches rely on hand-specified symbolic representations to ensure computational tractability and do not make any guarantees about the quality of plans returned. Because these symbolic model representations cannot easily be verified, many planning systems are brittle and prone to failure when the robot encounters situations not anticipated by the model designer.

This thesis addresses the limitations of conventional representations for task and motion planning by introducing a representation that explicitly places continuous and discrete dynamics on equal footing. We argue that the challenges in modelling problems with both discrete and continuous dynamics can be reduced to a trade-off between model complexity and empirical accuracy. We propose the use of abstraction to combine models that balance those two constraints differently, and we claim that by using abstraction we can build systems that reliably generate high-quality plans, even in complex domains with many objects.

We also use our representation as a theoretical framework to resolve long-standing open problems about the decidability and complexity of motion planning. We introduce the first known algorithms for complete or asymptotically optimal planning in hybrid domains, and we show that the reachability problem for dynamical systems is decidable only if those systems are compatible with a certain kind of symbolic structure, in which case the problem is in PSPACE. This proves the long-held conjecture that task and motion planning is PSPACE-complete.

Committee Members:
Nicholas Roy, Professor of Aeronautics and Astronautics (Supervisor)
John Leonard, Professor of Mechanical Engineering (Committee Chair)
Leslie Pack Kaelbling, Professor of Electrical Engineering and Computer Science
Alberto Rodriguez, Associate Professor of Mechanical Engineering
Daniel Koditschek, Professor of Electrical and Systems Engineering, University of Pennsylvania
Marc Toussaint, Professor of Computer Science, University of Stuttgart