Journal of Artificial Intelligence Research 4 (1996) 287-339
Submitted 1/96; published 5/96
(c) 1996 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved.

Planning for contingencies: A decision-based approach




next up previous
Next: Introduction

Planning for contingencies: A decision-based approach

Louise Pryor (louisep@aisb.ed.ac.uk)

Department of Artificial Intelligence, University of Edinburgh
80 South Bridge
Edinburgh EH1 1HN, Scotland

Gregg Collins (collins@ils.nwu.edu)

The Institute for the Learning Sciences, Northwestern University
1890 Maple Avenue
Evanston, IL 60201, USA

Abstract:

A fundamental assumption made by classical AI planners is that there is no uncertainty in the world: the planner has full knowledge of the conditions under which the plan will be executed and the outcome of every action is fully predictable. These planners cannot therefore construct contingency plans, i.e., plans in which different actions are performed in different circumstances. In this paper we discuss some issues that arise in the representation and construction of contingency plans and describe Cassandra, a partial-order contingency planner. Cassandra uses explicit decision-steps that enable the agent executing the plan to decide which plan branch to follow. The decision-steps in a plan result in subgoals to acquire knowledge, which are planned for in the same way as any other subgoals. Cassandra thus distinguishes the process of gathering information from the process of making decisions. The explicit representation of decisions in Cassandra allows a coherent approach to the problems of contingent planning, and provides a solid base for extensions such as the use of different decision-making procedures.


  1. Introduction
    1. Issues for a Contingency Planner
    2. A Note on Terminology
    3. Outline
  2. Cassandra's Plan Representation
    1. Action Representation
      1. Representing Uncertain Effects
      2. Representing Other Sources of Uncertainty
    2. Basic Plan Representation
    3. Representing Contingencies
      1. Contingency Labels
      2. Representing Decisions
  3. Planning Without Contingencies
    1. Resolving Open Conditions
    2. Protecting Unsafe Links
  4. Contingency Planning
    1. Contingencies
      1. Introducing Contingencies
      2. Uncertainties with Multiple Outcomes
      3. Multiple Sources of Uncertainty
    2. Decision-steps
      1. Formulating Decision-rules
      2. Adding a Decision-rule in our Example
      3. How Cassandra Constructs Decision-rules
      4. Decision-rules and Unsafe Links
  5. A Contingency Planning Algorithm
    1. Plan Elements
      1. Steps and Effects
      2. Links and Open Conditions
      3. Bindings and Orderings
      4. Contingency Labels
    2. Algorithm
      1. Resolving Threats to Unsafe Links
      2. Establishing Open Conditions
  6. Issues in Contingency Planning
    1. Soundness
    2. Completeness
    3. Systematicity
    4. Knowledge Goals
    5. Miscellaneous Issues in Contingency Planning
      1. Dependence on Outcomes and Superfluous Contingencies
      2. One-sided Contingencies
      3. Identical Branches
      4. Branch Merging
      5. Fail-safe Planning
      6. Contingent Failure
  7. Related Work
    1. The Representation of Uncertainty
    2. Knowledge Goals
    3. Probabilistic and Decision-theoretic Planning
    4. Interleaving Planning and Execution
    5. Reactive Planning
  8. Discussion
    1. Contributions
    2. Limitations
    3. Conclusion

next up previous
Next: Introduction

Louise Pryor <louisep@aisb.ed.ac.uk&gt</a>;
Last modified: Sun May 5 13:52:50 1996