Contingent Planning with Goal Preferences

Dmitry Shaparau, Marco Pistore, Paolo TraversoAAAI 2006

Automated reasoning in real-world environments faces two significant hurdles: unpredictable action outcomes and complex, prioritized objectives. This paper, presented at AAAI 2006, introduces a formal framework and a symbolic algorithm designed to generate optimal conditional plans that balance these challenges.

The Challenge: Non-determinism and Prioritized Goals

In classical planning, actions are typically assumed to be deterministic. However, in practice, an action like "move to the next room" might result in several outcomes: the robot succeeds, the door is locked, or it ends up in an entirely different location. Simultaneously, users often have a hierarchy of preferences (e.g., "Plan A" is ideal, but "Plan B" is an acceptable fallback).

Non-deterministic action outcomes in a robot navigation scenario.

Most prior research handled non-determinism and goal preferences separately. This paper bridges that gap by proposing a strategy that interleaves different preference levels based on the actual outcomes of actions observed at runtime.

Methodology: Qualitative Preferences and Backward Induction

The authors avoid the complexity of numerical probability distributions (common in Markov Decision Processes) by using a Qualitative Preference Model. Preferences are defined as an ordered list of goals $\langle g_1, ..., g_n \rangle$. A plan is considered "optimal" if its best-case outcome is more preferred than others; if best-cases are tied, the plan with the superior worst-case outcome is selected.

The BuildPlan Algorithm

The core contribution is the BuildPlan algorithm, which operates via backward induction:

  1. Safety Net First: It starts by computing a "universal plan" for the least preferred goal. This ensures the agent always has a recovery strategy.
  2. Iterative Improvement: It then moves to higher-priority goals, identifying actions that either reach a better goal directly or lead to states where a previously computed plan can take over.
  3. Symbolic Implementation: The algorithm utilizes Binary Decision Diagrams (BDDs) to represent massive state spaces efficiently, allowing the planner to manipulate sets of states without enumerating them individually.

Key Results and Scalability

The approach was evaluated using robot navigation benchmarks and a Web Service Composition domain. In the latter, the planner coordinated multiple non-deterministic services (e.g., booking and payment) to satisfy prioritized user requests.

Scalability of the planning algorithm across varying numbers of services and goals.

The BDD-based implementation demonstrated remarkable efficiency. In the Web Service domain, the planner successfully managed environments with up to 30 services—representing a state space exceeding $2^{82}$ states—within approximately 600 seconds. Furthermore, the algorithm's performance scales near-linearly with the number of goals, making it a practical solution for complex, real-world requirements.

Conclusion

By combining a "safety net" strategy with symbolic computation, the authors provided a robust framework for contingent planning. While the current model assumes a total ordering of goals and ignores outcome probabilities, it offers a clean, human-readable way to specify and achieve optimal behavior in uncertain environments.

Summary updated

BibTeX
@inproceedings{shaparau2006contingent,
  author = {Dmitry Shaparau and Marco Pistore and Paolo Traverso},
  title = {{Contingent Planning with Goal Preferences}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure