This category includes systems such as STRIPS [Fikes and Nilsson 1971], HACKER [Sussman 1975], NOAH [Sacerdoti 1977] and MOLGEN [Stefik 1981a, Stefik 1981b]. Recent classical planners include TWEAK [Chapman 1987], SNLP [McAllester and Rosenblitt 1991] and UCPOP [Penberthy and Weld 1992]. The term is due to Wilkins [1988].

Cassandra was a Trojan prophet who was fated not to be believed when she accurately predicted future disasters. An earlier version of Cassandra was described in [Pryor and Collins 1993].

Appendix A shows the plans that Cassandra constructs for all the examples described in this paper. This plan is in Section A.1.

An alternative method would be to split the plan into two branches, regardless of the number of outcomes. In this case, one branch would be associated with a given outcome of the uncertainty, while the other would be associated with all other possible outcomes of that uncertainty. This is effectively how SENSP operates [Etzioni et al. 1992].

Note that we are describing the contingency in this way for clarity of exposition. The actual label is constructed as described in Section 2.3.1.

Assuming that ?U, the variable representing the source of uncertainty, is instantiated to U1.

An obvious extension to Cassandra would be the construction of a post-processor that spots decision-rules that do not discriminate between particular sets of outcomes, and prunes the plan to remove superfluous contingencies. Note that it cannot be determined until the plan is complete whether such a condition pertains.

This raises the obvious question as to whether planning in advance for every possibility is a sensible thing to do. See Section 7.4 for a discussion of this issue.

Neither NOAH [Sacerdoti 1977] nor Interplan [Tate1975] explicitly addressed issues of uncertainty, although both tackled problems involving it [Collins and Pryor1995].

See Section 8.2 for further discussion of this issue and an alternative approach.

Not all agents can make use of this information, as there is no guarantee that the third type of step will actually be executable.

Louise Pryor <louisep@aisb.ed.ac.uk>;
Last modified: Wed May 1 11:19:46 1996