An Asymmetric Distributed Method for Sorting a Robot Swarm

Abstract

We consider the problem of sorting a swarm of labeled robots in Euclidean space. Our goal is to organize the robots into a sorted and equally-spaced straight line between the robots with lowest and highest labels, while maintaining a connected communication network. We break the symmetry between the minimum and maximum, in order to keep time, travel distance, and communication costs low, without using central control. We run in parallel a set of functions, including leader election, tree formation, path formation, path modification, and geometric straightening. We show that our algorithm is safe, correct, efficient, and robust to changes in population and connectivity. We validate our theoretical results with simulations. Our implementation uses messages of fixed size and robots of constant memory, and is a practical solution for large populations of low-cost robots.