Agents in deployed multi-agent systems monitor other agents to coordinate and col-laborate robustly. However, as the number of agents monitored is scaled up, two key challenges arise: (i) the number of monitoring hypotheses to be considered can grow exponentially in the number of agents; and (ii) agents become physically and logically unconnected (unobservable) to their peers. This paper examines these challenges in teams of cooperating agents, focusing on a monitoring task that is of particular impor-tance to robust teamwork: detecting disagreements among team-members. We present YOYO, a highly scalable disagreement-detection algorithm which guarantees sound detection in time linear in the number of agents despite the exponential number of hy-potheses. In addition, we present new upper bounds about the number of agents that must be monitored in a team to guarantee disagreement detection. Both YOYO and the new bounds are explored analytically and empirically in thousands of monitoring problems, scaled to thousands of agents.

24 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by [email protected]