Planning can be seen as the process of deciding what to do in advance of when it is done [Collins 1987]. The need for contingency plans arises when the necessary decisions cannot be made in advance because of missing information (see Section 6.4). If the decisions cannot be made in advance, they must be made when the plan is executed. The agent executing a contingency plan must at some point decide which of the possible courses of action to pursue, in other words which branch to take.
Previous work has in effect assumed that the agent will execute those steps that are consistent with the contingency that actually holds [Warren 1976, Peot and Smith1992]. However, the determination of which steps are consistent cannot (by definition) be made in advance; in order to know which contingency holds during execution, the agent executing the plan must in general gather information on which the decision can be based. To ensure a viable plan, the planner must be able to guarantee that the steps required to gather information do not conflict with those required to carry out the rest of the plan. Therefore, the planner must in general be able to include information gathering steps, as well as any other steps that support decision making, in the plan it is constructing. Cassandra achieves this by representing decisions explicitly as plan steps. The preconditions of these decision-steps include goals to be in possession of information relevant to making the decision; the scheduling of actions to obtain information is thus handled by the normal planning process.
For instance, consider the contingency plan alluded to above: `` try taking Western Avenue, but if it's blocked use Ashland.'' During the execution of such a plan, the agent must at some point decide which branch of the plan to execute. The decision-step in this case would have the precondition of knowing whether Western Avenue is blocked or not, which would cause the planner to schedule an information-gathering action to check the traffic status on Western. This operation might in turn have the precondition of being on Western, which can be achieved by traveling to the junction of Western and Belmont. After the decision is taken, the agent can either take Western up to Evanston or continue along Belmont to Ashland.
Figure 3: A plan that includes a decision-step
Assuming the goal of the plan is to be in Evanston, the final plan
might be as depicted in Figure 3.
Note that control
flow after a decision is represented by heavy lines. Solid lines in
the diagram represent links, with the action at the tail of the link
achieving a precondition of the action at the head of the link. In
this plan, the agent will take Western to Evanston in one contingency,
and will take Belmont to Ashland and then Ashland to Evanston in the
other.
Notice that in order to determine the appropriate precondition for a given decision-step, the planner must have some way of determining exactly what it will need to know in order to make the decision at execution time. This somewhat complex determination depends in part on how the decision-making process is to be carried out. In Cassandra, decisions are modeled as the evaluation of a set of condition-action rules of the form:
Each possible outcome of a given uncertainty gives rise to a decision rule; the condition of this decision-rule specifies a set of effects that the agent should test in order to determine whether to execute the contingency plan for that outcome. For example, the decision-rules for the driving plan example would look like this:
Cassandra's derivation of inference rules in decisions is explained in detail in Section 4.
The preconditions for a decision-step are goals to know the truth values of the conditions in the decision-rules: they are thus knowledge goals [McCarthy and Hayes 1969, Pryor 1995] (see Section 6.4). These goals are treated in the same way as are the preconditions of any other step. Cassandra thus requires no other special provisions to allow the construction of information-gathering plans.
The explicit representation of decision-steps provides a basis for supporting alternative decision procedures. While Cassandra's basic model of the decision procedure is quite simple, more complex decision procedures can be supported within the same framework (one such procedure is described in Section 6.5.5). For example, the model could be changed to a differential-diagnosis procedure. The representation of decision procedures as templates in the same way that actions are represented as templates would allow the planner to choose between alternative methods of making a decision in the same way as it can choose between alternative methods of achieving a subgoal. An even better approach might be to formulate an explicit goal to make a correct decision, and allow the system to construct a plan to achieve that goal using inferential operators. However, this would in effect require that the goals for these operators be stated in a meta-language describing the preconditions and results of operators. We have not yet addressed this possibility in any detail.
Cassandra's separation of the gathering of information from the making of decisions allows one information-gathering step to serve several decisions. This allows the flexible use of information-gathering actions; there is no effective difference between such actions and any other action that may appear in a plan.