Learning to Gather without Communication

El Mahdi El Mhamdi, Rachid Guerraoui, Alexandre Maurer, Vladislav TempezarXiv 2018 · OpenReview

Abstract

A standard belief on emerging collective behavior is that it emerges from simple individual rules. Most of the mathematical research on such collective behavior starts from imperative individual rules, like always go to the center. But how could an (optimal) individual rule emerge during a short period within the group lifetime, especially if communication is not available. We argue that such rules can actually emerge in a group in a short span of time via collective (multi-agent) reinforcement learning, i.e learning via rewards and punishments. We consider the gathering problem: several agents (social animals, swarming robots...) must gather around a same position, which is not determined in advance. They must do so without communication on their planned decision, just by looking at the position of other agents. We present the first experimental evidence that a gathering behavior can be learned without communication in a partially observable environment. The learned behavior has the same properties as a self-stabilizing distributed algorithm, as processes can gather from any initial state (and thus tolerate any transient failure). Besides, we show that it is possible to tolerate the brutal loss of up to 90% of agents without significant impact on the behavior.

Introduction

In nature, complex collective behaviors such as fish schooling or bird flocking emerge from simple, local interactions. In computer science, the "gathering problem"—where multiple agents must agree on a meeting point without central coordination—is a fundamental challenge. While traditional approaches rely on hard-coded algorithms, this research explores whether such behavior can emerge through decentralized reinforcement learning (RL) without any direct communication between agents.

Methodology: Sector-Based Perception

The primary challenge in multi-agent reinforcement learning (MARL) is the "combinatorial explosion" of the state space as the number of agents increases. To address this, the authors propose a sector-based state representation. Agents operate on a 1D ring topology, which eliminates border effects and simplifies the problem to a relative coordinate system.

Sector-based state representation on a 1D ring topology.

Instead of tracking the exact coordinates of every other agent, each agent perceives the world through six relative sectors: Central, Near Left/Right, Far Left/Right, and Opposite. The state is defined by the fraction of the total population present in each sector, quantized with 10% precision. This abstraction ensures that the state space remains constant regardless of the total number of agents, facilitating scalability.

Key Results: Emergent Gathering

The agents were trained using Q-learning with eligibility traces. Initially, agents moved randomly, taking approximately 60 cycles to form a group. As training progressed, the time required to gather decreased significantly.

Reduction in time to create the first group over training cycles.

After roughly 5,000 training cycles, the gathering time stabilized at approximately 10 steps. Remarkably, the learned behavior outperformed a deterministic "move to barycenter" algorithm when both were restricted to the same limited perception.

Scalability and Robustness

A significant finding of this work is the inherent scalability of the learned policy. Agents trained in groups of 10 were able to successfully gather in groups of up to 100 agents with a 99.7% success rate. This is possible because the state representation relies on population fractions rather than absolute counts.

Furthermore, the system demonstrates extreme robustness. It can tolerate the sudden loss of up to 90% of the agents. Since the remaining agents continue to follow the same local rules based on the relative density of their neighbors, they simply regroup at a new center of mass without requiring additional training.

Conclusion

This study provides the first experimental evidence that gathering behavior can be learned without communication in a partially observable environment. The resulting behavior is self-stabilizing, scalable, and robust, mirroring the resilient collective behaviors observed in biological systems. Future work may explore higher-dimensional environments and the emergence of heterogeneous roles within the group.

Summary updated

Abstract

A standard belief on emerging collective behavior is that it emerges from simple individual rules. Most of the mathematical research on such collective behavior starts from imperative individual rules, like always go to the center. But how could an (optimal) individual rule emerge during a short period within the group lifetime, especially if communication is not available. We argue that such rules can actually emerge in a group in a short span of time via collective (multi-agent) reinforcement learning, i.e learning via rewards and punishments. We consider the gathering problem: several agents (social animals, swarming robots...) must gather around a same position, which is not determined in advance. They must do so without communication on their planned decision, just by looking at the position of other agents. We present the first experimental evidence that a gathering behavior can be learned without communication in a partially observable environment. The learned behavior has the same properties as a self-stabilizing distributed algorithm, as processes can gather from any initial state (and thus tolerate any transient failure). Besides, we show that it is possible to tolerate the brutal loss of up to 90\% of agents without significant impact on the behavior.
BibTeX
@misc{mhamdi2018learning,
  author = {El Mahdi El Mhamdi and Rachid Guerraoui and Alexandre Maurer and Vladislav Tempez},
  title = {{Learning to Gather without Communication}},
  year = {2018},
  eprint = {1802.07834},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1802.07834},
}
Figure