  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, exchanged 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 efficient 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 different 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 difficulty of the task.
