An Anytime Algorithm for Task and Motion MDPs

Siddharth Srivastava, Nishant Desai, Richard G. Freedman, Shlomo ZilbersteinarXiv 2018 · OpenReview

Abstract

Integrated task and motion planning (TAMP) is a critical challenge in robotics, requiring a system to bridge high-level strategic decisions with low-level physical constraints. While most TAMP research focuses on deterministic environments, real-world scenarios are inherently stochastic. We present the Anytime Task and Motion MDP (ATM-MDP) algorithm, which models the high-level decision problem as a Markov Decision Process (MDP). Unlike previous methods, ATM-MDP generates contingent behaviors in an anytime fashion, prioritizing the most likely execution-time outcomes. Our approach is evaluated on a realistic autonomous aircraft inspection task, demonstrating that consistent policies can be computed using only a fraction of the time required for exhaustive planning.

The Challenge of Stochastic TAMP

For autonomous robots to operate effectively, they must translate abstract commands—such as "inspect the left wing"—into feasible physical trajectories while accounting for uncertainty. Sensors may fail, actuators may drift, and environmental conditions can change unexpectedly.

Modeling these problems as MDPs allows for robust decision-making under uncertainty. However, the hybrid nature of TAMP leads to a state-space explosion. Computing a valid motion plan for every possible stochastic outcome is often computationally prohibitive. The core bottleneck is efficiency: how can a robot generate a useful policy without waiting hours to account for every low-probability edge case?

The ATM-MDP Algorithm

The ATM-MDP algorithm addresses this by factoring the problem into a high-level discrete solver and a low-level continuous motion planner, refined through an anytime process.

  1. Optimistic Abstraction: The high-level MDP initially ignores complex continuous constraints (like precise battery consumption or collision-free paths), assuming actions will succeed until proven otherwise.
  2. Contingent Policy Generation: A Stochastic Shortest Path (SSP) solver generates a tree-structured policy based on this abstraction.
  3. Prioritized Refinement: This is the algorithm's key innovation. Instead of refining the entire tree, it prioritizes paths based on the ratio of their probability of occurrence ($p$) to the estimated cost of computing their motion plans ($c$).
  4. Feedback and Replanning: A motion planner (such as RRT) attempts to validate the abstract actions. If a plan fails (e.g., a path is blocked), the failure reason is fed back to the MDP, which updates its model and replans locally rather than backtracking globally.

Experimental Evaluation: Aircraft Inspection

To test the algorithm, we developed a 3D hangar environment where a UAV is tasked with inspecting various components of an aircraft. The robot must manage its battery life, return to docking stations, and handle stochastic sensor failures.

The autonomous aircraft inspection scenario modeled in OpenRAVE, featuring a UAV navigating a hangar to inspect specific aircraft components.

This scenario provides a complex testbed where high-level task sequences (which components to visit) are tightly coupled with low-level motion constraints (avoiding the aircraft fuselage and managing energy).

Key Results and Anytime Performance

The ATM-MDP algorithm exhibits a "concave" anytime performance profile, meaning it secures high coverage of the most likely outcomes very early in the computation process.

  • Efficiency: In low-noise scenarios (5% error), the algorithm covers 90% of all possible execution outcomes in under 10 seconds, utilizing only 10% of the time needed for an exhaustive solution.
  • Robustness: In high-noise environments (20% error), it still achieves 80% coverage using just 40% of the total computation time.
Anytime performance plots showing the "mass refined" (probability of covered outcomes) versus the percentage of nodes refined across different noise levels.

These results suggest that robots do not need a 100% complete policy to begin acting safely. By focusing on high-probability trajectories, the robot can start its mission quickly and handle rare edge cases by pausing to compute or failing safely if they occur.

Conclusion and Future Work

ATM-MDP provides a scalable framework for integrated task and motion planning in stochastic settings. By leveraging optimism and prioritized refinement, it bridges the gap between long-horizon strategic planning and short-horizon continuous control. Future work may involve integrating this hierarchical approach with Deep Reinforcement Learning, using DRL for low-level maneuver learning while maintaining the ATM-MDP structure for high-level task coordination.

Summary updated

Abstract

Integrated task and motion planning has emerged as a challenging problem in sequential decision making, where a robot needs to compute high-level strategy and low-level motion plans for solving complex tasks. While high-level strategies require decision making over longer time-horizons and scales, their feasibility depends on low-level constraints based upon the geometries and continuous dynamics of the environment. The hybrid nature of this problem makes it difficult to scale; most existing approaches focus on deterministic, fully observable scenarios. We present a new approach where the high-level decision problem occurs in a stochastic setting and can be modeled as a Markov decision process. In contrast to prior efforts, we show that complete MDP policies, or contingent behaviors, can be computed effectively in an anytime fashion. Our algorithm continuously improves the quality of the solution and is guaranteed to be probabilistically complete. We evaluate the performance of our approach on a challenging, realistic test problem: autonomous aircraft inspection. Our results show that we can effectively compute consistent task and motion policies for the most likely execution-time outcomes using only a fraction of the computation required to develop the complete task and motion policy.
BibTeX
@misc{srivastava2018anytime,
  author = {Siddharth Srivastava and Nishant Desai and Richard G. Freedman and Shlomo Zilberstein},
  title = {{An Anytime Algorithm for Task and Motion MDPs}},
  year = {2018},
  eprint = {1802.05835},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1802.05835},
}
Figure