Cassandra is constructed using UCPOP [Penberthy and Weld 1992] as a platform. UCPOP is a partial order planner that handles actions with context-dependent effects and universally quantified preconditions and effects. UCPOP is an extension of SNLP [Barrett et al. 1991, McAllester and Rosenblitt 1991] that uses a subset of Pednault's ADL representation [Pednault 1989].
An early contingency planner was Warren's WARPLAN-C Warren 1976. Contingency planning was
more or less abandoned between the mid seventies and the early
nineties,
until SENSp [Etzioni et al. 1992] and CNLP [Peot and Smith1992]. Both SENSp and CNLP
are members of the SNLP family: SENSp is, like Cassandra, based on
UCPOP, and CNLP is based directly on SNLP. C-BURIDAN [Draper et al. 1994a, Draper, Hanks, and Weld 1994b], a
probabilistic contingency planner, is based on the probabilistic
planner BURIDAN [Kushmerick, Hanks, and
Weld 1995] (which is itself based on SNLP) and on CNLP. PLINTH [Goldman and Boddy 1994a, Goldman and Boddy1994b] is a total-order
planner based on McDermott's PEDESTAL, McDermott 1991, and is strongly
influenced by CNLP in its treatment of contingency plans.
WARPLAN-C, unlike the other planners considered here, did not use a STRIPS-based action representation, but was based on predicate calculus. It could handle actions that had just two possible outcomes, and did not merge the resulting plan branches.
SENSp also differs from the other planners considered here. It represents uncertainty through the use of run-time variables, distinguished from ordinary variables by being treated as constants whose values are not yet known. In SENSp plan branches arise from the introduction of information-gathering steps that bind the run-time variables. SENSp handles plan branching by constructing separate plans that each achieve the goal in a particular contingency. It then combines the separate plans at a later stage, keeping the branches totally separate. SENSp thus considers contingency branches separately, rather than in parallel. Actions that achieve knowledge goals may not have preconditions in SENSp: this restriction is required in order to maintain completeness.
Not surprisingly, Cassandra, CNLP, and C-BURIDAN, and to a lesser extent PLINTH, are in many respects very similar. All except PLINTH use the basic SNLP algorithm, and all use extended STRIPS representations. Cassandra differs from CNLP and PLINTH principally in the way that uncertainty is represented (Section 7.1); this difference has important implications for the handling of knowledge goals (Section 7.2). The principal difference between Cassandra and C-BURIDAN lies in the latter's use of probabilities (Section 7.3).
Contingency planning is only one approach to the problem of planning under uncertainty. The aim of contingency planning is to construct a single plan that will succeed in all circumstances: it is essentially an extension of classical planning. There are other approaches to planning under uncertainty that do not share this aim: probabilistic planners aim to construct plans that have a high probability of succeeding (Section 7.3); systems that interleave planning and execution do not attempt to plan fully in advance (Section 7.4). In both these approaches it is possible to address the problem of determining which contingencies should be planned for, which is not currently possible in Cassandra. A third approach is that of reactive planning, in which behavior is controlled by a set of reaction rules (Section 7.5).