Abstract
Task and Motion Planning (TMP) is a fundamental challenge in robotics, requiring the integration of high-level discrete logic with low-level continuous geometric constraints. While practical solvers have proliferated, the field has lacked a definitive theoretical foundation regarding its computational complexity. This paper establishes that TMP is PSPACE-complete when the environment is stratified and accessible—conditions met by most realistic robotic systems. Conversely, the authors prove that without these structural constraints, the general TMP problem is undecidability. By introducing the Continuous Constraint Contract ($C^3$) framework, this work provides a unified mathematical language for TMP and identifies the precise boundary between decidable and undecidable planning problems.
Introduction
Robotic autonomy relies on the synergy between two distinct planning paradigms: Task Planning, which handles high-level symbolic goals (e.g., "assemble the engine"), and Motion Planning, which manages low-level trajectory generation (e.g., "move the end-effector through these coordinates"). While both discrete task planning (such as STRIPS) and continuous motion planning are known to be PSPACE-complete, the complexity of their combination—Task and Motion Planning (TMP)—remained an open question.
Prior to this work, it was unclear whether the hybrid nature of TMP introduced a new layer of exponential complexity or if the problem was even decidable in a general sense. This paper provides a rigorous theoretical foundation, proving that TMP is no harder than its constituent parts, provided the problem space adheres to specific geometric properties.
The Continuous Constraint Contract ($C^3$)
To analyze TMP complexity, the authors introduce the Continuous Constraint Contract ($C^3$) representation. This framework utilizes semialgebraic sets—geometric shapes and constraints defined by finite sets of polynomial equalities and inequalities.
The $C^3$ framework is significant because it provides a universal language to describe both discrete states (e.g., an object being "grasped") and continuous configurations (e.g., joint angles) simultaneously. While real-world robots often involve trigonometric or transcendental functions, the authors demonstrate that these can be approximated by polynomials to any required precision, making the $C^3$ representation applicable to nearly all deterministic robotic systems.
Complexity and Decidability
The paper’s core contribution lies in identifying the "sweet spot" of complexity through two primary mathematical concepts:
- Stratification: This involves partitioning the complex configuration space into simpler "strata" (manifolds). For example, a solid object is decomposed into its interior, its faces, its edges, and its vertices.
- Uniform Stratified Accessibility: This condition ensures that if a robot can reach a specific state, it can also reach all nearby states within that same stratum through small perturbations in its actions.
PSPACE-Completeness
By applying Savitch’s Theorem, the authors develop a recursive decision procedure that decomposes the semialgebraic state space into a finite number of cells. They prove in Theorem 2 that for stratified, accessible environments, TMP is PSPACE-complete. This is a landmark result, as it indicates that the hybrid nature of the problem does not add a new level of computational difficulty beyond what is already present in motion or task planning alone.
The Boundary of Undecidability
Crucially, the authors also explore what happens when these conditions are relaxed. In Theorem 3, they prove that without the "stratified accessibility" condition, TMP becomes undecidable. They demonstrate this by showing that an unstructured TMP problem can be constructed to solve Diophantine equations (Hilbert's 10th problem), which is a known impossible task for any algorithm. This highlights that the "well-behaved" nature of physical environments is not just a convenience, but a mathematical necessity for solvability.
Key Results and Implications
- Theoretical Ceiling: The PSPACE-completeness result provides a theoretical upper bound for the field, suggesting that researchers should focus on heuristics that exploit the stratified nature of configuration spaces.
- Near-Optimality: The authors extend their findings to show that finding a "near-optimal" plan (within a specific cost threshold) is also PSPACE-complete.
- Universal Specification: The $C^3$ framework offers a potential path toward a standardized specification language for TMP benchmarks, allowing for more consistent comparison between different solvers.
Conclusion and Future Work
While the algorithms presented in this paper are theoretical tools designed to prove complexity bounds rather than practical solvers, they clarify the mathematical landscape of robotics. The work confirms that the difficulty of TMP is rooted in the same complexity classes as its components, provided the environment is sufficiently structured.
Future research may build on these findings by extending the $C^3$ framework to stochastic environments or partially observable states. For practitioners, the results reinforce the importance of stratification, suggesting that planners which explicitly respect the geometric boundaries of the environment are more likely to remain computationally tractable.
Summary updated