An agent executing contingency plans must be able to acquire information about the actual state of the world so that it can determine which of the possible courses of action to pursue. A system that constructs contingency plans must be able to plan for this information acquisition: in general, the acquisition process may be arbitrarily complex [Pryor and Collins 1991].
An early and influential discussion of goals to possess knowledge about the world was that by McCarthy and Hayes [1969]. Since then, various theories have been developed to account for them (e.g., Moore 1985, Haas 1986, Morgenstern 1987, Steel 1995). The common thread in all this work is that knowledge goals arise from the need to specify the actions that are to be performed; in other words, from the need to make actions operational. Work in this area has on the whole concentrated on being able to describe and represent knowledge goals, and has largely ignored the issues involved in building planners that construct plans containing them.
The structure of Cassandra is based on the notion that knowledge goals arise out of the need to make decisions as to the actions to be performed [Pryor 1995]. In our view, planning is the process of deciding what to do in advance of when it is done [Collins 1987]. In a world conforming to the perfect knowledge assumptions of classical planning this is always possible because the world is totally predictable, and plans therefore need contain no knowledge goals. However, when those assumptions are relaxed it may not be possible to make all decisions in advance if the information necessary to make them is not available to the planner. The information may be unavailable either because of the planner's limited knowledge of the world or because the events that will nondeterministically cause the conditions that affect the decisions have not yet occurred. In both cases it may be possible for the planner to determine that a decision must be made even though it cannot at that time actually make it. In this case the planner can defer the decision: plan to make it in the future, when the necessary information will be available. Part of the plan is then to acquire the information; the plan thus contains knowledge goals.
Cassandra's use of ``unknown'' preconditions to indicate nondeterminism is thus a crucial part of its mechanism. In Cassandra, knowledge goals arise as the result of deferring decisions. These deferred decisions are represented explicitly in its plans, and themselves arise directly from the incompleteness of Cassandra's knowledge of the world, whether through the effects of nondeterministic actions or through incompletely specified initial conditions. Both these forms of uncertainty are handled in the same way: once Cassandra has recognized the need to defer a decision, the reason for its deferral is not important except inasmuch as it results from incomplete knowledge of the world.
The view of knowledge goals as arising from deferred decisions is
basically consistent with the view that they are needed in order to
make actions operational, but differs from the traditional view in
that knowledge goals are not directly preconditions of physical
actions, but are instead preconditions of actions that make decisions.
For example, McCarthy and Hayes consider the problem of a combination
safe: it is commonly held that the action of opening the safe has a
precondition to know the combination. In Cassandra, however, the goal of
knowing the combination would arise as a subgoal of deciding which
plan branch to follow, where there would be a branch for each possible
combination.
The branches would arise because of Cassandra's incomplete knowledge of
the world: the initial conditions in which the plan will be executed
are not fully specified.
Cassandra uses a variant of the syntactic approach proposed by Haas [1986] to represent knowledge goals, limiting knowledge goals to the form know-if(fact). This turns out to be adequate if, as we assume, all possible outcomes of any given uncertainty are known. In general, the representation used by Cassandra, based on the STRiPS representation of add and delete lists, is less powerful than the logics proposed by either Morgenstern or Haas.