Coverage Optimization Algorithm for Multi-robot System based on Virtual Force Refinement

Abstract

Multi-robot systems have been increasingly employed to explore and detect unknown environments in recent years, such as geological surveys, disaster detection and so on. To ensure effective area detection, area coverage is one of the key issues for multi-robot systems. However, most of the robot systems have the problems of high redundancy and covering holes. Adding robots to the detected holes will lead to increased redundancy and cost of the robot system. Therefore, this paper studies the problem of area coverage hole optimization for multi-robot systems that have limited perception range, and proposes an improved Lloyd-Voronoi algorithm based on virtual force (LVVF). The minimum number of robots required is determined by the inscribed polygon rule according to the circle perception model, and the preliminary coverage is based on Voronoi diagram and Lloyd algorithm. On the basis, a virtual force algorithm based on the Euclidean distance of regions is applied to refine the proposed Lloyd-Voronoi algorithm. The numerical simulations show that the improved Lloyd-Voronoi algorithm can improve the area coverage of the entire system and reduce the system redundancy.