Contents |
|
The Middle Ground
As we explained, for predefined behaviors the character doesn't have to do any searching for actions that achieve its goals. It simply follows the instructions it was given and ends up at a goal situation. In effect, for a given set of inputs, the path through the tree of possible situations has been determined in advance. If the predefined behaviors were defined properly, then the path that they specify through the tree will lead to a goal situation.
In this section, the question we want to ask is whether there is some middle ground between asking the character to do all the work at run-time and asking the programmer to all the work at compile time. In particular, consider that on the one hand we have predefined behavior which corresponds to a single path through the situation tree, and on the other hand we have goal-directed behavior which corresponds to searching the whole tree. Clearly, the middle ground has to be searching some subset of the tree.
Note that this "middle ground" is still technically goal-directed behavior, but we now have control over how much nondeterminism is allowed in the behavior specification. Only in the limiting case, when we have removed all the nondeterminism, does the behavior reduce to deterministic predefined behavior.
Precondition Axioms
Although we might not have realized it, we have already seen one way to exclude parts of the situation tree from the search space. In particular, precondition axioms prune off whole chunks of the tree by stating that not all actions are possible in all situations. Figure 7 shows an example of an abstract tree in which it is not possible to do an action a2 because an action a1 changed something which made it impossible.
![]() |
Figure
7. Preconditions preclude portions of the
tree |
While preconditions are important for cordoning off parts of the situation tree, they are a clumsy way to try and coerce a character to search a particular portion of the tree. In particular, we need a way to give a character general purpose heuristics to help it find a goal faster. For example, we might want to give the character a heuristic that will cause it look at certain groups of actions first, but we do not want to absolutely exclude the other actions.
The hard part of exploiting the middle ground between predefined and goal-directed behavior is to think up a useful way to specify subsets of the tree. In the next section, we will introduce a convenient way to specify arbitrary subsets of the situation tree to search.
Complex Actions
We would like to provide a character with a "sketch plan" and have it responsible for filling in the remaining missing details. In this way, we salvage some of the convenience of the planning approach while regaining control over the complexity of the planning tasks we assign the character. We will show how we can use the idea of complex actions to write sketch plans.
The actions we discussed previously, defined by precondition and effect axioms, are referred to as primitive actions. (The term "primitive action" is only meant to indicate an action is an atomic unit, and not a compound action. Unfortunately, the term can be misleading when the action actually refers to some sophisticated behavior, but we will stick with the term as it is widely used in the available literature). Complex actions are abbreviations for terms in the situation calculus; they are built up from a set of recursively defined operators. Any primitive action is also a complex action. Other complex actions are composed using various operators and control structures, some of which are deliberately chosen to resemble a regular programming language. When we give a character a complex action a, there is a special macro Do that expands a out into terms in the situation calculus. Since complex actions expand out into regular situation calculus expressions, they inherit the solution to the frame problem for primitive actions.
Complex actions are defined by the macro Do(a,s,s'), such that is a state that results from doing the complex action a in state s. The complete list of operators for the (recursive) definition of Do are given below. Together, the operators define an instruction language we can use to issue direction to characters. The mathematical definitions can be difficult to follow, and the reader is encouraged to consult the book , in which we explain the basic ideas more clearly using numerous examples of complex actions (note there are two freely available implementations of complex actions that can be studied for a more practical insight into how the macro expansion works--see www.cs.toronto.edu/~funge/book).
![]() |
Figure
8. Effect of the complex action on a situation
tree |
The macro expansion Do(a,s,s') specifies a relation between two situations s and s', such that is a situation that results from doing the complex action a in situation s. In general, there is not a unique s', so if we have some initial situation s0, a complex action "program", and a bunch of precondition and effect axioms, then Do(program, s0, s') specifies a subset of the situation tree. Figure 8 shows a quick example of how a complex action can be used to limit the search space to some arbitrary subset of the situation tree. The other thing we can see from the figure is that the mathematical syntax can be rather cryptic. Therefore, in the appendix, we introduce some alternative syntax for defining complex actions that is more intuitive and easy to read.
On its own, just specifying subsets of the situation tree is not
particularly useful. Therefore, we would normally explicitly mention the
goal within the complex action. We shall see many examples of this in what
follows. For now, suppose the complex action "program" is such a complex
action. If we can find any
such that Do(program, s0, s'), then the plan of length n, represented by the actions a0,...,an-1. , is the behavior that the character believes will result in it obtaining its goals. Finding such an s' is just a matter of searching the (pruned) situation tree for a suitable goal situation. Since we still end up searching, research in planning algorithms is just as relevant to this section as to the straight goal-directed specification section.
Implementation
Note that we defined the notion of a situation tree to help us visualize some important ideas. We do not mean to suggest that in any corresponding implementation that there need be (although, of course, there may be) any data structure that explicitly represents this tree. In particular, if we explicitly represent the tree, then we need a potentially exponential amount of memory. Therefore, it makes more sense to simply build portions of the tree on demand, and delete them when they are no longer required. In theorem provers and logic programming languages (e.g., Prolog), this is exactly what happens continually behind the scenes.
Logic programming languages also make it straightforward to under-specify the domain knowledge. For example, it is perfectly acceptable to specify an initial state that contains a disjunction, e.g. OnTable(cup,s0) v OnFloor(cup,s0). Later on, we can include information that precludes a previously possible disjunct, and the character will still make valid inferences without us having to go back and alter any of the previous information. If we do not need such a sophisticated notion of elaboration tolerance, then it might be simpler to build a situation tree explicitly. Moreover, if the tree is not too deep, or if it is heavily pruned, it needn't be excessively large and thus can be fast to search. Whether such a shallow, or sparse, tree is useful or not will depend on the particular application, but in computer games and animation there are countless examples where a character with even a moderate ability to plan ahead can be extremely useful.
_____________________________________________________________________