TL;DR
This paper tackles the complex challenge of planning in real-world scenarios where actions take time (durative), can happen simultaneously (concurrent), and have uncertain outcomes and durations. The authors introduce a unified framework and algorithms that can handle these complexities, enabling more realistic and efficient planning for applications like robotics.
What Problem Does This Paper Address?
Traditional AI planning often assumes actions are instantaneous and executed one after another. However, many real-world problems, like controlling a Mars rover, involve actions that take time (e.g., moving, calibrating instruments), can occur at the same time (e.g., taking pictures while transmitting data), and have uncertain outcomes or durations (e.g., a movement might take longer than expected). These assumptions severely limit the applicability of classical planners. This paper aims to bridge this gap by developing a planning framework that explicitly models and efficiently solves problems with concurrent, durative actions in stochastic environments.
Methods
The core of the paper lies in extending the standard Markov Decision Process (MDP) framework.
- Concurrent MDPs (CoMDPs): The authors introduce CoMDPs, which allow multiple actions to be executed in parallel within a single decision epoch. This is achieved by treating combinations of actions as single operators.
- Interwoven and Aligned Epochs: To handle durative actions, two state-space formulations are proposed:
- Aligned Epochs: A simpler, faster approach where decisions are made only after all currently executing actions have completed. This is an approximation.
- Interwoven Epochs: A more complex but exact formulation that considers actions midway through their execution, leading to a larger state space.
- Algorithms (The "DUR" Family): To combat the computational explosion caused by these extensions, several algorithms are developed:
- Pruning: Techniques like "combo-skipping" and "combo-elimination" are used to remove provably suboptimal action combinations, reducing the search space.
- Sampling: "Sampled RTDP" explores a subset of action combinations, significantly speeding up the process while aiming for near-optimal solutions.
- Heuristics: "Maximum Concurrency" (admissible) and "Average Concurrency" (inadmissible but often more informed) heuristics are introduced to guide the search.
- Hybridization: A "hybridized planner" (DURhyb) combines the strengths of fast but suboptimal aligned-epoch planning with the slower but optimal interwoven-epoch planning.
- Stochastic Durations: Extensions are made to handle uncertain action durations, including expected-duration and archetypal-duration planners.
Datasets
The authors evaluate their algorithms on several benchmark domains:
- NASA Rover Domain: A probabilistic variant of a domain used in planning competitions, involving object photography, rock testing, and data communication.
- Machineshop Domain: A probabilistic version involving multiple subtasks (rolling, shaping, painting, etc.) performed on different objects using various machines.
- Artificial Domain: A custom domain designed to test specific aspects of concurrency and parallelism, similar to the example in Figure 1.
These domains were modified to include action durations and stochasticity.
Key Insights and Ideas
- Concurrency is a Major Bottleneck: The number of possible concurrent action combinations grows exponentially, making naive MDP solutions intractable. This necessitates specialized pruning and sampling techniques.
- Durative Actions Create Complex State Spaces: Modeling actions that take time requires tracking not just the current state but also which actions are in progress and how much time they have left. This significantly expands the state space.
- Trade-offs are Inevitable: There's a fundamental trade-off between solution quality (optimality) and computation time. Algorithms like sampled RTDP offer dramatic speedups at the cost of near-optimality, while others like pruned RTDP are slower but guarantee optimality.
- Hybridization is Powerful: Combining fast, approximate methods with slower, more accurate ones can yield efficient algorithms that produce high-quality solutions quickly.
- Heuristics are Crucial: Well-designed heuristics can dramatically speed up planning by guiding the search towards promising states and actions.
Key Results
- Significant Speedups: Pruning and sampling techniques (especially sampled RTDP) achieved dramatic improvements in running times, often orders of magnitude faster than unpruned methods.
- Near-Optimal Solutions: Sampled RTDP and hybridized algorithms produced solutions that were very close to optimal, with errors typically less than 1%.
- Scalability: The proposed algorithms, particularly sampled RTDP and the hybridized planner, demonstrated better scalability to larger and more concurrent problems compared to traditional methods. For instance, in the Artificial domain, only the hybridized and aligned-epoch planners could solve the largest problems.
- Impact of Concurrency: The experiments showed that as the degree of parallelism (concurrency) increased, the performance gap between efficient (sampled, hybridized) and less efficient (unpruned) algorithms widened considerably.
Limitations and Future Work
- Incompleteness of State-Space Planners: The paper proves that standard state-space temporal planners are incomplete for expressive action models like PDDL2.1, which has implications for future research.
- Multi-modal Durations are Challenging: While the paper extends to stochastic durations, multi-modal distributions (where an action might have distinct, common durations) significantly complicate the problem by creating many critical decision points (pivots). This makes optimal planning intractable for large problems.
- Future Work: The authors suggest several avenues for future research:
- Exploring other objective functions beyond make-span (e.g., mixed cost optimization, resource usage).
- Handling infinite horizon problems and continuous-valued duration distributions.
- Investigating more expressive action models and interruptible actions.
- Developing methods to aggregate states to handle the "curse of large durations" more efficiently.
- Extending the work to incorporate notions of goal satisfaction beyond simply reaching a state.
Summary updated