%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%	Document class
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\documentclass[jair,twoside,11pt]{article}

\usepackage{jair}
\usepackage{theapa}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%	Packages used
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\usepackage{aaai}
%\usepackage{times}
%\usepackage{amstex}
\usepackage{amsopn}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{ifthen}
%\usepackage{euscript}
%\input{psfig}
\usepackage{epsfig}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%	Other options
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% allow page break in the middle of multiline form
\allowdisplaybreaks[1]


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%	Generic definitions
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\input{/home/jb/Latex/Definitions/generic_article.tex}
%\input{/usr/project/fury/buihh/Phd/Doc/Latex/Definitions/generic_article.tex}
%\input{generic_article.tex}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%	Generic definitions, to be "input"ed into every document
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  Theorem-like definitions
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\theoremstyle{plain}
\newtheorem{corollary}{Corollary}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  Commands
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



% comments
\newcommand{\rem}[1]
	%{}
	{\vspace{0.5\baselineskip} \noindent {\sffamily \slshape #1}}

% force to change spacing, used inside document body only
\newcommand{\changespace}[1]{
	\renewcommand{\baselinestretch}{#1}
	\small\normalsize
	}

% such that
\newcommand{\st}{\ensuremath{\text{ s.t }}}

% short hand for \overline
\newcommand{\ovl}{\overline}

% imply
\newcommand{\imply}{\ensuremath{\Rightarrow}}

% raisebox, useful in mid-row entry in column
\newcommand{\rb}[1]{\raisebox{1.5ex}[1ex]{#1}}

% frame box
\newcommand{\fb}[1]{\fbox{#1}}

% cross through a character
\newcommand{\cx}[1]{\makebox[0pt][l]{/}#1}

% tuple
\newcommand{\tuple}[1]{
	\ensuremath{\left \langle #1 \right \rangle}
	}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  Environments
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%
% This provides a rudimentary environment for writing algorithm.
% It can be encapsulated in floating environment, such as table.
% Indentation is provided by \q command.
% Caption is provided by \algocaption, which works with label and ref
% as usual, but cannot yet generate list of algorithms.
%

\newcommand{\q}{\qquad}

\newcounter{algo}

\newcommand{\algocaption}[1]
	{
	\refstepcounter{algo}
	\begin{center}
		Algorithm \thealgo: #1
	\end{center}
	}

\newenvironment{algorithm}
	{\begin{tabular}{|l|}\hline\hfill\\}
	{\\ \hfill\\ \hline\end{tabular}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  Theorem-like definitions
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\theoremstyle{plain}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{guess}{Conjecture}

\theoremstyle{definition}

\newtheorem{definition}{Definition}
\newtheorem{defn}[definition]{Definition}
\newtheorem{assume}{Assumption}
\newtheorem{example}{Example}
\newtheorem{proposition}{Proposition}

\theoremstyle{remark}

\newtheorem{remark}{Remark}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  Notations
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\newcommand{\bigO}{\ensuremath{O}}

\newcommand{\const}{\ensuremath{\text{const}}}

\newcommand{\card}[1]{\ensuremath{\vert #1 \vert}}

\newcommand{\union}{\cap}

\newcommand{\intsect}{\cup}

\newcommand{\reals}{\ensuremath{\mathbb{R}}}
\newcommand{\realsplus}{\ensuremath{\reals_{+}}}

\newcommand{\rarr}{\ensuremath{\rightarrow}}

\newcommand{\defeq}{\ensuremath{\stackrel{\mathrm{def}}}}

\newcommand{\powset}[1]
	{\ensuremath{2^{#1}}}

% random variable
\newcommand{\Rv}[1]{\ensuremath{\text{\it #1}}}

% expected value
\DeclareMathOperator*{\ev}{E}

% variance
\DeclareMathOperator*{\variance}{VAR}

% the set of all (total) mappings from #1 to #2
\newcommand{\mapto}[2]
	{\ensuremath{{#2}^{\vert #1 \vert}}}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%	Private definitions
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\input{polrec_notation.tex}

% generic

\newcommand{\rx}{\ensuremath{\Rv{x}}}

\newcommand{\CPr}[2]{\ensuremath{\Pr(#1 \, \vert \, #2)}}

%\newcommand{\upidx}[2]{\ensuremath{#1^{(#2)}}}

%\newcommand{\tem}[2]{\upidx{#1}{#2}}

\newcommand{\sq}[1]{\ensuremath{\tilde{#1}}}
\newcommand{\tsq}[2]{\ensuremath{\sq{#1}_{#2}}}

%\newcommand{\tsq}[1]{\ensuremath{\tilde{#1}}}

\newcommand{\true}{\ensuremath{\text{\it true}}}
\newcommand{\false}{\ensuremath{\text{\it false}}}

\newcommand{\pind}{\ensuremath{\perp}}
\newcommand{\cind}{\ensuremath{\vec{\perp}}}

%\newcommand{\imply}{\ensuremath{\rightarrow}}

% private


%
% graphs stuffs
%

%\newcommand{\gr}{\ensuremath{\mathcal{G}}}
%\newcommand{\vic}{\ensuremath{\text{\it vic}}}

%
% location, and spatial stuff
%

%\newcommand{\locs}{\ensuremath{\mathcal{L}}}
%\newcommand{\rank}{\ensuremath{r}}

%\newcommand{\BPEM}{BPEM}

%\newcommand{\LDPN}{LDPN}

%\newcommand{\SEM}{SEM}

%\newcommand{\sem}{\ensuremath{\sigma}}
\newcommand{\tran}{\ensuremath{\sigma}}
\newcommand{\dest}{\ensuremath{d}}
\newcommand{\Dest}{\ensuremath{D}}
\newcommand{\State}{\ensuremath{S}}
\newcommand{\AllState}{\ensuremath{\State^{+}}}

\newcommand{\pol}{\ensuremath{\pi}}
%\newcommand{\polt}[1]{\ensuremath{\pol^{(#1)}}}
%\newcommand{\polst}[2]{\ensuremath{\polt{#2}_{#1}}}
\newcommand{\polt}[1]{\ensuremath{\pol_{#1}}}
\newcommand{\polst}[2]{\ensuremath{\polt{#2}^{#1}}}
\newcommand{\hpolst}[2]{\ensuremath{\sq{\pol}^{#1}_{#2}}}

\newcommand{\toppol}{\ensuremath{\pol^K}}

\newcommand{\Pol}{\ensuremath{\Pi}}
\newcommand{\HPol}{\ensuremath{\mathcal{H}}}

%\newcommand{\sini}{\ensuremath{\sem^{(0)}}}

%\newcommand{\GPM}{GPM}

%\newcommand{\gpm}{\ensuremath{\gamma}}

%\newcommand{\OM}{OM}

\newcommand{\om}{\ensuremath{\omega}}

\newcommand{\model}{\ensuremath{\lambda}}


\newcommand{\obs}{\ensuremath{o}}

%\newcommand{\obst}[1]{\upidx{\obs}{#1}}
\newcommand{\obst}[1]{\ensuremath{\obs_{#1}}}

\newcommand{\obss}{\ensuremath{O}}

\newcommand{\hobs}{\ensuremath{\sq{\obs}}}

%\newcommand{\hobst}[1]{\ensuremath{\hobs^{(#1)}}}
\newcommand{\hobst}[1]{\ensuremath{\hobs_{#1}}}

%\newcommand{\goal}{\ensuremath{g}}

%\newcommand{\goalt}[1]{\upidx{\goal}{#1}}

%\newcommand{\goals}{\ensuremath{G}}

%\newcommand{\goalgr}{\ensuremath{\gr^{g}}}

%\newcommand{\goalend}{\ensuremath{\goal_{\text{end}}}}

%\newcommand{\sg}{\ensuremath{g}}
%\newcommand{\sgt}[2]{\upidx{\sg_{#1}}{#2}}

%\newcommand{\plan}{\sq{\goal}}

\newcommand{\state}{\ensuremath{s}}

%\newcommand{\statet}[1]{\upidx{\state}{#1}}
\newcommand{\statet}[1]{\ensuremath{\state_{#1}}}

\newcommand{\states}{\ensuremath{S}}

%\newcommand{\stategr}{\ensuremath{\gr^{s}}}

\newcommand{\beg}{\ensuremath{b}}

%\newcommand{\ach}{\ensuremath{a}}
%\newcommand{\acht}[1]{\upidx{\ach}{#1}}

%\newcommand{\slice}{\ensuremath{c}}
%\newcommand{\slicet}[1]{\upidx{\slice}{#1}}

%\newcommand{\achst}[2]{\upidx{\ach_{#1}}{#2}}

%\newcommand{\topg}{\ensuremath{\sg_{\text{\it top}}}}

%\newcommand{\topgt}[1]{\upidx{\topg}{#1}}

\newcommand{\tfin}{\ensuremath{\tau}}

\newcommand{\tcur}{\ensuremath{c}}

%\newcommand{\finm}{\ensuremath{\mu}}

\newcommand{\Sample}{\ensuremath{\mathcal{S}}}

\newcommand{\weight}{\ensuremath{w}}
\newcommand{\trueweight}{\ensuremath{\dot{\weight}}}
\newcommand{\normweight}{\ensuremath{\tilde{\weight}}}

\newcommand{\bs}{\ensuremath{\mathcal{B}}}
\newcommand{\bst}[1]{\ensuremath{\bs_{#1}}}

\newcommand{\rbst}[1]{\ensuremath{\mathcal{R}_{#1}}}

\newcommand{\chain}{\ensuremath{\mathcal{C}}}
%\newcommand{\chaint}[1]{\ensuremath{\chain^{(#1)}}}
\newcommand{\chaint}[1]{\ensuremath{\chain_{#1}}}

\newcommand{\clup}{\ensuremath{{}_\uparrow\psi}}
\newcommand{\clupt}[1]{\ensuremath{\clup^{(#1)}}}
\newcommand{\clupst}[2]{\ensuremath{\clupt{#2}_{#1}}}

\newcommand{\cldown}{\ensuremath{{}_\downarrow\psi}}
\newcommand{\cldownt}[1]{\ensuremath{\cldown^{(#1)}}}
\newcommand{\cldownst}[2]{\ensuremath{\cldownt{#2}_{#1}}}

\newcommand{\marg}{\ensuremath{\mu}}
%\newcommand{\margt}[1]{\ensuremath{\marg^{(#1)}}}
%\newcommand{\margst}[2]{\ensuremath{\margt{#2}_{#1}}}
\newcommand{\margt}[1]{\ensuremath{\marg_{#1}}}
\newcommand{\margst}[2]{\ensuremath{\margt{#2}^{#1}}}

\newcommand{\Action}{\ensuremath{A}}
\newcommand{\action}{\ensuremath{a}}
\newcommand{\reward}{\ensuremath{r}}
\newcommand{\stopp}{\ensuremath{\beta}}

\newcommand{\etran}{\ensuremath{\bar{\tran}}}

\newcommand{\pend}{\ensuremath{e}}
%\newcommand{\pendt}[1]{\ensuremath{\pend^{(#1)}}}
%\newcommand{\pendst}[2]{\ensuremath{\pendt{#2}_{#1}}}
\newcommand{\pendt}[1]{\ensuremath{\pend_{#1}}}
\newcommand{\pendst}[2]{\ensuremath{\pendt{#2}^{#1}}}

\newcommand{\topend}{\ensuremath{l}}
\newcommand{\topendt}[1]{\ensuremath{\topend_{#1}}}
\newcommand{\htopend}{\ensuremath{\sq{\topend}}}
\newcommand{\htopendt}[1]{\ensuremath{\htopend_{#1}}}

\newcommand{\polend}{\ensuremath{\stackrel{.}{\state}}}
%\newcommand{\polendt}[1]{\ensuremath{\polend^{(#1)}}}
%\newcommand{\polendst}[2]{\ensuremath{\polendt{#2}_{#1}}}
\newcommand{\polendt}[1]{\ensuremath{\polend_{#1}}}
\newcommand{\polendst}[2]{\ensuremath{\polendt{#2}^{#1}}}

%\newcommand{\ongoing}{\ensuremath{\oslash}}

\newcommand{\btime}{\ensuremath{\tau}}
%\newcommand{\btimet}[1]{\ensuremath{\btime^{(#1)}}}
%\newcommand{\btimest}[2]{\ensuremath{\btimet{#2}_{#1}}}
\newcommand{\btimet}[1]{\ensuremath{\btime_{#1}}}
\newcommand{\btimest}[2]{\ensuremath{\btimet{#2}^{#1}}}

%\newcommand{\etime}{\ensuremath{T}}
%\newcommand{\etimet}[1]{\ensuremath{\etime^{(#1)}}}

\newcommand{\bstate}{\ensuremath{b}}
%\newcommand{\bstatet}[1]{\ensuremath{\bstate^{(#1)}}}
%\newcommand{\bstatest}[2]{\ensuremath{\bstatet{#2}_{#1}}}
\newcommand{\bstatet}[1]{\ensuremath{\bstate_{#1}}}
\newcommand{\bstatest}[2]{\ensuremath{\bstatet{#2}^{#1}}}

\newcommand{\factored}{\ensuremath{\mathcal{F}}}

%\newcommand{\estate}{\ensuremath{d}}
%\newcommand{\estatet}[1]{\ensuremath{\estate^{(#1)}}}

\newcommand{\partn}{\ensuremath{\mathcal{P}}}

\newcommand{\hstate}{\ensuremath{\sq{\state}}}
%\newcommand{\hstatet}[1]{\ensuremath{\hstate^{(#1)}}}
\newcommand{\hstatet}[1]{\ensuremath{\hstate_{#1}}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%	Document starts
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\jairheading{17}{2002}{451-499}{12/00}{12/02}
\ShortHeadings{Policy recognition in the Abstract Hidden Markov Model}
{Bui, Venkatesh \& West}
\firstpageno{451}


\begin{document}

\bibliographystyle{theapa}

%\input{polrec_body.tex}
%
% paper starts here
% =================

\renewcommand{\rem}[1]{}

%\input{tr_title.tex}

%\title{On the Recognition of Abstract Markov Policies}
\title{Policy Recognition in the Abstract Hidden Markov Model}

%\author {Hung H. Bui, Svetha Venkatesh and Geoff West \\
%	Department of Computer Science \\
%	Curtin University of Technology \\
%	PO Box U1987, Perth, WA 6001, Australia \\
%	\{buihh, svetha, geoff\}@cs.curtin.edu.au\\
%	}

\author
	{\name Hung H. Bui \email buihh@cs.curtin.edu.au\\
	\name Svetha Venkatesh \email svetha@cs.curtin.edu.au\\
	\name Geoff West \email geoff@cs.curtin.edu.au\\
	\addr
	Department of Computer Science \\
   Curtin University of Technology \\
	PO Box U1987, Perth, WA 6001, Australia \\
	}
\date{}

\maketitle

%{\large On the Recognition of Abstract Markov Policies}

\begin{abstract}


%Abstraction plays an essential role in the way the agents plan their
%behaviours, especially to reduce the computational complexity of planning
%in large domains. However, the effects of abstraction in 
%the inverse process -- plan recognition -- are unclear. 

In this paper, we present a method for recognising an agent's 
behaviour in dynamic, noisy, uncertain domains, and across multiple levels 
of abstraction.  We term this problem 
{\em on-line plan recognition under uncertainty} and view it generally 
as probabilistic 
inference on the stochastic process representing the execution of the 
agent's plan. Our contributions in this paper are twofold.
In terms of probabilistic inference, we introduce the 
Abstract Hidden Markov Model (AHMM), a novel
type of stochastic processes, provide its dynamic Bayesian network (DBN)
structure and analyse the properties of this network. 
We then describe an
application of the Rao-Blackwellised Particle Filter to the AHMM
which allows us to construct an efficient, hybrid inference method for this
model.
In terms of plan recognition, we propose a novel plan recognition framework
based on the AHMM as the plan execution
model. 
The Rao-Blackwellised hybrid inference for AHMM
%to construct an efficient, hybrid inference method that
%to construct hybrid inference methods that 
%take advantage of the tractable sub-structures present
%in the DBN.
can take advantage of the independence
properties inherent in a model of plan execution, leading to
an algorithm for online probabilistic plan recognition
that scales well with the number of levels in the plan hierarchy.
This illustrates that while stochastic models for plan execution can be
complex, they exhibit special structures which, if exploited, can lead
to efficient plan recognition algorithms.
We demonstrate the usefulness of the AHMM framework via a behaviour
recognition system in a
complex spatial environment
using distributed video surveillance data.




%We propose the use of the Abstract Hidden Markov Model
%(AHMM) as a general model for plan execution the associated noisy
%observation. We investigate this novel type of stochastic processes and
%provide an efficient hybrid inference


%We use
%the concept of abstract Markov policies in abstract probabilistic planning
%as the model of the agent's behaviours and employ probabilistic inference
%in Dynamic Bayesian Networks (DBN) to infer the correct policy from a 
%sequence of observations. When the states are fully observable, 
%we show that for a broad and often-used class of abstract policies, the 
%complexity of policy recognition scales well with the number of abstraction
%levels in the policy hierarchy. For the partially observable case, we derive 
%an efficient hybrid inference scheme on the corresponding DBN to 
%overcome the exponential complexity.








%We are interested in the problem of monitoring the behaviour of an agent in 
%noisy, uncertain domains, whose state space is large, and possibly
%over a long period of time. 



%Our main approach is first, to construct a probabilistic model of the agent's 
%behaviour in the domain similar to those being used for probabilistic 
%planning with abstraction. The model relates the possible behaviours with
%the observation obtained during the monitoring process. We then apply
%probabilistic inference to infer the conditional probabilities for various
%possible behaviours given the observation at hand.
%The contributions of the paper are two-fold. First, we describe the Hidden
%Layered Markov Model (HLMM), a Bayesian network representation of the 
%model being used in probabilistic planning with abstraction, and derive 
%some of its conditional probabilistic independence properties. 
%Second, we present an efficient hybrid algorithm for
%performing probabilistic inference in this type of networks.
%These results are then combined in the design of a system for tracking and 
%monitoring movement of people in wide-area spatial environments.

%\begin{center}
%{\bf Keywords:} Plan Recognition, Bayesian Networks \\
%{\bf Paper No: A171}
%\end{center}


\end{abstract}


\section{Introduction}

%\subsection{The Plan Recognition Problem}

Plan recognition is the problem of inferring an actor's plan by watching
the actor's actions and their effects. Often, the actor's behaviour follows
a hierarchical plan structure. Thus, in plan recognition, the observer
needs to infer about the actor's plans and sub-plans at 
different levels of abstraction in its plan hierarchy.
The problem is complicated by the two sources of uncertainty 
inherent in the actor's planning process:
(1) the stochastic aspect of plan refinement (a plan can be
non-deterministically refined into different sub-plans),
and (2) the stochastic outcomes of actions (the same action can 
non-deterministically result in different outcomes). 
Furthermore, the observer has to deal with a third source of uncertainty
arising from the noise and inaccuracy in its own observation 
about the actor's plan. In addition, we would like our observer to be able
to perform the plan recognition task ``on-line'' while the observations about
the actor's plan are streaming in.
We refer to this general problem as {\em on-line plan recognition under
uncertainty}.  



\rem{how others have approached this? - remaining problem}

The seminal work in plan recognition~\cite{KaA86} 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~\cite{ChG93,Bau94,Bee96},
and Bayesian probability has been argued as the 
appropriate model~\cite{ChG93,Bee96}.
The dynamic, ``on-line'' aspect of plan
recognition has only been recently 
considered~\cite{PyW95,PyW000,GGM99,HDW94,AZN98}.
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.

\subsection{Aim and Significance}

\rem{aim}

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.

\rem{approach}

\rem{amp as model of plan execution}

In order to achieve 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~\cite{SPS99,PaR97,FoV78,HMKDB98,DeL95}. To our advantage,
we adopt their basic model, known as the 
{\em abstract Markov policies (AMP)}~\footnote
{Also known as {\em options}, {\em policies of 
Abstract Markov Decision Processes}, or
{\em supervisor's policies}.}
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 hierarchy. 
%The concept originates from the abstract probabilistic planning literature
%as a way to scale up MDP-based planning to domains whose state spaces
%are large. 
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.

\rem{ahmm and policy recognition}

The execution of an AMP leads to a
special stochastic process which we called the {\em 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~\cite{Rab89}.
The result is an interesting and novel stochastic 
process which we term the {\em Abstract Hidden Markov Model}.
Intuitively, the 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 {\em policy recognition}. 
%to emphasise the aspect of
%uncertainty in the plan recognition problem that we consider.

\rem{complexity of policy recognition}

Viewing the AHMM as a type of dynamic Bayesian
network~\cite{DeK89,NiB92},
%In policy recognition,
%we need to reverse the direction of causality in the AHMM 
%and compute the conditional probability of the current policies 
%at different levels in the hierarchy given an observation sequence. 
it is known that the complexity of this kind of inferencing in the 
DBN depends on 
the size of the representation of the so-called {\em belief state}, the
conditional joint distribution of the variables in the DBN at time $t$ 
given the observation sequence up to $t$~\cite{BoK98}. 
Thus we can ask the
following question: how does the policy hierarchy affect the size of the
belief state representation of the corresponding AHMM? 

\rem{solution}

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 belief state
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
{\em Rao-Blackwellisation}~\cite{CaR96}
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.



%Using conditional independence relations on
%the network, we show that 
%if at some level of abstraction, the set of applicable domains of all 
%the policies forms a partition of the full state space. As a
%consequence, if the AMP is constructed through the region-based decomposition
%of the state space as in~\cite{FoV78,DeL95,HMKDB98}, 
%its belief state can be represented compactly as a chain in the fully
%observable case, facilitating very efficient inferencing. 
%Based on this result, for the
%partially observable case, we derive a hybrid inference scheme 
%combining both exact inference as in the fully observable case, and
%sampling-based approximate inference to handle the noisy observation. 
%We provide experiment results showing the hybrid inference scheme 
%achieving much better accuracy/time ratio than the original sampling-based
%inference~\cite{KKR95}.


\subsection{Structure of the Paper}

The main body of the paper is organised as follows. 
Section~\ref{sec:background} introduces the background material 
in dynamic Bayesian networks and probabilistic inference.
Section 3
formally defines the abstract Markov policy and the policy
hierarchy.
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. 
%Here we also describe the use of Rao-Blackwellisation to construct
%hybrid inference for general DBN, with the AHMM being a special
%case. 
%Section 5 discusses a specific application of the AHMM framework
%to the problem of surveillance in wide-area environment. 
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.


%Computationally, we view policy recognition as probabilistic inference 
%on the Dynamic Bayesian Network representing the execution of the AMP 
%(together with the noisy observation of states in the partially observable 
%case). 


%While planning their behaviours in large domains, the agents often have to
%employ abstraction techniques to reduce the complexity associated with 
%large state spaces. As a consequence, their behaviours often follow a
%hierarchical plan structure. 


%In this paper, we address the problem of recognising such a policy --
%the inverse of the abstract probabilistic planning problem, i.e.
%to infer the underlying abstract policy from the external observation 
%of the induced behaviour.
%%policy execution process.

%\rem{relates to plan recognition}

%The problem can be classified under the umbrella of key-hole plan
%recognition~\cite{CPA81,KaA86}
%where the agent who carries out the plan (the actor) is not
%aware that it is being observed. The recent trend in approaching this
%problem is first constructing a probabilistic model for the plan 
%execution, and then employing abductive reasoning techniques such as
%probabilistic (Bayesian) inference to infer the underlying plan from the
%observation sequence~\cite{HDW94,GGM99}. To represent the evolution 
%of the plan over time, some authors~\cite{FHK95,PyW95,AZN98} 
%have employed the Dynamic Bayesian Network (DBN)~\cite{DeK89,NiB92} as the 
%framework for inferencing.
%All of this work in plan recognition uses a hierarchical structure 
%of plans and actions. However, to the best of our knowledge, the 
%question of how the structure of a plan hierarchy would affect the complexity
%of the recognition process has not been investigated.

%influence of the structure of the plan hierarchy on the complexity of the 
%recognition process has not been investigated.

%\rem{come back to our approach}

%In our approach, 

% removed to save space!!!!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%Our approach is motivated by the problem of monitoring and tracking human
%movement in large spatial domains~\cite{BuiVW99}. In this type of
%problems, in addition to the uncertainty in plan execution
%(e.g. indeterministic action selection, 
%actions with uncertain outcomes), 
%there is also the uncertainty 
%in the observation process that can be attributed to noisy sensors, 
%incorrect, or the lack of information available to the observer. 
%For example, a
%visual surveillance system has to deal with the noise in the cameras which
%might lead to incorrect information about the position of people on the
%ground. 

%Throughout the paper, we make the assumption that only the 
%states (which bear the effects of actions) can be observed, 
%but not the actions themselves. Thus, the policy recognition problem can be
%divided into two cases: when state observations are certain 
%({\em fully observable}), and when the observations are partial and uncertain
%({\em partially observable})~\footnote
%{This only means that the external observer has partial information. Our
%model however assumes that the actor always has full information about the
%current state.}.

\section{Background in Probabilistic Inference}
\label{sec:background}

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.


\subsection{Bayesian Networks}

The {\em Bayesian network} (BN)
~\cite{Pea88,Jen96,CGH97} 
(also known as {\em probabilistic network} or {\em 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,\ldots X_n$ in the form of
a directed acyclic graph (DAG) whose nodes correspond to the domain variables.
For each node $X_i$, the links from the parent nodes $Pa(X_i)$
are parameterised by the
conditional probability of that node given the parents
$\CPr{X_i}{Pa(X_i)}$. 
The network structure together with the parameters 
encode a factorisation of the
joint probability distribution (JPD) 
$\Pr(X_1,\ldots X_n) = \prod_{i=1}^{n} \CPr{X_i}{Pa_i}$. 
Given a Bayesian network, conditional independence
statements of the form $X \pind 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~\cite{Pea88}.  
The network 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~\cite{LaS88,JLO90,DAm93}
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.
Approximative inference 
algorithms~\cite{Pea87,Yor92,Hen88,FuC89,ShP89}
compute only an approximation of the required probability, usually obtained
either through ``forward'' 
sampling~\cite{Hen88,FuC89,ShP89} 
(a variance of Bayesian Importance Sampling~\cite{Gew89}), 
or through Gibbs (Monte-Carlo Markov-Chain) sampling~\cite{Pea87,Yor92}.
These algorithms have the advantages of simple implementation,
can be applied to all types of network, and 
can trade off the accuracy in the estimates for computation
resources. It is known that exact inference in BN is NP-hard 
with respect to the
network size~\cite{Cop90}, while approximate inference, 
although scales well with the
network size, is NP-hard with respect to the hard-bound accuracy of the 
estimates~\cite{DaL93}. In the light of these theoretical results, 
approximate inference can be useful in large networks when
exact computation is intractable, but a certain
degree of error in the probability estimate 
can be tolerated by the application.
%is tolerable.



%Sometimes, a large network can be split
%into different regions, some suitable for performing exact inference, some
%for inexact inference. Such a hybrid inference scheme may have the
%advantage of combining the best of the two inferencing methods by making
%the inference task still tractable while reducing the error
%margins~\cite{DKL95}. 
%The inference algorithm for the AHMM presented here can be thought
%of as a hybrid inference scheme of this kind.


\subsection{Dynamic Bayesian Networks}

To model the temporal dynamics of the
environment, the Dynamic Bayesian Network
(DBN)~\cite{DeK89,NiB92,DGH92} is a special
Bayesian network architecture for representing the evolution of the domain
variables over time. A DBN consists of a sequence of time-slices where each
time-slice contains a set of variables representing the state of the 
environment at the current time. A time-slice is in itself a Bayesian
network, with the same network structure replicated at
each time-slice. 
The temporal dynamics of the environment is encoded via the network links 
from one time-slice to the next.
In addition, each time-slice can contain observation nodes which model the
(possibly noisy) observation about the current state of the environment.

Given a DBN and a sequence of observations, we might want to draw 
predictions about the future state variables (predicting), or about the 
unobserved variables in the past (smoothing)~\cite{Kja92}. This problem can 
be solved using an inference algorithm for Bayesian networks described
above.  However, if we want to revise the prediction as the 
observations arrive over time,
reapplying the inference algorithm each time the observation sequence
changes could be costly, especially as the sequence grows.
To avoid this, we need to keep the joint
distribution of all the variables in the current time-slice, given the
observation sequence up to date. This probability distribution is termed
the {\em belief state} (also known as the {\em filtering distribution})
and plays an important role in inferencing in the DBN. 
All existing inference schemes for the DBN
involve maintaining and updating the belief state (i.e., filtering).
When a new observation is received, the current belief state is
rolled over one time-slice ahead following the evolution model, then 
conditioned on the new observation to obtain the updated belief state.

An obvious problem with this approach is the size of the belief state
that we need to maintain. It has been noted that while the interaction of
the variables in the DBN is localised, the variables in the belief state
can be highly connected~\cite{BoK98}. This is because the marginalisation
of the past time-slices usually destroys the conditional independence of the
current time-slice. When the size of the belief state is large, exact
inference methods like~\cite{Kja95} is intractable, 
and it becomes necessary to maintain only an approximation of the 
actual belief state, either in the 
form of an approximate distribution that can be represented 
compactly~\cite{BoK98}, 
or in the form of a set of weighted samples as in the 
Sequential Monte-Carlo Sampling methods~\cite{DGA000,KKR95,LiC98}.

The most simple case of the DBN where, in each time-slice, there 
is only a single
state variable and an observation node, is the well-known Hidden Markov 
Model (HMM)~\cite{Rab89}. Filtering in this simple structure can be solved
using dynamic programming in the discrete HMM~\cite{Rab89}, or
Kalman filtering in the linear Gaussian model~\cite{Kal60}.
More recently, extensions of the HMM with multiple
hidden interacting chains such as the Coupled Hidden Markov Models (CHMM) and 
the Factorial Hidden Markov Models (FHMM) have been 
proposed~\cite{Bra97:tr,GhJ97,JGS97}. In these models, the size of the
belief state is exponential in the number of hidden chains. Therefore, 
the inference and parameter estimation problems become intractable 
if the number of hidden chains is large.
For this reason, approximate techniques are required.
CHMM~\cite{Bra97:tr} employs a deterministic approximation that approximates full
dynamic programming by keeping only a fixed number of ``heads'' with
highest probabilities. The ``heads'' are thus chosen deterministically
rather than randomly as in sampling-based methods.
FHMM~\cite{GhJ97,JGS97} uses variational
approximation~\cite{JGJ000} which approximates the full FHMM
structure by a sparsified tractable structure. This idea is similar to the
structured approximation method in~\cite{BoK98}.

Our AHMM can be viewed as a 
type of Coupled/Factorial HMM since the AHMM also
consists of a number of interacting chains. 
However the type of interaction in our AHMM is different from the 
other types of 
interaction that have been considered~\cite{Bra97:tr,JGS97,GhJ97}. This is
because the main focus of the AHMM is the dynamics of temporal abstraction
among the chains, rather than the correlation between them at the same time
interval. 
In
addition, each node in the AHMM has a specific meaning (policy, state,
or policy termination status),
and the links have a clear causal interpretation based on 
the policy selection and persistence model.
This is in contrast to the Coupled/Factorial HMM where the
nodes and links usually do not have any clear 
semantic/causal interpretation.
The advantage is that prior knowledge about the temporal decomposition of an
abstract process can be incorporated in the AHMM more naturally.

\subsection{Sequential Importance Sampling (SIS)}
\label{subsec:sis}

Sequential Importance Sampling (SIS)~\cite{DGA000,LiC98}, also known as 
Particle Filter (PF), is a general  Monte-Carlo approximation scheme for 
dynamic stochastic models.
In principle, the SIS method is the same as the 
so-called Bayesian Importance Sampling (BIS)
estimator in the static case~\cite{Gew89}.
Suppose that we want to
estimate the quantity $\bar{f} = \int f(x)p(x)dx$, i.e., the mean of 
$f(x)$ where $x$ is a random variable with density $p$. 
Note that if $f$ is taken as the identity function of an event $A$ then
$\bar{f}$ is simply $\Pr(A)$.
Let $q(x)$ be an arbitrary\footnote{For the weight to be properly defined, 
the support of $q$ has to be a subset of the support of $p$.} 
density function, termed the 
{\em importance distribution}.
Usually, the importance distribution $q$ is 
chosen so that is it easy to obtain random samples from it. The expectation
under estimation can then be rewritten as:
\[
\bar{f} = 
\frac
{\int [f(x)p(x)/q(x)] q(x) dx}
{\int [p(x)/q(x)] q(x) dx}
=
\frac
{\ev_q f(x)p(x)/q(x)}
{\ev_q p(x)/q(x)}
\]
From this expression, the BIS estimator w.r.t $q$ can be obtained:
\[
\bar{f} \approx 
\hat{f}_{BIS} = 
\frac
{\frac{1}{N}\sum_{i=1}^N f(x^{(i)}) \trueweight(x^{(i)})}
{\frac{1}{N}\sum_{i=1}^N \trueweight(x^{(i)})}
= \sum_{i=1}^N f(x^{(i)}) \normweight(x^{(i)})
\]
where $\{x^{(i)}\}$ are the $N$ i.i.d samples taken from $q(x)$, 
$\trueweight(x) = p(x)/q(x)$ and \normweight\ is the normalised weight
$\normweight(x^{(i)}) = 
\trueweight(x^{(i)})/\sum_i \trueweight(x^{(i)})$. Note that 
the normalised weight can be computed from any weight function 
$\weight(x) \propto \trueweight(x)$, i.e.,
the weight function need only be
computed up to a normalising constant factor.

In the dynamic case, we want to estimate 
$\bar{f} = \int_{\tsq{x}{t}} f(\tsq{x}{t}) p(\tsq{x}{t}|\tsq{o}{t})$ where 
$\tsq{x}{t} = (x_0,\ldots,x_t)$ and $\tsq{o}{t} = (o_0,\ldots,o_t)$ 
are two sequences of random variables; $o_t$ 
represents the observation available to us at time $t$.
Often, $(\tsq{x}{t})$ is a Markov sequence
and $o_t$ is the observation of $x_t$ as in a HMM. 
In a DBN, $x_t$ corresponds to the set of state variables 
and $o_t$ corresponds to the set of observations at time-slice $t$. 
The SIS method presented here however applies to the most general case
where $(\tsq{x}{t})$ can be non-Markov, and $o_t$ not only depends
on $x_t$.

We now can introduce the importance distribution 
$q(\tsq{x}{t} | \tsq{o}{t})$ to obtain the estimator:
\begin{equation}
\bar{f} \approx
\hat{f}_{SIS} =
\sum_{i=1}^N f(\tsq{x}{t}^{(i)}) \normweight(\tsq{x}{t}^{(i)})
\label{eqn:sis}
\end{equation}
To ensure that we can obtain sample from 
$q(\tsq{x}{t} | \tsq{o}{t})$ ``online'', i.e., to sample a new value
$x_t$ for the sequence $\tsq{x}{t}$ when the current observation $o_t$
arrives, $q$ must be restricted to the form:
\[
q(\tsq{x}{t} | \tsq{o}{t}) = 
q(\tsq{x}{t-1} | \tsq{o}{t-1}) 
q(x_t | \tsq{x}{t-1}, \tsq{o}{t})
\]
With this restriction on $q$, we can use the weight function
$\weight(\tsq{x}{t}) = p(\tsq{x}{t}, \tsq{o}{t})/q(\tsq{x}{t}|\tsq{o}{t})$ 
so that the weight can also be updated ``online'' using:
\begin{equation}
\weight(\tsq{x}{t}) = \weight(\tsq{x}{t-1})
p(x_t,o_t|\tsq{x}{t-1},\tsq{o}{t-1})/q(x_t|\tsq{x}{t-1},\tsq{o}{t})
\label{eqn:sis-weight}
\end{equation}

 
Let $w_t = w(\tsq{x}{t})/w(\tsq{x}{t-1})$ be the weight updating factor 
at time $t$, and $q_t = q(x_t|\tsq{x}{t-1},\tsq{o}{t})$ be the sampling
distribution used at time $t$. From (\ref{eqn:sis-weight}) we have
\begin{equation}
w_t q_t = p(x_t,o_t|\tsq{x}{t-1},\tsq{o}{t-1})
%, \text{of if } (\tsq{x}{t},\tsq{o}{t}) \text{ is a HMM: }
%w_t q_t = p(x_t,o_t|x_{t-1})
\label{eqn:weight-imdist}
\end{equation}
which means that $p(x_t,o_t|\tsq{x}{t-1},\tsq{o}{t-1})$ is factorised into
two parts: $w_t$ and $q_t$. By choosing different factorisations, we obtain
different forms for $q_t$ and thus different important distributions $q$.
For example, when $(\tsq{x}{t},\tsq{o}{t})$ is a HMM, $q_t$ can be chosen
as $p(x_t|x_{t-1})$ with $w_t = p(o_t|x_t)$ as in the likelihood weighting
(LW) method, or $q_t$ can be chosen as $p(x_t|x_{t-1},o_t)$ with
$w_t = p(o_t|x_{t-1})$ as in the likelihood weighting with evidence reversal
(LW-ER)~\cite{KKR95}. In general, 
the ``forward'' $q_t$ can be chosen as $p(x_t|\tsq{x}{t-1},\tsq{o}{t-1})$
with the corresponding weight $w_t$ = $p(o_t|\tsq{x}{t},\tsq{o}{t-1})$.
The ``optimal'' $q_t$, in the sense discussed 
in~\cite{DGA000}, is chosen as $q_t = p(x_t|\tsq{x}{t-1},\tsq{o}{t})$
with the associating $w_t=p(o_t|\tsq{x}{t-1},\tsq{o}{t-1})$.

The general SIS approximation scheme is thus as follows. At time $t-1$, 
we maintain $N$ sample sequences $\{\tsq{x}{t-1}^{(i)}\}$ and the $N$
corresponding weight values $\{\weight^{(i)}\}$. When the current
observation $o_t$ arrives, each sequence $\tsq{x}{t-1}^{(i)}$ is lengthened
by a new value $x_t^{(i)}$ sampled from the distribution 
$q(x_t | \tsq{x}{t-1}^{(i)}, \tsq{o}{t})$. The weight value for 
$\tsq{x}{t}^{(i)}$ is then updated using~(\ref{eqn:sis-weight}). Once the
new samples and the new weights are obtained, the expectation of any
functional $f$ can be estimated using~(\ref{eqn:sis}). This procedure can
be furthered enhanced with a re-sampling step and a Markov-chain sampling
step (see~\citeA{DGA000,DFM000}). We do not describe these important
improvements of the SIS here.\footnote{Note that these improvements can be
used orthogonal to the Rao-Blackwellisation procedure discussed
subsequently. Our implementation of the policy recognition algorithm 
in the later sections does include a 
re-sampling step, which is crucial for keeping the error of SIS over time
under control.}


\subsection{Rao-Blackwellisation}

Rao-Blackwellisation is a general technique for improving the accuracy of
sampling methods by analytically marginalising some variables
and only sampling the remainder~\cite{CaR96}. 
In its simplest form, consider the problem of estimating the expectation 
$\ev f(x)$, where $x$ is a joint product of two variables $r,z$.
Using direct Monte-Carlo sampling, we obtain the estimator: 
$\hat{f} = \frac{1}{N} \sum_{1}^{N} f(r^{(i)},z^{(i)})$. 
Alternatively, a Rao-Blackwellised
estimator can be derived by sampling only the variable $r$, with
the other variable $z$ being integrated out analytically:
\[
\ev f(r,z) = \ev_r h(r) \approx \hat{f}_{RB} = \frac{1}{N}\sum_{1}^{N} h(r^{(i)})
\]
where $h(r) = \ev_z [f(r,z)| r]$. For our convenience, $r$ will be referred
to as the {\em Rao-Blackwellising variable}.

The Rao-Blackwellised estimator
$\hat{f}_{RB}$ is generally more accurate than $\hat{f}$ for the same
number of samples $N$. This is a direct consequence of the 
Rao-Blackwell theorem which gives the relationship
between unconditional and conditional variance: 
\[
\variance X = \variance [\ev [X|Y]] + \ev [\variance [X|Y]]
\]
When applying to the problem of estimating $\ev f(r,z)$, we have:
\[
\variance f(r,z) = \variance [\ev [f(r,z) | r]] + \ev [\variance
[f(r,z)|r]]
\]
and thus 
$\variance f(r,z) \ge \variance [\ev [f(r,z) | r]] = \variance h(r)$.
This suggests that for direct Monte-Carlo sampling, 
the error of RB-sampling (sample only $r$ and marginalise $z$) is
always smaller than the error of sampling both $r$ and $z$ for the same
number of samples, except in the degenerated case. 
For Bayesian Importance Sampling, using the
variance convergence result from~\cite{Gew89}, one can also easily prove
that as the number of samples tend to infinity, the RB-BIS would 
generally do better than BIS for the same number of samples. 

\subsection{SIS with Rao-Blackwellisation (RB-SIS)}
\label{subsec:rb-sis}

\rem{the problem}

Since SIS is a form of BIS,
Rao-Blackwellisation can also be used to improve its 
performance~\cite{LiC98,DGA000}.  
Let us consider again the problem of estimating the 
expectation $\bar{f} = \int f(\tsq{x}{t}) p(\tsq{x}{t}|\tsq{o}{t})$,
where each variable $x_t$ is the joint product of two variables $(z_t, r_t)$.  
We shall restrict ourselves to the case where \tsq{x}{t} is Markov 
and $o_t$ is an observation of $x_t$, i.e., when $(\tsq{x}{t},\tsq{o}{t})$ 
can be represented by a DBN.
In addition, we only consider $f$ that depends only on the current variable
$x_t$, i.e., $\bar{f}$ is an expectation over the filtering distribution
$p(x_t | \tsq{o}{t})$. For example, if $A$ is a ``future'' event, i.e., an
event that depends on $\{x_{t'} | t' \ge t\}$, we can estimate
$p(A|\tsq{o}{t})$ by
letting $f(x_t) = p(A|x_t)$ so that $\bar{f} = \int_{x_t}
p(A|x_t)p(x_t|\tsq{o}{t}) = p(A|\tsq{o}{t})$.

\rem{general RB ideas}

Applying Rao-Blackwellisation to this setting,
we can let $h(\tsq{r}{t}) = \int_{z_t} f(z_t,r_t) p(z_t |
\tsq{r}{t},\tsq{o}{t})$, so that
$\bar{f} = \bar{h} = \int_{\tsq{r}{t}} h(\tsq{r}{t}) p(\tsq{r}{t}|\tsq{o}{t})$.
Thus, if we use SIS to estimate $\bar{h}$, we also obtain an estimator 
for $\bar{f}$:
\begin{equation}
\bar{f} \approx \hat{f}_{RBSIS} = \hat{h}_{SIS} = 
\sum_{i=1}^N h(\tsq{r}{t}^{(i)}) \normweight(\tsq{r}{t}^{(i)})
\end{equation}

\rem{trade off}

The benefit of doing this is the increase in the accuracy of the
estimator, as we now only need to sample the variables $\tsq{r}{t}$.
The down side is that for each sample \tsq{r}{t}, we need to 
compute $h(\tsq{r}{t})$ using some exact inference method. Furthermore, 
the SIS procedure to estimate $\bar{h}$ might require some additional 
complexity since the sequence \tsq{r}{t} is generally non-Markov,
and $o_t$ no longer depends only on $r_t$. 
Overall, in comparison with the normal SIS estimator $\hat{f}_{SIS}$
(Eq.~\ref{eqn:sis}), for the same number of samples $N$, 
$\hat{f}_{RBSIS}$ is more accurate but is also more computationally
demanding to compute. 

%Rao-Blackwellisation allows us to gain more accuracy with the cost of the
%extra computational time. Thus, Rao-Blackwellisation is only useful if the
%added complexity required is minimal.


%The RB-SIS estimator is fundamentally an SIS estimator of the
%expectation $\bar{h}$.  Although the RB-SIS method only needs to sample the 
%variables \tsq{r}{t} (and thus is more accurate), 
%for each sample \tsq{r}{t}, 



%To estimate $\bar{f}$, a normal SIS method would need to sample
%both $\tsq{r}{t}$ and $\tsq{z}{t}$. In a RB-SIS method, we only sample the
%Rao-Blackwellising variables \tsq{r}{t} and integrating out the remaining
%variables $\tsq{z}{t}$ analytically.



%For Rao-Blackwellisation to be useful, we need to be able to do two things
%efficiently:
%(1) perform the integration in $h(\tsq{r}{t})$ and (2) sample $\tsq{r}{t}$
%and update its weight.




%RB-SIS is thus useful only in some special cases where it is both simple to
%perform SIS to estimate $\bar{h}$ and to calculate each term
%$h(\tsq{r}{t})$.
%The most general formulation of RB-SIS up-to-date~\cite{DFM000,Mur000} 
%assumes that the Rao-Blackwellising variables \tsq{r}{t} is a Markov sequence,
%and the remaining variables \tsq{z}{t} are the children of \tsq{r}{t}. In
%this setting, sampling \tsq{r}{t} would be simple, and given \tsq{r}{t},
%it becomes easier to marginalise \tsq{z}{t} using an exact inference
%method. 


% which trivialises the second 
%requirement. Since this assumption does not hold when Rao-Blackwellisation
%is applied to the AHMM, we need to look at the precise condition 
%in which both requirements can be satisfied.

To see more clearly what is involved in implementing the RB-SIS method, let us
look at the {\em Rao-Blackwellised belief state}, i.e., the belief state of
the dynamic process when the Rao-Blackwellising variables can be observed:
$\rbst{t} = p(z_t,r_t,o_t | \tsq{r}{t-1}, \tsq{o}{t-1})$ and its posterior
$\rbst{t+} = p(z_t | \tsq{r}{t},\tsq{o}{t})$. 
All the entities needed in the RB-SIS procedure can be computed from
these two distributions. Indeed,
the functional $h$ can be rewritten in terms of \rbst{t+} as:
\begin{equation}
h(\tsq{r}{t}) 
%= 
%\int_{\tsq{z}{t}} f(z_t,r_t) p(\tsq{z}{t} |
%\tsq{r}{t},\tsq{o}{t})
=
\int_{z_t} f(z_t,r_t) p(z_t | \tsq{r}{t},\tsq{o}{t})
=
\int_{z_t} f(z_t,r_t) \rbst{t+}(z_t)
\label{eqn:h-rb}
\end{equation}
In addition, while performing SIS to estimate $\bar{h}$,
from Eq.~(\ref{eqn:weight-imdist}),
the weight $w_t$ and the sampling distribution $q_t$ can be computed from
\rbst{t}:
\begin{equation}
w_t q_t = p(r_t, o_t| \tsq{r}{t-1}, \tsq{o}{t-1}) = 
\rbst{t}(r_t,o_t) = \int_{z_t} \rbst{t}(z_t,r_t,o_t)
\label{eqn:wtqt-rb}
\end{equation}

Thus, computing the RB belief state \rbst{t} and its posterior \rbst{t+} 
is an essential step in the RB-SIS method. Since we have to maintain an 
RB belief state for each sample of the RB variables \tsq{r}{t}, 
it is crucial that this can be done efficiently using an exact inference 
method. If $x_t$ is composed of many variables, as in the case of a DBN, 
our choice of the Rao-Blackwellising variables should be so that
the Rao-Blackwellised belief state can be maintained in a tractable way.
Hence, Rao-Blackwellisation is especially useful when
the set of variables in a DBN can be split into two parts such that
conditioning on the first part makes the structure of the second part
tractable and amenable to exact inference.


The general RB-SIS algorithm is given in
Fig.~\ref{fig:algo-RB-SIS-general}. For illustrating purpose, we assume 
that the ``optimal'' $q_t$ and the corresponding $w_t$ are being used
($q_t = \rbst{t}(r_t|o_t)$ and $w_t = \rbst{t}(o_t)$).
At each time point, we need to maintain
$N$ samples $\tsq{r}{t}^{(i)}$, $i=1,\ldots,N$. For each sample, 
%the last point $r_t^{(i)}$ of the sequence $\tsq{r}{t}^{(i)}$, 
in addition to the sample weight $\weight^{(i)}$, we also need to store
a representation of the RB belief state corresponding to
that sample sequence: $\rbst{t}^{(i)} =
p(r_t,z_t,o_t|\tsq{r}{t-1}^{(i)},\tsq{o}{t-1})$
and $\rbst{t+}^{(i)} = p(z_t | \tsq{r}{t}^{(i)},\tsq{o}{t})$.


\begin{figure}
\small
\begin{center}
\begin{algorithm}
Begin\\
For $t=0,1,\ldots$ \\
\q	For each sample $i=1,\ldots,N$  \\
\q\q	Sample $r_t^{(i)}$ from $\rbst{t}^{(i)}(r_t|o_t)$ \\
\q\q	Update weight $\weight^{(i)} = \weight^{(i)}\rbst{t}^{(i)}(o_t) $ \\
\q\q	Compute the posterior RB bel state	
$\rbst{t+}^{(i)} = \rbst{t}^{(i)}(z_t|r_t^{(i)},o_t)$\\
\q\q	Compute the new RB belief state $\rbst{t+1}^{(i)}$ from $\rbst{t+}^{(i)}$\\ 
\q\q	Compute $h^{(i)}$ from $\rbst{t+}^{(i)}$\\
\q	Compute the estimator $\hat{f}_{RBSIS} = \sum_{i=1}^N h^{(i)}\normweight^{(i)}$\\
End \\
\end{algorithm}
\caption{RB-SIS for general DBN}
\label{fig:algo-RB-SIS-general}
\end{center}
\end{figure}


%Since SIS is a form of
%BIS, the variance reduction result for BIS applies directly to SIS, as 
%has been proved in~\cite{DGK99}. 


A number of applications of the RB-SIS method (also known as
the Rao-Blackwellised Particle Filter (RBPF)) have been 
discussed in the literature.
A general framework for using RB-SIS to do inference on DBNs has been 
presented by~\citeA{DFM000,Mur000,MuR001}. However, these authors have
mainly focused on the case where the sequence of
the Rao-Blackwellising variables $(\tsq{r}{t})$ is Markov (for example,
when the RB variables are the root nodes at each time slice). This
assumption simplifies the sampling step in the RB procedure since obtaining
the sample for the RB variable at time $t+1$ is straightforward.
In our previous work~\cite{BuiVW000:aaai}, we introduced a hybrid-inference
method for the AHMM in the special case of the state-space decomposition 
policy hierarchy, which is essentially an RB-SIS method. 
Note that when applied to AHMMs, the sequence of Rao-Blackwellising variables 
that we use does not satisfy the Markov property. In this case, care must be
taken to design an efficient sampling step, especially when the
sampling distribution for the next RB variable does not have a tractable form.
The use of non-Markov 
RB variables also appears in other special models such as
the Bayesian missing data model~\cite{LiC98}, and the partially observed
Gaussian state space model~\cite{AnD000} where
the RB belief state can be maintained by a Kalman filter.

%Earlier work~\cite{Mur000} also uses

Since we have to make the Rao-Blackwellised belief state
tractable, the context variables in the framework of 
context-specific independence~\cite{BFGK96} can be used conveniently 
as Rao-Blackwellising variables~\cite{Mur000}. 
Indeed, since the context variable acts as a mixing gate for
different Bayesian network structures, conditioning on these variables
would simplify the structure of the remaining variables. 
Because of this property of the context variables, 
\citeA{BFGK96} have suggested to use them
as the cut-set variables in the cut-set conditioning 
inference method~\cite{Pea88}. The cut-set variables play a similar role to
the Rao-Blackwellising variables in which they help to simplify the
structure of the remaining network.
In Rao-Blackwellised sampling, instead of summing over all the
possible values of the cut-set variables which can be intractable, 
only a number of representative sampled values are used.

The idea of combining both exact and approximate inference in RB sampling 
is also similar to the hybrid inference scheme described by~\citeA{DKL95}, 
however it's unclear if RB sampling can be described using 
their model of communicating belief universe.  Also, \citeauthor{DKL95} 
use hybrid inference
mainly to do inference on networks with a mixture of
continuous and discrete variables,
as opposed to RB whose goal is to improve the sampling performance.


%\newpage









%Here, we  show that as long as
%both the RB belief state and its posteriori have tractable structures (and for
%that matter, updating the RB belief state is also tractable), the two
%requirements for the RB-SIS method can be satisfied.

%\paragraph{Computing $h$:}

%Indeed, for the first requirement, 
%the integration in $h(\tsq{r}{t})$ can be obtained from \bst{t+} since:


%In particular, if we are trying to estimate $p(A|\hobst{t})$ for a future
%event $A$, 
%$f=p(A|x_t)$, and 
%$h(\tsq{r}{t}) = \int_{z_t} p(A|z_t, r_t) p(z_t |
%\tsq{r}{t},\tsq{o}{t}) = p(A |\tsq{r}{t},\tsq{o}{t})$. 
%If it is the next state that we are interested in, $A = \{x_{t+1}\}$ and 
%$h(\tsq{r}{t}) = p(x_{t+1} | \tsq{r}{t},\tsq{o}{t}) = \bst{t+1}(x_{t+1})$.






%\newpage

%\paragraph{Sampling $r_t$ and update its weight:}

%For the second requirement, from
%(\ref{eqn:weight-imdist}), we have 
%$w_t q_t = p(r_t, o_t| \tsq{r}{t-1}, \tsq{o}{t-1})$ which is the marginal 
%$\bst{t}(r_t,o_t)$. This suggests that both the sampling distribution and
%the weight update factor at time $t$ can be computed from the
%representation of \bst{t}. 

%We first look at the simple ``forward''
%importance distribution $q_t = p(r_t | \tsq{r}{t-1}, \tsq{o}{t-1})$ and the
%corresponding weight $w_t = p(o_t | r_t,\tsq{r}{t-1}, \tsq{o}{t-1})$. 
%The weight $w_t$ is the conditional probability $\bst{t}(o_t | r_t)$ and
%thus can be computed by performing exact inference within the structure of
%\bst{t}. To sample $r_t$ from the distribution $q_t$, there are two
%alternatives. We can try to obtain the marginal distribution of 
%$\bst{t}(r_t)$ and sample from it directly. Alternatively, we can sample
%every variables in \bst{t} and simply discard the ones which are not in $r_t$.
%The first method can work well if $r_t$ contains a single variable since an
%exact inference method can compute this marginal easily. However, if $r_t$
%contains multiple variables, the second method might be more convenient.
%Especially, if \bst{t} is already given in a the form of a 
%directed network representation then
%we can use simple forward sampling to sample from it~\footnote
%{There is also the possibility of using a MCMC-typed sampling method 
%to obtain samples from \bst{t}. While this might be convenient in an 
%undirected Markov network representation of \bst{t}, we do not 
%pursue it further here.}.

%The case for the ``optimal'' important distribution
%$q_t = p(r_t | \tsq{r}{t-1}, \tsq{o}{t})$ and
%the corresponding weight update 
%$w_t = p(o_t | \tsq{r}{t-1}, \tsq{o}{t-1})$ can be analysed similarly.
%Here, the weight is simply
%the marginal $\bst{t}(o_t)$ and can be computed efficiently 
%using exact inference within the structure of \bst{t}.
%Sampling from
%$q_t = p(r_t | \tsq{r}{t-1}, \tsq{o}{t}) = \bst{t}(r_t | o_t)$ 
%requires an extra step of conditioning the structure of \bst{t} on the
%observation $o_t$. After this, the two methods of sampling $r_t$ described 
%above can be used. Note that if \bst{t} is provided as a directed network,
%conditioning on $o_t$ is equivalent to performing evidence reversal, i.e.
%to reverse all the links pointing to $o_t$ so that $o_t$ becomes a root
%node which can then be removed upon its instantiation. Depending on the
%structure of \bst{t}, doing this could be costly. In our AHMM, this can be
%done efficiently since we only need to reverse one link 
%from \statet{t} to \obst{t}.


%we can
%first compute $\bst{t}(r_t | o_t)$ by inferencing then sample directly from
%this distribution. Alternatively, to avoid marginalising $z_t$, we can
%sample $r_t$ and $z_t$ from $\bst{t}(z_t,r_t|o_t)$ and discard the
%unnecessary sample $z_t$.

%\paragraph{The RB-SIS algorithm:}
%The steps in the 
%procedure are similar
%to the original SIS, except that for each sample we also need to maintain
%its RB belief state. Thus, it is crucial that the RB-belief state can be
%updated efficiently. From the point of view of choosing the appropriate
%Rao-Blackwellising variables, the variable $r_t$ should be chosen so that
%it simplifies the RB belief state update from \bst{t-1} to \bst{t}. 
%In this respect, the context variables in any context-specific independence
%properties of the transition network between \bst{t-1} and \bst{t} can
%potentially act as the Rao-Blackwellising variables since
%conditioning on them would greatly simplify the network structure, 
%hence the updating procedure.



\section{Abstract Markov Policies}
\label{section:amp}

%\rem{Overall}

\rem{motivation and intro to abstract probabilistic plan}

\rem{General things about abstract probabilistic planning}

In this section, we formally introduce the AMP concept as originating from
the literature of abstract probabilistic planning with
MDPs~\cite{SPS99,PaR97,FoV78,HMKDB98,DeL95}. 
%The abstract policy model presented in
%section~\ref{section:amp} is borrowed from the model for abstract probabilistic
%plans from the abstract probabilistic planning
%literature~\cite{Sut95,SPS99,FoV78,Par98}.
The main motivation in abstract probabilistic planning is to 
scale up MDP-based planning to problems with large state space.
It has been noted that a hierarchical
organisation of policies can help reduce the complexity of MDP-based
planning, similar to the role played by the plan hierarchy in classical
planning~\cite{Sac74}. In comparison with a classical plan
hierarchy, a policy hierarchy can model different sources of
uncertainty in the planning process such as stochastic actions, uncertain
action outcomes, and stochastic environment dynamics.

While the work in planning is concerned with finding the optimal
policy given some reward function, 
our work focuses on policy recognition which is
the inverse problem, i.e., to infer the agent's policies 
from watching the effects of the agent's actions.
The two problems however share a common element which is the model of a
stochastic plan hierarchy.
In policy recognition, although it is possible to derive 
some information about the reward function by observing the agent's 
behaviour, we choose not to do
this, thus omitting from our model the reward function and also
the optimality notion. This leaves the model open to tracking
arbitrary agent's behaviours, regardless of whether they are optimal or
not.

\subsection{The General Model}
\rem{MDP}

\subsubsection{Actions and Policies}
In an MDP, the world is modelled as a set of possible
states \State, termed the state space. At each state \state, an agent has a
set of actions $\Action$ available, where each action \action, 
if employed, will cause the world to evolve to the next state $\state'$ 
via a transition probability $\tran_\action(\state,\state')$. 
An agent's plan of actions is modelled
as a policy that prescribes how the agent would choose its action at each
state. For a policy \pol, this is modelled by a selection function 
$\tran_\pol : \State \times \Action \rarr [0,1]$
where at each state \state, $\tran_\pol(\state,\action)$ is the 
probability that the agent will choose the action \action.
It is easy to see that, given a fixed policy \pol, 
the resulting state sequence is a
Markov chain with transition probabilities
$\Pr(\state' \, | \, \state) = 
\sum_\action \tran_\pol(\state,\action) 
\tran_\action(\state,\state')$. Thus, a policy can also be viewed
as a Markov chain through the state space.

%If the agent takes action \action\ at state \state\ and the resulting next 
%state is $\state'$, it receives a reward, defined by a real-valued 
%reward function
%$\reward(\state,\action,\state')$. 


\subsubsection{Local Policies}
In the original MDP, behaviours are modelled at only two levels: the
primitive action level, and the plan level (policy). We would like to
consider policies that select other more refined policies and so 
on, down a number of abstraction levels. 
The idea is to form intermediate-level abstract policies as 
policies defined over a local region of the state space, having a certain
terminating condition, and can be invoked and executed
just like primitive actions~\cite{FoV78,SPS99}. 


\rem{describe local policy first}

\begin{defn}[Local policy] A local policy is a tuple 
$\pol = \tuple{\State, \Dest, \stopp, \tran}$ where:
\begin{itemize}
\item \State\ is the set of applicable states.
\item \Dest\ is the set of destination states. 
$\stopp: \Dest \rarr (0,1]$  is the stopping probabilities
such that $\stopp(\dest) = 1, \forall \, \dest \in \Dest\setminus\State$.
\item $\tran : \State\times \Action \rarr [0,1]$
is the selection function. Given the current state \state, 
$\tran(\state, \action)$ is the probability that the action \action\
is selected by the policy \pol\ at state \state.
\end{itemize}
\end{defn}

The set \State\ models the local region over which the policy is
applicable. 
\State\
will be called the set of applicable states, since the policy can start
from any state in \State. We shall assume here that \State\ is discrete, 
and thus shall not be concerned with the technical details in generalising
the AHMM formulation to the continuous state space case.
The stopping condition of the policy is
modelled by a set of possible destination states \Dest\ and a set of
positive stopping probabilities $\stopp(\dest), \dest\in\Dest$ 
where $\stopp(\dest)$ is the probability that the policy will terminate 
when the current state is \dest. 
It is possible to allow the policy to stop at some state outside of
\State, however, for all $\dest\in\Dest\setminus\State$ we enforce the 
condition that 
$\stopp(\dest) = 1$, i.e., \dest\ is a terminal destination state. 
Sometimes, we might only want to consider policies with deterministic
stopping condition. In that case, 
every destination is a terminal destination: 
$\forall \dest\in\Dest$,
$\stopp(\dest) = 1$. 
Thus, for a deterministically terminating policy, we can ignore 
the redundant parameter \stopp, and need only specify the set of destinations
\Dest.
%The set of both applicable states and terminal
%destination states $\State \cup \Dest$ is denoted by \AllState.

Given a starting state $\state\in\State$, a local policy as defined above
generates a Markov sequence of states according to its transition
model. Each time a destination state $\dest\in\Dest$ is reached, the
process stops with probability $\stopp(\dest)$. 
%If a terminal destination
%state $\dest\in\Dest\setminus\State$ is reached, the process stops with
%probability 1. 
Since the process starts from within \State, but
terminates only in one of the states in \Dest, the destination states play
the role of the possible exits out of the local region \State\ of 
the state space.

When we want to make clear which policy is currently being referred to, we shall
use the subscripted notations $\State_\pol$, $\Dest_\pol$, $\stopp_\pol$, 
$\tran_\pol$ to denote the elements of the policy \pol.


\begin{figure}
\begin{center}\epsfbox{local-policy.eps}
\caption{\label{fig:local-policy} Visualisation of a policy}
\end{center}
\end{figure}

Fig.~\ref{fig:local-policy} illustrates how a local policy \pol\ can be
visualised. Fig.~\ref{fig:local-policy}(a) shows the set of applicable states 
\State,
the set of destinations \Dest, and a chain starting within \State\ and
terminating in \Dest. The Bayesian network in Fig.~\ref{fig:local-policy}(b)
provides the detailed view of the chain from start to finish.
The Bayesian network in Fig.~\ref{fig:local-policy}(c) 
is the abstract view of the 
chain where we are only interested in its starting and stopping states.  

\rem{now lead from local to abstract policy}

\subsubsection{Abstract Policies}
The local policy as defined above selects among the set of primitive
actions. Similarly, but more generally, we can define higher level policies 
that select among a set of other policies. 


\begin{defn}[Abstract Policy] \hspace{0.5cm}
\label{def:abstract-pol}
Let \Pol\ be a set of abstract policies. An abstract
policy $\pol^*$ over the policies in \Pol\ is a tuple
\tuple{\State_{\pol^*}, \Dest_{\pol^*}, \stopp_{\pol^*}, \tran_{\pol^*}} 
where:
\begin{itemize}
\item $\State_{\pol^*} \subset \cup_{\pol\in\Pol} \State_\pol$ is the
set of applicable states.
\item $\Dest_{\pol^*} \subset \cup_{\pol\in\Pol} \Dest_\pol$ is the set of
destination states. $\stopp_{\pol^*} : \Dest_{\pol^*} \rarr (0,1]$ 
is the set of stopping probabilities.
\item $\tran_{\pol^*} : \State_{\pol^*}\times\Pol \rarr [0,1]$
is the selection function where $\tran_{\pol^*}(\state, \pol)$ is the
probability that $\pol^*$ selects the policy \pol\ at the state \state.
\end{itemize}
\end{defn}

%Formally, let \Pol\ be a set of abstract policies.
%We can then define an abstract policy $\pol^*$ over \Pol\ as a tuple
%\tuple{\State_{\pol^*}, \Dest_{\pol^*},\tran_{\pol^*}} where 
%$\State_{\pol^*} \subset \State$ is the
%set of applicable states,
%$\Dest_{\pol^*} \subset \State$ is the set of destination states, and
%$\tran_{\pol^*} : \State_{\pol^*}\times\Pol \rarr [0,1]$
%is the selection function where $\tran_{\pol^*}(\state, \pol)$ is the
%probability that $\pol^*$ selects the policy \pol\ at the state \state.



Note the recursiveness in definition~\ref{def:abstract-pol}
that allows an abstract policy to 
select among a set of other abstract policies. At the base level,
primitive actions are viewed as abstract policies 
themselves. Since primitive actions always stop after one
time-step, $\Dest_\action \supset \State_\action$ and 
$\stopp(\dest)=1 \, \forall \dest\in\Dest_\action$~\cite{SPS99}.
The idea that policies with suitable stopping condition can be viewed
just as primitive actions is first made explicit in~\cite{Sut95},
which also introduces the $\beta$ model for representing the stopping
probabilities.  Their subsequent work~\cite{SPS99} introduces the 
abstract policy concept under the name {\em options}.


The execution of an abstract policy $\pol^*$ is as follows. Starting 
from some state \state, $\pol^*$ selects a policy $\pol\in\Pol$ according
to the distribution $\tran_{\pol^*}(\state,.)$. The selected policy
\pol\ is then executed until it is terminated in some state
$\dest\in\Dest_{\pol}$. If $\dest$ is also a destination state of
$\pol^*$ ($\dest \in \Dest_{\pol^*}$), the policy $\pol^*$ stops with
probability $\stopp_{\pol^*}(\dest)$. If $\pol^*$ still continues, 
a new policy $\pol'\in\Pol$ is selected by $\pol^*$ at $\dest$, which will be
executed until its termination and so on (Fig.~\ref{fig:abspol-chain}). 

Some remarks about the representation of an abstract policy are needed
here.
Let $\state\in\cup_{\pol\in\Pol} \State_\pol$, we denote the 
subset of policies in \Pol\
which are applicable at \state\ by $\Pol(\state) = \{\pol\in\Pol \,|\,
\state\in\State_\pol\}$. For an abstract policy $\pol^*$ to be well-defined, 
we have to make sure that at each state \state, $\pol^*$ only selects among 
the policies that are applicable at \state. Thus, the selection function has
to be such that $\tran_{\pol^*}(\state,\pol) > 0$ only if
$\pol\in\Pol(\state)$. This helps to keep the specification of the
selection function to a manageable size, even when the set of all policies \Pol\
to be chosen from can be large. In addition, the specification of the
selection function and the stopping probabilities can make use of factored
representations~\cite{BDG001} in the case where the state space is the
composite of a set of relatively independent variables. This ensures that
we still have a compact specification of the probabilities conditioned 
on the state variable, even though the state space can be of high dimension.

\begin{figure}
\begin{center}\epsfbox{abspol-chain.eps}
\caption{\label{fig:abspol-chain} A chain generated by an abstract policy}
\end{center}
\end{figure}




%When an abstract policy $\pol^*$ is invoked, it will keep on selecting the
%policies in \Pol\ for execution, and terminate in a
%destination state $\dest\in\Dest_{\pol^*}$.
%is reached~\footnote 
%{Sutton, Precup and Singh's model allows non-deterministic
%stopping conditions and thus is more general than what we consider here. 
%Nevertheless, our theorem~\ref{thrm-ind} 
%can also be shown to hold in the general case as well.}. 


\subsubsection{Policy Hierarchy}
Using abstract policies as the building blocks, we can construct a
hierarchy of abstract policies as follows: 

\begin{defn}[Policy hierarchy]
A policy hierarchy is a sequence
$\HPol = (\Pol_0, \Pol_1, \ldots, \Pol_K)$ where 
$K$ is the number of levels in the hierarchy,
$\Pol_0$ is a set of primitive actions, 
and for $k=1,\ldots,K$, $\Pol_{k}$ is a set
of abstract policies over the policies in $\Pol_{k-1}$.
\end{defn}

When a top-level
policy $\toppol$ is executed, it invokes a sequence of level-(K-1) policies,
each of which invokes a sequence of level-(K-2) policies and so on.
A level-1 policy will invoke a sequence of primitive actions which leads to 
a sequence of states. Thus, the execution of $\toppol$
generates an overall state sequence
$(\statet{0}, \statet{1}, \ldots, \statet{t}, \ldots)$
that terminates in one of the destination states in $\Dest_{\toppol}$.
When $K=1$ this sequence is simply a Markov chain (with suitable stopping
conditions). However, for $K \ge 2$, it will generally be non-Markovian, 
despite the fact that 
all the policies are Markov, i.e., they select the lower level policies 
based solely on the current state~\cite{SPS99}. 
This is because knowing the current state \statet{t} alone
does not provide information about the current intermediate-level
policies, which can affect the selection of the next state \statet{t+1}.
Intuitively, this means that an agent's behaviour to achieve a given goal
is usually non-Markovian, since its choice of actions depends not only on
the current state, but also on the current intermediate intentions of the
agent.

We term the dynamical process in executing a top-level abstract policy
$\toppol$ the {\em Abstract Markov Model} (AMM). 
When the states are only partially observable, 
the observation can be modelled by
the usual observation model $\CPr{\obst{t}}{\statet{t}} =
\om(\statet{t},\obst{t})$.
The resulting process is termed the 
{\em Abstract Hidden Markov Model} (AHMM) since the states are hidden as in 
the Hidden Markov Model~\cite{Rab89}.


\rem{relate to previous work}

The idea of having a higher level policy controlling the lower level ones
in an MDP can be traced back to the work by~\citeA{FoV78},
who investigated a two layer structure similar to 
our 2-level policy hierarchy with deterministic stopping condition. 
\citeauthor{FoV78} showed that that the sub-process, obtained by
sub-sampling the state sequence at the time when the level-1 policy
terminates, is also Markov, thus the policies at level 1 simply play 
the role of an ``extended'' action. In our framework, given a policy hierarchy,
one can consider a ``lifted'' model where only the policies from 
level $k$ up and the observations
at the time points when a policy at level $k$ ends are considered. 
The level-$k$ policies can then be considered as primitive actions, and the 
lifted model can be treated like a normal model.

\subsection{State-Space Region-Based Decomposition}
\label{subsec:rd-hierarchy}

%The construction of the hierarchy policy via
%region-based decomposition of the state space appears in~\cite{HMKDB98,
%DeL95} and proves to be useful when the state space, or some dimension of
%it, already has a natural hierarchy structure.

In some cases, the state space or some of its dimensions already exhibit a
natural hierarchical structure. For example, in the spatial domain, the set of
ground positions can be divided into small local spaces such as rooms, 
corridors, etc. A set of these local spaces can be 
grouped together to form a larger space at the higher level (floors,
buildings, etc).
An intuitive and often-used method for constructing the policy hierarchy 
in this case is via the so-called region-based decomposition of the 
state space~\cite{DeL95,HMKDB98}. 
Here, the state space \State\ is successively partitioned into a 
sequence of partitions $\partn_K,\partn_{K-1},...\partn_1$ 
corresponding to the $K$ levels of abstraction, 
where $\partn_K = \{\State\}$ is the coarsest partition, 
and $\partn_1$ is the finest. 
For each region $R_i$ of
$\partn_i$, the periphery of $R_i$, $Per(R_i)$ is defined as
the set of states not in $R_i$, but connected to some state in $R_i$. 
Let $Per_i$ be the set of all peripheral states at level $i$:
$Per_i = \cup_{R_i\in\partn_i} Per(R_i)$. Fig.~\ref{fig:4room}(b) shows an
example where the state space representing a building is partitioned 
into 4 regions corresponding to the 4 rooms. 
The peripheral states for a region is shown in
Fig~\ref{fig:4room}(a), and Fig~\ref{fig:4room}(b) shows all such peripheral 
states.

\begin{figure}
\begin{center}\epsfbox{4room.eps}
\caption{\label{fig:4room} The environment and its partition}
\end{center}
\end{figure}

To construct the policy hierarchy, we first define for each region
$R_1\in\partn_1$ a set of abstract policies applicable on $R_1$, and having
$Per(R_1)$ as the destination states. 
For example, for each room in
Fig~\ref{fig:4room}, we can define a set of policies that model the
agent's different behaviours while it is inside the room, e.g., 
getting out through a particular door. These policies can be initiated
from inside the room, and terminate when the agent
steps out of the room (not necessarily through the target door since the
policy might fail to achieve its intended target). Note that since
$Per(R_1) \cap R_1 = \emptyset$, all the policies defined in this manner
have deterministic stopping conditions.

Let the set of all
policies defined be $\Pol_1$. At the higher level
$\partn_2$, for each region $R_2$, we can define a set of
policies that model the agent's behaviours inside that region 
with applicable state space $R_2$, destination set $Per(R_2)$, and the
constraint that these policies must use the policies previously defined at
level-1 to achieve their goals. An example is a policy to navigate between
the room-doors to get from one building gate to another.
Let the set of all policies defined at this level be $\Pol_2$.
Continuing doing this at the higher levels, we obtain the policy hierarchy 
$\HPol = (\Pol_0, \Pol_1, \Pol_2, \ldots, \Pol_K)$. A policy hierarchy
constructed through State-space Region-based Decomposition is termed
an SRD policy hierarchy.

An SRD policy hierarchy has the property that 
%at each abstraction level, 
the set of applicable states of all the policies 
at a given abstraction level
forms a partition of the state
space. Thus, from the state sequence 
$(\statet{0},\ldots,\statet{t},\ldots)$ resulting
from the execution of the top level policy, we can infer the exact 
starting and terminating times of all intermediate-level policies. 
For example, at level
$k$, the starting/stopping times of the policies in this level are the
time indices $t$'s at which the state sequence crosses over a region boundary:
$\statet{t-1}\in R_k$ and
$\statet{t} \not\in R_k$ for some region $R_k$ of the partition $\partn_k$.
Later in section~\ref{subsec:polrec-tractable}, we will show that this 
property helps to simplify
some of the complexity of the policy recognition problem.

%The observation model together with the movement model at the 
%bottom level can be learned from training data using parameter 
%re-estimation for the HMM. 


%In wide-area
%surveillance, we usually have to deal with a large state space with complex
%spatial layout and an inherent hierarchy of sub-region decomposition such as
%buildings, floors, rooms, etc. The AHMM can take direct advantage of this
%natural hierarchical structure of in a spatial environment, making it
%scalable to larger spatial layouts. 

%\subsection{Examples of AMM's}
%
%\rem{The driving example from \cite{Pyn99,PyW000}}
%
%\rem{The tracking example}

\subsection{A Policy Hierarchy Example}
\label{subsec:amm-example}


As an example, consider the task
to monitor and predict the movement of an agent through a building
shown in Fig.~\ref{fig:bld-param}(a). 
Each room is represented by a $5\times5$ grid, 
and two adjacent rooms are connected via a door in the center of their common
edge. The four entrances to the building are labeled north (N), west (W), 
south (S) and east (E). In addition, the door in the center of the building
(C) acts like an entrance between the building's north wing and south wing.
At each state (cell), the agent can move
in 4 possible directions except when it is blocked by a wall.
%We assume that these actions have 
%0.5 failure probability, in
%which case the agent either stays in the same cell, or moves 
%unintendedly to one of the other three neighbours. 

The policy hierarchy to model the agent's behaviour in this environment
can be constructed based on region-based 
decomposition at three levels of abstraction. 
Firstly, a region hierarchy is constructed.
The partition of the environment 
consists of the 8 rooms at level 1, the two wings (north and south) at
level 2, and the entire building at level 3. 
The behaviours of the agent at level 1 (within each room) 
is represented by a set of level 1 policies.
For example, in each room, we use 4
level-1 policies to model the agent's behaviours of exiting the room via 
the 4 different doors. These are essentially four Markov
chains within the room which terminate outside of the room.
One way to represent these policies is to
specify which movement action the
agent should take given the current position and the current heading.
At the higher level, the agent's behaviours within each wing are specified.
For example, we use 3 level-2 policies in each wing
to model the agent's behaviours of exiting the wing via the 3 wing 
exits. These policies are built on top of the set of level-1 policies
already defined. They specify which level-1 policies the agent should take
to leave the wing at the intended exit.
Finally, at the top level, the agent's behaviours within the entire
building can be specified. For example, we use 4 top-level
policies to model the agent's behaviours of leaving the building via the
four building exits N, W, S, E. 
A sample of these policies and their 
parameters is given in Fig.~\ref{fig:bld-param}(b).


\begin{figure}
\begin{center}\epsfbox{bld-param.eps}
\caption{\label{fig:bld-param} An example policy hierarchy}
\end{center}
\end{figure}




\subsection{AMM as a Plan Execution Model}
\label{subsec:amm-planmodel}

\rem{general: relate AMM back to the task of plan recognition}

Up to now, we have presented the AMM as a formal plan execution
model to be used later in the plan recognition process. In this subsection,
we discuss the expressiveness of the AMM as a formal plan specification
language, and also the suitability of using the AMM to encode plans 
in the context of plan recognition. Note that the discussion here
focuses on the representational aspect of the AMM alone. 
A discussion of the computational aspects of the AMM/AHMM in
comparison with other works in probabilistic plan recognition 
will be presented in Section~\ref{sec:related-work}.


The AMM is particularly well-suited for representing 
goal-directed behaviours at different levels of abstraction. 
Each policy in the AMM can be viewed as a plan trying to achieve a
particular goal.  
%Like a classical plan hierarchy,
%the adoption of a new policy at the lower level is similar to the 
%refinement of a plan into its sub-plans. 
However, unlike a classical
plan, a policy specifies the course of actions at all applicable states,
and is more similar to a {\em contingent plan}.
The ending of a policy could either means that the goal has been achieved,
or the attempt to achieve the goal using the current policy has failed.
This interpretation of the persistence of a policy fits into
the persistence model of {\em intentions}~\cite{CohLev90}: when an
intention ends, there is no guarantee that the intended goal has been
achieved.  Thus, conceptually, there are two types of destination states:
one corresponds to the intended goal states, and the other corresponds 
to unintended failure states resulting from the stochastic nature in the 
execution of the plan.  Due to its generality, the AMM  does not need to
distinguish between these two types;
both the successful termination
states and the unsuccessful ones are treated the same as possible
destination states, albeit with different reaching 
probabilities.\footnote{One would expect that an agent would more likely to 
reach the intended destination state rather a random failure state.}

Using the AMM as a model of plan execution thus allows us to blur the 
difference between planning and re-planning. 
At the same time, it moves from the
recognition of a classical plan towards the recognition of
the agent's {\em intention}.
Most of the existing framework for
probabilistic plan recognition does not explicitly represent the current
state, and thus, the relationship between states and the adoption and
termination of current plans is 
ignored~\cite{GGM99}.\footnote{with the exceptions of~\cite{GGM99,PyW000}
which will be discussed in detail in Section~\ref{sec:related-work}.}
Thus, it would be
impossible to tell if the current plan has failed and the new plan is an
attempt to recover from this failure, or the current plan has succeeded and
the new plan is part of a new higher level goal. 

\rem{HAM}

A more expressive language for describing abstract probabilistic plan is the
Hierarchical Abstract Machines (HAM) proposed in~\cite{PaR97,Par98}. In
a HAM, the abstract policy is replaced by a stochastic finite
automaton, which can call other machines at the lower level. 
Our abstract policies can be written down as machines of this
type. Such a machine would choose one of the machines correspond to the
policies at the lower level and then go back to the start state after the
called machines have terminated. The HAM framework allows for
machines with arbitrary finite number of machine states and transition 
probabilities,\footnote{
with the constraint that there is no recursion in the calling stack to
keep the stack finite.} thus can readily represent 
more complex plans such as
concatenation of policies, alternative policy paths, etc. 
It is possible to
represent each machine in HAM as a policy in our AMM,
however with the cost of augmenting the state space to include 
the machine states of all the machines in the current call stack.
Thus, the size of the AMM's new state space would be exponential with 
respect to the number of nested levels in the HAM's call stack.
While this shows in theory the expressiveness of HAM and our policy
hierarchy is the same, performing policy recognition on the HAM-equivalent
policy hierarchy is probably unwise since the state space becomes
exponentially large after the conversion. 
A better idea would be to represent the 
internal state of each machine as a variable in a DBN and
perform inference on this DBN structure directly.


\rem{What about PSDG?}

The AMM is also closely related to a model for probabilistic plan
recognition called the Probabilistic State-Dependent 
Grammar (PSDG), independently proposed in~\cite{Pyn99,PyW000}.
%and deserves a more detailed discussion.
The PSDG can be described as the Probabilistic Context Free Grammar 
(PCFG)~\cite{JLM92}, augmented with a state space, and a state transition 
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.
Interestingly, the PSDG is directly related to
the HAM language described above, similar to the way production-rule
grammars are related to finite automata. Given a PSDG, we can convert it to an
equivalent HAM by constructing a machine for each non-terminating symbol,
and
modelling the production rules for each non-terminating symbol by 
the automaton. 

Our policy hierarchy is equivalent to a special class of PSDG
where only production rules of the form 
$X \rightarrow YX$ and $X \rightarrow \emptyset$ are allowed. 
The former rule models the adoption of a lower level policy $Y$  by a
higher level policy $X$, while the latter models the termination of a
policy $X$. The PSDG model considered in~\cite{Pyn99,PyW000} 
allows for more general rules
of the form $X \rightarrow Y_1\ldots Y_m X$, 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.
The implicit assumption here is that when a policy in the
sequence terminates, it always does so at a state where the next policy 
in the sequence is applicable.
Given this assumption,
in the language of the AHMM
we can define a {\em compound} policy $\pol^k$ as a policy that
simply and orderly
executes a sequence of policies at the lower level 
$\pol^{k-1}_{(1)},
\ldots,
\pol^{k-1}_{(m)}$, independent of the current state.
A PSDG is then equivalent to an AHMM if compound policies of this form 
are allowed.

%Note that due to the uncertain
%nature of the execution of a policy, it is reasonable for us to assume that
%control should be returned immediately to the higher level layer after each
%lower level policy terminates. This is because the lower level policy
%might fail to achieve its intended purpose, and the higher level plan would
%then need to be invoked to recover from this failure.


%Thus, the previous discussion for converting a HAM
%to an equivalent
%policy hierarchy and performing inference for a HAM structure
%also applies to PSDG.


\rem{possible applications}

Since the AMM closely follows the models used in abstract probabilistic
planning, it can be used to model and recognise the behaviours of 
any autonomous agent whose decision making process is equivalent to an
abstract MDP. It is also useful as a formal language for specifying 
contingent plans whose execution can then be monitored using the policy
recognition algorithm. The language is also rich enough to specify a range
of useful human behaviours, especially in domains where there is a natural
hierarchical decomposition of the state space. 
Section 6 presents an application of the AHMM framework to the problem
of recognising people behaviours in a complex spatial environment.
Here, each policy of the AHMM 
represents the evolution of possible trajectories of people movement 
while the person performs a certain task in the environment such as heading
towards a door, using the computer at a certain location, etc.
The policies at different levels would
represent the evolution of trajectories at different levels of abstraction.
Due to the existing hierarchy in the
domain, the policies can be constructed using the region-based decomposition of
the state space.  
The environment is populated with
multiple cameras divided into different zones that can provide the 
current location of the tracking target, albeit a noisy one. The noisy
observations can be readily handled by the observation model in the AHMM. 
The policy recognition algorithm can then be
applied to infer the person's
current policy at different levels in the hierarchy.


One main restriction of the current AHMM model is that we
consider only one top-level policy at a time, thus are unable to model the
inter-leaving of concurrent plans. Another more subtle restriction 
is the assumption
that a high level policy selects the lower level policies depending only on
the current state. 
If the state space is interpreted as the states of the
external environment, this assumption implies that the actor either has 
full observation about the current state, or at least refines its
intentions based on the actor's observation about the current state only
(and not the entire observation history). 
Note that these restrictions of the AHMM also apply in the case of
the PSDG model. 

%Alternatively, if the state 
%space is interpreted as some internal machine states of the actor
%, the
%assumption in the AHMM model is that the observer can observe 
%these internal states of the actor, albeit with random noise. 


%Except~\cite{GGM99}, we are unaware of any
%other work in probabilistic plan recognition that addresses this type of
%problems. 

%
%The main strength of the AMM is in its ability to explicitly model
%the uncertainty and likelihood in both the policy refinement and persistence
%models. 



%The policy recognition 
%algorithms in the AHMM then allow us to monitor the stage of execution of the
%goal-directed process at all levels of its abstraction hierarchy, e.g. to
%infer the current intention of an agent at various abstraction levels. 


%\rem{Plan recognition in general}

%The AHMM also provides a tailor-made framework for performing probabilistic
%plan recognition. 

%The AHMM policy construction, taken from the
%the abstract probabilistic planning, provides adequate representation for 
%modelling a rich type of probabilistic plans. The policy recognition method
%can then be used to perform probabilistic plan recognition for the plan
%hierarchy modelled by the AHMM. 



%\newpage
\section{Dynamic Bayesian Network Representation}
\label{section:dbn}
\rem{Section overview}

In this section, we describe the Dynamic Bayesian Network (DBN) 
representation of the AHMM.
The network serves two purposes: (1) as the
tool to derive the probabilistic independence property of this stochastic model,
and (2) as the computational framework for the policy recognition 
algorithms in Section~\ref{sec:pol-rec}.

\subsection{Network Construction}

%The process of executing the top-level abstract policy $\toppol$ 
%can be represented by a DBN (Fig.~\ref{fig:dbn}). 

At time $t$, let \statet{t} represent the current state, 
$\polst{k}{t}$ represent
the current policy at level $k$
($k=0,\ldots,K$),
\pendst{k}{t} represent the ending status of \polst{k}{t}, 
i.e., a boolean variable indicating whether the policy 
\polst{k}{t} terminates at the current time. 
These variables would make up the current time-slice of the full DBN. 
For our convenience, the notation \polst{all}{t} refers to the set of all 
the current policies $\{\polst{K}{t},\ldots,\polst{0}{t}\}$.
Before presenting the full network, 
we first describe the two sub-structures that model how policies are 
terminated and selected.  The full DBN 
can then be easily constructed from these sub-structures.


\subsubsection{Policy Termination}
\label{subsubsec:pol-terminate}

From the definition of abstract policies, a level-$k$ policy \polst{k}{t}
terminates only if the lower level policy \polst{k-1}{t} terminates, and if
so, \polst{k}{t} terminates with probability 
$\stopp_{\polst{k}{t}}(\statet{t})$. In the Bayesian network
representation, the terminating status \pendst{k}{t} therefore has three
parent nodes: \polst{k}{t}, \statet{t}, and
\pendst{k-1}{t} (Fig.~\ref{fig:polterminate}(a)).

The parent variable \pendst{k-1}{t} however plays a special role.
If $\pendst{k-1}{t} = T$, meaning the lower level policy terminates at the
current time, 
$\CPr{\pendst{k}{t} = T}{\polst{k}{t}, \statet{t}} = 
\stopp_{\polst{k}{t}}(\statet{t})$ which gives the conditional probability 
of \pendst{k}{t} given the other two parent variables  
(Fig.~\ref{fig:polterminate}(b)).
However, if $\pendst{k-1}{t} = F$, \polst{k}{t}
should not terminate and so $\pendst{k}{t} = F$. 
Therefore, given that
$\pendst{k-1}{t} = F$, \pendst{k}{t} is
deterministically determined and is independent of the other two parent
variables \polst{k}{t} and \statet{t}. 
Using the notion of context-specific independence (CSI)~\cite{BFGK96}, 
we can then safely remove the links from the other two parents to
\pendst{k}{t} in the context that \pendst{k-1}{t} is false 
(Fig.~\ref{fig:polterminate}(c)).

At the bottom level, since the primitive action always terminates 
immediately, $\pendst{0}{t} = T$ for all $t$.
Since we are modelling the execution of a single top-level policy $\toppol$,
we can assume that the top-level policy does not terminate and remains
unchanged: $\pendst{K}{t} = F$ and $\polst{K}{t} = \toppol$ for all $t$. 
Also, note that $\pendst{l}{t} = T \imply \pendst{k}{t} = T$ for all $k\le l$, 
and $\pendst{l}{t} = F \imply \pendst{k}{t} = F$ for all $k\ge l$. Thus, at
each time $t$, there exists $0 \le \topendt{t} < K$ such that
$\pendst{k}{t} = T$ for all $k \le \topendt{t}$, and
$\pendst{k}{t} = F$ for all $k > \topendt{t}$. The variable 
$\topendt{t}$ 
is termed
the highest level of termination at time $t$. Knowing the value of 
$\topendt{t}$ 
is equivalent to knowing the terminating status of all the current policies.


\begin{figure}
\begin{center}\epsfbox{polterminate.eps}
\caption{\label{fig:polterminate} Sub-network for policy termination}
\end{center}
\end{figure}

\subsubsection{Policy Selection}
\label{subsubsec:pol-select}

The current policy \polst{k}{t} in general is dependent on the higher level
policy \polst{k+1}{t}, the previous state \statet{t-1}, the previous policy at
the same level \polst{k}{t-1} and its ending status \pendst{k}{t-1}. In the
Bayesian network, \polst{k}{t} thus has these four variables as its parents
(Fig.~\ref{fig:polselect}(a)). 
This dependency can be further broken down into two cases, depending on the
value of the parent node \pendst{k}{t-1}.

If the previous policy has not terminated ($\pendst{k}{t-1} = F$), the
current policy is the same as the previous one: $\polst{k}{t} =
\polst{k}{t-1}$, and the variable \polst{k}{t} is thus independent of
\polst{k+1}{t} and \statet{t-1}. Therefore, 
in the context $\pendst{k}{t-1} = F$, 
the two links from \polst{k+1}{t} and \statet{t-1} to the current policy can be
removed, and the two nodes \polst{k}{t} and \polst{k}{t-1} can be merged
together (Fig.~\ref{fig:polselect}(b)). 

If the previous policy has terminated ($\pendst{k}{t-1} = T$), the current
policy is selected by the higher level policy with probability
$\CPr{\polst{k}{t}}
{\polst{k+1}{t}, \statet{t-1}}
= \tran_{\polst{k+1}{t}}(\statet{t-1},\polst{k}{t})$.
In this context, \polst{k}{t} is independent of \polst{k}{t-1} and the
corresponding link in the Bayesian network can be removed 
(Fig.~\ref{fig:polselect}(c)).


\begin{figure}
\begin{center}\epsfbox{polselect.eps}
\caption{\label{fig:polselect} Sub-network for policy selection}
\end{center}
\end{figure}


\subsubsection{The Full DBN}
\label{subsubsec:full-DBN}


\begin{figure}
\begin{center}\epsfbox{ahmm-full.eps}
\caption{\label{fig:ahmm-full} The DBN representation of the Abstract
Hidden Markov Model}
\end{center}
\end{figure}

The full dynamic Bayesian network can be constructed for all the policy,
ending status, and state variables by putting the sub-networks for policy
termination and selection together (Fig.~\ref{fig:ahmm-full}).
At the top level, since $\pendst{K}{t} = F$, we can remove the ending status
nodes and merge all the \polst{K}{t} into a single node $\toppol$.
At the base level, since $\pendst{0}{t} = T$, we can remove the ending status
nodes and also the links from \polst{0}{t} to \polst{0}{t+1}. 
To model the observation of the hidden states, an observation layer can 
be attached to the state layer as shown in Fig.~\ref{fig:ahmm-full}. 



Suppose that we are given a context where each of the variable \pendst{k}{t} 
is known. We can then modify
the full DBN using the corresponding link removal and node merging rules.
The result is a more intuitive tree-shaped network in 
Fig.~\ref{fig:amm-tree},
where all the policy nodes corresponding to the same
policy for its entire duration are grouped into one.
The grouping can be done since knowing the value of each \pendst{k}{t} is
equivalent to knowing the exact duration of each policy in the hierarchy.
One would expect that performing probabilistic inference on this structure
is more simple than that of the full DBN in Fig.~\ref{fig:ahmm-full}.
In particular, if the state sequence is known, the remainder of the
network in Fig.~\ref{fig:amm-tree} becomes singly-connected, i.e., a directed
graph with no undirected cycles, allowing inference to be performed 
with complexity linear to the size of the network~\cite{Pea88}. 
The policy recognition algorithms that follow later exploit
extensively this particular tractable case of the AHMM.

\begin{figure}
\begin{center}\epsfbox{amm-tree.eps}
\caption{\label{fig:amm-tree} Simplified network if the duration
of each policy is known (action nodes are omitted for clarity)}
\end{center}
\end{figure}


%Let $\polendst{k}{t}, k=0,\ldots,K-1$ represent the
%stopping status of the policy $\polst{k}{t}$. That is $\polendst{k}{t} =
%\statet{t}$ if the policy terminates at time $t$, and $\polendst{k}{t} =
%false$ otherwise. At the base level, since the primitive action always
%terminates after one time step, $\polendst{0}{t} = \statet{t}$ for all $t$.
%This is indicated by the special dotted lines in Fig.~\ref{fig:dbn}.
%Generally, we can look at the stopping status of the current 
%policy at the lower level \polendst{k-1}{t} and see whether this falls
%inside the destination states of \polst{k}{t} to determine the value of 
%\polendst{k}{t}. Thus, \polendst{k}{t} is dependent (deterministically) on
%\polst{k}{t} and \polendst{k-1}{t}.

%Now the evolution from one time-slice of the DBN to the next is as follows: 
%the current policy \polst{k}{t} is dependent on
%the current policy at the higher level \polst{k+1}{t}, the policy at the
%previous time \polst{k}{t-1}, and its stopping status \polendst{k}{t-1}.
%If $\polendst{k}{t-1} = false$, the previous policy $\polst{k}{t-1}$
%persists to time $t$, otherwise, a new policy at level-$k$ is generated by
%\polst{k+1}{t} using the distribution 
%$\tran_{\polst{k+1}{t}}(\polendst{k}{t-1},.)$.



\subsection{Conditional Independence in the Current Time-Slice}

The above discussion identifies a tractable case for the AHMM, but it
requires the knowledge of the entire history of the state and the
policy ending status variables.
In this subsection, we focus on 
the conditional independence property of the nodes in the current
time-slice: $\statet{t}, \polst{0}{t},\ldots,\polst{K}{t}$. Since these
nodes will make up the belief state of any future inference algorithm for
our AHMM, any independence properties among these variables, 
if exploited, can provide a
more compact representation of the belief state and reduce the inference
complexity.



%The belief state of the AMM is a joint distribution of $K+2$ variables in
%the current time-slice: $\statet{t}, \polst{0}{t},\ldots,\polst{K}{t}$. 
%Thus generally, the size of the belief state representation will be
%exponential of $K$.  
%However, due to the way policies are 
%invoked in the AMM, we can make an intuitive remark that,
%the higher level policies can only influence what happens 
%at the lower level through the current level. Therefore, knowing 
%enough information about the current level would make the higher 
%level policies probabilistically independent of the lower level policies.
%If this kind of probabilistic independence relations can be exploited,
%the belief state could be represented more compactly.

Due to the way policies are 
invoked in the AMM, we can make an intuitive remark that
the higher level policies can only influence what happens 
at the lower level through the current level. 
More precisely, for a level $k$ policy \polst{k}{t}, if we know
its starting state, the course of its execution is fully determined, where
being determined here means without influence from what is happening at the
higher levels.  Furthermore, if we also know how long the policy 
has been executed, or equivalently its starting time, the current state 
of its execution is also determined. Thus, the higher level policies can
only influence the current state of execution of \polst{k}{t} either
through its starting state or starting time.
%Therefore, knowing 
%enough information about the current level would make the higher 
%level policies probabilistically independent of the lower level policies.
%Thus, our motivation here is to find the least amount of
%information we need to know about the current level, in order to make the
%current policies at the higher and lower levels independent. 
In other words, if
we know \polst{k}{t} together with its starting time 
and starting state, then the current higher level policies are 
completely independent of the current lower level policies and the current
state. The theorem~\ref{thrm-ind} below formally states this in a 
precise form.
Note that the condition obtained is the strictest:
if one of the three conditional variables is unknown, 
there are examples of AMMs in which the higher level policies 
can influence the lower level ones.

\begin{theorem}
\label{thrm-ind}
Let \btimest{k}{t} and \bstatest{k}{t} be two random variables
representing the
starting time and the starting state, respectively, 
of the current level-$k$ policy \polst{k}{t}:
$\btimest{k}{t} = \max \{t' < t \, | \, \pendst{k}{t'} = T\}$ and
$\bstatest{k}{t} = \statet{\btimest{k}{t}}$.
Let $\polst{>k}{t}=\{\polst{k+1}{t},\ldots,\polst{K}{t}\}$ 
denote the set of current policies from level $k+1$ up
to $K$, and $\polst{<k}{t}=\{\statet{t}, \polst{0}{t},\ldots,\polst{k-1}{t}\}$ 
denote the set of current policies from level $k-1$ down to 0 together with 
the current state. We have:
\begin{equation}
\polst{>k}{t} \pind \polst{<k}{t} \,|\,
\polst{k}{t},\bstatest{k}{t}, \btimest{k}{t}
\label{eqn:ind}
\end{equation}
\end{theorem}

\begin{proof}
We sketch here an intuitive proof of this theorem through the use of the
Bayesian network manipulation rules for 
context-specific independence which have been discussed in 
\ref{subsubsec:pol-terminate} and \ref{subsubsec:pol-select}.
An alternative proof that does not use CSI can be found
in~\cite{BuiVW000:aaai}.

We first note that the theorem is not obvious by looking at the full DBN in
Fig.~\ref{fig:ahmm-full}.  Therefore, we shall proceed by modifying 
the network structure in the context that we know \btimest{k}{t}.

At time \btimest{k}{t}, all the policies at level $k$ and below must
terminate: $\pendst{l}{\btimest{k}{t}} = T$ for all $l \le k$. 
Thus we can remove all
the links from these policies to the new policies at time
$\btimest{k}{t}+1$.

On the other hand, from time $\btimest{k}{t}+1$ until the current time $t$,
all the policies at level $k$ and above must not terminate:
$\pendst{l}{t'} = F$ for all $l \ge k$, $\btimest{k}{t}+1 \le t' < t$. 
Thus we can group all the policies
at level $l \ge k$ between time $\btimest{k}{t}+1$ and $t$ into one node
representing the current policy at level $l$. 

These two network manipulation steps 
result in a network with the
structure shown in Fig.~\ref{fig:independence}. 
Once the modified network structure 
is obtained,  we  can observe that
\polst{>k}{t} and \polst{<k}{t} are d-separated by \polst{k}{t} and
\bstatest{k}{t} in the new structure. Thus \polst{>k}{t} and \polst{<k}{t} 
are independent given \polst{k}{t}, \bstatest{k}{t} and \btimest{k}{t}.
\end{proof}



%the policy \polst{k}{\btimest{k}{t}} (which is the
%last policy at level $k$) must terminate, 
%and also from that time until the current time $t$, the policy
%at level $k$ remains the same. Thus, $\pendst{k}{\btimest{k}{t}} = T$
%and $\pendst{k}{t'} = F$ for all $\btimest{k}{t} < t' \le t$, and we
%can use the network manipulation rules in \ref{subsubsec:pol-terminate}
%and \ref{subsubsec:pol-select} to modify the original DBN accordingly.
%In particular, we can group all the policy nodes at level $k$ from time
%$\btimest{k}{t}+1$ and $t$ into a single node representing the current
%policy \polst{k}{t}. Furthermore, we can also remove the link from the
%last policy at level $k$ to \polst{k}{t}.

%Furthermore, at time \btimest{k}{t}, all the policies at level $l < k$ also
%terminates. Thus, there is no link from the policy nodes 

%Knowing that 


%From these,
%we also obtain $\pendst{l}{\btimest{k}{t}} = T$ for all $l \le k$, and
%$\pendst{l}{t'} = F$ for all $l \ge k$. Knowing that $\pendst{l}{t'} = F$,
%we can merge all the policy nodes at level $l$ 
%between time $\btimest{k}{t} + 1$ and $t$ together. 
%Knowing that $\pendst{l}{\btimest{k}{t}} = T$ allows us to remove all 
%the links at level $l$ from time \btimest{k}{t} to $\btimest{k}{t}+1$. These
%node-merging and link removal operations result in a network with a
%structure in Fig.~\ref{fig:independence}. Once the modified network structure 
%is obtained,  we  can observe that
%\polst{>k}{t} and \polst{<k}{t} are d-separated by \polst{k}{t} and
%\bstatest{k}{t} in the new structure. Thus \polst{>k}{t} and \polst{<k}{t} 
%independent given \polst{k}{t}, \bstatest{k}{t} and \btimest{k}{t}.
%\end{proof}

\begin{figure}
\begin{center}\epsfbox{independence.eps}
\caption{\label{fig:independence} 
Network structure after being conditioned on \btimest{k}{t}}
\end{center}
\end{figure}


%\input{proof.tex}

%\newpage
\section{Policy Recognition}
\label{sec:pol-rec}

\rem{Define policy recognition}

In this section we begin to address the problem of policy 
recognition in the framework of the AHMM. We assume that a policy hierarchy
is given and is modelled by an AHMM, however the top level policy and the
details of its execution are unknown. The problem is then to determine the
top level policy and other current policies at the lower levels given the
current sequence of observations.
In more concrete terms, we are interested in the conditional probability:
\[\CPr{\polst{K}{t},\ldots,\polst{0}{t}}{\hobst{t-1}}\]
and especially, the marginals:
\[\CPr{\polst{k}{t}}{\hobst{t-1}}, \text{ for all levels }k\] 
Computing these probabilities gives us the
information about the current policies at all levels of abstraction, from the
current action ($k=0$), to the top-level policy ($k=K$), taking into
account all the observations that we have up to date.



\rem{Discuss difficulties}

In typical monitoring situations, 
these probabilities need to be computed ``online'',
as each new observation becomes available. To do this, it is required to
update the belief state (filtering distribution) 
of the AHMM at each time point $t$. This problem is generally 
intractable unless the belief state
has an efficient representation that affords a closed form update procedure.
In our case, the belief state is a joint distribution of $K+3$ discrete
variables:
$\CPr{\polst{K}{t},\ldots,\polst{0}{t},\statet{t},\topendt{t}}{\hobst{t}}$.
Without any further structure imposed on the belief state, the complexity
for updating it is exponential in $K$.


\rem{Plan of attack and things to follow}

To cope with this complexity, one generally has to resort to some form of
approximation to trade off accuracy for computational resources.
On the other hand, the analysis of the AHMM network in the previous 
section suggests
that the problem of inference in the AHMM can be tractable in the special
case when the history of the state and terminating status variables is
known.  Motivated by this property of the AHMM, 
our main aim in this section is to derive a hybrid inference scheme that
combines both approximation and tractable exact inference for efficiency.
We first treat the special
case of policy recognition where the belief state of the AHMM has a 
tractable structure in~\ref{subsec:polrec-tractable}. 
We then present a hybrid inference scheme for the general case
using the Rao-Blackwellised Sequential Importance Sampling (RB-SIS)
method in~\ref{subsec:polrec-general}. 



%We then discuss the
%sequential importance sampling with Rao-Blackwellisation (RB-SIS) method for 
%general Dynamic Bayesian Network in~\ref{subsec:rb-sis}. We apply RB-BIS to 
%the AHMM and present a algorithm for policy recognition for the general
%case in~\ref{subsec:polrec-general}.



\subsection{Policy Recognition: the Tractable Case}
\label{subsec:polrec-tractable}

\rem{Limit to the tractable case}

Here, we address the policy recognition problem under two assumptions: 
(1) the state sequence can be observed with certainty, and (2)
the exact time when each policy starts and ends is known.
More precisely, our
observation at time $t$ includes the state history
$\hstatet{t} = (\statet{0},\ldots,\statet{t})$ and the policy termination
history $\htopendt{t} = (\topendt{0},\ldots,\topendt{t})$. The belief state
that we need to compute in this case is 
$\bst{t} =
\CPr{\polst{all}{t},\statet{t},\topendt{t}}{\hstatet{t-1},\htopendt{t-1}}$
and its posterior after absorbing the observation at time $t$:
$\bst{t+} = \CPr{\polst{all}{t}}{\hstatet{t},\htopendt{t}}$.

\rem{discuss the assumptions}

The first assumption means that the observer always knows the 
true current state and is often referred to as ``full observability''. When
the states are fully observable, we can ignore the observation layer
$\{\obst{t}\}$ in the AHMM and thus only have to deal with the AMM instead. 
The second assumption means that the observer is fully aware when the
current policy ends and a new policy begins. 
If the policy hierarchy is constructed from the
region-based decomposition of the state space 
(subsection~\ref{subsec:rd-hierarchy}),
the termination status can be inferred directly from the state
sequence. Thus for SRD policy hierarchies, only the full observability
condition is needed since the second assumption is
subsumed by the first and can be left out. Except for SRD policy
hierarchies,
these two assumptions are usually too restrictive for the 
policy recognition algorithm
presented here to be useful by itself. However, the
algorithm for this special case will form the exact
step in the hybrid algorithm presented in 
subsection~\ref{subsec:polrec-general}
for the general case.

%In section~\, we will assume full
%observability, i.e. the observation sequence at time $t$ is the state sequence 
%$\hstatet{t-1} = (\statet{0},\ldots,\statet{t-1})$. 

%In more concrete terms, we
%are interested in the probabilities
%\CPr{\polst{k}{t}}{\hstatet{t-1}} for all level $k$. This gives us
%information about the agent's behaviour at all levels of
%abstraction, from the current action ($k=0$), to the 
%top-level policy ($k=K$). In addition, continuous monitoring would require 
%to compute these probabilities in all time steps $t$ (whenever an
%observation is made).

%Our solution to this problem is based on updating the belief state of
%the AMM, i.e. the joint
%distribution
%\CPr{\polst{K}{t},\ldots,\polst{0}{t},\statet{t}}{\hstatet{t-1}}. 
%Thus, the size of the representation of this distribution is crucial. 

\subsubsection{Representation of the belief state}

We first look at the conditional joint distribution 
$\CPr{\polst{all}{t},\statet{t}}{\hstatet{t-1},\htopendt{t-1}}$.
From the termination history \htopendt{t-1}, we can derive precisely the
starting time of the current level-k
policy: 
\[
\btimest{k}{t} 
= \max \{0\} \cup \{t' < t|\, \pendst{k}{t'} = T\}
= \max \{0\} \cup \{t' < t |\, \topendt{t'} \ge k\}
\]
On the other hand, knowing the starting time together with the 
state history also gives us the
starting state \bstatest{k}{t}. Thus, both the starting time and the
starting state of \polst{k}{t} can be derived from \hstatet{t-1} and
\htopendt{t-1}. From Theorem~\ref{thrm-ind}, we obtain for all level $k$:
\[
\polst{>k}{t} \pind \polst{<k}{t} \,|\, \polst{k}{t},\hstatet{t-1},
\htopendt{t-1}
\]
In other words, given \hstatet{t-1} and \htopendt{t-1}, the conditional
joint distribution of
$\{\polst{K}{t},\ldots,\polst{0}{t},\statet{t}\}$ can be represented by a
Bayesian network with a simple chain structure. We denote this chain network
by $\chaint{t} \equiv 
\CPr{\polst{all}{t},\statet{t}}{\hstatet{t-1},\htopendt{t-1}}$ 
and term it the {\em belief chain} for the role it plays in the 
representation of the belief state
(Fig.~\ref{fig:belstate}(a)).
If a chain is drawn so that all links point away from the level-k node, we
say that the chain has root at level $k$.
The root of the chain can be moved 
from $k$ to another level $k'$ simply by reversing the
links lying between $k$ and $k'$ using the standard link-reversal 
operation for Bayesian networks~\cite{Sha86}.

Each node in the belief chain also has a manageable size. In
principle, the domain of \polst{k}{t} is $\Pol^k$,
the set of all policies at level $k$, and the domain of \statet{t} is
\states, the set of all possible states. 
When $K$ is large, we basically want to model a larger state space, and
the set of policies to cover this state space is also large. 
The sizes of these domains would
most likely grow exponential w.r.t. $K$. 
However, given
a particular state, the number of policies applicable at that state would
remain relatively constant and independent of $K$. 
For each policy
\polst{k}{t}, we know its starting state \bstatest{k}{t}, which implies
that $\polst{k}{t} \in \Pol^k(\bstatest{k}{t})$, the set of all level-$k$
policies applicable at \bstatest{k}{t}. Thus $\Pol^k(\bstatest{k}{t})$ can
be used as the ``local'' domain for \polst{k}{t} to avoid the exponential
dependency on $K$. Similarly, the domain for \statet{t} can be taken as the
set of neighbouring states of \statet{t-1} (reachable from \statet{t-1} by
performing one primitive action). For a given state, we term the maximum
number of relevant objects 
(applicable policies/actions, neighbouring states) at a single
level the {\em degree of connectivity} $\mathcal{N}$ 
of the domain being modelled. 
The size of the conditional probability table for each link of 
the belief chain is then $O(\mathcal{N}^2)$, and the overall size
of the belief chain is $O(K \mathcal{N}^2)$. 


%For consistency purpose, level -1 will refer to the node \statet{t}, and
%thus $\polst{-1}{t} \equiv \statet{t}$.


%From 
%Theorem~\ref{thrm-ind}, if the starting time of the current level-k
%policy \btimest{k}{t} can be determined from the state sequence \hstatet{t-1}, 
%then so can the starting state \bstatest{k}{t}, and the belief state can be
%split into two independent parts conditioned on \polst{k}{t}: 
%%$\polst{>k}{t} \longleftarrow \polst{k}{t} \longrightarrow \polst{>k}{t}$.
%$\polst{>k}{t} \pind \polst{<k}{t} \,|\, \polst{k}{t},\hstatet{t-1}$.
%This condition is satisfied when the applicable domains of all the policies 
%at level $k$ do not partially overlap (i.e. any two domains 
%are either identical or mutually exclusive), so that the starting point of 
%the current policy \polst{k}{t} can be identified as the last time the state
%history sequence \hstatet{t-1} crossed 
%a region boundary at level $k$.


\begin{figure}
\begin{center}\epsfbox{belstate.eps}
\caption{\label{fig:belstate} Representation of the belief state}
\end{center}
\end{figure}

\begin{figure}
\begin{center}\epsfbox{bsupdate1.eps}
\caption{\label{fig:bsupdate1} Belief state updating: from \bst{t} to \bst{t+}}
\end{center}
\end{figure}


We now can construct the belief state \bst{t} from \chaint{t}.
Since the current terminating status is solely determined by the current
policies and the current state, the belief state \bst{t} can be factorised 
into:
\[
\CPr{\polst{all}{t},\statet{t},\topendt{t}}{\hstatet{t-1},\htopendt{t-1}}
=
\CPr{\topendt{t}}{\polst{all}{t},\statet{t}}
\CPr{\polst{all}{t},\statet{t}}{\hstatet{t-1},\htopendt{t-1}}
=
\CPr{\topendt{t}}{\polst{all}{t},\statet{t}}
\chaint{t}
\]
Note that the variable \topendt{t} is equivalent to the set of
variables $\{\pendst{K}{t},\ldots,\pendst{1}{t}\}$. Thus,
the full belief state
\bst{t} can be realised by adding to \chaint{t} the links from
the current policies and the current state to the terminating status
variables \pendst{k}{t} (Fig.~\ref{fig:belstate}(b)). The size of the
belief state would still be $O(K\mathcal{N}^2)$. 
If the state is a composite of many orthogonal variables, a factored
representation can be used so that the size of the belief state
representation does not depend exponentially on the dimensionality of 
the state space. We discuss factored representations 
further under subsection~\ref{subsubsec:factored-er}.



\subsubsection{Updating the belief state}

\rem{general about exact belief state update}

Since 
the belief state \bst{t} can be represented by a simple belief
network in Fig.~\ref{fig:belstate}(b), we 
can expect that a general exact inference method for
updating the belief state such as~\cite{Kja95} will work efficiently. 
However, this general method works with undirected network representation
of the belief state distribution which can be inconvenient for us later on
when we want to sample from such a distribution.
Here, we describe an algorithm that updates the belief state in the
closed form given by the directed network in Fig.~\ref{fig:belstate}(b).


\rem{updating procedure}

Assuming that we have a complete specification of the belief state \bst{t}, 
i.e., all the parameters for its Bayesian network representation,
we need to compute the parameters for the new network 
\bst{t+1}. This is done
in two steps, as in the standard ``roll-over'' of the belief state of
a DBN: (1) absorbing the new evidence \statet{t}, \topendt{t} 
and (2) projecting the belief state into the next time step.


\rem{the first step}

The first step corresponds to the instantiation of the variables \statet{t},
$\pendst{1}{t},\ldots,\pendst{K}{t}$ in the Bayesian network \bst{t} 
to obtain \bst{t+} which is
the conditional joint distribution of $\polst{K}{t},\ldots,\polst{0}{t}$.
By checking the conditional independence relationships in
Fig.~\ref{fig:belstate}(b), it is easy to see that 
\bst{t+} again has a simple chain network structure. Thus, conceptually,
the problem here is to update the parameters of the chain \chaint{t} so as
to absorb the given evidence to form a new chain \bst{t+}. This can be done
by a number of link-reversal steps as follows.

To instantiate \statet{t}, we first move the root of the chain \chaint{t}
to \statet{t}. The variable \statet{t} then has no parents and can be
instantiated and deleted from the network (Fig.~\ref{fig:bsupdate1}(a)).

To instantiate \topendt{t} which is equivalent to the value assignment
$
(\pendst{K}{t} = F,\ldots,
\pendst{\topendt{t}+1}{t}=F,
\pendst{\topendt{t}}{t}=T,
\ldots\,
\pendst{1}{t} = T)
$, starting from $k=1$, 
we iteratively reverse the links from \polst{k-1}{t} to \polst{k}{t} and from
\polst{k}{t} to \pendst{k}{t} (Fig.~\ref{fig:bsupdate1}(b)). 
In algebraic
forms, the first link reversal operation corresponds to computing the
following probabilities:
\begin{eqnarray}
\CPr{\polst{k}{t}}{\statet{t},\pendst{1}{t},\ldots,\pendst{k-1}{t}}
&=&
\sum_{\polst{k-1}{t}} 
	\CPr{\polst{k}{t}}{\polst{k-1}{t}}
	\CPr{\polst{k-1}{t}}{\statet{t},\pendst{1}{t},\ldots,\pendst{k-1}{t}}
\\
\CPr{\polst{k-1}{t}}{\polst{k}{t}, \statet{t},\pendst{1}{t},\ldots,\pendst{k-1}{t}}
&\propto&
\CPr{\polst{k}{t}}{\polst{k-1}{t}}
\CPr{\polst{k-1}{t}}{\statet{t},\pendst{1}{t},\ldots,\pendst{k-1}{t}}
\end{eqnarray}
and the second link reversal corresponds to:
\begin{equation}
\CPr{\polst{k}{t}}{\statet{t},\pendst{1}{t},\ldots,\pendst{k}{t}}
\propto
\CPr{\pendst{k}{t}}{\polst{k}{t},\statet{t},\pendst{k-1}{t}}
\CPr{\polst{k}{t}}{\statet{t},\pendst{1}{t},\ldots,\pendst{k-1}{t}}
\end{equation}

Effectively,
the $k$-th link reversal step positions the root of the chain \chaint{t} at
\polst{k}{t} and absorbs the evidence \pendst{k}{t}.
By repeating this link reversal operations with  $k=1,\ldots,\topendt{t}+1$, 
we obtain a new chain for \bst{t+} which has root at level $\topendt{t}+1$.
Note that there is no need to incorporate the instantiations
$\pendst{k}{t}=F$ for $k>\topendt{t}+1$ since they are the direct 
consequences of the instantiation $\pendst{\topendt{t}+1}{t} = F$.
The parameters of the chain \bst{t+} are given below. The upward links
remain the same as those of \chaint{t}, while the marginal at level
$\topendt{t}+1$ and the downward links are obtained as the results of 
the link reversal operations above:
\begin{eqnarray}
\CPr{\polst{k+1}{t}}{\polst{k}{t},\statet{t},\topendt{t}} 
&=& 
\CPr{\polst{k+1}{t}}{\polst{k}{t}}, 
k\ge\topendt{t}+1
\nonumber
\\
\CPr{\polst{k}{t}}{\statet{t},\topendt{t}}
&=& 
\CPr{\polst{k}{t}}{\statet{t},\pendst{1}{t},\ldots,\pendst{k}{t}},
k = \topendt{t}+1
\nonumber
\\
\CPr{\polst{k-1}{t}}{\polst{k}{t},\statet{t},\topendt{t}}
&=&
\CPr{\polst{k-1}{t}}{\polst{k}{t}, \statet{t},\pendst{1}{t},\ldots,\pendst{k-1}{t}},
k \le \topendt{t}
\nonumber
\end{eqnarray}


\rem{the second step}

In the second step, we continue to compute \chaint{t+1} from \bst{t+}.
Since all the
policies at levels higher than \topendt{t} do not terminate, 
$\polst{>\topendt{t}}{t+1}=\polst{>\topendt{t}}{t}$, and we can 
retain this upper sub-chain from \bst{t+} to \chaint{t+1}.
In the lower part, for $k \le \topendt{t}$, 
a new policy \polst{k}{t+1} is created by the
policy \polst{k+1}{t+1} at the state \statet{t}, and thus a new sub-chain can
be formed among the variables \polst{<\topendt{t}}{t+1} with parameters
$\CPr{\polst{k}{t+1}}{\polst{k+1}{t+1},\statet{t}} = 
\tran_{\polst{k+1}{t+1}}(\statet{t},\polst{k}{t+1})$. 
Note that the domain of the newly-created node \polst{k}{t+1} is
$\Pol^{k}(\statet{t})$.
The new chain
\chaint{t+1} is then the combination of these two sub-chains, 
which will be a chain with root at level $\topendt{t}+1$
(see Fig.~\ref{fig:bsupdate2}). 
Once we have the chain \chaint{t+1},
the new belief state \bst{t+1} can be obtained by simply adding the terminating
status variables $\{\pendst{k}{t+1}\}$ to \chaint{t+1}.

This completes the procedure for updating the belief state from \bst{t} to
\bst{t+1}, thus allowing us to compute the belief state \bst{t} at each
time step. Although the belief state is the joint distribution of all the
current variables, due to its simple structure, the marginal distribution 
of a single variable can be computed easily. For example, if we are only
interested in the current level-$k$ policy \polst{k}{t}, the marginal
probability
\CPr{\polst{k}{t}}{\hstatet{t-1},\htopendt{t-1}} is simply the marginal 
at the level-$k$ node in the chain \chaint{t}, and can be readily obtained
from the chain parameters.

The complexity of the belief state updating procedure at time $t$
is proportional to \topendt{t} since it only needs to modify the bottom
\topendt{t} levels of the belief state. On the other hand,
the probability that the current policy at level $l$ 
terminates can be assumed to be exponentially small w.r.t. $l$. 
Thus, the average updating
complexity at each time-step is $O(\sum_l l/exp(l))$ which is 
constant-bounded, and thus does not depend on the number of levels in
the policy hierarchy. In terms of the number of policies and states, the
updating complexity is linear to the size of a policy node in the belief chain, 
thus is linear to the degree of connectivity of the domain.

\begin{figure}
\begin{center}\epsfbox{bsupdate2.eps}
\caption{\label{fig:bsupdate2} Belief state updating: 
from \bst{t+} to \chaint{t+1}}
\end{center}
\end{figure}

\subsection{Policy Recognition: The General Case}
\label{subsec:polrec-general}

\rem{problem}

We now return to the general case of policy recognition, i.e., without the two
assumptions of the previous subsection. 
This makes 
the inference tasks in the AHMM much more difficult.
Since neither the starting times
nor the starting states of the current policies are known with certainty,
theorem~\ref{thrm-ind} cannot be used.  
Thus, the set of current policies no longer forms a
chain structure as it did in \chaint{t} since the conditional
independence properties of the current time-slice no longer hold.
We therefore cannot hope to represent the belief state by a simple 
structure as we did previously. 
An exact method for updating the belief state
will thus have to operate on a structure with size 
exponential in $K$, and is bound to be intractable when $K$ is large.

To cope with this complexity, an
approximation scheme such as 
sequential importance sampling (SIS)~\cite{DGA000,LiC98,KKR95}
can be employed.
In our previous work~\cite{BuiVW99}, 
we have applied an SIS method known as
the likelihood weighting with evidence
reversal (LW-ER)~\cite{KKR95}
to an AHMM-like network structure. 
However the SIS method needs to sample in the product space of 
all the layers of the AHMM and thus becomes less accurate and inefficient
with large $K$. 
The key to get around this inefficiency is to utilise the special 
structure of the AHMM, particularly, its special tractable case, 
to keep the set of variables that need to be sampled to a minimum.

The improvement of the SIS method to achieve this is has been presented in
subsection~\ref{subsec:rb-sis} in the name of the Rao-Blackwellised SIS
(RB-SIS) method. 
Rao-Blackwellisation specifically allows the marginalisation of some 
variables analytically and only samples the remaining variables. As a
result, this reduces the averaged error, measured as the variance of the
estimator~\cite{CaR96}. 

In order to apply RB-SIS to the AHMM, the main problem is to identify which
variables should be used as the Rao-Blackwellising variables and should
still be sampled, with the remaining variables being marginalised analytically. 
The key to choosing the Rao-Blackwellising variables, as we have shown 
in~\ref{subsec:rb-sis}, is
so that if those variables can be observed, the Rao-Blackwellised belief state 
becomes tractable.
In subsection~\ref{subsec:polrec-tractable}, we have demonstrated 
that if the state
history $\hstatet{t}$ and the terminating status history $\htopendt{t}$ can
be observed then the belief state has a simple network structure and
can be updated with constant average complexity. 
Thus, $(\statet{t},\topendt{t})$ can be used
conveniently as the Rao-Blackwellising variable $r_t$. 
Note that the variables $\htopendt{t}$ are the context variables which help
to simplify the network structure of the AHMM, while the 
state variables \hstatet{t}
help to make the remaining network singly-connected so that exact inference
can operate efficiently
(see subsection~\ref{subsubsec:full-DBN}).

%in~\ref{subsec:rb-sis-ahmm}. 

%The special tractable case of the AHMM can be exploited by combining the
%sampling scheme with a {\em Rao-Blackwellisation} (RB) procedure~\cite{CaR96}.


%The combination of sequential importance sampling and Rao-Blackwellisation
%has been suggested in~\cite{DGA000,LiC98} and recently applied to inference
%in Dynamic Bayesian Network~\cite{BuiVW000:aaai,DFM000,Mur000}. 

%\rem{outline}

%We first introduce the sequential importance sampling
%(SIS) method as a general approximate inference 
%scheme for DBNs in~\ref{subsec:sis}. We then discuss
%Rao-Blackwellisation as a way to exploit the tractability in 
%partial structures of a DBN in~\ref{subsec:rb-sis}. 
%Our discussion includes a novel improvement over the
%existing sequential importance sampling with Rao-Blackwellisation (RB-SIS)
%method~\cite{DFM000,Mur000} which allows for non-Markov 
%Rao-Blackwellising variables. 



\subsubsection{RB-SIS for AHMM}
\label{subsec:rb-sis-ahmm}

%We are now in the position to apply the RB-SIS method to the policy
%recognition problem in the AHMM. 

We now discuss the specific application of
RB-SIS to the problem of belief state
updating and policy recognition in the AHMM.
Our main objective is to use RB-SIS to estimate the conditional 
probability of the policy currently being executed at level-$k$ given the
current sequence of observations 
$\CPr{\polst{k}{t+1}}{\hobst{t}}$. 

Mapping the RB-SIS general framework in subsection~\ref{subsec:rb-sis} to
the AHMM structure, the set of all
current variables $x_t$ is now 
the set of current policies, terminating status
nodes, and the current state: $x_t = (\polst{all}{t},\statet{t},\topendt{t})$.
The probability under estimation
$\CPr{\polst{k}{t+1}}{\hobst{t}}$
can be viewed as an expectation by letting 
$f(\polst{all}{t},\statet{t},\topendt{t}) = 
\Pr(\polst{k}{t+1} | \polst{all}{t},\statet{t},\topendt{t})$ so that:
\[
\bar{f} = \sum_{\polst{all}{t},\statet{t},\topendt{t}} 
\Pr(\polst{k}{t+1} | \polst{all}{t},\statet{t},\topendt{t}) 
\Pr(\polst{all}{t},\statet{t},\topendt{t}|\tsq{o}{t})
= \CPr{\polst{k}{t+1}}{\hobst{t}}
\]

%\bar{f} = \ev f(x_t) \CPr{\polst{k}{t+1}}{\hobst{t}}

%In
%subsection~\ref{subsec:polrec-tractable}, we have shown that if the state
%history $\hstatet{t}$ and the terminating status history $\htopendt{t}$ can
%be observed then the belief state has a simple network structure and
%can be updated with constant average complexity. 
%Thus, $(\statet{t},\topendt{t})$ can be used
%conveniently as the Rao-Blackwellising variable $r_t$. 
%Note that the variables $\htopendt{t}$ are the context variables which help
%to simplify the structure of the AHMM, while the state variables \hstatet{t}
%help to make the remaining network singly-connected
%(see subsection~\ref{subsubsec:full-DBN}).

Using RB-SIS to estimate this expectation, 
we shall split $x_t$ into two sets of variables:
the set of RB variables $r_t= (\statet{t},\topendt{t})$, 
and the set of remaining variables $z_t = \polst{all}{t}$ which
is the set of all the current policies. The functional $h$, which depends only
on the RB variables and is obtained from $f$ by integrating out the
remaining variables (Eq. (\ref{eqn:h-rb})), now has the form:
\begin{equation}
h(\tsq{r}{t}) =
h(\hstatet{t},\htopendt{t}) = 
\sum_{\polst{all}{t}} 
\CPr{\polst{k}{t+1}}{\polst{all}{t},\statet{t},\topendt{t}}
\CPr{\polst{all}{t}}{\hstatet{t},\htopendt{t},\hobst{t}} =
\CPr{\polst{k}{t+1}}{\hstatet{t},\htopendt{t}}
\label{eqn:h-ahmm}
\end{equation}
which is the marginal $\chaint{t+1}(\polst{k}{t+1})$ from the belief chain at time
$t+1$.

The RB belief state, which is the belief state of the AHMM when the RB
variables are known, becomes:
\begin{equation}
\rbst{t} =
%\CPr{z_t,r_t,o_t}{\tsq{r}{t-1},\tsq{o}{t-1}}
%=
\CPr{\polst{all}{t},\statet{t},\topendt{t},\obst{t}}
{\hstatet{t-1},\htopendt{t-1},\hobst{t-1}}
=\CPr{\polst{all}{t},\statet{t},\topendt{t},\obst{t}}
{\hstatet{t-1},\htopendt{t-1}}
\label{eqn:rbbel-ahmm}
\end{equation}
and is identical to the special belief state \bst{t} discussed in
subsection~\ref{subsec:polrec-tractable}, except a minor modification to
attach the observation variable \obst{t}. 

From (\ref{eqn:h-ahmm}) and (\ref{eqn:rbbel-ahmm}), both the
$h$ function and the RB belief state can be computed very efficiently using the
exact inference techniques described in 5.1. Thus RB-SIS can be implemented
efficiently with minimal overhead in exact inference.

The main RB-SIS algorithm for the AHMM is given in
Fig.~\ref{fig:algo-RB-SIS-AHMM}.
Note that we only need to sample the RB variables 
\hstatet{t} and \htopendt{t}.
For each sample $i$, in addition to the weights $\weight^{(i)}$, we also
maintain a parametric representation of the Rao-Blackwellised belief state
$\bst{t}^{(i)}$, and the value of the $h$ function for 
that sample $h^{(i)}$. 
The weights of the samples, together with the values of the
$h$ function can then be combined to yield an
approximation for $\bar{f}$.


\begin{figure}
\small
\begin{center}
\begin{algorithm}
Begin\\
For $t=0,1,\ldots$ \\
\q	For each sample $i=1,\ldots,N$  \\
%\q\q	Sample $s_t^{(i)},l_t^{(i)},\polst{all}{t}$ from 
%$\bst{t}^{(i)}(s_t,l_t,\polst{all}{t}|o_t)$ \\
%\q\q Discard unnecessary sample \polst{all}{t}\\
\q\q	Sample $s_t^{(i)},l_t^{(i)}$ from 
$\bst{t}^{(i)}(s_t,l_t|\,o_t)$ \\
\q\q	Update weight $\weight^{(i)} = \weight^{(i)}\bst{t}^{(i)}(o_t) $ \\
\q\q	Compute the posterior RB bel state	
$\bst{t+}^{(i)} = \bst{t}^{(i)}(\polst{all}{t}|s_t^{(i)},l_t^{(i)},o_t)$\\
\q\q	Compute the belief chain $\chaint{t+1}^{(i)}$ from $\bst{t+}^{(i)}$\\ 
\q\q	Compute the new belief state $\bst{t+1}^{(i)}$ from
$\chaint{t+1}^{(i)}$ \\
\q\q	Compute $h^{(i)} = \chaint{t+1}^{(i)}(\polst{k}{t+1})$\\
\q	Compute the estimator 
$\CPr{\polst{k}{t+1}}{\hobst{t}} \approx \hat{f}_{RBSIS} = \sum_{i=1}^N h^{(i)}\normweight^{(i)}$\\
End \\
\end{algorithm}
\caption{RB-SIS for policy recognition}
\label{fig:algo-RB-SIS-AHMM}
\end{center}
\end{figure}


%Substituting these into the RB-SIS main algorithm , we obtain the
%algorithm for policy recognition in the general case

%In this particular realisation of the RB-SIS, we can use the optimal
%importance distribution $q_t = \bst{t}(\statet{t},\topendt{t}|\, \obst{t})$
%with the weight update factor $w_t = \bst{t}(\obst{t})$.

\begin{figure}
\begin{center}\epsfbox{rbsample.eps}
\caption{\label{fig:rbsample} Sampling the Rao-Blackwellising variables in
AHMM}
\end{center}
\end{figure}


Some details on how we can obtain the new samples at each time step
are worth noting here.
Since we are using the optimal sampling distribution $q_t = \bst{t}(\statet{t},
\topendt{t}|\, \obst{t})$ to sample 
the RB variables \statet{t} and \topendt{t}, 
we need to perform the 
evidence reversal step.\footnote{The term {\em evidence reversal}
is used in this paper to refer to a general procedure in which the
link to the observation node is reversed prior to sampling~\cite{KKR95}, 
thus allowing
us to sample according to the optimal sampling distribution $q_t$.}
This can be done by
positioning the root of the belief chain \chaint{t} at
\statet{t} and reverse the link from \statet{t} to \obst{t}. 
This gives us the network structure for
$\bst{t}^{er} = \bst{t}(\statet{t},\topendt{t},\polst{all}{t}|\,\obst{t})$ which is
exactly the same as \bst{t} (see Fig.~\ref{fig:rbsample}), 
except that the evidence \obst{t} has been
absorbed into the marginal distribution of \statet{t}.
The weight $w_t = \bst{t}(\obst{t})$ can also be obtained as a by-product
of this evidence reversal step.
%, and the network structure for 
%$\bst{t}(\statet{t},\topendt{t},\polst{all}{t}|\,\obst{t})$.
In order to sample \statet{t} and \topendt{t} from $\bst{t}^{er}$
without the need to compute the marginal distribution for these 
two variables,
we can use forward sampling to sample every variable of 
%$\bst{t}(\statet{t},\topendt{t},\polst{all}{t}|\obst{t})$, 
$\bst{t}^{er}$,
starting from
the root node \statet{t} and proceeding upward. Since $\topendt{t}$ by
definition is the highest level of policy termination, the sampling can
stop at the first level $k$ where $\pendst{k}{t} = F$.
We can then assign $\topendt{t}$ the value $k-1$.
Any unnecessary samples for the policy nodes along the way are
discarded. Once we have the new samples for \statet{t} and \topendt{t},
%\polst{all}{t} is then discarded. 
the updating of the RB belief
state from \bst{t} to \bst{t+1} is 
identical to the belief state updating procedure
described in~\ref{subsec:polrec-tractable}. 
The $h$ function can then be obtained by computing the corresponding
marginal of the new belief chain \chaint{t+1}.

At each time step, the complexity of maintaining a sample (sampling the new
RB variables and updating the RB belief state) is again $O(\topendt{t})$,
and thus, on average, bounded by a constant. The overall complexity of
maintaining every sample is thus $O(N)$ on average. If a prediction is
needed, for each sample, we have to compute $h$ by manipulating the 
chain \chaint{t+1} with the complexity $O(K)$. Thus the complexity 
at the time step when a prediction needs to be made is $O(NK)$.

%which has constant average complexity. 
%Both the time and space complexity of
%this RB-SIS procedure is linear to the number of samples $N$ and to the
%number of levels in the policy hierarchy $K$.

In comparison with the use of an SIS method such as LW-ER, the RB-SIS has
the same order of computational complexity (the SIS also has 
complexity $O(NK)$).
However, while the SIS method needs to sample every layers of the AHMM, 
the
RB-SIS method only needs to sample two sequences of variables \hstatet{t},
\htopendt{t}, and avoids having to sample the $K$ policy sequences
$\{\hpolst{k}{t}\}$. After Rao-Blackwellisation,
the dimension of the sample space 
becomes much smaller, and more importantly, does not grow with $K$. 
As a result, the accuracy of the approximation by the RB-SIS method
does not depend on the height of the hierarchy $K$.
In contrast, due to the problems of sampling in high dimensional space,
the accuracy of SIS methods tends to degrade, especially when $K$ is large.


\subsubsection{Performing Evidence Reversal with a Factored State Space}
\label{subsubsec:factored-er}

\rem{introducing factored representation}


In many cases, the state space \states\ is the Cartesian product of many
state variables representing relatively independent properties of a state:
$\statet{t} = (\statet{t}^1,\statet{t}^2,\ldots,\statet{t}^M)$. 
Since the overall state space is very large, specifying an action by
the usual transition probability matrix is problematic.
It is advantageous in this case to represent the state information in a
factored form, i.e., representing each state variable 
$\statet{t}^m$ in a separate node rather than lumping them into a single node
$\statet{t}$.
It has been shown that using factored representations, we can specify
the transition probability of each action in a compact form since
an action is likely to affect only a small number of state variables and
the specification of the effects of actions has many 
regularities~\cite{BDG001}.


The representation of the belief chain \chaint{t} and also
the RB belief state \bst{t} can take direct advantage
of this factored representation of actions. Indeed,
the chain parameter 
$\chaint{t}(\statet{t} | \polst{0}{t})$
of the link from \polst{0}{t} to \statet{t}
is precisely the transition probability for the action \polst{0}{t} 
at the previous state \statet{t-1} (note that \statet{t-1} 
is known due to Rao-Blackwellisation).  This conditional distribution
can be extracted from the compact factored representation of \polst{0}{t}
in the general form of a Bayesian network of the variables 
$\{\statet{t}^1,\statet{t}^2,\ldots,\statet{t}^M\}$. 
For our convenience, let us denote this Bayesian network by
$\factored(. | \polst{0}{t})$. 
This network is
usually sparse enough so that exact inference can operate efficiently.
For example, in the special case where
$\{\statet{t}^1,\statet{t}^2,\ldots,\statet{t}^M\}$ are independent 
given \polst{0}{t} and \statet{t-1}, \factored\ will be factored completely
into the product of $M$ marginals of $\statet{t}^m$.


%, as long as the root of the belief
%chain \chaint{t} is at the node \polst{0}{t} or above.

\rem{problem with evidence reversal}

Although factored representations can be used as part 
of the RB belief state, care must be taken 
when performing evidence reversal, i.e. to reverse the link from the
state variable to the observation node. 
In the procedure for evidence reversal discussed previously 
(see Fig.~\ref{fig:rbsample}), we first
position the root of \chaint{t} at the node \statet{t}, thus need to
compute and represent the distribution $\Pr(\statet{t})$. 
In the factored state space case, this becomes a joint distribution of all
the state variables $\{\statet{t}^1,\statet{t}^2,\ldots,\statet{t}^M\}$.
Without conditioning on the current action \polst{0}{t}, 
the factored representation of the state variables
$\{\state^m_t\}$
cannot be utilised, thus resulting in complexity exponential in $M$.

%manipulating the belief
%state so as not to destroy its tractable structure.
%In the evidence reversal step discussed in the previous subsection, we need 
%to manipulate the belief state \bst{t} to obtain the network after evidence
%reversal $\bst{t}^{er} = \bst{t}(.|\obst{t})$. 

\rem{fix}

The key to get around this difficulty is to always keep the specification
of the distribution of the current state conditioned on the current action,
not vice versa. 
Thus, when computing $\bst{t}^{er} = \bst{t}(.|\obst{t})$,
we first position the root of the
chain \chaint{t} at \polst{0}{t}, and then reverse the evidence 
from $\obst{t}$ to both \polst{0}{t} and \statet{t}. 
In algebraic form, we use the following 
factorisation of the joint distribution of the current action and state
given the current observation: 
\begin{equation}
\Pr(\polst{0}{t},\statet{t} | \obst{t}) = 
\Pr(\statet{t} | \polst{0}{t},\obst{t})
\Pr(\polst{0}{t}| \obst{t})
%\Pr(\obst{t})
\label{eqn:factored-er}
\end{equation}


\begin{figure}
\begin{center}\epsfbox{factored-er.eps}
\caption{\label{fig:factored-er} 
Evidence reversal with factored state space}
\end{center}
\end{figure}


Fig.~\ref{fig:factored-er} illustrates this evidence reversal procedure. 
In the model depicted here, \factored\ can be an arbitrary Bayesian 
network. The observation model can be specified by attaching the observation
nodes $\{\obst{t}^1,\obst{t}^2,\ldots\}$ to the state variables. The overall
network representing the distribution 
$\CPr{\statet{t},\obst{t}}{\polst{0}{t}}$ will be
denoted by $\factored^{obs}(.|\polst{0}{t})$.

%For simplicity, we assume that each state variable $\statet{t}^m$ has a
%corresponding observation $\obst{t}^m$ which depends solely on
%$\statet{t}^m$.

%Each term in (\ref{eqn:factored-er}) can now be computed efficiently
%without the exponential dependency on $M$. 


We first look at the first term in the RHS of (\ref{eqn:factored-er}).
Let $\factored^{er}(.|\polst{0}{t},\obst{t})$ represent the distribution 
\CPr{\statet{t}}{\polst{0}{t},\obst{t}}. Note that $\factored^{er}$ 
can be obtained by conditioning $\factored^{obs}(.|\polst{0}{t})$ on the 
observation \obst{t}. 
%It is easy to see that $\factored^{er}$ must have a
%structure identical to \factored. 
%This is due to the fact that $\obst{t}^m$ depends only
%on $\statet{t}^m$, thus conditioning \factored\ on the observation 
%$\obst{t}^0,\ldots,\obst{t}^M$ does not change
%the structure of \factored. 
This can be achieved by 
applying an exact inference method such as
the clustering algorithm~\cite{LaS88} on the network 
$\factored^{obs}(.|\polst{0}{t})$.

For the second term in the RHS of (\ref{eqn:factored-er}), we note that:
\[
\CPr{\obst{t}}{\polst{0}{t}} = 
\sum_{\statet{t}} \CPr{\statet{t},\obst{t}}{\polst{0}{t}}
=
\sum_{\statet{t}} \factored^{obs}(\statet{t},\obst{t} | \polst{0}{t})
\]
This integration can be readily obtained as a by-product when performing
the above clustering algorithm on $\factored^{obs}(.|\polst{0}{t})$. 
Once \CPr{\obst{t}}{\polst{0}{t}} is known, we 
can compute \CPr{\polst{0}{t}}{\obst{t}}
by:
\[
\CPr{\polst{0}{t}}{\obst{t}} \propto \CPr{\obst{t}}{\polst{0}{t}}
\Pr(\polst{0}{t})
\]




%Assuming that at time $t$ we have an 
%observation $\obs^m_t$ for each state variable $\state^m_t$, we obtain
%the factorisation:
%\begin{equation}
%\CPr{\polst{0}{t},\statet{t}}{\obst{t}} =
%\left(
%\prod_{m=1}^M \CPr{\state^m_t}{\polst{0}{t},\obs^m_t}
%\right)
%\CPr{\polst{0}{t}}{\obs^1_t,\ldots,\obs^M_t}
%\label{eqn:factored-er}
%\end{equation}



%In deed, we have:
%\[\CPr{\state^m_t}{\polst{0}{t},\obs^m_t} \propto 
%\CPr{\state^m_t}{\polst{0}{t}} \CPr{\obs^m_t}{\state^m_t}\]
%and
%\[
%\CPr{\polst{0}{t}}{\obs^1_t,\ldots,\obs^M_t} \propto
%\CPr{\obs^1_t,\ldots,\obs^M_t}{\polst{0}{t}} \Pr(\polst{0}{t})
%=
%\left(
%\prod_{m=1}^M 
%\CPr{\obs^m_t}{\state^m_t}\CPr{\state^m_t}{\polst{0}{t}}
%\right)
%\Pr(\polst{0}{t})
%\]

This shows that the belief state after evidence reversal
$\bst{t}^{er} = \bst{t}(.|\,\obst{t})$ still has a simple structure 
that exploits the
independence relationships between the state variables 
$\{\state^m_t\}$ given the current action \polst{0}{t}. 
Sampling the RB variables from this structure can proceed as follows:
$\CPr{\polst{0}{t}}{\obst{t}}$ is first used to sample
\polst{0}{t}; $\factored^{er}(\statet{t}|\polst{0}{t},\obst{t})$ is then used to
sample \statet{t}. Once we have obtained the sample for \polst{0}{t} and
\statet{t}, we can proceed to sample the remaining nodes in the network
$\bst{t}^{er}$ to obtain a sample for \topendt{t} as usual.
Finally, we note that the weight $w_t = \Pr(\obst{t})$
can also be computed efficiently by:
\[
\Pr(\obst{t}) = \sum_{\polst{0}{t}} \CPr{\obst{t}}{\polst{0}{t}}\Pr(\polst{0}{t})
\]



In this evidence reversal procedure, for each value of \polst{0}{t}, we
need to perform exact inference on the structure of
$\factored^{obs}(\statet{t},\obst{t}|\polst{0}{t})$. 
Thus the complexity of this procedure
heavily depends on the complexity of the network structure of \factored.
However, as we have noted, due to the nature of the factored
representation, $\factored$ usually has a sparse structure so that exact
inference can be performed efficiently. For example, in the special case 
where \factored\
is completely factored into the product of $M$ independent state variables 
which are then independently observed, the
complexity becomes linear w.r.t. $M$.


%\[
%w_t = \Pr(\obs^1_t,\ldots,\obs^M_t) = 
%\sum_{\polst{0}{t}} 
%\left(
%\prod_{m=1}^M 
%\CPr{\obs^m_t}{\state^m_t}\CPr{\state^m_t}{\polst{0}{t}}
%\right)
%\Pr(\polst{0}{t})
%\]





\section{Experimental Results}

%By performing exact inference through updating the chain of each sample, 
%our algorithm avoids sampling at the higher layers, and thus can be
%expected to achieve better accuracy than the original sampling method
%in~\cite{KKR95}. Here, we provide the experimental result to back up this
%claim.

In this section, we present our experimental results with the
policy recognition algorithm. In subsection~\ref{subsec:effective-RB}, we
demonstrate the effectiveness of the Rao-Blackwellised sampling method for
policy recognition by comparing the performance of our Rao-Blackwellised
procedure against likelihood weighting sampling in a synthetic
tracking task. In subsection~\ref{subsec:real-tracking}, we present an
application of the AHMM framework to the problem of tracking human
behaviours in a complex spatial environment using distributed video
surveillance data.


\subsection{Effectiveness of Rao-Blackwellisation}
\label{subsec:effective-RB}

\begin{figure}
\begin{center}\epsfbox{bld.eps}
\caption{\label{fig:bld} The environment and a sample trajectory}
\end{center}
\end{figure}

\begin{figure}
\begin{center}\epsfbox{exit_pr8_1_sof.eps}
\caption{\label{fig:dest-prob} Probabilities of top-level destinations over time}
\end{center}
\end{figure}


\begin{figure}
\begin{center}
\begin{minipage}{9cm}
\epsfbox{sample_error.eps}
\end{minipage}
\\ (a) Sample size and average error\\ \vspace{0.5cm}
\begin{minipage}{9cm}
\epsfbox{sample_time.eps}
\end{minipage}
\\ (b) Sample size and CPU time\\ \vspace{0.5cm}
\begin{minipage}{9cm}
\epsfbox{time_error.eps}
\end{minipage}
\\ (c) CPU time and average error 
\caption{\label{fig:lw_vs_hyb} Performance profiles of SIS vs. RB-SIS}
\end{center}
\end{figure}

\begin{figure}
\begin{center}
\epsfbox{efficiency.eps}
\caption{Efficiency coefficients of SIS and RB-SIS\label{fig:RB-SIS-eff}}
\end{center}
\end{figure}

To demonstrate the effectiveness of the Rao-Blackwellised inference method
for AHMM, we again consider
the synthetic tracking task in which it is required
to monitor and predict the movement of an agent through the building
environment previously discussed in subsection~\ref{subsec:amm-example}.
The structure of the AHMM used is the same as the one shown in
Fig.~\ref{fig:bld-param}. 
The parameters of the policies are chosen manually, 
and then used to simulate the movement of the agent in the building. 
To simulate the observation noise, we assume that the
observation of the agent's true position can be anywhere among its
8 neighbouring cells with the probabilities given by a predefined
observation model.

%Each room is represented by a $5\times5$
%grid, and at each state, the agent can move
%in 4 possible directions. We assume that these actions have 
%0.5 failure probability, in
%which case the agent either stays in the same cell, or moves 
%unintendedly to one of the other three neighbours. 

%The policy hierarchy is constructed based on region-based 
%decomposition at three levels of abstraction. 
%The partition of the environment 
%consists of the 8 rooms at level 1, the two wings (north and south) at
%level 2, and the entire building at level 3. In each room, we use 4
%level-1 policies to model the agent's behaviours of exiting the room via 
%the 4 different doors. These policies specify which movement action the
%agent should take given the current heading.
%At the higher level, we use 3 level-2 policies in each wing
%to model the agent's behaviours of exiting the wing via the 3 wing 
%exits. These policies specify which level-1 policies the agent should take
%to leave the wing at the intended exit.
%Finally, we use a total of 4 top-level
%policies to model the agent's behaviours of leaving the building via the
%four building exits. 


\rem{SIS and RB-SIS}

We implement the RB-SIS method (with re-sampling) and use the policy
hierarchy specification and the simulated
observation sequence as input to the algorithm.  In a
typical run, the algorithm can return the probability of the main building
exit, the next wing exit, and the next room-door that the agent is
currently heading to. An example track is shown in Fig.~\ref{fig:bld}. As
the observations about the track arrive over time, 
the prediction probability distribution of which main building exit the track is
heading to is shown in Fig.~\ref{fig:dest-prob}.

To illustrate the advantage of RB-SIS, 
we also implement an SIS method without
Rao-Blackwellisation (LW with ER and re-sampling~\cite{KKR95}) 
and compare the performance of the two algorithms.
%Here, we are interested in the
%averaged error of the approximation schemes. 
We run the two 
algorithms using different sample population sizes to obtain their
performance profiles. For a given sample size $N$,
the standard deviation ($\sigma(N)$) over 50 runs in the estimated 
probabilities of the top-level policies is used as the measure of 
expected error in the probability estimates.
We also record the average time taken in each update iteration.

\rem{Discuss result}

Fig.~\ref{fig:lw_vs_hyb}(a) plots the standard deviation of the two algorithms
for different sample sizes. 
The behaviour of the error follows closely the theoretical curve 
$\sigma(N) = c/\sqrt{N}$, or $\sigma^2(N) = c^2/N$, 
with $c_{SIS} \approx 0.26$ and
$c_{RB-SIS} \approx 0.055$.
As expected, for the same number of samples,
the RB-SIS algorithm delivers much better accuracy. 

Fig.~\ref{fig:lw_vs_hyb}(b) plots the average CPU time ($\mathcal{T}$)
taken in each iteration versus the sample size. As expected, 
$\mathcal{T}(N)$ is linear to $N$, with the RB-SIS taking about
twice longer due to the overhead in updating the RB belief state while
processing each sample.

%This however comes with
%the overhead in updating the RB belief state for each sample, which makes the 
%new algorithm run about twice slower for a given sample size
%(Fig.~\ref{fig:lw_vs_hyb}(b)). 

Fig.~\ref{fig:lw_vs_hyb}(c) plots the actual CPU time taken versus 
the expected error for the two algorithms. It shows that for the same 
CPU time spent, 
the RB-SIS method still significantly reduces the error 
in the probability estimates. 

Note that for each algorithm, the quantity 
$\eta = \sigma^2(N) \mathcal{T}(N)$ is approximately
constant since the dependency on $N$ cancels one another out. Thus, 
this constant can
be used as an efficiency coefficient to measure the performance of the
sampling algorithm independent of the number of samples. For example, if an
algorithm has a twice smaller coefficient, it can deliver the same accuracy
with half CPU time, or half the variance for the same CPU time.
Fig.~\ref{fig:RB-SIS-eff} plots the efficiency coefficients for both SIS
and RB-SIS, with $\eta_{SIS} \approx 0.0018$ and $\eta_{RB-SIS} \approx
0.000235$. This indicates a performance gain of almost an order of magnitude
(8 folds) for RB-SIS.


\subsection{Application to Tracking Human Behaviours}
\label{subsec:real-tracking}

Using the policy recognition algorithm, we have implemented a real-time
surveillance system that tracks the behaviour of people in a complex indoor
environment using surveillance video data. The environment consists of a 
corridor, the Vision lab and two offices (see Fig.~\ref{trajectory 1}). 
People enter/exit the scene via the left or the right entrance of the 
corridor. The system has six static cameras with overlapping field of views
which cover most of the ground plane in the scene. 

The entire environment is divided into a grid of cells, and the current
cell position of the tracked object acts like the current state in our
AHMM.  The cameras are calibrated so that they can return the 
current position of the tracked object on the ground, however the returned
coordinates are unreliable as the cameras have to deal with noisy video
frames and occlusion of objects in the scene. 
For more information on how
low-level tracking is done with multiple cameras, readers are referred
to~\cite{NVWB02}.
We assume that the
observation of a state can only be in the area surrounding it, thus the
observation model is a matrix specifying the observation
likelihood for each cell within a neighbourhood of the current state.


\rem {Logical description of the scene}

The policy hierarchy for behaviours in this environment is constructed as
follows.  First, we construct the region hierarchy with three levels. 
At the bottom
level, we identify 7 regions of special interest: the corridor, the two
offices, the areas surrounding the Linux server, NT server, printer, and
the remaining free space in the Vision lab (Fig.~\ref{trajectory 1}).
At the higher level, all regions in the Vision lab are grouped together.
The top level consists of the entire environment.
The policy hierarchy representing people's behaviors has three levels 
corresponding to the three levels of the region hierarchy 
(see Fig.~\ref{hierarchy}). 
At the bottom level, we are interested in the behaviours that take place
within each of the 7 regions of interest. For example, 
near the Linux server, the person might be using the Linux machine, 
or simply passing through that region, leading to two different policies.
Similar policies are defined for the NT server region, 
the printer region, and the two small offices. In the corridor and inside
the Vision lab (region 1 and 5), we construct different policies 
corresponding to the different destinations that the person is heading to. 
Region 5 also has a special policy representing 
the ``walk-around'' behaviour.
At the middle level,
three policies are defined for the corridor and office space representing 
a person's plan of exiting this space by the left/right entrance or by 
the door of the Vision lab.
We define only one policy for the Vision lab
to represent the typical behaviour of a lab user (e.g., go to Linux server, 
followed by go to printer).\footnote{If we consider different groups of 
lab users, each group might give rise to a different policy at this level.}
Finally, for the top level region (the whole environment),
we define two policies representing a person's leaving the scene via the 
left/right entrance. 

%The parameters of all the policies are learned off-line by observing
%activities of people in the scene. The observation models of the AHMM are
%learned separately for each camera by comparing the people's
%positions returned by the system with the corresponding true positions of
%people which are specified manually. This process is performed off-line using a number of
%sample video sequences for each camera.

\begin{figure}
\begin{picture}(100,300) 
\put(80,0){\special{psfile=trajectory-0.eps hscale=100 vscale=100}}
\end{picture}
\caption{The environment and the trajectory of person 1}
\label {trajectory 1} 
\end{figure}

\begin{figure}
\begin{picture}(100,300) 
\put(80,0){\special{psfile=trajectory-1.eps hscale=100 vscale=100}}
\end{picture}
\caption{The trajectory of person 2}
\label {trajectory 2} 
\end{figure}


\begin{figure}
\begin{picture}(100,150) 
\put(20,0){\special{psfile=hierarchy.eps hscale=100 vscale=100}}
\end{picture}
\caption{The region and policy hierarchy}
\label {hierarchy} 
\end{figure}

\rem {Physical description of the scene}
\rem {describe the Figure}

Fig.~\ref{trajectory 1} and~\ref{trajectory 2} show two concurrent 
trajectories of two different people in this environment. 
Some sample video frames captured by the different cameras in the system
are shown in Fig.~\ref{people}.


\begin{figure}
\begin{picture}(300,140) 
 \put(0,-120){\special{psfile=person1-enter.eps hscale=45 vscale=45}}
 \put(130,-10){$(a)$}
 \put(200,-120){\special{psfile=person2-enter.eps hscale=45 vscale=45}}
 \put(330,-10){$(b)$}
\end{picture}
\caption{(a) Person 1 enters the scene and (b) Person 2 enters the scene.}
\label {people} 
\end{figure}

\begin{figure}
\begin{center}
\begin{minipage}{7cm}
\begin{center}
\epsfbox{error-time-realdata.eps}
\\ (a) Error vs. CPU time
\end{center}
\end{minipage}
\hspace{0.5cm}
\begin{minipage}{7cm}
\begin{center}
\epsfbox{efficiency-realdata.eps}
\\ (b) Efficiency coefficients
\end{center}
\end{minipage}
\end{center}
\caption{Performance of RB-SIS and SIS with real tracking data}
\label{fig:performance-realdata}
\end{figure}

\rem {AHMM help to query the destination of people}

With the AHMM model defined above, and a sequence of observations returned
by the cameras,  we first determine the performance
profiles of RB-SIS and SIS in this real environment. The two algorithms
behave in a similar way as in the previous experiment with simulated
data. Fig.~\ref{fig:performance-realdata} shows the error curve against the
CPU time for the two algorithms. The efficiency co-efficient for RB-SIS
in this case is $\eta_{RB-SIS} \approx 0.011$, and for SIS is $\eta_{SIS}
\approx 0.06$. This shows that the RB-SIS still performs about 5 times better
than SIS in this domain.

In the surveillance system, the low level tracking module returns the
observations at the rate of approximately two per second. The
observation is then passed to the RB-SIS algorithm which produces the
probability estimate of the current policy at different levels in the
hierarchy.  At the moment, our surveillance system can run in real time 
using two AMD 1G machines. Examples of the output returned by the system for
the two trajectories in Fig.~\ref{trajectory 1} and Fig.~\ref{trajectory 2}
are given below.

Fig.~\ref {pro21} 
shows the probabilities that person 1 is exiting the environment by the 
left or right entrance (denoted by $p_{\mbox {\em left\_e}}$ and 
$p_{\mbox {\em right\_e}}$ respectively). At the beginning, 
$p_{\mbox {\em left\_e}}$ increases when person 1 is heading to the left 
entrance (see the trajectory in Fig.~\ref {trajectory 1}). Then, 
$p_{\mbox {\em left\_e}}$ is approximately constant from time slice 50 
when person 1 is inside the Vision lab. This is because only one middle 
level policy is defined for the Vision lab and his movement inside the 
lab is independent of his final exit/entrance. At time slice 310, 
$p_{\mbox {\em left\_e}}$ decreases when person 1 is leaving the lab, turning right, and entering office 2. Then, it increases and approaches 1 when he 
is leaving office 2, turning left, and going towards the left entrance. 
In contrast, $p_{\mbox {\em right\_e}}$ falls quickly to zero during this time.

\begin{figure}
\begin{picture}(100,120) 
\put(60,-70){\special{psfile=21.eps hscale=100 vscale=100}}
\end{picture}
\vspace{0.1cm}
\caption{ 
The probabilities that person 1 is leaving the scene via the entrances (top level policies)}
\label {pro21} 
\end{figure}

\begin{figure}
\begin{picture}(100,120) 
\put(60,-70){\special{psfile=05.eps hscale=100 vscale=100}}
\end{picture}
\vspace{0.1cm}
\caption{ 
Behaviours of person 2 inside the Vision lab}
\label {pro05} 
\end{figure}


We now look at the results of querying of the bottom level policies. 
Fig.~\ref{pro05} shows the distribution of the possible 
destinations of person 2 from time slice 180 
to time slice 260, when he is in region 5 (see the trajectory in 
Fig~\ref {trajectory 2}). The probabilities obtained show that 
the system is able to correctly detect the ``walk-around'' behaviour.

The final result (Fig.~\ref{action_prob}) shows the inferred 
behaviours of person 1 when he is at
the Linux server region. Initially, the probabilities for ``using Linux
server'' and for ``passing through'' are the same. 
As the person stays in the same
position for an extended period of time, the system is able to identify the 
correct behaviour of person 1 as ``using the Linux server''.


\begin{figure}
\begin{picture}(100,120) 
\put(60,-70){\special{psfile=03.eps hscale=100 vscale=100}}
\end{picture}
\vspace{0.2cm}
\caption{Behaviour of person 1 inside the Linux server region}
\label {action_prob} 
\end{figure}



%Alternatively,
%the RB-SIS can achieve the same error margin with only about
%half the CPU time.


%\section{Application domains}



%\subsection{Surveillance in wide-area environment}

%\rem{Discuss PSDG}

%The AHMM is closely related to the Probabilistic State-Dependent Grammar
%(PSDG) model for plan recognition, independently proposed by~\cite{PyW000}. 
%In fact, an 
%AHMM is equivalent to a special class of PSDG where only production rules
%of the form 



%However it is easy to see
%(check!!!) that any PSDG with this type of rules can also be converted into 
%a PSDG using only the simple rule $X \rightarrow XY$ by expanding the state
%space to keep track of the order of the current symbol in its current
%expansion. Thus, the AHMM model can act like a canonical representation
%for the type of PSDG considered in~\cite{PyW000}. 




%\rem{Relevance to PSDG - not sure if it should be here or in the related
%work section}



\section{Related Work in Probabilistic Plan Recognition}
\label{sec:related-work}

%In this section, we discuss related work and its relevance to the work
%presented here. We first review probabilistic networks and inferences. The
%model for abstract probabilistic plans which arise from the work in abstract
%probabilistic planning is described next. Finally, we compare AHMM with other
%existing models for probabilistic plan recognition.

%\subsection{Probabilistic models for plan recognition} 

\rem{intro to probabilistic plan recognition}

The case for using probabilistic inference for plan recognition has been
argued convincingly by~\citeA{ChG93}. However, the plan recognition Bayesian 
network used by~\citeauthor{ChG93} is a static network. 
Thus their approach would
run into problems when they have to process on-line a stream of evidence about 
the plan. More recent 
approaches~\cite{PyW95,PyW000,GGM99,HDW94,AZN98}
have used dynamic stochastic models for plan recognition and thus are
more suitable for doing on-line plan recognition under uncertainty.

\rem{PSDG}

\rem{computational aspect of PSDG}

Among these, the most closely related model to the AHMM 
is the Probabilistic State-Dependent 
Grammar (PSDG)~\cite{Pyn99,PyW000}. A comparison of the representational 
aspect of the two models has been discussed under
subsection~\ref{subsec:amm-planmodel}.
In terms of algorithms for plan recognition,
\citeauthor{PyW000} only offer
an exact method to deal with the case where
the states are fully observable. When the states are partially observable,
a brute-force approach is suggested which amounts to summing over all possible
states. We note that even for the fully observable case, the belief state
that we need to deal with can still be large since the policy
starting/ending times are unknown.\footnote{Of course, if an SRD
policy hierarchy is considered then full observability alone is enough.}
Since an exact method is used by~\citeauthor{PyW000}, the complexity
for maintaining the belief state would most likely be
exponential to the number of levels in the PSDG expansion hierarchy (i.e.,
the height of our policy hierarchy).
%It is unclear how their algorithms would scale up for hierarchy with
%greater depth\footnote{Pending further communication with the authors.}.
On the other hand, our RB-SIS policy recognition algorithm can handle 
partially observable states and the Rao-Blackwellisation procedure ensures
that the sampling algorithm scales well with the number of levels in the
policy hierarchy. Furthermore, as we have noted in
subsection~\ref{subsec:amm-planmodel}, if we consider
compound policies, the PSDG can be converted to an AHMM. 
In our framework, a compound policy 
$\pol^k = 
\pol^{k-1}_{(1)},\ldots,
\pol^{k-1}_{(m)}$ can be represented just as a normal policy, with a slight
modification to let the variable $\pend^{k}$ take on values between $1$
and $m+1$, where the value $m+1$ indicates that the compound policy has
terminated. The policy recognition algorithm can then be modified
to also work with this model.




% and deserves a more
%independently proposed 
%detailed discussion.
%The PSDG can be described as the Probabilistic Context Free Grammar 
%(PCFG)~\cite{JLM92}, augmented with a state space, and a state transition 
%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.
%Our policy hierarchy is equivalent to a special class of PSDG
%where only production rules of the form 
%$X \rightarrow YX$ and $X \rightarrow \emptyset$ are allowed. 
%The former rule models the adoption of a lower level policy $Y$  by a
%higher level policy $X$, while the latter models the termination of a
%policy $X$. The PSDG model considered in~\cite{Pyn99,PyW000} 
%allows for more general rules
%of the form $X \rightarrow Y_1\ldots Y_m X$, i.e. the recursion symbol must
%be located at the end of the expansion. 
%Interestingly, the PSDG is directly related to
%the HAM language described above, similar to the way production-rule
%grammar is related to finite automata. Given a PSDG, we can convert it to an
%equivalent HAM by constructing a machine for each non-terminating symbol,
%and
%modelling the production rules for each non-terminating symbol by the
%machine automata. Thus, the previous discussion for converting a HAM
%to an equivalent
%policy hierarchy and performing inference for a HAM structure
%also applies to PSDG.



Similar to our AHMM and the PSDG, the recent work by~\citeA{GGM99} 
also makes use of a detailed model of the
plan execution process. Using the rich language of probabilistic Horn
abduction, they are able to model more sophisticated plan structures
such as interleaved/concurrent plans, partially-ordered plans. 
However the
work serves mainly as a representational framework, and provides
no analysis on the complexity of plan recognition in this setting.

Other work in probabilistic
plan recognition up to date has employed much coarser models for 
plan execution. Most have ignored the important 
influence of the state of the world to the agent's planning
decision~\cite{GGM99}.
To the best of our knowledge, none of the work up to date
has addressed the problem of partial and noisy observation of the
state. Most, except the PSDG, do not look at the observation of the
outcomes of actions, and assume that the action can be observed
directly and accurately. We note that this kind of simplifying assumptions
is needed in previous work so that the computational complexity of
performing probabilistic plan recognition remains manageable. In contrary,
our work here illustrates that although the plan recognition 
dynamic stochastic model can be complex, 
they exhibit special types of conditional independence which, if exploited,
can lead to efficient plan recognition algorithms.




%relevance of hidden state and POMDP \cite{KLC98}
% Our previous work~\cite{BuiVW99}


\section{Conclusion and Future Work}
\label{sec:conclude}

In summary, we have presented an approach for on-line plan recognition
under uncertainty using the AHMM as the model for the
execution of a stochastic plan hierarchy and its noisy observation.
The AHMM is a novel type of stochastic processes, capable of
representing a rich class of plans and the associating uncertainty in the
planning and plan observation process. 
We first analyse the AHMM structure and its conditional 
independence properties. This leads to the proposed
hybrid Rao-Blackwellised
Sequential Importance Sampling (RB-SIS) algorithm for performing 
belief state updating (filtering) for the
AHMM which exploits the structure of the AHMM for greater efficiency and
scalability. 
%In doing this we also make a contribution to the application of
%RB-SIS to dynamic Bayesian network inference in general by allowing the
%Rao-Blackwellising variables to be non-Markov.
We show that the complexity of RB-SIS when applied to the AHMM only depends 
linearly on the number of levels $K$ in the policy hierarchy, while 
the sampling error does not depend on $K$. 

In terms of plan recognition, these results show that while the stochastic
process for representing the execution of a plan hierarchy can be complex,
they exhibit certain conditional independence properties that are inherent
in the dynamics of the planning and acting process. These independence
properties, if exploited, can help to reduce the complexity of performing
inference
on the plan execution stochastic model, leading to feasible and scalable 
algorithms for on-line plan recognition in noisy and uncertain domains.
The scalability of the algorithm for policy recognition provides the
possibility to consider more complex plan hierarchies and more detailed
models of the plan execution process.
The key to achieve this efficiency, as we have shown in the paper, is a
combination of recently developed techniques in probabilistic inference:
compact representations for Bayesian networks
(context-sensitive independence, factored representations), and hybrid
DBN inference which can take advantage of these compact representations
(Rao-Blackwellisation).

Several future research directions are possible. 
To further investigate the AHMM, we would like to
consider the problem of learning the parameters of an AHMM from a database
of observation sequences, e.g., to learn the plan execution model by
observing multiple episodes of an agent executing the same plan.
The structure of the AHMM suggests that we can try to learn the model of each
abstract policy separately. Indeed, if we can observe the execution of
each abstract policy separately, the learning problem is
reduced to HMM parameter re-estimation for level-1 policies, and simple
frequency counting for higher-level policies. If the observation
sequence is a long episode with no clear cut temporal boundary between the
policies, the problem becomes a type of parameter estimation for DBN with 
hidden variables, and techniques for dealing with hidden variables such as 
EM~\cite{DLR77} can be applied.


Extensions can be made to the AHMM to make the model more expressive and
suitable for representing more complex agents' plans. For example, a more
expressive plan execution model such as the HAM model~\cite{Par98} can be
considered so that state-independent sequences of policies can be
represented. The current model can also be enriched to consider
a set of top-level policies which can be interleaved during their
execution. We expect that these new models would exhibit
context-specific independence properties similar to the AHMM, and 
Rao-Blackwellised sampling methods for policy recognition in these models
can be derived.


\section*{Acknowledgement}

We would like to thank the anonymous reviewers for their 
insightful comments which have helped improve both the presentation and
the contents of this paper. Many thanks to Nam Nguyen for his
implementation of the distributed tracking system used in this paper.



%In addition, the AHMM can be extended to incorporate a
%factored representation of the state-space~\cite{BDG001}. 
%Since each action will only affect a small number of state variables,
%this will provide a compact network structure for representing a
%multi-variate state space and the effects of actions 





%inter-leaving plans/policies?
%
%multi-agent plan?
%
%MCMC sampling of RB variables?



%the recognition of 
%abstract Markov policies from external observation, based on probabilistic 
%inference on the Dynamic Bayesian Network representation of 
%the abstract policy. The paper
%presents two contributions to this problem. First, the analysis of the
%fully-observable case shows that policy recognition can be carried out more 
%efficiently if the domains of the intermediate abstract policies form a
%partition of the state-space (i.e. non-overlapping), due to fact that 
%the belief state of the DBN can be represented more compactly in this case.
%As a result, for abstract policies constructed by region-based
%decomposition of the state-space, policy recognition can be performed with
%constant averaged complexity (i.e. not dependent on the number of levels
%of abstraction). In the second contribution, we derive an efficient
%hybrid inference scheme for the recognition of this class of
%abstract policies under partial-observability. Experimental results
%illustrate our hybrid inference scheme performs better than the
%existing sampling-based scheme of~\cite{KKR95}.


%To solve the more general problem, we need to consider 
%what happens when the policy domains overlap, or their border is ``fuzzy'' 
%(i.e. when stopping conditions are non-deterministic). Our analysis here
%points the difficulty of this case to the uncertainty in the
%starting times of the current policies. 
%In addition, we are currently applying
%the framework presented here to the problem of tracking and predicting
%human movement in large spatial environment, and as part of this,
%addressing the problem of learning the parameters of the model from
%training data.

%~\cite{BuiVW000:b}

%\section*{Acknowledgement}
%The research described here was supported by an ARC grant from the
%Australian Research Council. The authors would like to thank 
%a number of anonymous reviewers for their helpful comments.

%\section*{Appendix}
%\appendix
%\section{Proof of Theorem~\ref{thrm-ind}}
%\label{append:proof}
%\input{proof.tex}


%\newpage

%In our previous work~\cite{BuiVW99}, we have
%used this algorithm to perform inference on a layered DPN. 
%In this paper, we improve on this inference method by combining it with the
%exact inference in chains to form an efficient hybrid-inference scheme for
%the AHMM with much better accuracy in the estimated probabilities.


%There has been a large number of applications of Dynamic Probabilistic
%Networks and Bayesian networks for dealing with noisy data in spatio-temporal 
%domains which we do not attempt to describe in detail here. 
%The DPN has been used in monitoring and 
%surveillance of traffic scenes~\cite{BuG95,HKM94}. The
%HMM is used to reconstruct
%and classify vehicle trajectories from noisy observations~\cite{FrM98}. 
%The CHMM is used to track human movement on the ground and some limited 
%group behaviours such as following, meeting, etc~\cite{ORP99}. Similar 
%techniques can
%also be used for recognising and classifying human gestures~\cite{BOP97}.
%In all these applications, the domains are usually locally restricted, e.g.
%tracking and surveillance is carried out independently within a single
%room or a single ground space region. Thus, the need for dealing with
%different levels of detail does not arise. The proposed AHMM architecture
%is capable of representing dynamic data such as human or vehicle
%trajectories at different levels of detail, and thus facilitates
%monitoring and surveillance at a larger scale over a wide spatial 
%environment and with multiple sensors.


%\newpage

\bibliography{bui}
%\bibliography{/home/jb/Work/Doc/Bib/Bibfile/bui}
%\bibliography{bui}
\end{document}
