Traffic control for a swarm of robots: Avoiding target congestion

Leandro Soriano Marcolino, Luiz ChaimowiczIROS 2009 · OpenReview

Abstract

In swarm robotics, congestion at target locations significantly hampers performance, often leading to cluttered, slow-moving masses. This paper proposes a decentralized coordination algorithm based on a Probabilistic Finite State Machine (PFSM) and local communication to manage traffic flow. By dividing the target area into concentric "Free" and "Danger" regions, robots autonomously regulate their movement. Experimental results demonstrate that this approach improves navigation efficiency by up to 22% in physical robot swarms, providing a scalable solution for unstructured environments.

Introduction

Congestion is a primary bottleneck in swarm robotics. When a large number of robots attempt to reach a single waypoint or narrow passage simultaneously, standard collision avoidance algorithms often result in "traffic jams." While these algorithms prevent physical impacts, they do not maintain efficient swarm movement, leading to a loss of throughput.

Existing solutions typically rely on centralized controllers or predefined lanes, which introduce single points of failure or lack flexibility in unstructured environments. This research addresses the need for a robust, distributed method to meter traffic into a target zone using only local sensing and peer-to-peer communication.

Methodology

The proposed coordination strategy utilizes a Probabilistic Finite State Machine (PFSM) to govern robot behavior. The environment around a target is categorized into two concentric zones: a central Free Region where robots move directly to the goal, and a surrounding Danger Region where coordination logic is applied.

The Probabilistic Finite State Machine (PFSM) governing robot transitions between Normal, Waiting, Impatient, and Locked states.

Robots operate in four distinct states:

  • Normal: The robot moves directly toward the target.
  • Waiting: Within the Danger Region, if a robot detects another robot ahead in its path (defined by a cone-shaped sensing area), it stops.
  • Impatient: To prevent permanent deadlocks, a Waiting robot has a probability $\rho$ at each time step to become Impatient, resuming its journey and ignoring further wait requests.
  • Locked: Robots outside the Danger Region stop if they detect a Waiting or Locked robot ahead, preventing further backlog.
Sequential visualization of robot coordination within the Danger and Free regions.

The use of a restricted sensing cone ensures that the dependency graph between robots remains a Directed Acyclic Graph (DAG), geometrically precluding circular waiting loops and deadlocks.

Experimental Evaluation

The algorithm was evaluated through both high-fidelity simulations and physical experiments.

  • Simulations: Using the Player/Stage framework, swarms of 30 to 75 robots were tested. In scenarios with more than 42 robots, the coordinated swarm consistently outperformed uncoordinated ones, showing a performance improvement of approximately 20%.
  • Physical Experiments: Tests were conducted with 12 e-puck robots. The coordinated swarm reached the target 22% faster than a baseline swarm using only local repulsion forces (7 minutes versus 9 minutes).

Qualitative observations showed that coordinated robots formed organized queues in the Danger Region, allowing robots closest to the target to complete their tasks without interference from incoming traffic.

Conclusion

The decentralized PFSM approach effectively mitigates target congestion in robot swarms. While the system shows significant efficiency gains, challenges remain regarding the "exit" problem, where robots leaving the target area encounter the incoming queue. Future research will focus on optimizing exit strategies and investigating the sensitivity of the system to the probability parameter $\rho$ and region dimensions.

Reference: Marcolino, L. S., & Chaimowicz, L. (2009). Traffic control for a swarm of robots: Avoiding target congestion.

Summary updated

BibTeX
@inproceedings{marcolino2009traffic,
  author = {Leandro Soriano Marcolino and Luiz Chaimowicz},
  title = {{Traffic control for a swarm of robots: Avoiding target congestion}},
  booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
  year = {2009},
  url = {https://openreview.net/forum?id=NdueZSEwp-sL},
}
Figure