Task and Motion Planning Is PSPACE-Complete
Authors: William Vega-Brown, Nicholas Roy10385-10392
AAAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. |
| Researcher Affiliation | Academia | William Vega-Brown, Nicholas Roy CSAIL, MIT 32 Vassar Street, 32-33x Cambridge, Massachusetts 02139 {wrvb,nickroy}@csail.mit.edu |
| Pseudocode | Yes | Algorithm 1 An algorithm to enumerate reachable subsets in semialgebraic C3. Algorithm 2 An algorithm for determining plan existence. |
| Open Source Code | No | The paper does not contain any statements about releasing code, nor does it provide links to source code repositories. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments on datasets, thus no dataset access information for training is provided. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments with dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe any specific hardware used for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not list specific software dependencies with version numbers for implementation. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup, hyperparameters, or training configurations. |