
## 1.2  Structure Of The Paper

The main body of the paper is organised as follows. Section 2 introduces the background material in dynamic Bayesian networks and probabilistic inference. Section 3 formally defines the abstract Markov policy and the policy hierary. Section 4 presents the AHMM,
its DBN representation and conditional independence properties. The algorithms for policy recognition are discussed in Section 5, first for the special tractable case and then for the general case. Section 6 presents our experimental results with the AHMM framework, including a real-time system for recognising people behaviour in a complex spatial environment using distributed video surveillance data. Section 7 provides a comparative review of related work in probabilistic plan recognition. Finally, we conclude and discuss directions for further research in Section 8.

## 2. Background In Probabilistic Inference

The aim of this section is to familiarise readers with some concepts in probabilistic inference that will be used later on in the paper. In subsections 2.1 and 2.2, we discuss Bayesian Networks (BN) and Dynamic Bayesian Networks (DBN) in general. In subsection 2.3, we discuss the Sequential Importance Sampling (SIS) algorithm, a general approximate sampling-based inference method for dynamic models. Subsections 2.4 and 2.5 introduce Rao-Blackwellisation, a technique for improving sampling-based methods by utilising certain special structures of the dynamic model. Later on, Rao-Blackwellisation will be used as our key computational technique for performing policy recognition.

## 2.1   Bayesian Networks

The Bayesian network (BN) (Pearl, 1988; Jensen, 1996; Castillo, Gutierrez, & Hadi, 1997)
(also known as probabilistic network or belief network ) is a well-established framework for dealing with uncertainty. It provides a graphical and compact representation of the joint probability distribution of a set of domain variables X 1 , . . . X n in the form of a directed acyclic graph (DAG) whose nodes correspond to the domain variables.  For each node Xi, the links from the parent nodes Pa(Xi) are parameterised by the conditional probability of that node given the parents Pr(Xi | Pa(Xi)). The network structure together with the parameters encode a factorisation of the joint probability distribution (JPD)
Pr(X 1 , . . . X n ) = Π i =1 Pr(X i | P a i ).  Given a Bayesian network, conditional independence statements of the form X ⊥ Y | Z (X is independent of Y given Z, where X, Y, Z are variables or sets of variables) can be asserted if X is d-separated from Y by Z in the network structure, where d-separation is a graph separation concept for DAGs (Pearl, 1988). The nnetwork structure of a BN thus captures certain conditional independence properties among the domain variables which can be exploited for efficient inference.

The main inference task on a Bayesian network is to calculate the conditional probability of a set of variables given the values of another set of variables (the evidence). There are two types of computation techniques for doing this. Exact inference algorithms (Lauritzen
& Spiegelhalter, 1988; Jensen, Lauritzen, & Olesen, 1990; D'Ambrosio, 1993) compute the exact value of the conditional probability required based on analytical transformation that exploits the conditional independence relationships of the variables in the network.