Abstract
Most current planners assume complete domain models and focus on generating correct plans. Unfortunately, domain modeling is a laborious and error-prone task, thus real world agents have to plan with incomplete domain models. While domain experts cannot guarantee completeness, often they are able to circumscribe the incompleteness of the model by providing annotations as to which parts of the domain model may be incomplete. In this paper, we study planning problems with incomplete STRIPS domain models where the annotations specify possible preconditions and effects of actions. We show that the problem of assessing the quality of a plan, or its plan robustness, is #P-complete, establishing its equivalence with the weighted model counting problems. We introduce two approximations, lower and upper bound, for plan robustness, and then utilize them to derive heuristics for synthesizing robust plans. Our planning system, PISA, incorporating stochastic local search with these novel techniques outperforms a state-of-the-art planner handling incomplete domains in most of the tested domains, both in terms of plan quality and planning time.
Introduction
In classical automated planning, such as STRIPS, agents operate under the assumption of perfect knowledge: every action's preconditions and effects are precisely defined. However, in real-world applications, creating such exhaustive models is often impractical. A modeler might know the core requirements of an action but remain uncertain about auxiliary conditions or side effects. This paper addresses the challenge of planning with incomplete action models, where uncertainty is explicitly annotated as "possible" preconditions and effects.
The goal is to find a robust plan—one that maximizes the probability of success across the space of all possible "true" models. Previous approaches often treated robustness as a secondary consideration or struggled with the computational overhead of exact probability calculations.
Complexity and Robustness Bounds
A key contribution of this work is the formal proof that calculating plan robustness (the exact probability of success) is #P-complete. This complexity class implies that exact calculation is as difficult as counting the number of satisfying assignments for a propositional formula, making it unsuitable for real-time search guidance.
To overcome this, the authors derive efficient lower and upper bounds for robustness. By treating the logical constraints of a plan as monotone clauses, they enable fast approximations of success probability.
The PISA Planning System
The proposed system, PISA, integrates these robustness bounds into a stochastic local search algorithm. Unlike traditional planners that prioritize plan length, PISA uses a "robust relaxed plan" heuristic. This heuristic guides the search toward paths that are statistically more likely to succeed despite the model's incompleteness. By placing robustness at the core of the search objective rather than using it as a tie-breaker, PISA can navigate uncertain state spaces more effectively.
Experimental Evaluation
PISA was evaluated against DeFault, the leading planner for incomplete domains, using 215 variations of standard International Planning Competition (IPC) benchmarks, including Freecell, Rover, and Zenotravel, as well as the real-world Parcprinter domain.
The results demonstrate that PISA consistently produces plans of equal or superior robustness. In the Zenotravel domain, PISA outperformed the baseline in 78.5% of instances. Beyond quality, PISA achieved massive speedups, often outperforming DeFault by orders of magnitude—averaging 1665x faster in the Rover domain.
Conclusion
The PISA planner demonstrates that in uncertain environments, efficient approximations of success probability are more valuable than exact but computationally expensive calculations. By leveraging the monotonicity of plan constraints, PISA provides a scalable solution for robust planning. Future work aims to address correlated uncertainties and automate the discovery of "possible" annotations from execution data.
Summary updated