represent the plan state of a team of agents within the unconstrained state space of an HMM. However, the HMM state space would have to represent all possible combinations of the individual plan states of the agents, so the size of the HMM state space would be exponential in the number of agents and plans. Thus, the standard algorithms for HMM
inference would not be able to exploit the structure of the plan and team hierarchies, nor the particular forms of evidence (as described in Section 3.2), in the way that we do in YOYO*.

Generalized versions of the HMM model ( Ghahramani & Jordan, 1997; Jordan, Ghahramani,
& Saul, 1997) could more compactly represent the same state space as in YOYO*, but exact inference is intractable for these models. These models have more efficient algorithms for approximate inference, but these would have difficulty with the determinism present in our planning models.

Pynadath and Wellman report on the Probabilistic State-Dependent Grammar (PSDG)
model (2000) that avoids the full complexity of DBN inference by making simplifying assumptions appropriate for plan recognition. However, while PSDG can incorporate broader classes of inference than YOYO*, it is intended for single-agent plan recognition, and does not support concurrency in a general enough fashion for multi-agent plan recognition.

Goldman, Geib and Miller (1999) develop a conceptual model for Bayesian plan recognition which does include, as one of its key novelties, the ability to infer the plans of a single agent from lack of observation of its action. However, Goldman et al. deal with a different issue altogether than the one our communications predictions address. Their framework looks at a sequence of observations, in which an observation may be missing, but observations of actions following it appear. Their framework then allows inference that plans that should have given rise to the missing observation can be ruled out as recognition hypothes. In contrast, our approach uses the communications predictions to make inference of plan-steps that did not yet occur. OVERSEER probabilistically expects the predictions to come true, and does not infer additional information from a missing (predicted) observation that is followed by another. In addition, our approach is fully implemented and deployed in multi-agent settings, rather than single agent.

A complementary line of work (in the context of the TEAMCORE architecture) has focused on intended plan-recognition for monitoring, where team-members may adapt their communications such that monitoring is made easier (Tambe et  al., 2000).  This work
(i) reduced, but did not eliminate uncertainty, and (ii) did not present any methods to address uncertainty, as we do here, However, it presents an interesting future direction for OVERSEER's development

## 8. Summary And Future Work

This paper introduced monitoring by overhearing, a technique that will be increasingly important with the growing need to monitor agent systems, particularly distributed or deployed. We presented OVERSEER, a system for monitoring teams by overhearing the routine communications team-members exchange as part of the execution of their joint tasks. Monitoring by overhearing, while being a plan-recognition task, presents characteristic challenges not previously addressed. These include the scarcity of observations compared to the rate of change in agent's state, and the fact that agents are not individually observable, as the observations are essentially of multi-agent actions. In addition to these, familiar challenges