Priority-Aware Multi-Robot Coverage Path Planning

• URL: http://arxiv.org/abs/2601.00580v1
• Date: Fri, 02 Jan 2026 05:45:15 GMT
• Title: Priority-Aware Multi-Robot Coverage Path Planning
• Authors: Kanghoon Lee, Hyeonjun Kim, Jiachen Li, Jinkyoo Park,
• Abstract summary: We introduce the Priority-Aware MCPP problem, where a subset of the environment is designated as prioritized zones with associated weights.<n>The goal is to minimize, in lexicographic order, the total priority-weighted latency of zone coverage and the overall makespan.<n> Experiments across diverse scenarios demonstrate that our method significantly reduces priority-weighted latency compared to standard MCPP baselines.
• Score: 29.15118436759072
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Timeliness-Oriented Scheduling and Resource Allocation in Multi-Region Collaborative Perception [19.430782700000158]
  Collaborative perception (CP) is a critical technology in applications like autonomous driving and smart cities.<n>Due to the dynamic nature of the environment, the timeliness of the transmitted information is critical to perception performance.<n>This work studies the dynamic scheduling problem in a multi-region CP scenario, and presents a Timeliness-Aware Multi-region Prioritized (TAMP) scheduling algorithm.
  arXiv  Detail & Related papers  (2026-01-08T03:16:00Z)
• QoS-Aware Hierarchical Reinforcement Learning for Joint Link Selection and Trajectory Optimization in SAGIN-Supported UAV Mobility Management [52.15690855486153]
  A space-air-ground integrated network (SAGIN) has emerged as an essential architecture for enabling ubiquitous UAV connectivity.<n>This paper formulates UAV mobility management in SAGIN as a constrained multiobjective joint optimization problem.
  arXiv  Detail & Related papers  (2025-12-17T06:22:46Z)
• Discrete-Guided Diffusion for Scalable and Safe Multi-Robot Motion Planning [56.240199425429445]
  Multi-Robot Motion Planning (MPMP) involves generating trajectories for multiple robots operating in a shared continuous workspace.<n>While discrete multi-agent finding (MAPF) methods are broadly adopted due to their scalability, their coarse discretization trajectory quality.<n>This paper tackles limitations of two approaches by introducing discrete MAPF solvers with constrained generative diffusion models.
  arXiv  Detail & Related papers  (2025-08-27T17:59:36Z)
• Unified Path Planner with Adaptive Safety and Optimality [20.37811669228711]
  Unified Path Planner (UPP) is a graph-search-based algorithm that employs a modified obstacle function incorporating a dynamic safety cost.<n>UPP achieves a high success rate, generating near-optimal paths with only a negligible increase in cost over traditional A*.
  arXiv  Detail & Related papers  (2025-05-29T07:34:56Z)
• P2Object: Single Point Supervised Object Detection and Instance Segmentation [58.778288785355]
  We introduce Point-to-Box Network (P2BNet), which constructs balanced textbftextitinstance-level proposal bags<n>P2MNet can generate more precise bounding boxes and generalize to segmentation tasks.<n>Our method largely surpasses the previous methods in terms of the mean average precision on COCO, VOC, and Cityscapes.
  arXiv  Detail & Related papers  (2025-04-10T14:51:08Z)
• Large-Scale Multirobot Coverage Path Planning on Grids With Path Deconfliction [2.5580729045474015]
  We study Multi-Robot Coverage Path Planning (MCPP) on a 4-neighbor 2D grid G, which aims to compute paths for multiple robots to cover all cells of G.<n>We reformulate the problem directly on G, revolutionizing grid-based MCPP solving and establishing new NP-hardness results.<n>We show that our approach significantly improves solution quality and efficiency, managing up to 100 robots on grids as large as 256x256 within minutes of runtime.
  arXiv  Detail & Related papers  (2024-11-03T22:37:56Z)
• Learning Coverage Paths in Unknown Environments with Deep Reinforcement Learning [17.69984142788365]
  Coverage path planning ( CPP) is the problem of finding a path that covers the entire free space of a confined area. We investigate how suitable reinforcement learning is for this challenging problem. We propose a computationally feasible egocentric map representation based on frontiers, and a novel reward term based on total variation.
  arXiv  Detail & Related papers  (2023-06-29T14:32:06Z)
• Autonomous search of real-life environments combining dynamical system-based path planning and unsupervised learning [0.0]
  This study develops a novel applied framework for real-world applications of chaotic coverage path planners.<n>It provides techniques for effective obstacle avoidance, chaotic trajectory dispersal, and accurate real-time coverage calculation.<n>The performance of this application was comparable to that of a conventional optimal path planner.
  arXiv  Detail & Related papers  (2023-05-03T00:09:31Z)
• Multi-Prompt Alignment for Multi-Source Unsupervised Domain Adaptation [86.02485817444216]
  We introduce Multi-Prompt Alignment (MPA), a simple yet efficient framework for multi-source UDA. MPA denoises the learned prompts through an auto-encoding process and aligns them by maximizing the agreement of all the reconstructed prompts. Experiments show that MPA achieves state-of-the-art results on three popular datasets with an impressive average accuracy of 54.1% on DomainNet.
  arXiv  Detail & Related papers  (2022-09-30T03:40:10Z)
• Intention-Aware Navigation in Crowds with Extended-Space POMDP Planning [5.01069065110753]
  This paper presents a hybrid online Partially Observable Markov Decision Process (POMDP) planning system. We consider the problem of autonomous navigation in dense crowds of pedestrians and among obstacles. We present a more capable and responsive real-time approach enabling the POMDP planner to control more degrees of freedom.
  arXiv  Detail & Related papers  (2022-06-20T22:26:14Z)
• Bottom-up mechanism and improved contract net protocol for the dynamic task planning of heterogeneous Earth observation resources [61.75759893720484]
  Earth observation resources are becoming increasingly indispensable in disaster relief, damage assessment and related domains. Many unpredicted factors, such as the change of observation task requirements, to the occurring of bad weather and resource failures, may cause the scheduled observation scheme to become infeasible. A bottom-up distributed coordinated framework together with an improved contract net are proposed to facilitate the dynamic task replanning for heterogeneous Earth observation resources.
  arXiv  Detail & Related papers  (2020-07-13T03:51:08Z)
• Boundary-assisted Region Proposal Networks for Nucleus Segmentation [89.69059532088129]
  Machine learning models cannot perform well because of large amount of crowded nuclei. We devise a Boundary-assisted Region Proposal Network (BRP-Net) that achieves robust instance-level nucleus segmentation.
  arXiv  Detail & Related papers  (2020-06-04T08:26:38Z)
• Deep R-Learning for Continual Area Sweeping [41.832987254467284]
  Non-uniform coverage planning is a well-studied problem in robotics. This paper considers the variant of non-uniform coverage in which the robot does not know the distribution of relevant events beforehand. We propose a novel approach based on reinforcement learning in a Semi-Markov Decision Process.
  arXiv  Detail & Related papers  (2020-05-31T19:15:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.