Gal A. Kaminka: Publications

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

Detecting Disagreements in Large-Scale Multi-Agent Teams

Gal A. Kaminka. Detecting Disagreements in Large-Scale Multi-Agent Teams. Journal of Autonomous Agents and Multi-Agent Systems, 18(3):501–525, 2009.

Download

[PDF]338.8kB  [gzipped postscript] [postscript] [HTML] 

Abstract

Intermittent sensory, actuation and communication failures may cause agents to fail in maintaining their commitments to others. Thus to collaborate robustly, agents must monitor others to detect coordination failures. Previous work on monitoring has focused mainly on small-scale systems, with only a limited number of agents. However, as the number of monitored agents is scaled up, two issues are raised that challenge previous work. First, agents become physically and logically disconnected from their peers, and thus their ability to monitor each other is reduced. Second, the number of possible coordination failures grows exponentially, with all potential interactions. Thus previous techniques that sift through all possible failure hypotheses cannot be used in large-scale teams. This paper tackles these challenges in the context of detecting disagreements among team-members, a monitoring task that is of particular importance to robust teamwork. First, we present new bounds on the number of agents that must be monitored in a team to guarantee disagreement detection. These bounds significantly reduce the connectivity requirements of the monitoring task in the distributed case. Second, we present YOYO, a highly scalable disagreement-detection algorithm which guarantees sound detection. YOYO's run-time scales linearly in the number of monitored agents, despite the exponential number of hypotheses. It compactly represents all valid hypotheses in single structure, while allowing for a complex hierarchical organizational structure to be considered in the monitoring. Both YOYO and the new bounds are explored analytically and empirically in monitoring problems involving thousands of agents.

Additional Information

The article's official web page is at: http://dx.doi.org/10.1007/s10458-008-9068-3.

BibTeX

@Article{jaamas09, 
  author = {Gal A. Kaminka}, 
  title  = {Detecting Disagreements in Large-Scale Multi-Agent Teams}, 
  journal = JAAMAS, 
  year = {2009}, 
  volume = {18},
  number = {3},
  pages = {501--525},
  note = {}, 
  abstract = {Intermittent sensory, actuation and communication failures may cause agents to fail in  maintaining their commitments to others. Thus to collaborate robustly, agents must monitor others to detect coordination failures.  Previous work on monitoring has focused mainly on  small-scale systems, with only a limited number of agents.  However, as the number of monitored agents 
is scaled up, two issues are raised that challenge previous work. First, agents become physically and  logically disconnected from 
their peers, and thus their ability to monitor each other is reduced.  Second, the number of possible  coordination failures grows exponentially, with all potential interactions. Thus previous techniques  that sift through all possible failure hypotheses cannot be used in large-scale teams. 
   This paper tackles these challenges in the context of detecting disagreements among team-members,  
 a monitoring task that is of particular importance to robust teamwork. First, we present new bounds  on 
the number of agents that must be monitored in a team to guarantee disagreement 
detection. These bounds significantly reduce the connectivity requirements of the monitoring task in  the distributed case. Second, we present YOYO, a highly scalable 
disagreement-detection algorithm which guarantees sound detection. YOYO's run-time scales 
linearly in the number of monitored agents, despite the exponential number 
of hypotheses. It compactly represents all valid hypotheses in single structure, while 
allowing for a complex hierarchical organizational structure to be considered in the monitoring. 
Both YOYO and the new bounds are explored analytically 
and empirically in monitoring problems involving thousands of agents.}, 
  wwwnote = {}, 
  doi = {10.1007/s10458-008-9068-3},
} 

Generated by bib2html.pl (written by Patrick Riley ) on Thu Feb 22, 2024 11:36:58