(PDF) Peter van Beek. An investigation of probabilistic interpretations of heuristics in plan recognition. Proceedings of the Fifth International Conference on User Modeling, Kailua-Kona, Hawaii, 113-120, January, 1996.
Plan recognition is the process of inferring a plausible set of plans that explain an agent's actions. In this paper, I use a small example to focus on some non-probabilistic heuristics proposed in the literature for preferring one plan over another. I show some of the conditions or constraints on the probability distributions so that the plan that is preferred by the heuristics is also the most probable plan and I look at some of the implications of these conditions. I also show that if the conditions do not hold there exist cases where the results of the heuristics clash with that of probabilities. One of the most interesting results of the analysis is that, given the assumption that the plan library is complete, the heuristics examined can be given a probabilistic interpretation or justification if and only if any two basic plans in the plan library which share a step are equally likely. The usefulness of the analysis is that we can test whether the conditions hold in a particular domain and so gain more insight into whether our choice of heuristic is appropriate to that domain. Further, this work can be seen as providing an alternative justification of the heuristics.