The seminal work in plan recognition (Kautz & Allen, 1986) considers a plan hierarchy, but does not deal with the uncertainty aspects of the problem. As a result, the approach can only postulate a set of possible plans for the actor, but is unable to determine which plan is more probable. Since then, the important role of uncertainty reasoning in plan recognition has been recognised (Charniak & Goldman, 1993; Bauer, 1994; van Beek, 1996),
and Bayesian probability has been argued as the appropriate model (Charniak & Goldman, 1993; van Beek, 1996). The dynamic, "on-line" aspect of plan recognition has only been recently considered (Pynadath & Wellman, 1995, 2000; Goldman, Geib, & Miller, 1999; Huber, Durfee, & Wellman, 1994; Albrecht, Zukerman, & Nicholson, 1998).  All of this recent work shares the view that online plan recognition is largely a problem of probabilistic inference in a stochastic process that models the execution of the actor's plan. While this view offers a general and coherent framework for modelling different sources of uncertainty, the stochastic process that we need to deal with can become quite complex, especially if we consider a large plan hierarchy. Thus, the main issue here is the computational complexity for dealing with this type of stochastic processes, and whether the complexity is scalable to more complex plan hierarchies.

## 1.1 Aim And Significance

In this paper, we demonstrate that the type of plan recognition problems described above scales reasonably well with respect to the number of levels of abstraction in the plan hierarchy. This is in contrast to the common-sense analysis that more levels in the plan hierarchy would introduce more variables to the stochastic process, which in turn, results in exponential complexity w.r.t the number of levels in the hierarchy.

In order to aieve this, we first assume a general stochastic model of plan execution that can model the three sources of uncertainty involved.  The model for planning with a hierarchy of abstraction under uncertainty has been developed recently by the abstract probabilistic planning community (Sutton, Precup, & Singh, 1999; Parr & Russell, 1997; Forestier & Varaiya, 1978; Hauskrecht, Meuleau, Kaelbling, Dean, & Boutilier, 1998; Dean
& Lin, 1995). To our advantage, we adopt their basic model, known as the abstract Markov policies (AMP) 1 as our model for plan execution. The AMP is an extension of a policy in Markov Decision Processes (MDP) that enables an abstract policy to invoke other more refined policies and so on down the policy hierary. Thus, the AMP is similar to a contingent plan that prescribes which sub-plan should be invoked at each applicable state of the world to achieve its intended goal, except that it can represent both the uncertainty in the plan refinement and in the outcomes of actions. Since an AMP can be described simply in terms of a state space and a Markov policy that selects among a set of other AMP's, using the AMP as the model for plan execution also helps us focus on the structure of the policy hierarchy.

The execution of an AMP leads to a special stochastic process which we called the Abstract Markov Model (AMM). The noisy observation about the environment state (e.g.,
the effects of action) can then be modelled by making the state "hidden", similar to the hidden state in the Hidden Markov Models (Rabiner, 1989).  The result is an interesting and novel stochastic process which we term the Abstract Hidden Markov Model. Intuitively, the