Research map / Graph learning / Graph algorithms and clustering
Large-Scale Multi-Robot Coverage Path Planning via Local Search
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.
Proposes LS-MCPP, a local search over subgraphs of the decomposed graph that uses a new Extended-STC paradigm and three boundary-editing operators to reduce makespan for graph-based multi-robot coverage path planning.
Problem
Graph-based multi-robot coverage path planning (MCPP) minimizing makespan on 2D grid terrain graphs; existing tree-cover + STC methods are suboptimal and cannot handle incomplete terrain graphs.
Approach
Instead of optimizing tree covers on the terrain graph, search directly over connected subgraphs of the decomposed graph via local search with grow, deduplicate, and exchange operators, evaluated by ESTC (an STC extension that handles incomplete vertices via augmented-graph MST and path deformation).
Key results
- LS-MCPP reduces makespan by up to 35.7% vs MFC and 30.3% vs MSTC* (up to 67.0% vs VOR) on benchmark instances, within 20 minutes.
- On smaller instances, LS-MCPP averages -1.02% and 1.16% makespan change relative to MIP(H) and MIP while running orders of magnitude faster.
- On Shanghai2 and NewYork1 (large), LS-MCPP achieves 570.9 and 1,062 makespan vs MIP(H) 1,509 and 4,736 (MIP unable to run).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply LS-MCPP instead of VOR | Graph-based MCPP · All evaluated instances | makespan: up to 67.0%; on average, 50.4% | Helped |
| Apply LS-MCPP instead of MFC | Graph-based MCPP · All evaluated instances | makespan: up to 35.7%; on average, 26.7% | Helped |
| Apply LS-MCPP instead of MSTC$^*$ | Graph-based MCPP · All evaluated instances | makespan: up to 30.3%; on average, 13.4% | Helped |
| Replace Full-STC with ESTC (ablation) | Coverage planning on incomplete terrain graphs · flr-l and trn1-l | path cost | Helped |
| Remove grow operators (ablation) | LS-MCPP · flr-l and trn1-l | makespan | Hurt |
| Remove deduplicate operators (ablation) | LS-MCPP · flr-l and trn1-l | makespan | Hurt |
| Remove exchange operators (ablation) | LS-MCPP · flr-l and trn1-l | makespan | Hurt |
| Use heuristic-based rather than uniform random operator sampling (ablation) | LS-MCPP · flr-l | path cost | Helped |
| Use heuristic-based rather than uniform random operator sampling (ablation) | LS-MCPP · trn1-l | path cost | Helped |
| Periodically call ForcedDeduplication (ablation) | LS-MCPP · flr-l and trn1-l | makespan | Helped |
| Initialize LS-MCPP with MIP rather than MFC (ablation) | LS-MCPP · trn1-l | makespan | No clear effect |
Surprising findings
- Optimal tree cover does not necessarily yield optimal MCPP solution on the decomposed graph, so searching directly on decomposed graphs can beat optimal tree covers.
Limitations
- Assumes complete terrain graphs in experiments; incomplete-graph results only on a perturbed setting without baseline comparison.
- Does not address inter-robot collisions.
- Relies on hand-designed heuristics for operator sampling; tuning of iteration counts and parameters per instance.
Experimental setup
Datasets: MCPP instances from prior work (flr-s, trn-m, mze-m, flr-l, mze-l, trn1-l) AR0701SR Shanghai2 NewYork1
Benchmarks: flr-s trn-m mze-m flr-l mze-l trn1-l AR0701SR Shanghai2 NewYork1
Metrics: makespan runtime
Baselines: VOR MFC MSTC* MIP MIP(H)
Builds on: Spanning Tree Coverage Full-STC simulated annealing MFC MSTC*
Closest papers by meaning
- Heterogeneous Multi-Robot Graph Coverage with Proximity and Movement Constraints (AAAI 2025 · similarity 0.91)
- Learning Coverage Paths in Unknown Environments with Deep Reinforcement Learning (ICML 2024 · similarity 0.85)
- Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding (AAAI 2024 · similarity 0.85)
- Multi-Robot Motion Planning with Diffusion Models (ICLR 2025 · similarity 0.84)
- Provably Efficient Long-Horizon Exploration in Monte Carlo Tree Search through State Occupancy Regularization (ICML 2024 · similarity 0.84)
- Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology (AAAI 2024 · 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.