Abstract
We consider the problem of organizing a scattered group of $n$ robots in two-dimensional space, with geometric maximum distance $D$ between robots. The communication graph of the swarm is connected, but there is no central authority for organizing it. We want to arrange them into a sorted and equally-spaced array between the robots with lowest and highest label, while maintaining a connected communication network. In this paper, we describe a distributed method to accomplish these goals, without using central control, while also keeping time, travel distance and communication cost at a minimum. We proceed in a number of stages (leader election, initial path construction, subtree contraction, geometric straightening, and distributed sorting), none of which requires a central authority, but still accomplishes best possible parallelization. The overall arraying is performed in $O(n)$ time, $O(n^2)$ individual messages, and $O(nD)$ travel distance. Implementation of the sorting and navigation use communication messages of fixed size, and are a practical solution for large populations of low-cost robots.
Introduction
Deploying a large swarm of autonomous robots often results in a scattered configuration where robots possess unique IDs but can only communicate with local neighbors. Coordinating such a swarm to form a perfectly spaced, sorted line—essential for tasks like traversing narrow corridors or sequential processing—presents a significant challenge in distributed computing and geometry. Centralized sorting typically requires $\Omega(n \log n)$ time, and physical coordination adds complexities like collision avoidance and network connectivity maintenance. This paper proposes a fully distributed algorithm that achieves optimal linear completion time $O(n)$ by decoupling geometric path-formation from logical sorting.
Methodology
The proposed approach organizes the swarm through five distinct, decentralized phases:
- Leader Election: Using an "echo wave" protocol, the swarm identifies robots with the minimum ($r_{min}$) and maximum ($r_{max}$) IDs to serve as stationary endpoints.
- Central Path Formation: A shortest path is established between $r_{min}$ and $r_{max}$. By using squared Euclidean distance as edge weights, the algorithm mathematically guarantees a non-self-intersecting path.
- Straightening: Robots on the central path utilize a "Go-To-The-Middle" (GTM) technique, moving toward the midpoint of their neighbors to straighten the line and ensure even spacing.
- Contracting Subtrees: Robots not on the initial path form routing trees and systematically move toward the path to integrate into the backbone. This occurs in parallel with the straightening phase.
- Wave Sort: Once a physical line is formed, an asynchronous distributed odd-even sort is executed. $r_{min}$ initiates "waves" of messages; as these pass through the line, adjacent robots compare IDs and swap positions if necessary.
Key Insights
- Geometric Integrity via Squared Distances: A critical innovation is the use of squared Euclidean distances for routing. This prevents path intersections, which are a common cause of physical deadlocks in swarm robotics.
- Physical Data Structures: The algorithm treats the physical swarm as a dynamic data structure. By first organizing the robots into a physical doubly linked list, the complex 2D navigation problem is simplified into a 1D array sorting problem.
- Parallel Sorting Efficiency: While standard comparison sorting is bounded at $\Omega(n \log n)$, the "Wave Sort" mechanism allows multiple sorting waves to propagate simultaneously. This massive parallelism enables the swarm to sort itself in $O(n)$ time.
Results and Performance
The algorithm was validated through physics-based simulations of swarms ranging from 15 to 130 robots. The results confirm that the process is mathematically optimal, completing in $\Theta(n)$ time with a total travel distance of $\Theta(nD)$. Communication overhead remains manageable at $O(n^2)$ messages, making it suitable for low-bandwidth, low-cost hardware. Simulations demonstrated that the algorithm effectively handles continuous motion and collision avoidance while scaling linearly.
Limitations and Future Work
The current strategy assumes sufficient environmental space for robots to execute physical swaps during the Wave Sort phase. In extremely dense settings, robots may lack the room to maneuver. Future research will explore dynamic environments where the endpoint robots ($r_{min}$ and $r_{max}$) actively move apart to create the necessary physical space for the rest of the swarm.
Summary updated