We conjecture that Cassandra is complete in the limited sense that, if there is a sound plan of the form that it can construct, then Cassandra will find it. We believe that this is a simple extension of UCPOP's completeness. If there are no uncertainties involved, Cassandra will always find a plan in the same way as UCPOP. The introduction of a source of uncertainty into a plan leads to the addition of new contingent goals. Cassandra will find a plan for each of these new goals in the appropriate contingency. Thus, if the goal can indeed be achieved in every contingency, Cassandra will find a plan that achieves it, as long as there is a way of determining which contingency holds.
For example, the plan to disarm a bomb that we described in McDermott 1987]. The algorithm described in the previous section cannot find a plan in this situation because it is impossible to achieve the preconditions of the decision-step that determines which package to dunk. In Section 6.5.5 we discuss this example in more detail and describe a simple extension to Cassandra that allows the correct plan (to dunk both packages) to be found.
UCPOP's completeness, like its soundness, depends on the perfect knowledge assumptions we discussed in Section 1. Cassandra's completeness depends on three extensions to these assumptions:
Unfortunately, these conditions are necessary but not sufficient. Cassandra can only find plans if the actions that it uses to determine the contingency do not interfere with the achievement of the goal. For instance, there might be a dropping action available that would detonate any bomb inside the package that was dropped. This is certainly an action that allows the determination of the outcome of the uncertainty, but there is no sound plan that makes use of it.
In order to have a useful notion of Cassandra's completeness, we must therefore specify the form of the plans that it can construct. This problem is common to proving the completeness of any planner: for example, we do not claim that SNLP, say, is incomplete because it cannot find a plan for the bomb-in-the-toilet problem. We say instead that there is no valid plan of the form that it can construct. It is fairly simple to specify the form of the plans that SNLP can construct: they consist of partially ordered sequences of steps, all of which are to be executed. The introduction of contingencies makes the description of Cassandra's plans rather more complex; we have yet to formalize a description, but are actively working in that direction. Informally, Cassandra can only construct plans that for every source of uncertainty include a step to decide on one of the relevant plan branches. The extension of Cassandra that solves the bomb-in-the-toilet problem can do so because it can construct plans that do not meet this criterion.