Reachability and Coverage Planning for Connected Agents

Tristan Charrier, Arthur Queffelec, Ocan Sankur, François SchwarzentruberIJCAI 2019 · DOI

TL;DR

This paper tackles the complex problem of coordinating multiple robots (like drones) to explore an area while maintaining constant communication. They introduce a new, more realistic model of robot communication and movement called "sight-moveable graphs," for which they develop efficient algorithms that are significantly faster than previous approaches.

What Problem Does This Paper Address?

Imagine a fleet of drones tasked with searching a disaster area or mapping a remote region. These drones need to cover as much ground as possible, but they also need to stay connected to a central base station, either directly or by relaying signals through each other. This "connected coverage" problem is crucial for information gathering and ensuring the drones can report their findings. The challenge lies in planning efficient paths for multiple robots that satisfy both coverage and connectivity constraints simultaneously. Existing models often simplify communication or movement, leading to algorithms that are either too slow for practical use or don't accurately reflect real-world robot capabilities. This paper aims to bridge this gap by proposing a more realistic model and analyzing its computational complexity.

Methods

The authors model the environment as a "topological graph," where nodes represent locations and edges represent possible movements and communication links. They introduce and analyze several classes of these graphs, including:

  • Neighbor-Communicable Graphs: Robots can communicate with adjacent nodes.
  • Sight-Moveable Graphs: This is their key contribution. It assumes robots can only communicate within their line of sight and that movement is restricted to where they can see. This is a more realistic model for drones.
  • Complete-Communication Graphs: A simplified case where communication is always possible.

They then analyze the computational complexity of two core problems: Reachability (can agents reach a specific configuration?) and Coverage (can agents visit all parts of the area?). They use techniques from computational complexity theory, including reductions between problems, to establish lower bounds (proving problems are hard) and design algorithms to establish upper bounds (proving problems are solvable efficiently).

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Realistic Communication Models Matter: The complexity of the connected coverage problem changes dramatically depending on how communication is modeled. Restricting communication to line-of-sight (sight-moveable graphs) makes the problem significantly more tractable.
  • Sight-Moveable Graphs Enable Efficiency: For their proposed "sight-moveable" graphs, both reachability and coverage problems can be solved in LOGSPACE. This is a huge improvement over PSPACE-completeness for more general graph types, meaning efficient parallel algorithms can be developed.
  • Bounded vs. Unbounded Problems: The bounded versions of these problems (where a maximum execution time is given) are often NP-complete, suggesting that while efficient algorithms exist for the general case, finding optimal short plans can still be hard.
  • Anonymity Simplifies: The assumption that agents are anonymous (their individual identities don't matter, only their positions) simplifies the problem and is useful for developing more efficient algorithms.

Key Results

  • General and Neighbor-Communicable Graphs: Coverage and Reachability problems are PSPACE-complete, indicating they are computationally hard.
  • Sight-Moveable Graphs:
    • Reachability and Coverage problems are in LOGSPACE, meaning they can be solved very efficiently.
  • Bounded Reachability is NP-complete.
  • Complete-Communication Graphs: Bounded Reachability is in LOGSPACE, and Bounded Coverage is NP-complete.

The paper provides a table summarizing these complexity results, highlighting the significant gains achieved with the sight-moveable graph model.

Limitations and Future Work

  • Symmetric Movement: The paper notes that their PSPACE-hardness result for coverage on neighbor-communicable graphs might not hold if movement edges are always symmetric (i.e., if you can move from A to B, you can also move from B to A). This is an open question.
  • Planar/Grid Environments: While the paper focuses on abstract topological graphs, real-world applications often involve planar or grid-like environments. The authors suggest that extending their findings to these specific environments, especially considering the intractability of MAPP on general grids, would be valuable.
  • Parametrized Complexity: The authors plan to investigate the parametrized complexity of their problems, where parameters like the treewidth of the graph or the number of agents could lead to more nuanced complexity results.
  • Real-World Constraints: Future work could incorporate more realistic constraints such as agent collisions, varying communication ranges, and dynamic environments.

Summary updated

BibTeX
@inproceedings{charrier2019reachability,
  author = {Tristan Charrier and Arthur Queffelec and Ocan Sankur and François Schwarzentruber},
  title = {{Reachability and Coverage Planning for Connected Agents}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/21},
}
Figure