Adaptive Coverage Algorithms for Mobile Ad Hoc Networks in Dynamic Worlds

Hugo Gandhi, Edwin Meriaux, Antonio LoríaarXiv 2026 · arXiv

TL;DR

This paper introduces the Dynamic Partially Observable Cooperative Guard Art Gallery Problem (DPOCGAGP), a new framework for multi-robot systems to maintain communication and coverage in unpredictable, changing environments. The authors present adaptive versions of centralized and decentralized algorithms that successfully recover from agent failures and structural collapses, revealing a fundamental trade-off between deployment speed and agent efficiency across 4,500 simulated test cases.

What Problem Does This Paper Address?

Deploying a Mobile Ad Hoc Network (MANET) of robots into an unknown, constrained space—like a collapsed building or a deep mine—is a classic challenge in robotics. This is often modeled as the Art Gallery Problem: how do you place the fewest "guards" (robots) so every point in the "gallery" (the environment) is visible?

Previous work established the POCGAGP, where a team of robots must simultaneously explore an unknown space, cover it entirely with their sensors, and maintain a connected communication graph. However, these models assumed a static world. In reality, robots break (Agent Loss) and environments change (World Change), such as a wall collapsing and blocking a hallway.

Fig. 1: Robots attempting to form a MANET in a partially observed indoor environment with collapsed wall sections and a failed agent.

The authors address this "dynamic instability" by requiring systems to not only explore but also autonomously recover connectivity and coverage after unpredictable disturbances.

Methods

The researchers adapted two state-of-the-art algorithms to handle these dynamic "adversarial" settings:

  1. CADENCE (Centralized): This approach uses a single "brain" with global knowledge. It identifies "valid corners"—specifically 270° reflexive vertices in an orthogonal map—as optimal targets for robot placement.
  2. Adaptive Twist: The authors tested three recovery methods. The most effective, Method 3 (Proactive Deployment), focuses resources on the "frontier" (the edge of current coverage) to repair gaps rather than refilling every internal position.
  3. Fig. 2: Illustration of a polygon W with all invalid reflexive corners in green and valid corners in red.
Fig. 2: Illustration of a polygon W with all invalid reflexive corners in green and valid corners in red.
  1. DADENCE (Decentralized): Here, robots act as an autonomous swarm using only local information. They reach a consensus on the next target by looking at the "edge of coverage" and minimizing travel distance.
  2. Adaptive Twist: When the network fractures due to a lost robot or a new wall, the separated groups naturally transition into independent swarms. They continue to explore their local areas until they eventually "find" each other again and merge back into a single network.
  3. Greedy Deallocation: Both algorithms use a pruning step to remove "unnecessary" robots that don't contribute to total coverage or connectivity, keeping the network lean.

Datasets

The study evaluates these algorithms using a massive, procedurally generated benchmark:

  • 4,500 simulations across 200 unique 2D "dungeon" maps.
  • Maps vary in size and complexity, measured using quadtree decomposition.
  • World Mutation: The benchmark includes sequences of world states where floor space is added or walls are inserted mid-deployment.
  • Example 2D dungeon map after 2 successive mutations.
Example 2D dungeon map after 2 successive mutations.

Key Insights and Ideas

  • The Speed vs. Efficiency Trade-off: A core finding is that centralized systems (CADENCE) are incredibly fast at recovering coverage but are "agent-hungry," requiring temporary surges in the number of robots deployed. Decentralized systems (DADENCE) are slower but much more efficient with resources.
  • Natural Resilience: DADENCE’s decentralized nature is a "free" feature for resilience. Because agents already operate on local consensus, network fragmentation doesn't break the algorithm; it just creates two smaller, functional swarms that eventually heal the fracture upon reconnection.
  • Fracture Dynamics: The paper visualizes how the loss of a single "routing node" can split a MANET, a critical failure point that the adaptive algorithms are specifically designed to bridge.
  • Graph-based representation of a disconnected MANET due to agent attrition.
Fig. 3: Graph-based representation of a disconnected MANET due to agent attrition.

Key Results

The adapted algorithms significantly outperformed the standard benchmark (ISDA):

  • Recovery Speed: CADENCE was the clear winner, requiring 78.88% fewer steps than the benchmark to restore coverage. DADENCE was also faster than the benchmark, especially in complex mutated worlds (up to 31% faster).
  • Agent Usage: DADENCE was the most efficient, using 18.48% fewer maximum agents than the benchmark.
  • Steady State: After the "surge" of recovery and subsequent deallocation, both CADENCE and DADENCE maintained the environment with fewer robots than the benchmark (13.85% and 28.94% fewer, respectively).

Limitations and Future Work

  • Dimensionality: While the framework supports 3D, the current testing and specific "valid corner" heuristics are optimized for 2D orthogonal (grid-like) planes.
  • Idealized Sensors: The model assumes ideal 360° LiDAR and perfect line-of-sight communication. Real-world signal degradation through different building materials (referenced in the paper) remains a challenge for future physical implementation.
  • Future Directions: The authors suggest moving toward 3D environments and incorporating more complex hardware constraints like battery life and non-ideal sensor noise.

Summary updated

Abstract

This paper extends an existing framework for the coordination of mobile agents in unknown worlds, by considering the possibility of dynamic instability. In the original problem, known as the Partially Observable Cooperative Guard Art Gallery Problem (POCGAGP) (arXiv:2512.09495), the multi-agent system must establish a communication network which completely covers an initially unknown constrained space. However, the POCGAGP fails to account for the unpredictability often seen in real-world deployment. To address this, the dynamic case (DPOCGAGP) introduces two settings which can influence the mobile network during deployment: Agent Loss and World Change, which represent dynamic changes to the world. Within this study, we present advancements to two state-of-the-art algorithms, the Centralized Agent-Directed Exploration for Network Coverage (CADENCE), and its decentralized analogue, DADENCE, to provide solutions in these cases. We then compare their performance against another state-of-the-art benchmark algorithm, and show that the adapted algorithms outperform across our benchmark test set, which comprises over 4500 test cases of varied size and structure.
BibTeX
@misc{gandhi2026adaptive,
  author = {Hugo Gandhi and Edwin Meriaux and Antonio Loría},
  title = {{Adaptive Coverage Algorithms for Mobile Ad Hoc Networks in Dynamic Worlds}},
  year = {2026},
  eprint = {2610.41936},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.41936},
}
Figure