A Discrete Model of Collective Marching on Rings

Michael Amir, Noa Agmon, Alfred M. Bruckstein

Abstract

We study the collective motion of autonomous mobile agents on a ringlike environment. The agents' dynamics is inspired by known laboratory experiments on the dynamics of locust swarms. In these experiments, locusts placed at arbitrary locations and initial orientations on a ring-shaped arena are observed to eventually all march in the same direction. In this work we ask whether, and how fast, a similar phenomenon occurs in a stochastic swarm of simple agents whose goal is to maintain the same direction of motion for as long as possible. The agents are randomly initiated as marching either clockwise or counterclockwise on a wide ring-shaped region, which we model as $k$ "narrow" concentric tracks on a cylinder. Collisions cause agents to change their direction of motion. To avoid this, agents may decide to switch tracks so as to merge with platoons of agents marching in their direction. We prove that such agents must eventually converge to a local consensus about their direction of motion, meaning that all agents on each narrow track must eventually march in the same direction. We give asymptotic bounds for the expected amount of time it takes for such convergence or "stabilization" to occur, which depends on the number of agents, the length of the tracks, and the number of tracks. We show that when agents also have a small probability of "erratic", random track-jumping behaviour, a global consensus on the direction of motion across all tracks will eventually be reached. Finally, we verify our theoretical findings in numerical simulations.

Introduction

Collective motion is one of nature’s most mesmerizing phenomena, seen in bird flocks, fish schools, and locust swarms. Biologists have long observed that when locusts are placed in a ring-shaped arena, they eventually all begin marching in the same direction, either clockwise or counter-clockwise. While various continuous models exist, there is a gap in formal, algorithmic analysis of these systems at a "mesoscopic" level—where agents are simple and discrete. This research seeks to identify the minimal, myopic rules that lead to this behavior and determine the time required to reach consensus.

Laboratory experiments show that locusts in a ring-shaped arena eventually align their marching direction.

The Discrete Model

The environment is modeled as a discretized cylinder consisting of $k$ concentric "narrow" tracks, each of length $n$, populated by $m$ identical agents. The dynamics are governed by four primary rules:

  1. Horizontal Movement: At each time step, agents attempt to move in their current heading. If the path is blocked by another agent, they remain stationary.
  2. Conflicts: If two agents with opposing headings are adjacent, they "conflict." One is chosen at random to flip its heading to match the other.
  3. Track Switching (Inertia): Agents can move vertically between tracks to avoid an imminent collision, provided the new neighbors in the adjacent track share their heading. This represents a "rational" desire to maintain momentum.
  4. Erratic Behavior: A small probability $p$ is introduced where an agent moves vertically even if the "rational" conditions aren't met.
The discrete model illustrates agents moving on concentric tracks, resolving conflicts, and switching lanes to maintain momentum.

Using Markov chain analysis and Lyapunov functions, the study tracks "disorder" (empty spaces between groups) to prove convergence and derive time bounds.

Key Insights and Results

Local vs. Global Consensus

On a multi-track ring, "local consensus" (where every agent on a single track moves the same way) is guaranteed. However, without noise, different tracks can march in opposite directions indefinitely because they never interact through collisions. Global consensus is only guaranteed when agents behave "erratically" with some small probability $p$. This randomness forces interactions between tracks that would otherwise remain isolated.

The Efficiency of Lane-Changing

In sparse swarms (e.g., 10% density), the ability to switch tracks significantly speeds up the time to reach local consensus, allowing agents to bypass obstacles and join like-minded platoons. In numerical simulations of a $30 \times 30$ setup, track switching nearly halved the stabilization time. However, in dense configurations (e.g., 50% density), track switching had almost no effect because tracks were too crowded to allow vertical movement.

Stabilization Time Bounds

  • Single Track ($k=1$): The expected time to stabilization is $E[T_{stable}] \leq m^2 + 2(n-m)$. This bound is asymptotically tight, growing quadratically with the number of agents and linearly with track length.
  • Multi-Track ($k>1$): The local stabilization bound is proven to be $O(\min(\log(k)n^2, mn + m^2))$.

Conclusion

The study demonstrates that while "rational" collision avoidance speeds up local order, a touch of "erratic" behavior is required to reach a true global consensus. Paradoxically, purely rational behavior can hinder global order by preventing the very conflicts needed to flip "wrong" headings. Future work will focus on refining upper bounds for global consensus time and exploring these rules in more complex topologies, such as square arenas or irregular graphs.

Summary updated

Abstract

We study the collective motion of autonomous mobile agents on a ringlike environment. The agents' dynamics is inspired by known laboratory experiments on the dynamics of locust swarms. In these experiments, locusts placed at arbitrary locations and initial orientations on a ring-shaped arena are observed to eventually all march in the same direction. In this work we ask whether, and how fast, a similar phenomenon occurs in a stochastic swarm of simple agents whose goal is to maintain the same direction of motion for as long as possible. The agents are randomly initiated as marching either clockwise or counterclockwise on a wide ring-shaped region, which we model as $k$ "narrow" concentric tracks on a cylinder. Collisions cause agents to change their direction of motion. To avoid this, agents may decide to switch tracks so as to merge with platoons of agents marching in their direction. We prove that such agents must eventually converge to a local consensus about their direction of motion, meaning that all agents on each narrow track must eventually march in the same direction. We give asymptotic bounds for the expected amount of time it takes for such convergence or "stabilization" to occur, which depends on the number of agents, the length of the tracks, and the number of tracks. We show that when agents also have a small probability of "erratic", random track-jumping behaviour, a global consensus on the direction of motion across all tracks will eventually be reached. Finally, we verify our theoretical findings in numerical simulations.
BibTeX
@inproceedings{amir2021discrete,
  author = {Michael Amir and Noa Agmon and Alfred M. Bruckstein},
  title = {{A Discrete Model of Collective Marching on Rings}},
  booktitle = {DARS},
  year = {2021},
  url = {https://openreview.net/forum?id=0dmpAwy5Oh},
}
Figure