Abstract
Automated planning often assumes fixed action durations, a simplification that fails in real-world scenarios like space exploration or manufacturing. This paper addresses the complexity of concurrent actions with stochastic durations by introducing the $\Delta\text{DUR}$ family of algorithms. These methods leverage a Concurrent Markov Decision Process (CoMDP) model and various approximation strategies to achieve significant computational speedups while maintaining high solution quality.
Introduction
Classical planners typically operate under the assumption of deterministic action durations. However, in domains such as the NASA Rover or industrial machine shops, durations are inherently uncertain and often follow complex probability distributions. When multiple such actions occur concurrently, the state space expands exponentially, making optimal planning computationally prohibitive. This research explores the "double whammy" of concurrency and stochastic durations, proposing algorithms that balance optimality with practical execution time.
Methodology
The authors model the planning problem as a Concurrent Markov Decision Process (CoMDP) within an interwoven epoch search space. This approach tracks world states alongside the execution status and elapsed time of active actions. Five algorithms are proposed under the $\Delta\text{DUR}$ (Delta-Duration) framework:
- $\Delta\text{DUR}_{\text{prun}}$: An optimal planner utilizing pruned Real-Time Dynamic Programming (RTDP).
- $\Delta\text{DUR}_{\text{samp}}$: A faster variant using sampled RTDP to explore the state space.
- $\Delta\text{DUR}_{\text{hyb}}$: A hybrid approach that iteratively improves sub-optimal solutions toward optimality.
- $\Delta\text{DUR}_{\text{arch}}$: Optimized for multi-modal distributions by selecting representative duration "modes."
- $\Delta\text{DUR}_{\text{exp}}$: A high-speed approximation that treats durations as their expected values and employs a re-planning loop to handle deviations.
Experimental Results
The algorithms were evaluated across three domains: a probabilistic NASA Rover domain, a Machine-Shop with multi-modal durations, and a custom Artificial benchmark designed to test high degrees of parallelism. The largest problems tested involved up to 4 million world states.
Computational Efficiency
The $\Delta\text{DUR}_{\text{exp}}$ algorithm demonstrated exceptional performance, often outperforming the optimal $\Delta\text{DUR}_{\text{prun}}$ by orders of magnitude in planning time. This efficiency stems from its ability to treat complex probabilistic problems as a series of simpler deterministic ones.
Solution Quality
Despite the aggressive approximations used in the faster algorithms, the quality of the resulting plans remained high. The average make-span for $\Delta\text{DUR}_{\text{exp}}$ was consistently close to the optimal values, with plans rarely exceeding optimal lengths by more than 35%.
Conclusion
This work demonstrates that handling concurrent actions with uncertain durations is feasible even for large state spaces. The $\Delta\text{DUR}_{\text{exp}}$ algorithm, in particular, offers a powerful trade-off, providing near-optimal plans with minimal computational overhead through the use of expected values and re-planning. Future work aims to extend these techniques to continuous duration distributions and more expressive action languages.
Summary updated