Priority-Aware Multi-Robot Coverage Path Planning
Kanghoon Lee, Hyeonjun Kim, Jiachen Li, Jinkyoo Park
AI summary
Problem
Existing multi-robot coverage methods assume uniform region importance, failing when certain zones require faster attention. This paper addresses how to coordinate robots to ensure complete coverage while strictly prioritizing the early visitation of high-priority areas.
Approach
A two-phase framework that first assigns prioritized zones to robots via greedy allocation and local search to minimize weighted latency, then covers remaining areas using Steiner-tree-guided residual coverage with workload balancing.
Key results
- Formalization of the PA-MCPP problem with lexicographic objectives
- Scalable two-phase planning framework integrating greedy assignment, local search, and Steiner-tree coverage
- Significant reduction in priority-weighted latency compared to standard MCPP baselines
- Competitive overall makespan and strong scalability with increasing robot counts
Why it matters
Enables safer and more responsive multi-robot operations in time-sensitive applications like search-and-rescue, surveillance, and hazardous environment inspection.
Abstract
Multi-robot systems are widely used for coverage tasks that require efficient coordination across large environ- ments. In Multi-Robot Coverage Path Planning (MCPP), the ob- jective 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.