Next: Interleaving Planning and Up: Related Work Previous: Knowledge Goals

## Probabilistic and Decision-theoretic Planning

When constructing plans Cassandra recognizes the presence of uncertainty but not its extent. Other planners specifically address issues of probability. For example, BURIDAN constructs plans whose probability of achieving the goal is above a given threshold [Kushmerick et al.1995]; and DRIPS uses the utility of the different possible outcome of various plans to choose the one with the highest expected utility [Haddawy and Suwandi1994]. Neither BURIDAN nor DRIPS constructs contingency plans, i.e., plans that involve alternative courses of action to be performed in different circumstances. C-BURIDAN, which is based on BURIDAN, constructs contingency plans that are likely to succeed [Draper et al. 1994a, Draper et al.1994b]. It represents an extension of CNLP in the direction of decision-theoretic planning.

Probabilistic planners use information about the probabilities of the possible uncertain outcomes to construct plans that are likely to succeed. Cassandra, on the other hand, cannot use such information and constructs plans that are guaranteed to succeed. Probabilistic planning, because it relies on explicit probabilities, is both more and less powerful than the deterministic contingency planning performed by Cassandra. Cassandra cannot use information about probabilities but it can construct plans in circumstances in which no such information is available. For example, in order to solve the bomb-in-the-toilet problem, C-BURIDAN would have to have some information, or at least make an assumption, about the probabilities of the bomb being in each package. Whatever assumptions are made might turn out to be wrong, thus invalidating the basis of the plan.

We believe that it would be possible to build a probabilistic planner using ideas from both C-BURIDAN and Cassandra. Because of the explicit representation of decisions in Cassandra, such a planner would provide an excellent opportunity for investigating the use of different decision procedures. C-BURIDAN relies on having full knowledge of all the probabilities at the time that it constructs its plans. This knowledge, like any other, may not be available until the plan is executed. It would be relatively simple to add decision procedures to Cassandra's decision representation that depend on information about probabilities, e.g., to follow a particular course of action if the probability of a given outcome exceeds a certain value. The introduction of such decision procedures might, of course, result in the introduction of knowledge goals to determine probabilities, possibly leading eventually to a system that would construct plans to perform empirical studies to determine probabilities.

A problem associated with contingency planning is that of branch merging, i.e., the determination of whether two steps in separate branches can be treated as the same step. C-BURIDAN performs full merging: this is an effect of the probabilistic algorithm on which it is based. Adding this capability to Cassandra is an area of future work. A major problem encountered when considering branch merging is how to identify the variables in the different branches with each other: C-BURIDAN's representations do not include variables, so the problem does not arise. This may cause difficulties in the adaptation of C-BURIDAN's merging mechanism for Cassandra's use.

An advantage of combining probabilistic planning and contingency planning is the resulting ability to judge whether it is worth planning for a given contingency. One of the limitations of Cassandra in its present form is the requirement that every possible contingency be planned for. In complex situations this makes the resulting plans cumbersome. Moreover, Cassandra's performance deteriorates with the number of distinct branches in the plan. The cost of determining that the presence of a particular branch would not significantly change the probability of the plan's success might well be much less than the cost of constructing that branch. This is an interesting issue to be considered in the future.

Next: Interleaving Planning and Up: Related Work Previous: Knowledge Goals

Louise Pryor <louisep@aisb.ed.ac.uk>;