Towards Decentralized Formation of Minimum-Length Communication Networks Using Robot Swarms
Authors: Genki Miyauchi, Mohamed S. Talamali, Julian Rau, Roderich Groß
Organizations: Bristol Robotics Laboratory, University of Bristol, Bristol, UK · School of Electrical and Electronic Engineering, University of Sheffield, Sheffield, UK · Department of Computer Science, Technical University of Darmstadt, Darmstadt, Germany
Multi-robot missions in infrastructure-denied environments frequently rely on reliable communication links between spatially separated locations. We propose a fully decentralized framework for constructing and dynamically maintaining communication networks without centralized topology planning or global positioning infrastructure. Driven strictly by local interactions, robots reconfigure local network topologies and adjust their physical positions to minimize overall network length while adhering to communication constraints. Formal analysis shows that our local reconfiguration operations guarantee continuous network connectivity, strictly decrease network length with every branch transfer, and bound worst-case performance to the shortest starlike tree. Embodied simulations and physical multi-robot experiments confirm that our approach forms networks near the length of centrally computed Euclidean Steiner trees. Additionally, the system dynamically adapts to moving targets and optimizes deployment by utilizing only necessary connectors, preserving excess robots for auxiliary tasks. This work enables autonomous swarms to self-organize adaptive ad hoc communication infrastructure in communication-denied environments, which could support applications varying from subterranean exploration to planetary missions.
Figures & tables
Fig. 1: Robots forming a communication network between several locations in the environment. Some robots (or humans) operate at the locations of interest (indicated by exclamation marks) while other robots maintain the network in an environment where global positioning systems and communication infrastructure are not available.
Fig. 2: Overview of the three self-organized topology reconfiguration processes: branch extension, branch shortening, and branch transfer.
Fig. 3: Finite state machine executed by each worker robot. The colored states indicate the different topology reconfiguration processes.
Fig. 4: Left: Snapshots from a simulation trial. Right: Final robot positions for the same trial. Gray circles indicate target locations. Lines show the network formed by our approach, the centrally computed Steiner tree, and the centrally computed shortest starlike tree, as indicated in the legend.
Fig. 5: Comparison of the network length ( L(G)/n ) and number of connectors ( Nconnector/n ) per target for varying numbers of target locations.
Fig. 6: Number of connectors for varying communication ranges when using our approach.
Fig. 7: Snapshots from a real robot experiment. (a) Final network with branch transfer. (b) Final network without branch transfer. Leaders (L, red), connectors (C, cyan), and free workers (F, green) are labelled. Cyan lines denote connections between robots. Red circles indicate target locations.
Fig. 8: Comparison of the total network length and number of connectors from real robot experiments.
Department of Computer Science, University of Illinois Chicago, Chicago, IL 60607, USA · Department of Computer Science, University of North Carolina at Charlotte, Charlotte, NC 28223, USA