Error cascades in collective behavior a case study of the gradient algorithm on 1000 physical agents

Melvin Gauci, Michael Rubenstein, Monica E. Ortiz, Radhika Nagpal

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Scopus citations

Abstract

The gradient, or hop count, algorithm is inspired by natural phenomena such as the morphogen gradients present in multi-cellular development. It has several applications in multi-agent systems and sensor networks, serving as a basis for self-organized coordinate system formation, and finding shortest paths for message passing. It is a simple and well-understood algorithm in theory. However, we show here that in practice, it is highly sensitive to specific rare errors that emerge at larger scales. We implement it ou a system of 1000 physical agents (Kilobot robots) that communicate asynchronously via a noisy wireless channel. We observe that spontaneous, short-lasting rare errors made by a single agent (e.g. Due to message corruption) propagate spatially and temporally, causing cascades that severely hinder the algorithm's functionality. We develop a mathematical model for temporal error propagation and validate it with experiments on 100 agents. This work shows how multi-agent algorithms that are believed to be simple and robust from theoretical insight may be highly challenging to implement on physical systems. Systematically understanding and quantifying their current limitations is a first step in the direction of improving their robustness for implementation.

Original languageEnglish (US)
Title of host publication16th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2017
EditorsEdmund Durfee, Michael Winikoff, Kate Larson, Sanmay Das
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages1404-1412
Number of pages9
ISBN (Electronic)9781510855076
StatePublished - 2017
Externally publishedYes
Event16th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2017 - Sao Paulo, Brazil
Duration: May 8 2017May 12 2017

Publication series

NameProceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
Volume3
ISSN (Print)1548-8403
ISSN (Electronic)1558-2914

Conference

Conference16th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2017
Country/TerritoryBrazil
CitySao Paulo
Period5/8/175/12/17

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering

Keywords

  • Complex systems
  • Kilobots
  • Multi-agent systems in hardware
  • Reality gap
  • Spatio-temporal error propagation

Fingerprint

Dive into the research topics of 'Error cascades in collective behavior a case study of the gradient algorithm on 1000 physical agents'. Together they form a unique fingerprint.

Cite this