AHMM models how an AMP causes the adoption of other policies and actions at different levels of abstraction, which in turn generate a sequence of states and observations. In the plan recognition task, an observer is given an AHMM corresponding to the actor's plan hierarchy, and is asked to infer about the current policy being executed by the actor at all levels of the hierarchy, taking into account the sequence of observations currently available.

This amounts to reversing the direction of causality in the AHMM, i.e. to determine a set of policies that can explain the sequence of observations at hand. We shall refer to this problem as policy recognition.

Viewing the AHMM as a type of dynamic Bayesian network (Dean & Kanazawa, 1989; Nicholson & Brady, 1992), it is known that the complexity of this kind of inferencing in the D D N  depends on the size of the representation of the so-called belief state, the conditional joint distribution of the variables in the DBN at time t given the observation sequence up to t (Boyen & Koller, 1998). Thus we can ask the following question: how does the policy hierarchy affect the size of the belief state representation of the corresponding AHMM?

Generally, for a policy hierarchy with K levels, the belief state would have at least K variables and thus the size of their joint distribution would be O(exp(K)). However, the AHMM has a specific network structure that exhibits certain conditional independence properties among its variables which can be exploited for efficiency. We first identify these useful independence properties in the AHMM and show that there is a compact representation of the special beliefstate in the case where the state sequence can be correctly observed (full observability assumption) and the starting and ending time of each policy is known.

Consequently, policy recognition in this case can be performed very efficiently by updating the AHMM compact belief state. This partial result, although too restricted to be useful by itself, leads to an important observation about the general belief state: although it cannot be represented compactly, it can be approximated efficiently by a collection of compact special belief states. This makes the inference problem in the AHMM particularly amenable to a technique called Rao-Blackwellisation (Casella & Robert, 1996) which allows us to construct hybrid inference methods that combine both exact inference and approximate sampling-based inference for greater efficiency. The application of Rao-Blackwellisation to the AHMM structure reduces the sampling space that we need to approximate to a space with fixed dimension that does not depend on K , ensuring that the hybrid inference algorithm scales well w.r.t K.

The contributions of the paper are thus twofold. In terms of stochastic processes and dynamic Bayesian networks, we introduce the AHMM, a novel type of stochastic processes, provide its DBN structure and analyse the properties of this network. We present an application of the Rao-Blackwellised Particle Filter to the AHMM which results in an efficient hybrid inference method for this stochastic model. In terms of plan recognition, we propose a novel plan recognition framework based on probabilistic inference using the AHMM as the plan execution model. The complexity of the inference problem is addressed by applying a range of recently developed techniques in probabilistic reasoning to the plan recognition problem. Our work illustrates that while the stochastic models for plan execution can be complex, they exhibit certain special structures that can be exploited to construct efficient plan recognition algorithms.