A Multi-Robot Indoor Coverage Path Planning Method Based on the Improved BCD Segmentation

Abstract

Multi-robot collaborative task planning is gradually becoming a hot topic in robotics technology. Collaborative coverage path planning is one of the critical issues in the field. Based on the advantages of Boustrophedon Cellular Decomposition (BCD), which is more lightweight and efficient in storage and computation and has a more regular traversal path, BCD has a wide range of applications. Currently, there are some issues with BCD- related algorithms at both the path planning and task allocation levels. For a structured indoor environment, the original unit segmentation method did not consider side-by-side obstacles, which may result in losing some areas under special circumstances, making it impossible to traverse the entire environment. On the other hand, task allocation only considers the area threshold, leading to fragmented task allocation, which may reduce overall execution efficiency. This article proposes an improvement of BCD based on region area threshold and vertex degree to avoid the problems of fragmented allocation of unit clusters occurring in special situations with pure threshold criteria and ensuring the unique connectivity determined within the unit cluster through breadth-first search. Finally, we conducted simulations and tests in real-world scenarios separately with the algorithm proposed in this paper validated on a multi-robot platform in the context.