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.
- 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.
- Contingent Policy Generation: A Stochastic Shortest Path (SSP) solver generates a tree-structured policy based on this abstraction.
- 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$).
- 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.
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.
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