Priority-Aware Multi-Robot Coverage Path Planning
This addresses the limitation of uniform region importance in MCPP for scenarios requiring faster attention to specific zones, offering a scalable solution for multi-robot systems in coverage tasks.
The paper tackles the problem of Multi-Robot Coverage Path Planning (MCPP) by introducing priority-aware zones with weights, aiming to minimize priority-weighted latency and makespan. It proposes a two-phase framework that significantly reduces priority-weighted latency compared to baselines while maintaining competitive makespan, as demonstrated in experiments across diverse scenarios.
Multi-robot systems are widely used for coverage tasks that require efficient coordination across large environments. In Multi-Robot Coverage Path Planning (MCPP), the objective is typically to minimize the makespan by generating non-overlapping paths for full-area coverage. However, most existing methods assume uniform importance across regions, limiting their effectiveness in scenarios where some zones require faster attention. We introduce the Priority-Aware MCPP (PA-MCPP) problem, where a subset of the environment is designated as prioritized zones with associated weights. The goal is to minimize, in lexicographic order, the total priority-weighted latency of zone coverage and the overall makespan. To address this, we propose a scalable two-phase framework combining (1) greedy zone assignment with local search, spanning-tree-based path planning, and (2) Steiner-tree-guided residual coverage. Experiments across diverse scenarios demonstrate that our method significantly reduces priority-weighted latency compared to standard MCPP baselines, while maintaining competitive makespan. Sensitivity analyses further show that the method scales well with the number of robots and that zone coverage behavior can be effectively controlled by adjusting priority weights.