A parallel distributed strategy for arraying a scattered robot swarm

Dominik Krupke, Michael Hemmer, James McLurkin, Yu Zhou, Sándor P. Fekete

TL;DR

This paper presents a fully distributed algorithm to organize a scattered swarm of robots into a straight, evenly spaced, and ID-sorted line without any central control. By decoupling the geometric path-formation from the logical sorting process, the authors achieve an optimal linear completion time $O(n)$ and travel distance, making it highly efficient for large populations of simple, low-cost robots.

What Problem Does This Paper Address?

Imagine deploying a large swarm of autonomous robots across a field. They are scattered, possess unique IDs, and can only communicate with nearby neighbors. If you need them to line up in a perfectly spaced, sorted order (e.g., to pass through a narrow corridor or perform a sequential task), how do you coordinate this without a central "brain"?

This problem sits at the intersection of two-dimensional geometry, distributed computing, and sorting. Centralized sorting typically requires $\Omega(n \log n)$ time. Doing this in a distributed, asynchronous physical space is even harder because robots must physically move without colliding, maintain a connected communication network, and figure out their relative sorted positions using only local peer-to-peer messages.

Methods

The authors tackle the problem by breaking it down into five distinct phases. The first four phases essentially build a physical "doubly linked list" of robots in space, and the final phase sorts them:

  1. Leader Election: The swarm uses an "echo wave" communication protocol to identify the robots with the minimum ($r_{min}$) and maximum ($r_{max}$) IDs. These two robots become the stationary endpoints of the final line.
  2. Central Path Formation: The algorithm finds a shortest path through the communication graph between $r_{min}$ and $r_{max}$. Crucially, it uses the squared Euclidean distance as the edge weight, which mathematically guarantees the resulting path will not cross itself.
  3. Straightening: Robots on the central path continuously move toward the midpoint of their two path neighbors (a technique called "Go-To-The-Middle" or GTM). This naturally straightens the path and spaces the robots evenly.
  4. Contracting Subtrees: Robots not on the initial path form routing trees connected to the path. They systematically move toward the path and integrate into it. This runs in parallel with the straightening phase.
  5. Wave Sort: Once all robots form a straight line, they are sorted. The authors introduce a novel asynchronous, distributed version of odd-even sort (a parallel bubble sort). $r_{min}$ sends out continuous "waves" of messages. As a wave passes through the line, adjacent pairs of robots compare IDs and physically swap places if they are out of order.

Datasets

Not discussed in the paper. The authors validated their approach using custom physics-based simulations rather than standard datasets. They simulated swarms ranging from 15 to 130 robots to measure runtime, collision avoidance, and message complexity.

Key Insights and Ideas

  • Squared Distances Prevent Intersections: A major geometric headache in swarm robotics is paths crossing, which leads to physical deadlocks. The authors proved that routing a path using the squared Euclidean distance between robots naturally prevents self-intersections, ensuring a clean initial backbone for the swarm.
  • Physical Data Structures: The algorithm brilliantly treats the physical swarm as a data structure. By first forcing the robots into a physical doubly linked list, the complex 2D navigation problem is reduced to a 1D array sorting problem.
  • Beating the Sorting Lower Bound via Parallelism: Standard comparison sorting is bounded at $\Omega(n \log n)$. By using "Wave Sort," multiple sorting waves propagate through the physical chain of robots simultaneously. Because multiple pairs swap at the same time, the entire swarm sorts itself in $O(n)$ time.

Key Results

  • Optimal Time and Distance: The entire arraying and sorting process completes in $\Theta(n)$ time, with a total travel distance of $\Theta(nD)$ (where $D$ is the maximum initial distance between robots). Both metrics are mathematically optimal for this setup.
  • Message Complexity: The protocol requires $O(n^2)$ individual messages, keeping communication overhead manageable for low-bandwidth robots.
  • Simulation Validation: Simulations with up to 130 robots confirmed that all components of the algorithm scale linearly in practice, even when accounting for continuous motion, sensing, and collision avoidance.

Limitations and Future Work

  • Space Constraints: The algorithm assumes that the environment is dense enough to maintain a connected communication graph, but sparse enough that there is physical room to form the final line. If the robots are packed too tightly, they may not have enough space to execute the physical swaps during the Wave Sort phase.
  • Future Work: The authors acknowledge this density limitation and suggest future work focusing on highly dense settings. A proposed solution is to allow the global minimum and maximum robots to actively move apart during the process, dynamically creating enough physical space to accommodate the rest of the swarm.

Summary updated

Abstract

We consider the problem of organizing a scattered group of n robots in two-dimensional space. 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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ) individual messages, and O(n) travel distance per robot. Implementation of the sorting and navigation use communication messages of fixed size, and are a practical solution for large populations of low-cost robots.
BibTeX
@inproceedings{krupke2015parallel,
  author = {Dominik Krupke and Michael Hemmer and James McLurkin and Yu Zhou and Sándor P. Fekete},
  title = {{A parallel distributed strategy for arraying a scattered robot swarm}},
  booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
  year = {2015},
  url = {https://openreview.net/forum?id=630Wwm-nEOQ},
}

Loading related content...

Figure