Task and Motion Planning Is PSPACE-Complete

Authors

  • William Vega-Brown MIT
  • Nicholas Roy MIT

DOI:

https://doi.org/10.1609/aaai.v34i06.6607

Abstract

We present a new representation for task and motion planning that uses constraints to capture both continuous and discrete phenomena in a unified framework. We show that we can decide if a feasible plan exists for a given problem instance using only polynomial space if the constraints are semialgebraic and all actions have uniform stratified accessibility, a technical condition closely related to both controllability and to the existence of a symbolic representation of a planning domain. We show that there cannot exist an algorithm that solves the more general problem of deciding if a plan exists for an instance with arbitrary semialgebraic constraints. Finally, we show that our formalism is universal, in the sense that every deterministic robotic planning problem can be well-approximated within our formalism. Together, these results imply task and motion planning is PSPACE-complete.

Downloads

Published

2020-04-03

How to Cite

Vega-Brown, W., & Roy, N. (2020). Task and Motion Planning Is PSPACE-Complete. Proceedings of the AAAI Conference on Artificial Intelligence, 34(06), 10385-10392. https://doi.org/10.1609/aaai.v34i06.6607

Issue

Section

AAAI Technical Track: Robotics