A Message Passing Algorithm for Plan Recognition

Abstract

We present a general framework for plan recognition whose formulation is motivated by a general purpose algorithm for effective abduction. The knowledge representation is a restricted form of first order logic, which is made computationally explicit as a graph structure in which plans are manifest as a special kind of graph walk. Intuitively, plans are fabricated by searching an action description graph for relevant connections amongst instances of observed actions. The class of plans for which our method is applicable is wider than those previously proposed, as both recursive and optional plan components can be represented. Despite the increased generality, the proposed message-passing algorithm has an asymptotic upper bound that is an improvement on previous related work.