Asynchronous Network Formation in Unknown Unbounded Environments

Selim Engin, Volkan Isler

Abstract

In this paper, we study the Online Network Formation Problem (ONFP) for a mobile multi-robot system. Consider a group of robots with a bounded communication range operating in a large open area. One of the robots has a piece of information which has to be propagated to all other robots. What strategy should the robots pursue to disseminate the information to the rest of the robots as quickly as possible? The initial locations of the robots are unknown to each other, therefore the problem must be solved in an online fashion. For this problem, we present an algorithm whose competitive ratio is $O(H \cdot \max\{M,\sqrt{M H}\})$ for arbitrary robot deployments, where $M$ is the largest edge length in the Euclidean minimum spanning tree on the initial robot configuration and $H$ is the height of the tree. We also study the case when the robot initial positions are chosen uniformly at random and improve the ratio to $O(M)$. Finally, we present simulation results to validate the performance in larger scales and demonstrate our algorithm using three robots in a field experiment.

Introduction

The Online Network Formation Problem (ONFP) addresses a critical challenge in multi-robot systems: how to "wake up" and connect a scattered swarm of robots in an expansive, unknown environment. Initially, one robot is "active" (the leader) while the others are "frozen" or asleep. When an active robot enters the communication range of a frozen one, that robot activates and joins the search. Unlike prior research confined to bounded environments or discrete graphs, this work tackles the complexities of unbounded space and asynchronous operations.

Methodology: The CIRCLE-TAG Algorithm

To solve the ONFP, we introduce CIRCLE-TAG, a decentralized search strategy that systematically expands the search area and dynamically divides labor as the active swarm grows. The algorithm relies on two primary movement patterns:

  1. Concentric-Circles-Search (CCS): The initial leader robot begins by traveling in expanding concentric circles around its starting position to locate the first set of neighbors.
  2. Dynamic Partitioning: Once the leader finds other robots, it partitions the unexplored outer boundary into equal-sized "blocks" (shaped like circle sectors) based on the number of currently active robots.
  3. Block-Cover: Each active robot is assigned a block and sweeps it using an arc-shaped back-and-forth motion.
  4. Reassignment: The leader continuously circles the perimeter, collecting newly awakened robots and re-partitioning the expanding boundary into smaller, more numerous blocks to maximize parallelization.
The CIRCLE-TAG algorithm utilizes Concentric-Circles-Search (CCS) for initial discovery and Block-Cover for systematic area sweeping.

This approach ensures mathematically guaranteed coverage of the unbounded space while efficiently scaling the search effort as more robots become active.

Theoretical Performance

The algorithm's performance is tied to the geometric properties of the swarm's initial layout, specifically the Euclidean Minimum Spanning Tree (MST). By using the MST's maximum edge length ($M$) and height ($H$), we establish the following competitive ratios:

  • Arbitrary Deployments: $O(H \cdot \max\{M, \sqrt{MH}\})$.
  • Random Deployments: For robots distributed uniformly at random, the ratio tightens to $O(M)$.

Experimental Validation

We evaluated CIRCLE-TAG using both large-scale simulations and real-world field experiments. MATLAB simulations scaling from 20 to 1,000 robots confirmed that the empirical performance fits the theoretical bounds tightly, particularly as the swarm size increases.

Simulation results comparing the performance of CIRCLE-TAG against theoretical upper bounds as the number of robots increases.

Furthermore, the algorithm was successfully demonstrated in a field experiment using three DJI Matrice 100 UAVs. Operating in a 100m x 150m outdoor environment and communicating via XBee modules, the drones successfully executed the search, wake-up, and dynamic path-generation phases, proving the algorithm's resilience to real-world asynchrony.

Conclusion

CIRCLE-TAG provides a robust framework for network formation in unknown, unbounded environments. Future research will focus on adapting this problem for heterogeneous robot teams, where task assignments can be optimized based on hardware capabilities—such as utilizing fast-moving aerial drones for distant exploration while slower ground robots perform thorough local sweeps.

Summary updated

Abstract

In this paper, we study the Online Network Formation Problem (ONFP) for a mobile multi-robot system. Consider a group of robots with a bounded communication range operating in a large open area. One of the robots has a piece of information which has to be propagated to all other robots. What strategy should the robots pursue to disseminate the information to the rest of the robots as quickly as possible? The initial locations of the robots are unknown to each other, therefore the problem must be solved in an online fashion. For this problem, we present an algorithm whose competitive ratio is $O(H \cdot \max\{M,\sqrt{M H}\})$ for arbitrary robot deployments, where $M$ is the largest edge length in the Euclidean minimum spanning tree on the initial robot configuration and $H$ is the height of the tree. We also study the case when the robot initial positions are chosen uniformly at random and improve the ratio to $O(M)$. Finally, we present simulation results to validate the performance in larger scales and demonstrate our algorithm using three robots in a field experiment.
BibTeX
@inproceedings{engin2019asynchronous,
  author = {Selim Engin and Volkan Isler},
  title = {{Asynchronous Network Formation in Unknown Unbounded Environments}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2019},
  url = {https://openreview.net/forum?id=GCyOWuYKGb},
}
Figure