Dynamic Task-Priority Coverage Planning for Efficient Multi-Robot Collaboration

Abstract

The global efficiency of multi-robot system coverage planning is challenging, particularly in scenarios involving stochastically emerging subtasks that dynamically interfere with coverage processes, imposing a temporal burden on overall operations. In this article, a multi-robot coverage planning strategy is proposed to provide high-quality solutions with favorable efficiency. The architecture comprises three interconnected procedures: 1) work area allocation; 2) spanning tree coverage; and 3) dynamic replanning. In the area allocation process, different robots are assigned independent work areas through weight-balanced task allocation and smoothing metrics, where comparable sizes and smooth boundaries of these regions can effectively improve coverage efficiency. In the process of spanning tree coverage, the work area is partitioned into nonoverlapping blocks as partial branches. These partial branches are subsequently connected to form the complete spanning tree with reduced turns via a heuristic-driven strategy. Then, the multiple robots begin the coverage task within assigned regions guided by the spanning tree. Notable progress discrepancies triggered by stochastic subtasks may activate the dynamic replanning procedure, redistributing residual areas and replanning paths to improve collaborative efficiency. A thorough analysis of the proposed strategy is provided, including completeness and computational complexity. Finally, comprehensive simulation comparisons with current-leading planning approaches in different scenarios, along with a series of convincing real-world studies, have been conducted to provide evidence for verifying the feasibility and validity of the proposed method. Warehouse inspection tasks systematically validate the method’s operational feasibility.