Controlling the Hypothesis Space in Probabilistic Plan Recognition

1 Introduction

The ability to understand the goals or plans underlying the behaviours of an observed agent, also known as plan recognition, is an important characteristic of intelligent behaviours. It is central for achieving situation awareness in many contexts, including understanding the intent of other agents we interact with. Examples of applications include user modelling [Lesh et al., 1999; Conati and VanLehn, 1996], assistive technologies [Demeester et al., 2008; Kautz et al., 2003], malicious activity detection [Geib and Goldman, 2009; Jarvis et al., 2004], and opponent intent recognition in video games [Synnaeve and Bessi`ere, 2011].

One of the main plan recognition paradigms, commonly referred to as a plan-library based approach, is to assume that the observing agent is given a plan library describing the expected behaviours of the observed agent. The plan recognition problem is thus reduced to inferring both goals and plans from the plan library that explain the observed behaviour. Approaches of this kind mainly differ on their plan representation formalisms and their inference theories and techniques. Examples include approaches based on Hierarchical Task Networks (HTN) [Geib and Goldman, 2009; Avrahami-Zilberbrand and Kaminka, 2005], probabilistic grammars [Pynadath and Wellman, 2000], Bayesian networks [Synnaeve and Bessi`ere, 2011], Hidden Markov Models [Bui et al., 2002], and Markov logic [Sadilek and Kautz, 2010].

Goals and plans can be inferred from observations and a plan library by generating or counting an exhaustive set of mutually exclusive models of plan execution that are consistent with the observed behaviour. The probability of a given goal can then be computed as a proportion of models satisfying the goal; in other words, based on the weight of the model. Such an explicit plan execution model facilitates the handling of interleaved plans or plans geared towards achieving multiple goals [Geib et al., 2008; Geib and Goldman, 2009]. However, this approach results in a combinatorial explosion of the goal and plan hypothesis space, which is intractable for most real-world applications.

Domain-specific knowledge could be used to prune or prioritize the hypothesis space in plan-library based approaches [Sukthankar and Sycara, 2008]. In this paper, we approach the problem from a different but complementary angle. We trade the slow computation of exact goal hypothesis probabilities against a quick computation of lower and upper bounds of goal hypothesis probabilities. As the computation of bounding intervals only requires a partial enumeration of plan execution models, our algorithm is able to provide early assessments of the observed agent's goals much faster than a standard model counting algorithm. The goal probability intervals shrink as processing time increases, and converge to the exact goal probability values. This is particularly useful when an agent needs to recognize the behaviours of another agent within deadlines. For example, an agent may be interested in reacting only to the goals of another agent provided that they have a probability above a given threshold. In such a case, our algorithm will provide a result as soon as the bounds cross this threshold.

In the next section, we discuss the syntax and interpretation of plan libraries. From that point, we explain the basics of a standard weighted model counting approach. This is mostly background from [Geib and Goldman, 2009], but we formulate it differently for a concise, but nevertheless precise description. We then explain the controlled generation of plan execution models. Finally, we discuss experiments and conclude with brief remarks.

2 Plan Library

A plan library is specified as a partially-ordered multiset context-free grammar (pomset CFG) [Nederhof et al., 2003].

2.1 Syntax

Definition 1. A plan library is a tuple L = 〈A,G, I,R〉, where A is a finite set of action symbols (terminals), G is a finite set of goal symbols (non terminals), I ⊆ G is a set of intendable goal symbols, and R is a set of goal-decomposition rules (production rules) of the form g → τ , where:

• g ∈ G;
• τ is a partially ordered string over the alphabet (A∪G), represented as a pair [β, C], where:
• β ∈ (A ∪ G)∗ is a string of goal and action symbols;
• C is a set of ordering constraints of the form (i, j), meaning that the ith symbol of β must precede the j th symbol of β.

A rule g → [Y0, . . . , YN,C] means that the goal g can be accomplished by achieving or executing each of the Yi in any order consistent with constraints C. A set of rules with a common left-hand side g represents alternative choices for accomplishing goal g. The specification of a plan library also supports the use of preconditions and parameters for production rules and actions. However, for the sake of conciseness, we will not use them in this paper. A pomset CFG augmented with preconditions and parameters is equivalent to traditional HTNs used in planning [Ghallab et al., 2004].

As an example, Figure 1 illustrates a plan library that is graphically displayed as an AND-OR tree. AND-nodes have an arc across the lines to their children, while ORnodes do not have such an arc. The actions are leaf nodes and the goals are interior nodes. Each rule of the form g → [Y0, ..., YN, C] is represented as an AND-node g along with children Y0, . . . , YN, such that an arrow from Yi to Yj accounts for a constraint (i, j) in C. A set of rules with a common left-hand side, g → [β0,C0], . . . , g → [βN,CN], corresponds to an OR-Node g along with children groups β0, . . . , βN, where the children in βi are linked according to Ci .

This example illustrates a plan library for the StarCraft real-time strategy (RTS) game. The example is partial and extremely simplified for illustration purposes. StarCraft players often follow rules of thumb, particularly during the opening phase. We can specify such rules in a plan library used by a game AI to recognize its opponent's goals and plans. Figure 1

illustrates rules of thumb for a player progressing on a terrain divided into four regions, which are his own base, R1 (neutral), R2 (neutral) and R3 (opponent's base). The Expand rule is a recipe for expanding the player's territory by taking control of an additional region. The Explore rule is for gathering intelligence information from the environment. The Attack rule is for destroying the opposing force. Note that by executing strategic and tactical actions to play the game, players will influence each other's behaviour. Their plans can also involve actions that achieve deceptive behaviours. However, our algorithm does not address mutual influences or detect deception. These are topics for future investigation.

2.2 Interpretation

We assume that the observed agent behaves by planning and then executing planned actions. He proceeds by first choosing a goal that is a conjunction of intendable goals, generates a plan achieving the goal, and then executes the plan. We also assume that the observing agent has a plan library L = 〈A,G, I,R〉 conveying the expected behaviours of the observed agent. We further assume there are no conflicting interdependencies between intendable goals 1 .

Under these assumptions, planning for a conjunctive goal amounts to choosing a set of production rules in the plan library that recursively expand each conjunct down into an action plan. The chosen rules for each conjunct form a complete derivation tree and the frontier of the tree is a partially ordered multiset of actions, that is, a plan [α,C], where α is the set of grammar symbols labelling the frontier, and C is a partial order progressed from rules used in the tree down to the frontier. The plan for the conjunctive goal is the frontier of the forest composed of trees. Specifically, if [αi,Ci] are the plans of trees ti for the conjuncts, the forest's plan is [α′ ,C ′ ], where α′ is the union of the αi and C ′ is the union of the Ci. A complete derivation tree (or forest) has a frontier that consists only of action symbols, representing a complete plan for achieving the tree's root goal (or forest's conjunctive goal). A partial derivation tree (or forest) has a frontier made of action and goal symbols, that is, a partial plan for achieving the tree's root goal (or forest's conjunctive goal).

1 Handling conflicts in a conjunctive goal is a difficult problem for plan-library based approaches. A workaround is to replace a conflicting conjunctive goal by a single intendable goal, while ensuring that the corresponding production rules resolve the conflict.

Figure 2 illustrates partial derivation forests for the plan library in Figure 1. Nodes are labelled either with goals or actions. A goal node g with children Y0, . . . , YN means that the rule g → [Y0, . . . , YN, C] was chosen to achieve g, with C reflected by the links between the children. We will revisit this figure later when discussing the generation of goal and plan hypotheses.

3 Basic Hypotheses Generation Algorithm

We assume the actions are observable-an assumption that can be relaxed as discussed in [Geib and Goldman, 2005], although at the expense of an additional exponential blow up in the hypothesis space. Thus, if an agent executes a plan in a library L = 〈A, G, I, R〉, then every sequence σ of observed actions is a prefix of a sequence of actions that is a particular ordering of a plan derived from a conjunctive goal. Ergo, we define a hypothesis for a sequence of observations σ as the goal and plan of a minimal derivation forest, such that the sequence of observations is a prefix of a total ordering of the plan.

Earlier complexity analysis of a plan-library based plan recognition approach suggests that the generation of hypotheses that explain a sequence of observations is at least an NPhard problem [Vilain, 1991]. A bottom-up approach, while more complicated, is on average more efficient than a topdown approach because it only generates hypotheses that are relevant to the observations. It proceeds by simulating the execution of an exhaustive set of mutually exclusive hypotheses, in synchrony with the sequence of observations (σ). This is done by generating a tree of hypotheses, as illustrated in Figure 3. The two circled frontiers illustrate breadth-first and controlled exploration strategies. At this point, we discuss the breadth-first strategy.

For a sequence of observations σ, let us note σi the observation in position i and σ[i:j] the subsequence of observations from position i to j. Each hypothesis at level i + 1 is an explanation for σ[0:i]. The root node in the hypothesis tree is the empty hypothesis. The children hc of a hypothesis hp at level i are generated by taking into account all possible ways of explaining σi, from hp. To understand how this is done, first note that each tree in a hypothesis has a multiset of enabled actions, that is, the multiset of actions having no precedence constraint in the tree's plan. We refer to this multiset as the pending set of the plan or, by extension, the pending set of the tree. These are actions pending execution by the observed agent assuming he is committed to the plan. A pending set for a hypothesis is the union of pending sets of the trees composing it.

Now, the procedure for expanding a hypothesis hp into its children hc, given the observation σi, is as follows:

• (a) Consider all possible ways of choosing and then executing an action of hp's pending set; each such possibility gives rise to a chid hc. Specifically, for each tree t in hp, if σi is in t's pending set, generate a child hc differing from hp by the fact that the action σi is trimmed from t.
• (b) Check whether σi could be the start of a new goal's execution-that is, check whether σi could be a leftmost symbol of a plan for a new goal. For each such tree t, generate a child hc from hp by adding t with the action σi trimmed off.

Figure 2 illustrates the expansions of hypotheses into some of their children. Note that step (a) requires performing a leftmost derivation of hp deep enough to derive its pending set. To efficiently check the membership of an action in a pending set, a bookkeeping optimization is to precompute actions that come first in a leftmost derivation of a plan for any goal. The actions that come first in a leftmost derivation of a plan for a given goal form the First multiset for the goal (for a goal g, we denote this by First(g)). This is a generalization to pomset CFG of a First set in traditional CFG top-down parsing [Sudkamp, 2006] 2 . Note that only the frontier of the hypothesis tree is kept in memory.

4 Computing Exact Goal Probabilities

The probability of a hypothesis and a sequence of observations (noted P(h ∧ σ)) measures the likelihood that an agent decides to execute h's plan following an action interleaving that matches σ. This probability can be used to compute the probability of a goal given the observations (noted P(g | σ)), the probability of a plan given the observation, or the probability of a behaviour (set of plans) given the observations. Here we only show how to compute P(g | σ). Using Bayes' rule, we can write:

2 Each element of a First multiset corresponds to the concept of a foot for derivation trees in [Geib et al., 2008].

Let us note Hσ the exhaustive set of mutually exclusive hypotheses for the sequence of observations to date, σ, and roots(h) the intendable goals of hypothesis h. We can rewrite the previous equation as:

To compute P(h ∧ σ), we need prior probability that the observed agent will commit to a set of intendable goals, P(goals), the goal commitment model. We also need the probability that he will choose a particular rule to achieve a goal, that is, P(rule | g), the planning model. Finally, we need the probability that he will execute an action given the current pending set, that is, P(action | PendingSet), the interleaving model. These distributions could be learned from a domain. By default, we assume that the agent selects identical goal instances by following a geometric distribution. The probability of choosing the same goal is thus independent from the goals already selected. In other words, P(goals) = ∏g∈I P(g)N (1-P(g)), where N is the number of instances of g in goals and P(g), given as input, is the a priori probability that an agent follows goal g at least once. For P(rule | g), we assume a uniform choice distribution among applicable rules. For P(action | PendingSet), we also assume a uniform choice distribution among enabled actions. As noted by [Geib and Goldman, 2009], these default distributions can be surprisingly effective in practice.

Let us note rules(h) the set of rules appearing in h and lhs(r) the left-hand side of rule r. It can be shown [Geib and Goldman, 2009] that:

P (h ∧ σ) =

where K = ∏g∈I (1 - P (g)) is the probability that an agent will not pursue more goals than he has already committed to, and PS(h, σ, i) is the pending set of h's plan after executing the first i actions of σ.

Current model counting algorithms, notably YAPPR [Geib et al., 2008] and PHATT [Geib and Goldman, 2009], enumerate all the hypotheses to compute the probability of a goal given the observations to date. Given the sequence of observations to date, σ[0:i], level i + 1 of the hypothesis tree is entirely generated (see Figure 3), and Equation (2) is applied to obtain goal probabilities. However, this exhaustive enumeration of plan execution models quickly becomes intractable.

5 Controlling the Generation of Hypotheses

In many applications, plan recognition is involved to enhance the understanding of a situation in order to decide how to react. In such cases, an agent may decide to react to another agent's goal or plan, based on whether or not the assessed probability of the goal or plan is above a certain threshold. For example, the game AI in an RTS game could decide to defend an asset or not, depending on whether or not the probability of an attack against the asset is above some threshold. In that case, instead of assessing the exact probability or expected utility of goals, it is sufficient to compute lower and upper bounds for goal probabilities. If the lower bound is above the threshold, the goal is worthy of attention. If the upper bound is below the threshold, the goal is not worth consideration. 3 At this point, we explain how to compute goal-probability bounds.

Interestingly, goal-probability bounds can be computed more efficiently than exact probabilities, without exhaustively enumerating all hypotheses. That is, by not fully expanding hypotheses to match the sequence of observations, we lose the ability to compute P(g | σ) precisely, but we can still estimate its lower and upper bounds. This idea is behind our new algorithm, the Decision-Oriented PLAn Recognizer, or DOPLAR. This algorithm expands the hypothesis tree by picking, each time, the hypothesis that weighs most in the computation of P(g | σ). The contribution of a hypothesis h to P(g | σ) is measured by P(h ∧ σ), therefore the hypothesis that has the highest value P(h ∧ σ) is always selected for the next expansion. This results in an unevenly expanded hypothesis tree, as illustrated in Figure 3.

To explain how the lower and upper bounds for P(g | σ) are calculated, we need to introduce the notion of a weight for a hypothesis. For an unevenly expanded hypothesis tree, let us note F the set of hypotheses on the frontier of the tree. For a sequence of observations σ and hypothesis h, let us also note DH(h, σ) all the descendants of h down to level |σ| of the hypothesis tree; in other words, the descendants of h that explain the sequence σ. If h is at level |σ|, then DH(h, σ) ≡ {h}. We define the weight of a hypothesis h with respect to a sequence of observations σ as follows:

An exact calculation of the weight of h requires that all of its descendants be generated down to level |σ|. Given that the principle of DOPLAR is to avoid an exhaustive exploration, it instead computes the lower and upper bounds of weight(h, σ) based on h, not its descendants. If a hypothesis h is at level |σ| (i.e., h explains σ), then its weight(h, σ) is precisely P(h∧σ). Thus, both lower and upper bounds are equal to P(h ∧ σ). The most interesting case is when h is at a level strictly less than |σ|. For this case, the lower bound is 0, because DH(h, σ) might be empty. The upper bound is given by the following lemma.

3 More generally, agents may react to goals based on the expected utility thresholds instead of probability thresholds. It would not be difficult to compute goal-utility bounds in our approach.

Lemma 1. For a hypothesis h explaining σ[0:i], with i ≤ n, weight(h, σ[0:n]) is bounded above by ub(weight(h, σ[0:n])), where:

A proof sketch for this lemma is as follows. First consider the basic case, i = n - 1, that is, when the hypothesis is one observation away from explaining σ. In order to define an upper bound on weight(h, σ[0:n]), we must consider the two steps used to expand a hypothesis (Section 3). When expanding h using elements of the pending set (step a), it can be shown that, if all potential expansions (hpe) of h match the sequence σ, then P(h ∧ σ[0:i]) = ∑hpe P (hpe ∧ σ). However, some of the children might not match the next observation, therefore the contribution of those hypotheses to weight(h, σ[0,n]) will be at most P(h ∧ σ[0:i]) or weight(h, σ[0:i]). Similarly, when expanding h by incorporating new goals (step b), it can be shown that, for each intendable goal g, the sum of P(hc ∧ σ) over all the children hc of h generated to account for g will not exceed P(h ∧ σ[0:i])P(g). Furthermore, a goal g for which σi+1 is not an element of First(g) will not produce any children for h and can be ignored for this step. This reasoning can be repeated inductively to obtain Lemma 1.

For a working hypothesis set F (i.e., the frontier of the hypothesis tree explored by DOPLAR), let us note T(F) the set of all fully expanded or terminal hypotheses in F , in other words, the hypotheses at level |σ|. We also note NT(F) the set of partially expanded or non-terminal hypotheses in F .

Theorem 1. Given a working set F over the sequence σ, we have the following lower bound on the posterior probability of a goal g:

A proof of this theorem hinges on the observation that, for a working set F over the sequence σ and a goal g, P(g | σ) will be at its minimum value when P(σ) is maximized and for each hypothesis hi in NT(F), DH(hi, σ) contains no hypothesis having a tree rooted on g. Indeed, in such a case, P(g ∧ σ) is the sum of the weight of all hypotheses in T(F) that are rooted on g. Furthermore, using Lemma 1, P(σ) can be overestimated by summing ub(weight(hi, σ)) for all hi ∈ F.

Theorem 2. Given a working set F over the sequence σ, the posterior probability of a goal g is bounded above as follows:

This theorem follows from the observation that P(g | σ) will be at its maximum value when, for each hypothesis hi in NT(F), the set DH(hi, σ) contains only hypotheses where the observed agent has g as one of his goals, and where weight(hi, σ) is maximized. Using Lemma 1, we can overestimate the contribution of a partial hypothesis hi to P (g∧σ) with ub(weight(hi, σ)). P (g ∧ σ) can then be overestimated by the sum of ub(weight(hi, σ)) for each hi ∈ T(F) and of the weight of all hypotheses in T(F) that have a plan for g. In such a case, P(σ) is at least the sum of ub(weight(hi, σ)) for each hi in F.

6 Experiments

We implemented DOPLAR in Common Lisp as an extension to YAPPR, a weighted model counting based plan recognizer that uses an HTN plan representation [Geib et al., 2008]. We tested both algorithms on artificial and simple StarCraft plan libraries, using GNU CLISP 2.48 on a quad-core Intel Core 2 Q8200 (2.33GHz) processor, running Windows 7. The tests were aimed at verifying the time and space taken by DOPLAR to recognize goals, using YAPPR as a baseline. We tested DOPLAR's two different stopping criteria: probability threshold (threshold), or error on the probability's uncertainty (error), which is the difference between the upper and lower bounds.

The artificial plan libraries were randomly generated by considering a number of plan library features that contribute to the explosion of the hypothesis space: the number of intendable goals, the nesting level of grammar rules (depth), the length of the right-hand side of grammar rules (branching factor), the number of rules sharing a left-hand side (ORchoice), the partial ordering constraints on the right-hand side of rules (constraints), and the number of actions. The grammar structure of the plan libraries is best explained by considering its AND-OR tree representation. The level of the AND-OR tree alternates between AND-nodes and OR-nodes, with the number of intendable goals set to 10, the depth to 4, the branching factor to 3, the OR-choice to 2, and with 100 unique actions. For each test, a plan library was generated with the structure just described, with terminal symbols randomly chosen among the 100 actions and the ordering constraint for each rule chosen randomly (an ordering constraint has a 33% chance of being added between any pair of symbols on the right-hand side of a rule). A sequence of observations derivable from an intendable goal was then randomly generated. Finally, the plan library and the sequence of observations were used as input for DOPLAR and YAPPR.

Figure 4 shows the results of the experiments for a sequence of 9 observations. The CPU times and number of hypotheses are plotted on a logarithmic scale. For each observation, the plotted y-value is the average over 100 tests, each involving a randomly chosen library and observation sequence. In Figure 4(a), DOPLAR computes goal-probability bounds up to the indicated threshold. Figure 4(b) shows the corresponding number of generated hypotheses. DOPLAR always performs significantly better than YAPPR except for the initial observation where DOPLAR's overhead outweighs the expansion of the initial empty hypothesis. The more observations, the larger the set of hypotheses, and the better the performance of DOPLAR compares to that of YAPPR. Assuming that an agent reacts to the goals of another agent depending on whether their probability is above a given threshold, it would be able to react much faster if it were using DOPLAR rather than YAPPR.

Figure 4: Comparison of DOPLAR and YAPPR. The x-axis is the sequence of observations (i is the ith observation of the sequence). For each observation, the value (y-axis) is an average over 100 tests. The y-axis is plotted on a logarithmic scale.

Figures 4(c) and 4(d) compare YAPPR to DOPLAR for errors on the uncertainty of goal probability computed by DOPLAR. The figures show that the exploration space can be efficiently controlled by tolerating some precision error on the goal probability using DOPLAR rather than trying to reach an exact probability using YAPPR. If DOPLAR is set to exhaustively generate all hypotheses (i.e., an error of 0), it generates the same hypotheses as YAPPR. However, as Figure 4(c) shows, the CPU time of YAPPR is slightly lower than DOPLAR's because of the overhead incurred by maintaining lower and upper goal-probability bounds. With much more complex plan libraries (obtained by increasing one of the random plan library generation parameters), YAPPR could not return any result in situations where DOPLAR was able to compute goal-probability bounds for different error values.

Tests on simplified plan libraries for the StarCraft domain produced results similar to those of the artificial domain.

7 Conclusion

We have introduced an anytime plan recognition algorithm based on weighted model counting. As for any other planlibrary based approach, the learning of plan libraries would be a significant complement to this approach.

Previous extensions to the standard weighted model counting approach to handle temporal constraints [Geib and Goldman, 2009] and goal abandonment [Geib and Goldman, 2003] remain compatible with our approach. The method handling of unobserved actions suggested in [Geib and Goldman, 2005] would also be applicable to our approach, albeit it is intractable in practice.

Future work will aim for more complex plan libraries for StarCraft and comparison between our approach and approaches that do not require plan libraries, but rather rely only on primitive actions, such as [Lis`y et al., 2012; Ram´ırez and Geffner, 2010].

Acknowledgments

This work was supported by a grant from the Natural Sciences and Engineering Research Council (NSERC) of Canada. We are grateful to Robert Goldman and John Maraist for making available their implementation of the YAPPR algorithm. We are also indebted to Philipe Bellefeuille and Francis Bisson for insightful comments on drafts of this paper.