Cassandra is one of an increasing number of planners that aim to extend the techniques of classical planning to more realistic domains. Cassandra is designed to operate in domains in which two of the three principal constraints observed by classical planners are relaxed: namely, we allow non-deterministic actions and incomplete knowledge of the initial conditions. Cassandra is, however, subject to the third constraint, that changes do not take place except as a result of actions specified in the plan. This clearly limits its effectiveness in many real-world domains. Moreover, there are limits on the extent of the nondeterminism and incompleteness of knowledge that are handled. Cassandra's plans will not necessarily achieve their goals if sources of uncertainty are ignored, or if all possible outcomes are not specified.
Cassandra cannot make use of information about how likely particular outcomes are, unlike probabilistic or decision-theoretic planners; it cannot plan to interleave planning and execution; and it does not provide reaction rules for all possible circumstances. It can only solve problems for which there are valid plans involving ways of discriminating between possible outcomes; the algorithm given here cannot solve the original version of the bomb-in-the-toilet problem, although the extension described in Section 6.5.5 can do so [Collins and Pryor 1995].
The algorithm described in this paper has two major practical limitations: first, the plans it produces are often more complex than necessary; and second, the time taken to produce plans precludes its use on all except simple problems.
The complexity of Cassandra's plans results from the necessity of planning for every contingency and from the lack of branch merging. For example, suppose you had to open a combination safe so that you could obtain the money to pay for an evening out. Cassandra's plan for the goal of enjoying an evening out would have one branch for each possible safe combination. Each branch would start off with the actions to open the safe, which are different for each combination, and would continue with the actions of going to a restaurant and then to the movies, say, which would be identical in each branch. A simpler plan would merge the separate branches after the safe had been opened. The consideration of methods for branch merging is an area of future work (see Sections 6.5.4 and 7.3).
In some circumstances, such as in this example, plan complexity could be reduced through the use of run-time variables, which were introduced in IPEM [Ambros-Ingerson and Steel 1988] and used in UCPOP [Etzioni et al.1992] (see Section 7). When the only uncertainty is in the value that an action parameter takes (which is the case when opening a combination safe) it would be possible to use a run-time variable to represent that parameter, obviating the need for separate plan branches. Implementing this strategy would require effective methods for determining when the effects of uncertainty are limited to parameter values. In general, this notion indicates a possible approach to the problem of branch merging: that of taking a least commitment approach to variable binding, in the same way that a least commitment approach is taken to step ordering in a partial order planner. This would then allow the concept of ``conditional'' variable binding: a variable binding could be labeled as being required or forbidden in a given contingency.
We have not analyzed the complexity of Cassandra's algorithm, but we believe it to be exponential. This is because of the effect of multiple plan branches, whose presence not only increases the number of steps in a plan but also increases the number of potential interactions and the number of ways of resolving them. Certainly, our subjective impression is that Cassandra runs even more slowly than other planners in the SNLP family. Effective domain-independent search control heuristics are difficult to find, and in many of the (toy) domains in which we have used Cassandra even problem-specific heuristics are hard to come by.