|
CMU-CS-01-159
Computer Science Department
School of Computer Science, Carnegie Mellon University
CMU-CS-01-159
Towards Robust Teams with Many Agents
Gal A. Kaminka, Michael Bowling
November 2001
CMU-CS-01-159.ps
CMU-CS-01-159.pdf
Keywords: Artificial intelligence, distributed artificial
intelligence, coherence and coordination
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
|