Abstract
In automated planning, determining the probability of meeting a deadline is critical for reliable execution. However, calculating this probability in Hierarchical Task Networks (HTNs) with stochastic task durations is computationally intensive. This paper demonstrates that exact calculation is NP-hard and proposes a polynomial-time approximation scheme (PTAS). By utilizing a novel "Trim" operator to manage probability distributions, the proposed algorithm maintains bounded error while significantly reducing computation time compared to exact and sampling-based methods.
Introduction
Real-world task durations are rarely fixed; they are stochastic. In Hierarchical Task Networks (HTNs), complex goals are represented as trees of sub-tasks that can be executed in sequence or in parallel. The core challenge is determining the probability $P(t \leq T)$—the chance that the total time $t$ taken by the plan will meet a deadline $T$.
While calculating this for parallel tasks is relatively straightforward (it is the product of their individual success probabilities), sequential tasks require a "convolution" of their probability distributions. As more tasks are added, the number of possible outcomes grows exponentially, making exact calculation impossible for large plans. The authors establish that even for a single sequence of independent random variables, deciding if the success probability exceeds a threshold is NP-hard via a reduction from the SubsetSum problem.
The Network Algorithm and Trim Operator
To address this complexity, the authors propose a deterministic approximation algorithm called Network. The algorithm traverses the plan tree from the leaves up, handling leaf nodes, sequence nodes, and parallel nodes recursively. The "secret sauce" of this algorithm is the Trim operator.
To prevent the exponential explosion of the probability distribution, the algorithm "trims" the distribution after every sequence operation. It merges consecutive values whose cumulative probability is less than a small error parameter $\epsilon$. This keeps the "support" (the number of possible values in the distribution) bounded by $1/\epsilon$. The authors provide a formal proof that the error introduced by trimming accumulates linearly, allowing them to provide a guaranteed "additive error" bound for the entire plan.
Experimental Evaluation
The authors evaluated their approach using three types of task trees: DRC Drive (DARPA Robotics Challenge simulation plans), Linear Plans (Seq), and a Logistics Domain (JSHOP2 generated plans). Primitive task durations were modeled as uniform distributions discretized to $M$ values.
As shown in the table above, the approximation algorithm demonstrates significant scalability advantages. On large plans (e.g., Logistics domain with $N=45$ and $M=10$), the exact algorithm timed out after 4 hours, while the approximation algorithm finished in roughly 2.19 seconds with an error bound of 0.1.
Key Results and Insights
- Deterministic vs. Stochastic: Unlike Monte Carlo sampling, which gives a result that is only "probably" correct, this approximation scheme provides a guaranteed error bound. Users know for certain that the true probability lies within a specific range.
- Efficiency Trade-off: The Trim operator allows a direct trade-off between runtime and precision. By adjusting $\epsilon$, users can obtain a quick estimate or a highly accurate calculation.
- Superiority over Sampling: While sampling is fast, its accuracy only improves with the square root of the number of samples. The approximation algorithm's accuracy improves linearly with $1/\epsilon$, meaning it eventually overtakes sampling as the requirement for precision increases.
Limitations and Future Work
The current work focuses on discrete probability distributions and assumes task durations are independent. Future work is needed to handle cases where tasks are correlated (e.g., shared weather conditions). Additionally, while the Trim operator is effective for probability mass, it is less suitable for estimating the expected value (mean) of a plan's duration, as small amounts of probability moved a long distance can significantly shift the mean.
Summary updated