Policy Recognition in the Abstract Hidden Markov Model (More Info)

This paper seems to be quite an influential paper in the current AI milieu around UW and Intel. In this work, the authors present a method for recognizing policies in an Abstract Hidden Markov Model (AHMM) from a sequence of state observations. The AHMM is an interesting model to try and infer policies on because it is a way of reverse engineering the policy that an Abstract Markov Process (which is a hierarchical version of a Markov Decision Process (MDP)) is executing.

The technique is to compile the AHMM to a DBN and perform inference on the DBN. The authors show that inference on the compiled DBN, which would usually require time exponential in the number of levels in the policy hierarchy, can be achieved in time linear to the size of the policy hierarchy.

They are able to achieve this through a combination of independence assumptions and Rao-Blackwellization. Inference is performed with SIS.

The main contribution of this paper seems to be in showing how to link an MDP to a DBN. If it weren't for this connection, I don't think that the AHMM is really that interesting. The compiled DBN is reasonable to understand and interpret and the presence of the AHMM is unnecessary as a result. In fact in the work that Lin and Dieter did the AHMM was completely unused, although the inference on the DBN borrowed heavily from this paper.

I also wasn't entirely clear on how strong the result was. There was some discussion in the paper about a sub-class of policies in which it was deterministically known that the policy had completed and I didn't follow whether or not that assumption was successfully relaxed or not. Similarly there was an assumption of perfect observability - that the states were known with certainty - that definitely is a difficult restriction to bring into the ubiquitous computing world, but maybe not in the digital world.

Overall it was a very well written paper that provided thorough background and explanation and will likely be a oft-cited paper because of that.