A Message Passing Algorithm for Plan Recognition

1 Introduction

In cases where we have incomplete specifications of how agents act in environments, the motivation for plan recognition is to somehow attribute a plan to the agent's observed actions, in order to help create a less incom­ plete specification of behaviour. The extra information, regardless of how it is fabricated, is typically used to do things like explain actions already taken, or to pre­ dict actions to be taken. Applications of plan recognition have been found in discourse understanding [Litman and Allen, 1991], intelligent interfaces [Goodman and Lit­ man, 1990], cooperative problem solving [Lochbaum et al. , 1990] and the analysis of goal-directed behavior in general.

Kautz [Kautz, 1987] proposed a formal theory of plan recognition. The advantages of Kautz's theory include its formal declarative semantics and expressive richness of its plan representation. Unfortunately, Kautz's plan recognition algorithm is exponential in the size of the knowledge base [Kautz, 1987, p.119] and thus may prove difficult to scale up. Vilain [Vilain, 1990] showed that, by imposing certain restrictions on plan representation, the plan recognition problem may be turned into a context free grammar parsing problem, which has well-known

Randy Goebel

Dept. of Computing Science University of Alberta Edmonton, Alberta, Canada T6G 2H1 goebel@cs. U alberta.ca

polynomial solutions. However, in order for Vilain's scheme to work, the plan components (steps) must be fully ordered and cannot be shared or interleaved. These conditions appear to be too restrictive in most applica­ tions.

Rather than restrict the plan representation formalism to suit parsing algorithms, we propose a new algorithm for plan recognition that is a generalization of a mes­ sage passing algorithm for context-free grammar parsing [Lin and Goebel, 1990]. The plans libraries are repre­ sented by first order logic (FOL) formulas, as in [Kautz, 1987]. The solutions for the plan recognition problem are scenarios which, together with background knowl­ edge (plan libraries) , logically entail the observations. The complexity of our algorithm is linear in size (num­ ber of axioms) of the knowledge base. If the same set of restrictive assumptions are made as in [Vilain, 1990], the complexity of our algorithm becomes O(l7iln 3 ), where IHI is the size (number of nodes and links) of the plan hierarchy and n is the number of observations to be ex­ plained. In contrast, the complexity of Vilain's algo­ rithm is O(l7il 2 n 3 ).

Another contribution of this research is a formal, declarative treatment of specificity of explanations. Specificity has always been a confusing issue in plan recognition. Some have argued that the most specific explanation should be preferred because more specific information should preempt the more general. Alterna­ tively, a more general statement about a plan instance is more likely to be true and therefore preferable. In [Kautz, 1987], specificity preference is not formally spec­ ified. Rather, it is dealt with by a consider-spec flag in the procedural description of the plan recognition al­ gorithm. In Vilain's simplification this issue is totally ignored. We have taken the approach where preference is given to the most general of the scenarios that consist only of arguments that are the most specific with respect to the observations.

2 Plan Representation

Our plan representation scheme is similar to that of [Kautz, 1987], but is more general in that recursive and optional plan components can be represented. On the other hand, the constraints in Kautz's plan represen­ tation language can be any FOL formula that does not contain predicates representing plan types, here, the con­ straints have more restrictive patterns.

The motivation for the more restrictive patterns of constraints is a computational one. A major source of complexity in Kautz's algorithm is the fact that the ex­ planation graphs in Kautz's algorithm are not able to contain local ambiguities. That is, two or more alterna­ tive explanations of a subset of observations from a plan type may combine with a similar set of alternatives for a different subset to produce an exponential growth in the number of global alternatives. However, local ambiguity may be globally irrelevant, in which case containment implies that local ambiguities are not multiplied. Our message passing algorithm is able to block the propa­ gation of local ambiguities; a more restrictive form of constraints in our plan representation language guaran­ tees that the global consistency is satisfied if the local constraints are satisfied.

We partition the domain of discourse into plan in­ stances and attribute values, which are denoted by PI and AV respectively. Attributes are functions which maps plan instances PI to attribute values. For example, time is an attribute which maps a plan instance to the time interval representing its duration. The set of attributes is denoted by A.

A plan type is a unary predicate on PI (or equivalently, a subset of PI). We use the symbol P to denote the set of plan types. For example, Mkldl (Make Noodle) and Boil are two plan types. The relationships between a plan and its immediate components are represented by features, which are functions from PI to PI. For example, that Boil is an immediate component of Mltldl is represented by a feature 11 which maps an instance of Mltldl into an instance of Boil. The set of features is denoted by F.

The symbol _l denotes the void element in PI. For an element x E PI, f(x) =.l means that x does not have an /-component. We defined p(.l) to be false and /(.l) =.l, for any p E P, and f E F .

Plans are axiomized by -three sets of FOL formulas: Abstraction Axioms, Feature Restriction Axioms, At­ tribute Value Constraints.

Definition 2.1 (Abstraction Axioms) An abstrac­ tion axiom is a formula of the form: 'lx.p1(x) __.,. P2(x), where Pl,P2 E P .

The following are two examples of abstraction axioms:

Corresponding to each abstraction axiom Vx.p(x) __.,. q( x), there is a specialization function q ..spec_p such that

The specialization functions make the functional inverse of abstraction axioms explicit.

Definition 2.2 (Feature Restriction Axioms) A feature restriction axiom is a formula of the form:

where p,p' E P and f E F .

We write p ...!.. p' as a short hand for this axiom. In­ tuitively, each plan type p has an associated set of fea­ ture restriction axioms which define the possible compo­ nents of each instance of p. The condition f(x) :f:.l ensures that the plan type of a component is speci­ fied only when a component exists. For example, sup­ pose 11 is a feature (function) that maps an instance of Mltldl to a component, say its second step, an in­ stance of Boil. Then there is a feature restriction axiom Vx.Mltldl(x) I\ (11(x):f:.l) __.,. Boi1(11(x)) .

A feature f E F is said to be a feature of a plan type p E P provided that there exists a feature restriction axiom Vx .p(x) I\ (f(x) :f:.l) __.,. p'(f(x)). For example, 11 is a feature of Mkldl, because

is a feature restriction axiom.

If a plan instance x belongs to plan type p and f is a feature of p (or a superclass of p), then f(x) is an immediate component of x. The components of a plan instance x are the plan instances that are either imme­ diate components of x or, recursively, components of the immediate components of x.

Definition 2.3 (Attribute Value Constraints)

There are two types of attribute value constraints: lo­ cal constraints and percolation constraints.

A Local Constraint specifies how the attributes of a plan instance are related, and is expressed by a formula of the form:

where p E P, r is a n-ary predicate over attribute values {AV} (n = 1, 2, ... ).

A Percolation Constraint specifies how the attributes of an plan instance are determined by the attributes of its immediate components and is a formula of the form:

where Pl, P2 E P, f is feature of P1 and a, a' E A are attributes.

Suppose time, time_l1, and time_f4 are attributes and before is a binary predicate on AV, then

Vx.MkSpag(x) __.,. before(time_f4(x), time_l1(x)) is an example of local constraints.

Suppose f 4 is a feature of MkSpag that maps an in­ stance of MkSpag to its GetSpag component, and 11 is a feature of Mltldl, two examples of percolation constraints are:

In summary, the knowledge about plans is represented by three sets of FOL formulas. We write KB to denote the conjunction of the set of abstraction axioms, feature restriction axioms and the attribute value constraints.

3 Scenarios

A plan recognizer's task is to find an explanation of the observed actions. We define explanations to be consis­ tent scenarios that entail the observations. A scenario is an FOL formula that describes an plan instance and its components. The syntax of a scenario is not defined by BNF, rather, it is defined in terms of walk trees in the plan hierarchy which is the diagrammatic form of the abstraction and feature restriction axioms in KB.

Definition 3.1 (Plan Hierarchy) A plan hierarchy is a directed graph whose nodes represent elements in P and whose links are as follows:

"isa" and specialization links: Corresponding to each abstraction axiom \fx .p1(x)--+ p2(x) in I, there is an "isa" link Pl ~ P2 , and a specialization link P2 ·~c Pl · feature links: Corresponding to each feature restriction axwm:

there is a feature link from Pl to P2 and labeled f.

We write 1l to denote the plan hierarchy for KB. The sets of "isa" links and feature links correspond to the ab­ straction and decomposition hierarchies in [Kautz, 1987] respectively. Figure 1 shows the plan hierarchy of a cook­ ing world. Each of the bidirectional gray arrows repre­ sents a pair of "isa" and specialization links. The upward arrow represents the "isa" link and the downward arrow represents the specialization link.

The "isa" links (as well as the specialization links) in­ duce a partial order ("isa" relation) over P. The closure of "isa" relation is denoted by ~* and the non-empty l . d d b i· <> h . spec spec c osure 1s enote y --++ . T e meanmg of --+ * and --+ + are similarly defined.

A directed path in the plan hierarchy 1l represents a plan- component relationship between the two end nodes of the path. The "isa" links allow plan types to inherit arguments from their superclasses. For ex­ ample, The path from MkPasta to Boil is an argument that an instance of MkPasta has an instance of Boil as one of its components. This argument can be in­ herited by MkSpagPesto via the "isa" link from it to MkPasta. The specialization links, on the other hand, allow plan types to inherit explanations from their su­ perclasses. For example, an explanation of a MkPasta instance, together with an assumption that the MkPasta instance is a MkSpagPesto instance, may also serve as an explanation of the MkSpagPesto instance, provided that there does not exist a more direct explanation for the lat­ ter. Similar to inheritance reasoning [Touretzky, 1986; Bacchus, 1988], path preemption ensures that only the most specific information is inherited.

Definition 3.2 (Path Preemption)

Generalization Preemption: A path p~+p2 -..!.. p 1 is preempted if there exists a path P~*Pl -..!.. Pi ~*P 1 such that Pl ~+p2 {Figure 2. a).

Specialization Preemption: A path p -..!.. P2·~c+p 1 is d f h . h spec 1 f spec 1 h preempte 1 t ere ex&sts a pat p--+ *Pl --+ Pl --+ *P sue that P2 s~c+p1 {Figure 2. b }.

An observed action can be related to some higher level plan by a path, which identifies the action as a possible component of achieving the plan. The plan recognizer's task, however, is not just to explain the observed actions separately. Rather , it must find a set of coherent rela­ tionships which relate all the observations to· a higher level plan. To accomplish this, we introduce the notion of walk tree. The definition of a walk tree is built recur­ sively upon the concept of a local tree, which identifies the relationships between a plan and its immediate com­ ponents.

Definition 3.3 (Local Tree) A local tree of1l is a di­ rected subtree T of 1l such that the paths from the root of T to the leaves of T are sequences of zero or more "is a" links followed by one feature link and the labels of the feature links are different .

An example of Local Tree is shown in Figure 3.a

1. The local trees of 1l are also walk trees of 1i.
2. Suppose a is a walk tree of 'H. If a leaf node of o: is labeled p and f3 is a local tree or a specialization link in 1£, with the root labeled p, then the tree formed by joining the node p in o: and the root of {3 is also a walk tree of1l.
3. All walk trees are either one of the above.

A walk tree is said to be valid if it does not contain any preempted paths. A walk tree is more general than a tree in that there may be multiple occurrences of the same node in 1£, and therefore can be used to represent iterative or recursive plan components. For example, Figure 3.b shows a valid walk tree, where there are two instances of PrepareADish.

An attribute assignment of a plan instance x is a set of assignments of attribute values to x and is denoted by V(x) . That is V(x) = A7= 1 a;(x)=v; , where a; E A and v; 's are constants in AV. For example, time(x) = [0, 1) A agent(x) =john is an attribute assignment of x . Definition 3.5 (Scenario) LetT be a valid walk tree of 1£. Let fi, fi, . . . f;.. be the compositions of the fea­ ture and specialization functions along the path from the root ofT to the leaf nodes of the local trees in T . Let P1 , P2, ... Pm be the corresponding plan types represented by the nodes. Then T and a set of attribute assignments V1 , V2 , . . . , Vm define a scenario o: , which is an FOL for­ mula:

For example, suppose time is an attribute of plans. Let a denote the scenario in Figure 4, where the intervals be­ side the nodes denote the values of their time attribute. Then a is the following formula:

4 The Plan Recognition Problem

An observation is an assertion that there exists a plan in­ stance of certain type and possessing certain attributes. Definition 4.1 (Observation) An observation is a formula of the form:

where p is a plan type and V is an attribute assignment. Definition 4.2 (Explanation) Given KB and a set of observations o1 , . .. , Ok, an explanation of the observa­ t ions is a scenario a such that

1. o: is consistent with KB, i.e., KB /1. a V= false .

2. KB /1. o: ~ 01 A . . . A Ok .

Definition 4.3 (Plan Recognition Problem) Given KB and a set of observations { 01, . . . , Ok} , the plan recognition problem is to find the most general ex­ planation o: of { o1 , ... , ok}. That is, there does not exist another explan~tion f3 of { 01, .. . , ok} such that roota~+rootfJ, where roota and root{J are the plan type represented by the root nodes of o: and f3 respectively.

The more general explanation is preferred because a more general statement about a plan instance is more likely to be true. For example, MkPasta(x) is more likely to be true than MkSpagPesto(x). On the other hand, the validity of the walk tree implies that each explanation contains only the arguments that are the most specific with respect to the observations.

4.1 Examples

Suppose the Abstraction Axioms and Feature Restric­ tion Axioms are represented by Figure 1. The Percola­ tion Constraints are as follows :

The Local Constraints are as follows:

Example 1: Suppose the following observations are made:

o3 = 3x.KkKari(x) A time(x) = [1, 2]

o1 = 3x.GetSpag(x) A time(x) = [0, 1] o2 = 3x.Boil(x)Atime(x)=[1,2]

Then the scenario that explains {o1, o2, oa} is the one shown in Figure 4. Note that the observations do not have to be a sequence of actions. In this example, Boil and MkMari are concurrent.

Example 2: Suppose the following two observations are made:

The explanations of { o1, 02} are shown in Figure 5. Since the explanation in 5.a is more general than those in 5.b, 5.c and 5.d, the solution of the plan recognition problem is the scenario in 5.a.

Example 3: Suppose the observations are:

Then the only explanation is the scenario in Figure 5.c. The walk tree shown in Figure 6 is not a valid one be­ cause the path:

is preempted by the path

5 A Recognition Algorithm

Since only a restricted subset of FOL is used to represent the observations, scenarios, as well as the domain knowl­ edge, the plan recognition problem may be solved by a specialized inference method. We now present a mes­ sage passing algorithm for plan recognition. Each node in the plan hierarchy is a computing agent which com­ municates with other agents by sending messages across the links in the plan hierarchy. A message is a pair: <V, B>, where V is an attribute assignment describing a plan instance, and B is a subset of observations. The messages are passed in the reverse direction of the links in the plan hierarchy. If a message < V, B> reaches a node p, then this means that the observations in B can be explained as components of an instance of plan type p that matches the description V. Therefore, the messages represent partial explanations of subsets of the obser­ vations. The partial explanations are combined at the nodes to generate explanations for larger subsets of the observations.

Let {o; = 3x.p;(x) 1\ V;(x)} (i = 1, 2, .. . , n) be a set of observations. The message passing process is initiated by sending the message < V;, { o;} > to the node p;, for i = 1, 2, ... , n . The message passing process stops when no further messages are being sent and the explaining scenarios can then be retrieved from the network by trac­ ing the origins of the messages whose B components are equal to {o1,o2, . .. ,on} .

When a node receives a message via a specialization link, the message is forwarded via the incoming special­ ization and feature links. When a node receives a mes­ sage < V, B> via an "isa" link or a feature link, the mes­ sage is first forwarded across the incoming "isa" links, then an item is created and saved into the local mem­ ory. An item is a triple <V, B , F>, where V and B are the same as in messages, and F is a set of features . The item created when the message <V, B> arrives is

<V', B, {/}>, where V' is determined by V according to the percolation constraints and f is the feature rep­ resented by the last feature link traversed by the mes­ sage. The node then attempts to combine the new item with previously stored items that are compatible with it. Two items <V1, B1, F1> and <V2, B2, F2> are com­ patible if F1 and F2 are disjoint and the unification of V1 and V2 satisfies the local constraints. If interleaved plan components are not allowed, B1 and B2 must also be consecutive sequences of observations. If shared plan components are not allowed, then the two items are only compatible if B1 n B2 = 0.

The combination of two items < V1 , B1, F1 > and <V2, B2, F2> is an item <Vo, Bo, Fo>, where Vo is the unification of V1 and V2; Bo = B1 UB2 and Fo = F1 UF2. If <Vo, B0 , Fo> satisfies all the local constraints, the message < Vo, B0 > is sent further if no identical mes­ sages have been previously sent by the current agent .

The message passing algorithm must ensure that the scenarios be consistent with the knowledge base and their walk tree is a valid one, i.e., they must not con­ tain preempted walks. The consistency of the explana­ tions is maintained by checking the percolation and local constraints during the message passing process. The va­ lidity of the walk trees of the scenarios is guaranteed by blocking certain messages.

We define a binary relation preempted as follows: Let a be a feature link p..!... q and b be a node in 1i. preempted( a, b) is true iff 1) the path b~+p..!... q is pred ) f spec . em pte ; or 2 the path p - q - +b IS preempted.

The relation preempted is precomputed and remains unchanged as long as the plan hierarchy is unchanged. A message sent across a "isa" link c ~ b is blocked if preempted( a, b) is true, where a is the last feature link traversed by the message. A message sent across a fea­ ture link a is blocked if preempted( a, b) is true, where b is the last node traversed by the message before reaching a via a sequence of specialization link.

The message passing algorithm is shown in Figure 7. The utility functions used in the algorithm are listed and explained in Table 1. A more detailed description of the algorithm as well as its correctness proof can be found in [Lin and Goebel, 1991] .

Since no identical messages are sent across a link more than once, the total number of messages is bounded by O(Mj1il), where l1il is define to be the number of links in 1i and M is the number of distinct messages. The to­ tal number of items created is bounded by O(MI1il2d), where dis the maximum number of immediate compo­ nents a plan has.

Suppose the same set of restrictions is imposed on the plan hierarchy as in [Vilain, 1990], that is, plan com­ ponents are linearly ordered and cannot be shared or interleaved. Then the plan recognition algorithm degen­ erates to a message passing algorithm for context-free grammars [Lin and Goebel, 1990], which has complexity O(n 3 j1il), where n is the number of observations. This is a significant improvement over [Vilain, 1990] which has the complexity 0( n 3 j1ij 2 ) because l1il tends to be a large number in non-trivial domains .

Algorithm 1 Send Message sendViaFeatureLink(Node sender, Message m, Node n) foreach feature link l of sender do if (not preempted(l, n)) receive(tailOf(l), m, l); end sendVialsaLink(Node sender, Message m, FeatureLink f) foreach isa link l of sender do if (not preempted(£, tailOf(l))) receive(tailOf(l), m, l); end sendViaSpecLink(Node sender, Message m, Node n) foreach specialization link l of sender do receiveViaSpec(tailOf(l), m, n); end

Algorithm 2 Receive Message receive(Node receiver, Message m, Link b) if (isNew(receiver, m)) sendVialsaLinks(receiver, m, b) ; i +- item(m, b); for all items i' such that compatible( receiver, i', i) do i" +- combine(receiver, i, i'); if (not complete(receiver, i' )) continue; m' +- message(i") . if (not isNew(receiver, m')) continue; sendViaFeatureLinks(receiver, m', nil); sendViaSpecLinks(receiver, m', receiver); end end receiveViaSpec(Node receiver, Message m, Node b) if (isNew(receiver, m)) sendViaSpecLinks(receiver, m, b); sendViaFeatureLinks(receiver, m, b); end end

·n is a Node; i and i' are Items; m is a Message; lis a Link;

If the plan components are partially ordered, but are not shared or interleaved, the complexity of our plan recognition algorithm is the same as the complexity of direct ID (Immediate Dominance) rule parsing in lLin and Goebel, 1990], i.e. , O(n 2 11ll2d), where dis the maximum number of features of a plan type.

6 Conclusion

We have presented a message passing algorithm for plan recognition, which has an asymptotic upper bound that is an improvement on previous related work. Our repre­ sentation scheme is more general than Kautz's in its abil­ ity to accommodate optional and recursive plan compo­ nents, but more restrictive in the pattern of constraints that can be specified. The logical representation of plans is made computationally explicit as a graph structure in which plans are manifest as a special kind of graph walk. Explanations of the observations are defined to be valid scenarios that are consistent with the knowledge base and, together with knowledge base, logically entail the observations. A scenario is valid if it consists only of arguments that are the most specific with respect to the observations. In case of multiple possible explanations, the most general one is preferred over the others.

Acknowledgement

Peter van Beek has read two drafts of this paper and provided valuable comments. Thanks are also due to critics and suggestions from anonymous reviewers. This research is done while the first author is at the Depart­ ment of Computing Science, University of Alberta.