Probabilistic grammars for plan recognition.

Abstract

A decision maker operating in the presence of a planning agent must often try to determine the plan of action driving the agent's behavior. Modeling the uncertainty inherent in planning domains provides a difficult challenge. If the domain representation includes an explicit probabilistic model, then the inference mechanism can compute a probability distribution over possible hypotheses, providing a sound, decision-theoretic basis for selecting optimal actions. The recognizer bases its conclusions on its uncertain a priori knowledge about the agent's mental state, its decision process, the world state, and the world's dynamics, which can be summarized by a probability distribution. It then uses its partial observations about the world to infer properties of the agent and its plan. This work first applies existing research in probabilistic context-free grammars (PCFGs) to specify this causal model and answer certain queries. This dissertation then presents new inference algorithms that generate a Bayesian network representation of the PCFG distribution. The new inference algorithms extend the set of possible queries to include posterior probability distributions over nonterminal symbols and flexible evidence handling that permits missing terminals and observations of nonterminals. However, the PCFG independence assumptions restrict the domains for which the methods are applicable. The second phase of this work defines a new model, the probabilistic state-dependent grammar (PSDG). A PSDG adds an explicit model of the external world and the agent's mental state to a PCFG model of plan selection. Production probabilities are conditioned on the values of these state variables, allowing domain specification to capture the effect of planning context on the selection process. The model also represents the world dynamics through state transition probabilities. A PSDG's explicit partition between plan and state variables facilitates both domain specification and inference, as illustrated by specifications of two example domains. The first is a driver model, constructed from scratch, that captures the planning process of a driver maneuvering on a highway. A second illustration, in the domain of air combat, demonstrates the translation of a pre-existing specification in another language into a roughly equivalent PSDG model. The PSDG model also provides practical inference algorithms. As in the PCFG case, algorithms can generate a Bayesian network representation of the underlying probability distribution. However, this work also presents specialized algorithms that exploit the particular independence properties of the PSDG language to maintain a more efficient summary of evidence in the form of a belief state. The final combination of the PSDG language model and algorithms extends the range of plan recognition domains for which practical probabilistic inference is possible.