Gal A. Kaminka: Publications

Sorted by DateClassified by Publication TypeClassified by TopicGrouped by Student (current)Grouped by Former Students

Towards Robust Teams with Many Agents

Gal A. Kaminka and Michael Bowling. Towards Robust Teams with Many Agents. Technical Report CMU-CS-01-159, Carnegie Mellon University, 2001.

Download

[PDF]233.3kB  [gzipped postscript]84.4kB  

Abstract

Agents in deployed multi-agent systems monitor other agents to coordinate and collaborate 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 importance 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 hypotheses. 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.

Additional Information

BibTeX

@techreport{scaleup-techreport, 
  author = 	 {Gal A. Kaminka and Michael  Bowling}, 
  title = 	 {Towards Robust Teams with Many Agents}, 
  institution =  {Carnegie Mellon University}, 
  year = 	 {2001}, 
  key = 	 {Kaminka and Bowling}, 
  number = 	 {CMU-CS-01-159}, 
  abstract = {Agents in deployed multi-agent systems monitor other agents to 
coordinate and collaborate 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 importance 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 
hypotheses. 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.}, 
  wwwnote = {}, 
} 

Generated by bib2html.pl (written by Patrick Riley ) on Mon Nov 16, 2020 22:25:46