In this section we briefly review the basic planning algorithm on which Cassandra is based. It follows closely that used in UCPOP [Penberthy and Weld 1992], which is in turn based on SNLP [McAllester and Rosenblitt 1991]. The principal difference between UCPOP and SNLP is the use of secondary preconditions (see Collins and Pryor 1992.
Cassandra does not attempt to construct a contingency plan until it encounters an uncertainty. Up until this point, it constructs a plan in much the same manner as other planners in the SNLP family. In fact, if no uncertainty is ever introduced into the plan, Cassandra will effectively function just as UCPOP would under the same circumstances. Planning proceeds through the alternation of two processes: resolving open conditions and protecting unsafe links. Each of these processes involves a choice of methods, and may therefore give rise to several alternative ways to extend the current plan. All possible extensions are constructed, and a best-first search algorithm guides the planner's exploration of the space of partial plans.
The initial plan consists of two steps: the start step, with no preconditions and with the initial conditions as effects, and the goal step, with the goal conditions as preconditions and with no effects. The planner attempts to modify its initial plan until it is complete: i.e., until there are no open conditions and no unsafe links.