Research map / Multi-agent systems and games / Human-AI and goal-conditioned
Heterogeneous Multi-Robot Graph Coverage with Proximity and Movement Constraints
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Formulates multi-robot graph coverage with formation-based proximity and transition constraints, gives an FPT exact algorithm (in formation size, max degree, treewidth) and PTAS approximations for trees, including a 3-robot connected case with error independent of max degree.
Problem
Minimizing the number of steps for a team of heterogeneous robots to cover a graph while satisfying proximity (formation) and movement (transposition/traversability) constraints.
Approach
Encodes proximity constraints as a set of robot formations (graph monomorphisms) and movement constraints as transpositions between formations; proves a Z-lemma that optimal traversals never repeat transitions, enabling bounded-size signatures for a tree-decomposition dynamic program and a greedy tree-cover PTAS when formations are collapsible.
Key results
- Exact FPT algorithm solves MRFGC in time O(n * h(||F||, Δ, tw)), i.e., FPT in formation size, max degree and treewidth.
- PTAS for collapsible formations on trees with traversal time at most OPT*(1+nε f(||F||,Δ)) and runtime O(n·g(||F||,ε)).
- For k=3 connected robots on trees, the cover error satisfies timecover - OPT <= 52nε, independent of max degree.
- Preliminary experiments on floor plans of several large hotel buildings show consistent improvement over the state-of-the-art approach.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed approach with heuristic simplifications instead of the current state-of-the-art approach | Multi-robot coverage of hotel floor plans · Hotel floor plans | traversal time | Helped |
Limitations
- Exact algorithm complexity grows quickly with formation size, max degree and treewidth.
- PTAS requires collapsible formations; non-collapsible settings like guards and passage constraints are excluded.
- Experimental evaluation is preliminary and uses heuristic simplifications.
Experimental setup
Benchmarks: floor plans of large hotel buildings
Metrics: traversal time
Baselines: state-of-the-art approach for multi-robot tree coverage (MRCTC)
Builds on: Multi-Robot Connected Tree Coverage nice tree decomposition
Closest papers by meaning
- Large-Scale Multi-Robot Coverage Path Planning via Local Search (AAAI 2024 · similarity 0.91)
- Inapproximability of Optimal Multi-Agent Pathfinding Problems (AAAI 2025 · similarity 0.85)
- Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology (AAAI 2024 · similarity 0.85)
- Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding (AAAI 2024 · similarity 0.85)
- Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures (AAAI 2025 · similarity 0.85)
- Simulation-Informed Diffusion for Decentralized Multi-robot Motion Planning (NeurIPS 2026 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.