MDSTC: A Dynamic Approach to Multi-Robot Coverage Path Planning

Maximizing the efficiency of multi-robot systems is one of the primary objectives in solving the multi-robot coverage path planning (mCPP) problem. During coverage tasks, unexpected imbalances in the multi-robot systems, such as changes in speed, can lead to suboptimal utilization of the system's capabilities, subsequently reducing the efficiency of task execution. In this paper, we developed a multi-robot dynamic spanning tree coverage (MDSTC) algorithm, an online area-division-based approach that adjusts region allocation among robots based on their coverage status through an exchange-based mechanism to enhance multi-robot system efficiency. To validate the effectiveness of the proposed algorithm, we conducted extensive numerical simulations. The results demonstrate that our algorithm achieves a superior solution in scenarios where robot efficiency remains balanced, closely matching the performance of state-of-the-art mCPP methods. Furthermore, when differences in efficiency arise among the robots during task execution, the proposed algorithm provides a dynamic solution that enhances overall coverage efficiency.