
## 7. Related Work In Probabilistic Plan Recognition

The case for using probabilistic inference for plan recognition has been argued convincingly by Charniak and Goldman (1993). However, the plan recognition Bayesian network used by Charniak and Goldman 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 (Pynadath & Wellman, 1995, 2000; Goldman et al., 1999; Huber et al., 1994; Albrecht et al., 1998) have used dynamic stochastic models for plan recognition and thus are more suitable for doing on-line plan recognition under uncertainty.

Among these, the most closely related model to the AHMM is the Probabilistic State-
Dependent Grammar (PSDG) (Pynadath, 1999; Pynadath & Wellman, 2000). A comparison of the representational aspect of the two models has been discussed under subsection 3.4. In terms of algorithms for plan recognition, Pynadath and Wellman 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. 9  Since an exact method is used by Pynadath and Wellman, 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). 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 hierary. Furthermore, as we have noted in subsection 3.4, if we consider compound policies, the PSDG can be converted to an AHMM. In our framework, a compound policy π k = π k − 1 . . . , π k − 1 can be represented just as a normal policy, with a slight modification to let the variable e 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.

Similar to our AHMM and the PSDG, the recent work by Goldman et al. (1999) 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 (Goldman et al., 1999).  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