In this paper we present Cassandra, describe its algorithm in some detail, discuss the approach it takes to some important issues in contingency planning, and show how it handles a variety of example problems.
We start by describing the structure of Cassandra's plans. Section 2 describes how Cassandra represents actions, including those with uncertain outcomes; explains the system of labels that allows the determination of which of the alternative courses of action in a contingency plan should be pursued; and introduces the notion of explicit decision steps.
Section 3 briefly describes the basic planning algorithm in the absence of uncertainty. Section 4 explains how the algorithm is extended to handle uncertain outcomes of actions. In particular, the structure of Cassandra's decisions is considered, as are the problems of ensuring the soundness of the plan that is constructed. The resulting algorithm is described in detail and its properties are discussed in Section 5.
In Section 6 we consider some issues that arise in contingency planning. Section 7 describes related work on planning under uncertainty. Finally, Section 8 summarizes the contributions of this work and discusses its limitations.