Labrou, & Mayfield, 1997; Reed, 1998) increases standardization of aspects of agent communcations, and provides increasing opportunities for observing and interpreting inter-agent communications. We assume that monitored agents are truthful in their messages, since they are communicating to their teammates; and that they are not attempting to deceive the monitoring agent or prevent it from overhearing (as it is deployed by the human operator of the team).  Given a (possibly stochastic) model of the plans that the agents may be executing, a monitoring system using plan-recognition can infer the current state of the agents from such observed routine messages.

However, the application of plan-recognition techniques for overhearing poses significant challenges. First, a key characteristic of the overhearing task is the scarcity of observations.

Explanations for overheard messages (i.e., the observed actions) can sometimes be fairly easy to disambiguate, but uncertainty arises because there are relatively few of them to observe: team members cannot and do not in practice continuously communicate among themselves about their state (Jennings, 1995; Grosz & Kraus, 1996). Thus team-members change their state while keeping quiet. Another key characteristic of overhearing is that the observable actions are inherently multi-agent actions : When agents communicate, it is only a single agent that sends the messages. The others implicitly act their role in the communications by listening. Yet despite the scarcity of observable communications, and the multi-agent nature of the observed actions, a monitoring system must infer the state of all agents in the team, at all times. Previous investigations of multi-agent plan-recognition (Tambe, 1996; Devaney & Ram, 1998; Intille & Bobick, 1999; Kaminka & Tambe, 2000) have typically made the assumption that all changes to the state of agents have an observable effect: Uncertainty resulted from ambiguity in the explanations for the observed actions. Furthermore, these investigations have addressed settings where observable actions were individual (each action is carried out by a single agent ).

In addition to these challenges that are unique to overhearing, a monitoring system must address additional challenges stemming from the use of monitoring in service of visualization. The representation and algorithms must support soft real-time response; reasoning must be done quickly to be useful for visualization. Furthermore, real-world applications demand techniques that can scale up as the number of agents increases, for monitoring large teams. However, many current representations for plan-recognition are computationally intense (e.g., Kjærulff, 1992), or only address single-agent recognition tasks (e.g., Pynadath
& Wellman, 2000). Multi-agent plan-recognition investigations have typically not explicitly addressed scalability concerns (Devaney & Ram, 1998; Intille & Bobick, 1999).

This paper presents OVERSEER, an implemented monitoring system capable of monitoring large distributed applications composed of previously-deployed agents. OVERSEER
builds on previous work in multi-agent plan-recognition (Tambe, 1996; Intille & Bobick, 1999; Kaminka & Tambe, 2000) by utilizing knowledge of the relationships between agents to understand how their decisions interact. However, as previous teniques proved insufficient, OVERSEER includes a number of novel multi-agent plan-recognition techniques that address the scarcity of observations, as well as the severe response-time and scale-up requirements imposed by realistic applications. Key contributions include: (i) a linear time probabilistic plan-recognition representation and associated algorithms, which exploit the nature of observed communications for efficiency; (ii) a method for addressing unavailable observations by exploiting knowledge of the social procedures of teams to effectively predict