TMSTC*: A Path Planning Algorithm for Minimizing Turns in Multi-Robot Coverage

Coverage path planning is a major application for mobile robots, which requires robots to move along a planned path to cover the entire map. For large-scale tasks, multirobot systems offer significant advantages. In this letter, we propose Turn-minimizing Multirobot Spanning Tree Coverage Star (TMSTC*), an improved multirobot coverage path planning (mCPP) algorithm based on MSTC*. Our algorithm partitions the map into minimum bricks as tree branches, transforming the problem into finding the maximum independent set of a bipartite graph. We then use a greedy strategy to connect bricks and form a tree, aiming to minimize the number of turns of the corresponding circumnavigating coverage path. Our experimental results show that our approach enables multiple robots to make fewer turns, resulting in faster completion of coverage tasks compared to other popular algorithms.