Abstract
In Partial-Order Planning (POP), "threats" occur when an action potentially undoes a condition required by another. Traditional algorithms like Systematic Nonlinear Planning (SNLP) resolve these threats immediately. This paper investigates the impact of delaying threat resolution on search space efficiency. We formalize five strategies, proving that the Delay Separable (DSep) strategy strictly dominates SNLP in terms of search space size. Our empirical analysis reveals that while "least-commitment" strategies like DUnf often yield the smallest search trees, delaying resolution too long can lead to a "least-commitment trap" where the planner fails to prune impossible branches early.
Introduction: The Cost of Eagerness
The efficiency of a Partial-Order Planner is largely determined by the size of its search space. A significant source of branching in this space is threat resolution. When a step $S_k$ threatens a causal link $S_i \xrightarrow{p} S_j$, the planner must choose between promotion (ordering $S_k$ before $S_i$) or demotion (ordering $S_k$ after $S_j$).
Classic planners like SNLP are "eager," resolving every threat as soon as it is detected. However, many threats are "ephemeral"—they arise from unbound variables and may disappear as the plan is refined. Eagerly resolving these can force unnecessary choices, leading to an exponentially larger search tree.
Formalizing Delay Strategies
The authors compare five strategies for threat removal, ranging from immediate resolution to delaying until the end of the planning process:
- SNLP (Baseline): Resolve all threats immediately.
- DSep (Delay Separable): Resolve a threat only when it becomes "unseparable" (i.e., the conflict is guaranteed regardless of variable bindings).
- DUnf (Delay Unforced): Delay until only one resolution option (promotion or demotion) remains.
- DRes (Delay Resolvable): Ignore threats until they become impossible to fix, then backtrack.
- DEnd (Delay to End): Wait until the plan is complete before addressing any threats.
As shown in Figure 1, these strategies form a hierarchy. The authors provide a mathematical proof that DSep is strictly dominant over SNLP, meaning it will never explore more nodes and will often explore significantly fewer.
The DSep Advantage and the Least-Commitment Trap
The core advantage of DSep lies in its handling of ephemeral threats. By waiting until a threat is unseparable, DSep avoids branching on choices that might have resolved themselves through other constraints. This mapping ensures that every partial plan in a DSep search corresponds to a unique, more constrained counterpart in the SNLP search.
However, the "ultimate" least-commitment strategy, DUnf, presents a trade-off. While it often results in the smallest search space by delaying decisions as long as possible, it can fall into a "least-commitment trap." By not adding constraints early, the planner may fail to recognize a dead-end branch, wasting significant computation on plans that are ultimately unresolvable.
Empirical Results
Evaluation across domains such as Russell’s Tire Changing, Minton’s Machine Shop, and various artificial benchmarks confirms these theoretical insights. In many cases, DSep and DUnf reduced the number of explored nodes by 50-70% compared to SNLP.
While there is a per-node computational overhead for checking separability, the exponential reduction in search space size makes these strategies far superior for complex problems. In difficult artificial domains, DUnf was found to be orders of magnitude faster than simpler, eager strategies.
Conclusion
Delaying threat resolution is a powerful technique for optimizing Partial-Order Planning. DSep provides a provable improvement over standard SNLP by avoiding premature commitments to ephemeral threats. While even more aggressive delay strategies like DUnf can offer further gains, they must be balanced against the risk of delayed pruning. Future work should focus on identifying specific threat types that can be safely ignored until the end of the planning process without triggering search space explosions.
Summary updated