Monitoring deployed agent teams

Recent years are seeing an increasing need for on-line monitoring of deployed distributed teams of cooperating agents, e.g., for visualization, or performance tracking. However, in deployed systems, we often cannot rely on the agents to communicate their state to the monitoring system: (a) we rarely can change the behavior of already-deployed agents to communicate the required information (e.g., in legacy or proprietary systems); (b) different monitoring goals require different information to be communicated (e.g., agents' beliefs vs. plans); and (c) communications may be expensive, unreliable, or insecure. This paper presents a non-intrusive approach based on plan-recognition, in which the monitored agents' state is inferred from observations of their routine actions. In particular, we focus on inference of the team state based on its observed \emph{routine} communications, exchanged as part of coordinated task execution. The paper includes the following key novel contributions: (i) a \emph{linear time} probabilistic plan-recognition algorithm, well-suited for processing communications as observations; (ii) an approach to exploiting general knowledge of teamwork to predict agent responses during normal execution, to reduce monitoring uncertainty; and (iii) a monitoring algorithm that trades 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. Our empirical evaluation illustrates that monitoring based on observed routine communications enables significant monitoring accuracy, while not being intrusive. The results also demonstrate a key lesson: A combination of complementary low-quality techniques is cheaper, and better, than a single, highly-optimized monitoring approach.