Recent years are seeing an increasing need for on-line monitoring of teams of cooperating
agents, e.g., for visualization, or performance tracking. However, in monitoring deployed teams, we often cannot rely on the agents to always communicate their state to the monitoring system.
This paper presents a non-intrusive approach to monitoring by overhearing, where the monitored
team's state is inferred (via plan-recognition) from team-members' routine communications, ex- changed as part of their coordinated task execution, and observed (overheard) by the monitoring
system. Key challenges in this approach include the demanding run-time requirements of monitoring, the scarceness of observations (increasing monitoring uncertainty), and the need to scale-up
monitoring to address potentially large teams. To address these, we present a set of complementary novel techniques, exploiting knowledge of the social structures and procedures in the monitored
team: (i) an ecient probabilistic plan-recognition algorithm, well-suited for processing communications as observations; (ii) an approach to exploiting knowledge of the team's social behavior to
predict future observations during execution (reducing monitoring uncertainty); and (iii) monitoring algorithms that trade expressivity for scalability, representing only certain useful monitoring
hypotheses, but allowing for any number of agents and their dierent activities to be represented
in a single coherent entity. We present an empirical evaluation of these techniques, in combination
and apart, in monitoring a deployed team of agents, running on machines physically distributed
across the country, and engaged in complex, dynamic task execution. We also compare the performance of these techniques to human expert and novice monitors, and show that the techniques
presented are capable of monitoring at human-expert levels, despite the diculty of the task.