Research on Multi-Robot Regional Search Planning Method Based on Voronoi Diagram

In multi-robot systems performing regional coverage search tasks, reasonable task point allocation and path planning are essential to improve coverage efficiency and reduce travel distances. This paper proposes a multi-robot regional search planning method based on Voronoi partitioning and K-means clustering. First, the Voronoi diagram is used for the initial partitioning of the search area, and the Lloyd algorithm is applied iteratively to optimize task point distribution for greater uniformity. Subsequently, an adaptive path optimization approach is employed to determine the optimal number of clusters K for K-means clustering, minimizing the total path length. Finally, within each task region, the genetic algorithm (GA) is utilized to optimize robot paths, reducing path redundancy and enhancing task execution efficiency. Simulation results demonstrate that the proposed method effectively optimizes task point allocation, reduces path length, and improves search efficiency, making it suitable for multi-robot coverage search tasks in irregular regions.