Contingency Labels

Keeping track of whether a plan achieves its goal in every contingency is a somewhat complex process. Cassandra, like CNLP, uses a system of labels to accomplish the necessary bookkeeping [Peot and Smith 1992]. Each goal, step, and effect in Cassandra's plan is labeled to indicate the contingencies in which that element participates:

• Goals are labeled to indicate the contingencies in which they must be achieved;
• Effects are labeled to indicate the contingencies in which they are expected to occur, i.e., the contingencies in which the goals they satisfy arise;
• Steps are labeled to indicate the contingencies in which they must be performed, i.e., the union of the contingencies in which any of their effects are expected to occur.

In general, it is assumed that a particular step could be executed in any contingency, albeit possibly to no purpose. However, it is sometimes necessary to rule a particular step out of a particular contingency as a means of preventing its interference with the plan for that contingency. For example, consider a plan to achieve the goal of having a coin heads up, the first action of which is to toss the coin (see Section 4.2.3 for a detailed discussion of this plan). In one contingency the coin lands heads up, and no further actions are required. In another contingency, the coin lands tails up and must be turned over in order for the goal to be achieved. It is clear, however, that the turning over action must not be performed in the first contingency: doing so would mean that the goal of having the coin heads up is not achieved. In Cassandra, ruling steps out is accomplished by associating negative labels with plan steps to indicate those contingencies in which the steps are not to be executed. Peot and Smith [1992] call this process conditioning.

In addition, every step that depends, directly or indirectly, on a particular outcome of a given source of uncertainty is ruled out of every contingency that involves an alternative outcome of that source of uncertainty. We discuss the reason for this restriction in more detail below.

Cassandra's labeling system thus provides very clear guidance to the agent executing the plan, which simply performs those steps whose positive labels reflect the actual circumstances that hold at execution. Steps with neither positive nor negative labels involving the current contingency will not affect the goals, but are not guaranteed to be executable. In contrast, the agent executing a plan produced by CNLP is guided by the reason labels attached to steps. In CNLP's plans, an action need only be executed if at least one of the goals represented in its reason labels is feasible. The agent must therefore have some method of deciding which of the top-level goals are feasible. We assume this can be done by comparing the context labels of each top-level goal (which are labeled because they are represented as dummy actions) with the circumstances that actually hold. Cassandra's method is thus simpler: the agent simply uses the positive labels of the plan steps instead of using the labels attached to a step to indicate those goals whose context labels must be analyzed.

The general principles of label propagation in Cassandra are:

• Positive labels, which denote that the plan element concerned contributes to goal achievement in that contingency, propagate along causal links from subgoals to the plan elements that establish them;
• Negative labels, which denote that the plan element concerned would prevent goal achievement in that contingency, propagate along causal links from effects to the plan elements that they establish.

The details are given in Section 5.1.4.