Multi-Robot Exploration with Communication Restrictions

Elizabeth A. JensenIJCAI 2015

Abstract

This paper presents three distributed algorithms—Rolling Dispersion Algorithm (RDA), Sweep Exploration Algorithm (SEA), and Train Exploration Algorithm (TEA)—designed for multi-robot coordination in unknown, post-disaster environments. These algorithms address the "communication crunch" where high-bandwidth networks or GPS are unavailable. By utilizing physical beacons and specific movement protocols, the algorithms guarantee full coverage and safe return to base. Simulation results demonstrate that SEA often outperforms RDA in efficiency, and scalability is achieved through managed communication overhead.

Introduction

In post-disaster scenarios, environments are frequently too hazardous for human rescuers. Robots deployed for scouting face significant challenges, primarily a lack of reliable communication infrastructure. Standard coordination methods often fail in collapsed buildings or subterranean voids where GPS and high-bandwidth signals are absent. The objective is to develop a system where a team of robots can fully explore an unknown area, avoid infinite loops, mark paths for humans, and operate robustly under severe communication constraints such as line-of-sight or low-bandwidth signals.

Distributed Exploration Algorithms

The proposed framework includes three algorithms tailored to varying communication restrictions:

  • Rolling Dispersion Algorithm (RDA): Optimized for Wi-Fi-like range-constrained communication. Robots leap-frog into the environment, maintaining signal range with their peers.
  • Sweep Exploration Algorithm (SEA): Designed for extremely restrictive environments (e.g., line-of-sight). To prevent signal interference, it employs a "one at a time" movement protocol, exploring paths sequentially.
  • Train Exploration Algorithm (TEA): An advancement of SEA where robots move as a cohesive "train," reducing latency in message propagation from the frontier back to the base.

All methods utilize physical beacons to mark explored territory and guide robots (and eventually humans) through the environment.

Experimental Evaluation

The algorithms were evaluated using Player/Stage and ROS/Stage simulation environments. These simulations featured complex, non-uniform obstacles to test the logic's ability to handle open spaces and loops.

Key Insights

The research highlights that the optimal algorithm depends heavily on the environment's layout. While SEA's sequential movement might seem slow, it prevents message collisions in low-bandwidth scenarios. SEA excels in environments with long, singular paths, whereas RDA is more effective in "hub-and-spoke" layouts where parallel exploration is possible.

Performance and Scalability

Quantitative analysis shows significant efficiency gains. In specific environments, SEA achieved full coverage 1.35 times faster than RDA. This is attributed to superior pathing logic and reduced initial robot collisions.

Exploration coverage over time for SEA and RDA algorithms with varying robot team sizes.

As shown in the figure above, increasing the number of robots generally improves the rate of coverage. However, the communication overhead must be carefully managed. The data illustrates that SEA consistently reaches 100% coverage faster than RDA for equivalent team sizes (5 and 8 robots). The "plateaus" visible in the curves represent periods where robots are retracting or repositioning rather than discovering new territory, yet the algorithms successfully maintain progress toward full coverage.

Conclusion and Future Work

The proposed algorithms provide theoretical guarantees for 100% coverage and robot recovery even in the face of partial hardware or beacon failure. Future work will focus on transitioning from simulation to physical hardware to address real-world sensor noise. Additionally, the researchers aim to relax the "leash" constraint, allowing robots to temporarily move out of communication range to further increase exploration speed while maintaining loop-prevention logic.

Summary updated

BibTeX
@inproceedings{jensen2015multi,
  author = {Elizabeth A. Jensen},
  title = {{Multi-Robot Exploration with Communication Restrictions}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure