A General Model for Online Probabilistic Plan Recognition

1 Introduction

The ability to perform plan recognition can be very useful in a wide range of applications such as monitoring and surveil­ lance, decision supports, and team work. However the plan recognizing agent's task is usually complicated by the uncer­ tainty in the plan refinement process, in the outcomes of ac­ tions, and in the agent's observations of the plan. Dealing with these issues in plan recognition is a challenging task, es­ pecially when the recognition has to be done online so that the observer can react to the actor's plan in real-time.

The uncertainty problem has been addressed by the sem­ inal work [Chamiak and Goldman, 1993] which phrases the plan recognition problem as the inference problem in a Bayesian network representing the process of executing the actor's plan. More recent work has considered dy­ namic models for performing plan recognition online [Py­ nadath and Wellman, 1995; 2000; Goldmand et al., 1999; Huber et al., 1994; Albrecht et al., 1998]. While this offers a coherent way of modelling and dealing with various sources of uncertainty in the plan execution model, the computational complexity and scalability of inference is the main issue, es­ pecially for dynamic models.

Inference in dynamic models such as the Dynamic Bayesian Networks (DBN) [Nicholson and Brady, 1994] is more difficult than in a static model. Inference in a static network utilizes the sparse structure of the graphical model to make it tractable. In the dynamic case, the DBN belief state that we need to maintain usually does not preserve the conditional independence properties of the single time-slice network, making exact inference intractable even when the DBN has a sparse structure. Thus, online plan recognition algorithms based on exact inference will run into problems when the belief state becomes too large, and will be unable to scale up to larger or more detailed plan hierarchies.

In our previous work, we have proposed a framework for online probabilistic plan recognition based on the Abstract Hidden Markov Models (AHMM) [Bui et al., 2002]. The AHMM is a stochastic model for representing the execution of a hierarchy of contingent plans (termed policies). Scal­ ability in policy recognition in the AHMM is achieved by using an approximate inference scheme known as the Rao­ Blackwellised Particle Filter (RBPF) [Doucet et al., 2000]. It has been shown that this algorithm scales well w.r.t. the number of levels in the plan hierarchy.

Despite its computational attractiveness, the current AHMM is limited in its expressiveness, in particular, its in­ ability to represent an uninterrupted sequence of plans and actions. This is due to the fact that each policy in the AHMM is purely reactive on the current state and has no memory. This type of memoryless policies cannot represent an unin­ terrupted sequence of sub-plans since they have no way of remembering the sub-plan in the sequence that is currently being executed. In other words, the decision to choose the next sub-plan can only be dependent on the current state, and not on the sub-plans that have been chosen in the past. Other models for plan recognition such that the Probabilistic State Dependent Grammar (PSDG) [Pynadath and Wellman, 2000; Pynadath, 1999] are more expressive and do not have this limitation. Unfortunately, the existing exact inference method for the PSDG in [Pynadath, 1999] has been found to be flawed and inadequate [Bui, 2002].

The main motivation in this paper is to extend the existing AHMM framework to allow for policies with memories to be considered. We propose an extension of the AHMM called the Abstract Hidden Markov mEmory Model (AHMEM). The expressiveness of the new model encompasses that of the PSDG [Pynadath and Wellman, 2000], thus the new model removes the current restriction of the AHMM. More impor­ tantly, we show that the RBPF approximate inference method used for the AHMM can be extended to the more general AHMEM as well, ensuring that the new generalized model remains computationally attractive. To the best of our knowl­ edge, we are the first to provide a scalable inference method for this general type of hierarchical probabilistic plan hierar­ chy.

The paper is structured as follows . Section 2 provides a more detailed discussion of the AHMM, PSDG and re­ lated models for online probabilistic plan recognition. The AHMEM is introduced in section 3 and the algorithms for plan recognition are presented in section 4. Experimental re­ sults with a prototype system are provided in section 5. Fi­ nally, we conclude and discuss directions for future work in section 6.

2 Related Models for Online Probabilistic Plan Recognition

In the AHMM [Bui et al., 2000; 2002], an agent's probabilis­ tic plan is modeled by an abstract Markov policy (AMP). An AMP is an extension of a policy in Markov Decision Pro­ cesses (MDP) defined within a subset of the environment state space so that it can select other more refined AMPs and so on to form a hierarchy of policies. The AMP is thus simi­ lar to a contingent plan that prescribes which sub-plan should be invoked at each applicable state of the world. The noisy observation about the environment state can be modelled by making the state "hidden", similar to the hidden state in the Hidden Markov Models [Rabiner, 1989]. The stochastic pro­ cess resulting from the execution of an AMP is termed the Ab­ stract Hidden Markov Model. Intuitively, the AHMM models how an AMP causes the adoption of other policies and ac­ tions at different levels of abstraction, which in tum generate a sequence of states and observations. In the plan recogni­ tion task, an observer is given an AHMM corresponding to the actor's plan hierarchy, and is asked to infer about the cur­ rent policy being executed by the actor at all levels of the hierarchy, taking into account the sequence of observations currently available. This problem is termed policy recogni­ tion [Bui et al., 2002].

Scalability of policy recognition in the AHMM is achieved by using a hybrid inference method, a variant of the Rao-Blackwellised particle filter (RBPF) [Doucet et al., 2000]. When applied to DBN inference, Rao­ Blackwellisation [Casella and Robert, 1996] splits the net­ work into two sets of variables: the set of variables that need to be sampled (termed the Rao-Blackwellising (RB) vari­ ables), and the set of remaining variables whose belief state conditioned on the RB variables need to be maintained via exact inference (termed the Rao-Blackwellised (RB) belief state). The RBPF thus allows us to combine sampling-based approximate inference with exact inference to achieve effi­ ciency and improve accuracy.

The Probabilistic State-Dependent Grammar (PSDG) [Py­ nadath, 1999; Pynadath and Wellman, 2000] can be described as the Probabilistic Context Free Grammar (PCFG) [Jelinek et al., 1992], augmented with a state space, and a state transi­ tion probability table for each terminal symbol of the PCFG. In addition, the probability of each production rule is made state dependent. As a result, the terminal symbol now acts like primitive actions and the non-terminal symbol chooses its expansion depending on the current state. The AHMM is equivalent to a special class of PSDG where only production rules of the form X -t Y X and X -t 0 are allowed. The first rule models the adoption of a lower level policy Y by a higher level policy X, while the second rule models the termination of the policy X. The PSDG model considered by Pynadath and Wellman allows for more general rules of the form X -t Y1 ... YmX, i.e., the recursion symbol must be located at the end of the expansion. Thus in a PSDG, a policy might be expanded into a sequence of policies at the lower level which will be executed one after another before control is returned to the higher level policy.

Although more expressive than the AHMM, the existing computational method for inference with the PSDG remains inadequate. Pynadath proposed an exact method for updat­ ing the belief state of the PSDG in a "compact" closed form. The proposed algorithm seemingly gets around the exponen­ tial blow up in the size of the belief state. Unfortunately, the derivation of the algorithm is based on a flawed assumption that the higher levels in the belief state are independent of the lower levels given the current level. For more details about the flaw in the inference algorithm for PSDG, interested read­ ers are referred to [Bui, 2002].

The AHMM, PSDG, and the proposed AHMEM are re­ lated to the Hierarchical Abstract Machines (HAM) [Parr, 1998] used in abstract probabilistic planning. In this model , the policy is represented by a stochastic finite automaton, which can call other automata at the lower level. Despite their representational similarity, the computational techniques for AHMEM and related models are intended for plan recogni­ tion whereas the HAM model is used for speeding up the pro­ cess of finding an optimal policy for MDP.

If we ignore the state dependency, the DBN structure of the AHMEM and PSDG is similar to the structure of the Hierar­ chical Hidden Markov Model (HHMM) [Fine et al., 1998; Murphy and Pashkin, 2001]. However, while the HHMM is a type of Probabilistic Context Free Grammar (PCFG), the AHMEM and PSDG are not due to the state dependency in the model.

3 The Abstract Hidden Markov Memory Models

This section introduces the Abstract Hidden Markov Mem­ ory Models (AHMEM), an extension of the AHMM where the policy can have internal memory. Our main aim is to construct a general model for plan recognition whose expres­ siveness encompasses that of the current AHMM and PSDG models, while retaining the computational attractiveness of the AHMM framework. We first define the AHMEM in sub­ section 3.1. The DBN structure of the new model is given in subsection 3.2.

3.1 The Model

Consider an MDP-like model with S representing the states of the environment, and A representing the set of primitive actions available to the agent. Each action a E A is defined by its transition probability from the current states to the next states': aa(s, s'). The set of abstract policies will include every primitive actions. Furthermore, the AHMM [Bui et al.,

2000] defines higher level abstract policies on top of a set of policies as follows:

Definition 1 (Abstract Markov Policy (AMP)). Let II be a set of AMPs, an AMP 1r* over II is defined as a tuple (S"., D"., (3"., IJ"·) where:

• S". C U1rEilS" is the set of applicable states.
• D". C U"EnD" is the set of destination states.
• (3". : D". -+ (0, 1] is the set of stopping probabilities such that (3". (d) = 1, V dE D". \ S" ·.
• IJJr· : s1f. X II -+ [0, 1] is the selection function where IJ"· (s, 1r) is the probability that 1r* selects the policy 1r at the state s.

An AMP as defined above is purely reactive, in the sense that it selects the next policy at the lower level based only on the current state s. This restricts the set of behaviours that an AMP can represent. For example, it will not be able to represent a plan consisting of a few sub-plans, one followed by another regardless of the state sequence. To represent this kind of plans, the agent needs to have some form of inter­ nal memory to remember the current stage of execution. Let M be a set of possible internal memory states. We first ex­ tend the definition of our policy to include a memory variable which takes on values in M and is updated after each stage of execution of the policy. 1

Definition 2 (Abstract Markov Policy with Memory (AMPE)). Let II be a set of AMPEs, an AMPE 1r* over II is defined as a tuple (S"., D"., (3"., IJ"·, z;.., IJ;..) where:

• S". C U1rEilS" is the set of applicable states.
• DJr. c u7rEilD7r is the set of destination states.
• (3". : D". x M -+ (0, 1] is the terminating proba­ bility. (3". ( d, m) is the probability that the policy 1r* would stop if the current state is d and the current mem­ ory value is m.
• IJJr· : s1f. X M X II-+ [0, 1] is the policy selection prob­ ability. IJ "* ( s, m, 1r) is the probability that 1r* selects the policy 1r at the state s and memory value m.
• z;.. : s1f. X M -+ [0, 1] is the initial distribution of memory values. z;.. (s, m) is the probability that the ini­ tial memory ism if 1r* commences at states.
• IJ;.. : s1f. X M X M -+ [0, 1] is the memory transi­ tion probability. IJ;.. (s, m, m') is the probability that the next memory value is m' given that the current memory value ism and the current state iss.

Subsequently, we will drop the subscript 1r* if there is no confusion about the policy in the context. Note that all the states in D \ S are called terminal states and thus (3(d, m) = 1, V m E M, d E D \ S. Also, the policy selection, memory initial and transition probability have to be proper probability distributions, i.e. I;"ETI !J(s, m , 1r) = 1, I:mEM ze(s, m) = 1, and I:m'EM !Je(s, m, m') = 1.

1 0ne can argue that we can always incorporate the memory vari­ able in the environment state, and hence we gain no extra represen­ tational power just by introducing the memory variables. However, incorporating the memory variables in the state variable would blow up the size of the state space and thus defeat our purpose of keeping the model computationally feasible.

When an AMPE 7r* is executed from a state s, it first initialises its memory value m according to the distribution ze(s,m). Then a policy at the lower Jevel1r will be selected according to the distribution iJ(s , m, 1r). This policy 1r will be executed until it terminates at some state s'. At the new state s', the policy 1r* itself will terminate with probability (3 ( s', m). If it does not terminate, the memory variable will be given a new value m' according to the transition probabil­ ity !Je(s',m,m'). Then a new policy at the lower Ievel1r 1 is selected with probability 1J( s', m', 1r 1 ) and so on.

Using the AMPEs, we can construct a hierarchy of abstract policies in the same way as in the AHMM. We start with a set of primitive actions II0 = A, and fork = 1, ... , K build a set of new AMPEs Ilk on top of Ilk_1 . Then, if a top-level policy 1rK is executed, it invokes a sequence of levei-(K-1) policies, each of which invokes a sequence of Jevel-(K-2) policies and so on. A Ievel-l policy will invoke a sequence of primitive actions which leads to a sequence of states. We can then in­ troduce the hidden states and model the noisy observation of the state by an observation model Pr( Ot I St) = w( St, Ot). The dynamic process of executing a top-level AMPE is termed the Abstract Hidden Markov mEmory Model (AHMEM).

Some special cases of the AHMEM are worth mention­ ing here. First, the AHMM itself is a special AHMEM. The memoryless policies of the AHMM are equivalent to AM­ PEs where the dependency on the memory variable is ignored (e.g. when M is a singleton set). The class of PSDG con­ sidered in [Pynadath, 1999] can also be easily converted to an AHMEM. The terminal symbols in the PSDG are equiv­ alent to the primitive actions. Each non-terminal symbol is equivalent to a memory less policy. In addition, each sequence Y = Y1 Y2 .. . Yn encountered on the RHS of a production X -+ Y1 Y2 . . . Yn or X -+ Y1 Y2 ... YnX is equivalent to a policy whose memory m taking on the values 1, ... , n. Y then simply selects the (memoryless) policy Y; if m = i .

Note that in the AHMEM definition, we assume a balanced policy hierarchy for the ease of presentation (all the actions must appear at the same bottom level). However, we can also specify an unbalanced hierarchy by introducing some dummy policies which are equivalent to primitive actions at the higher levels in the hierarchy .

3.2 DBN Representation of the AHMEM

The DBN structure of an AHMEM is very similar to that of an AHMM: at each time slice t, the variable St represents the current state, 7rf, k = 0, . .. , K represents the current pol­ icy at all levels, ef represents whether 7rf terminates at the current time, and lt = max{klef = T} denotes the highest level of termination. In addition to these variables, we need to introduce the memory variable mf for k ~ 1 to repre­ sent the current memory value of the policy 7rf (the primitive action 1r~ has no memory). The 2-time-slice DBN is given in Fig. 1. The structure of this network is described below. Note that if x is a variable, we use the notation Xi:j to denote the sequence (x; , x;+l, ... , Xj ), and similarly xi:j to denote ( . +1 ") x', x' ... , xJ .

Policy Termination and Selection

The policy termination and selection model for the AHMEM is essentially the same as in the AHMM, except for the depen­ dency on the value of the current memory variable m~ . We note that the same context specific independence [Boutilier et al., 1996] properties of the AHMM still hold. For example, if e~-l = F then e~ = F and e~ becomes independent of the remaining parents of this variable. Now consider the variable ·n{ If eL1 = F then 7rf = 1rL1 and 7rf is independent of the . . h . P ( k I k+l k+l) remammg parents; ot erwtse, r 1ft 1ft , St-l, mt ( k+l k) d k . . d d f k 17 .,.k+' St - 1, mt , 1ft an 1ft ts m epen ent o 1ft-l· t

Memory Update

Consider the variable m~. There are two parents of this node that act like context variables: e~.=-l and eL1. If e~_=:-1 1 = F, the policy at the lower level has not terminated and memory is not updated at this time. Thus, m~ = mL1 , and m~ becomes independent of all the remaining parents. If e~.=-l = T then there are two cases. If eL 1 = F, the policy at level k continues from the previous time, and thus the memory value will be updated according to the memory transition model: Pr(mf 17rf,st-l,mL1) = 17~k(st-l,mL 1 ,mn. Ife~_1 = t T, the policy at level k has just started at state St-1 , and thus the memory value will be initialised: Pr(m~ l1rf, St-d = ~ e k (st-l, m~). In this case, m~ is independent of the previ-.,., ous memory value mL 1 .

3.3 Independence Properties in the AHMEM

Even though AMPEs are more expressive than memoryless policies, they remain "autonomous", in the sense that the higher layers have no influence over the state of an AMPE during its execution. The only way the higher layers can influ­ ence the current state of an AMPE is through the conditions at the start: either through the starting state or the starting time. Thus, the conditional independence theorem for poli­ cies in the AHMM still holds in this more general setting. We state the theorem for the AHMEM below. The proof for the AHMM [Bui et al., 2002] can be directly extended to this general case using the context specific independence proper­ ties described in the previous subsection.

Theorem 1. Let Ttk and b~ be two random variables repre­ senting the starting time and the starting state, respectively, of the current level-k policy 7rf: Ttk = max{ t' < tI e~, = T} and b~ = Srk. Then given the policy 7rf and its starting t state and time, the set of current policies and memories at the higher levels are independent of the set of current policies, memories and state at the lower level:

Let rt = (st, lt) . Note that knowing ll:t-l is equivalent to knowing precisely when each of the policies starts and ends. Therefore, given TJ:t-l, the starting time and state of every current policy are known. The following corollary is thus a direct consequence of theorem 1.

Corollary 1. Let Ct represent the conditional joint distribu­ tion Pr(1r~ : K, m~'K, St I r1:t- 1 ). Then Ct has the following Bayesian network factorization:

Ct thus also has the following undirected network repre­ sentation. We first form the set of cliques: c0 = { 1r? , St}, Ck = { 7rf, m~, 1rt-l }, k = 1. .. , K . Note that the set of cliques co:K form a chain of cliques in this order, therefore we term Ct the policy-clique chain. This extends the concept of the policy chain in the memory1ess case of the AHMM [Bui et al., 2000]. Ct can be factored into the product of potentials on these cliques: Ct <X TI~=O 1/Jk(ck)· When 1/Jk = Pr(7rf, m~ l1r;-l, rl:t_t) and 1/Jo = Pr(1r? , St I TJ:t-1), i.e. when the potential factorization is the same as the directed network factorization, the potentials are said to be in canoni­ cal form. Any potential representation of the clique chain can be canonicalized by first perform message passing (exact in­ ference) to compute the marginal at each clique. The canoni­ cal form can then be computed directly from these marginals. Later on we will use the undirected representation of Ct for exact inference, and the canonical form (directed representa­ tion) of Ct for obtaining samples from the joint distribution using simple forward sampling.

4 Approximate Inference for AHMEM

In this section, we look at the online inference prob­ lem in the AHMEM. Assume that at time t, we have a sequence of observations about the environment state ol:t-1 = (ol, ... ,Ot-1). Weneedtocomputethebe­ lief state of the DBN which is the joint distribution of all the current variables given this observation sequence: Pr(1r?'K, m~ ' K, St, lt, Ot I OJ:t-d. From this, we can answer various queries about the current status of the plan execution.

For example, the marginal probability of 1r~ tells us about the current policy the actor is executing at some level k; the pro~ability Pr(~~ 11rp tells us ab~~t the current stage of ex­ ecutiOn of a policy 1rt ; the probability Pr( ez l1rt} tells us if 1r~ will end after the current time, etc.

Since there is no compact closed form representation for the above belief state, exact inference in the structure of the AHMEM is intractable when K is large. How­ ever, theorem 1 suggests that we can apply the Rao­ Blackwellised Particle Filter (RBPF) to this problem in a sim­ ilar way as in the AHMM [Bui et al., 2002], i.e. by us­ ing rt as the Rao-Blackwellising (RB) variables. The Rao­ Blackwellised ( RB) belief state is then similar to the origi­ nal belief state of the AHMEM, except that now rl:t_1 are known: Bt = Pr(1rr:K, mfK, lt, St, Ot I rl:t_r). Note that the RB belief state Bt can be obtained directly from the policy-clique chain Ct by adding in the network represent­ ing the conditional distribution of Ot and ef'K, i.e. Bt = Pr( efK l1r?'K, mfK, st) Pr( Ot I St)Ct (see Fig. 2).

Two main steps in the RBPF procedure are: ( 1) updating the RB belief state using exact inference, and (2) sampling the RB variable rt from the current RB belief state.

4.1 Updating the RB Belief State

Fig. 2 shows the modified 2-time-slice DBN when the RB variables are known (St = s, lt = l). We note that all the nodes from above level l remain unchanged, while all the links across time slices from level l and below can be re­ moved. This greatly simplifies the network structure, allow­ ing the updating operations to be performed efficiently.

Since the Bt can be obtained directly from Ct. all we have to do is to compute Ct+1 from Ct. The procedure for updating as usual has two stages: (1) absorbing the new evidence, i.e. from Ct. we need to compute Ct+ = Pr( 1r?'K, mf'K I rl:t); and (2) projecting to the new time slice, i.e. from Ct+· we need to compute Ct+l·

In principle, we apply a simplified version of the junction­ tree algorithm [Jensen, 1996] on the undirected network rep­ resentation of Ct to perform the update step. This is in fact a generalization of the arc-reversal procedure which operates on directed network representation of the policy chain in the AHMM [Bui et al., 2002]. The algorithm for updating the RB belief state is given in Fig. 3. The absorbing step involves simply incorporating the evidence likelihood into the poten­ tials of Ct to obtain the potentials for Ct+· The projecting step involves first adding time-slice t + 1 to Ct+ (see Fig. 2), then marginalizing the now redundant variables 1r?' 1 , m~:l+l in the old time slice. The marginalization is done by perform­ ing message passing between the cliques of the 2-time-slice network shown in Fig. 2.

Since the potentials of Ct from level l + 2 to level K stay unchanged, the complexity of the algorithm is O(l) where lis the highest level of termination. Furthermore, if one of these potentials is in canonical form, it remains in canonical form after the updating procedure.

4.2 RBPF for AHMEM

The full RBPF algorithm for policy recogmtwn in the AHMEM is provided in Fig 4. The general structure is the same as the RBPF procedure for AHMM [Bui et al., 2002]. At each time step t, the algorithm maintains a set of N sam­ ples, each consists of a value for St- 1 and lt_1 , and a para­ metric representation of Ct . The differences are in the details of how to obtain new samples and update the RB belief state.

To obtain each new sample (st , lt). we first need to canoni­ calize the potentials of Ct. However, assuming that Ct_1 is in canonical form, we only have to canonicalize the potentials of Ct between level 0 and Ievell + 1 with complexity O(l). Thus the complexity of the sampling step is O(Nl) . Since the complexity of the updating step is also O(Nl), the overall complexity of the algorithm at each time step is O(Nl). Fur­ thermore, the distribution for l usually decays exponentially, thus the average complexity is only O(N).

If at some time t, an estimation e.g. Pr( 1r{' I 01:t-d is required, we need to compute h = Ct(7r{') for each sam­ ple. This involves performing message passing for the entire chain Ct. Thus the complexity for this time step is O(N K). Other types of queries are also possible, as long as the proba­ bility required can be computed from the RB belief state. For example, we can ask the question: if the actor is currently executing 1r~, what is the current stage of execution of this policy? To answer this query, we need to compute the con­ ditional probability Pr(m~ l1r~, ol:t_1). This can easily be achieved by replacing the h function in the algorithm with h = Ct(mZI7rt}.

5 Experimental Results

We have implemented the above algorithm in a surveillance domain to demonstrate its working in a practical application. The environment consists of a spatial area which has two sep­ arate rooms and a corridor monitored by a set of 5 cameras (Fig. 5). The monitored area is divided into a grid of cells, and the cell coordinates constitute the overall state space S . The coordinates returned by the cameras are modelled as the noisy observations of the true coordinates of the tracked per­ son, and over time, provide the sequence of observations ol:t .

At the top-level, each policy models a type of activity per­ formed by the person. For example, print is a policy that involves a sequence of going to the computer and the printer, possibly going to the paper store if the printer is out of paper, and exiting. Note that this policy cannot be represented in the AHMM framework. In the AHMEM, this can be represented by a policy whose memory transition model is given in Fig. 6. The policies at the lower level, such as going to a computer, model the person's trajectories toward a set of special land­ marks in the environment. These policies are constructed as memoryless policies in the same way as in the AHMM [Bui etal.,2002].

The result of querying the top-level policy for the trajec­ tory in Fig. 5 is given in Fig. 7. The system correctly identi­ fies the most probable policy as print. The result of querying the memory variable of this policy is given in Fig. 8. The sys­ tem correctly identifies the sequence of lower-level policies invoked by the print policy. These results are obtained by running the RBPF algorithm with 3000 samples. The aver­ age processing time for each observation is approximately 0.9 seconds on a 1.7GHz desktop machine. For a more detailed description of this surveillance system, readers are referred to [Nguyen et al., 2003] .

6 Conclusion

In conclusion, we have presented the Abstract Hidden Markov Memory Models (AHMEM), a general framework for representing and recognizing probabilistic plans online. The new framework extends the AHMM by allowing the poli­ cies to have internal memories which are updated in a Markov fashion. This allows the AHMEM to represent a richer set of hierarchical probabilistic plans, including those belonging to the class of PSDG previously considered. Furthermore, we have shown that the Rao-Blackwellised Particle Filter (RBPF) approximate inference method used for the AHMM can be extended to the AHMEM, resulting in efficient and scalable procedures for plan recognition in this general set­ ting. Our work demonstrates the advantage of phrasing prob­ abilistic plan recognition as inference in DBN so that suitable approximate methods can be employed to cope with the com­ plexity issue. A similar approach can be applied to more gen­ eral models to consider more complex plan constructs such as multi-agent plans, interleaving plans etc.