On plan recognition and parsing

Probabilistic plan recognition systems based on weighted model counting all work roughly the same way: first they compute the exclusive and exhaustive set of models that ex-plain a given set of observations; next they assign a proba-bility to each model; finally they compute the likelihood of a particular goal by summing the probability of the explanatory models1 in which that goal occurs. In this paper we discuss an optimization for the model-building first step: rather than retain the full tree-like structure of goals which have been par-tially observed, we can keep only the frontier of as-yet unob-served actions and unachieved subgoals. The system Yappr which we present here uses techniques familiar from pars-ing algorithms. We give an informal introduction to Yappr in Section 1, a more formal presentation in Section 2, and an analysis of Yappr’s complexity in Section 3. In Section 4 we present experimental result showing the improvement real-ized from this technique, and then conclude with discussions of the algorithm’s limitations, and future work.