A Cell Potential and Motion Pattern Driven Multi-robot Coverage Path Planning Algorithm

This paper proposes an intelligent “Cell Potential and Motion Pattern driven Coverage (CPMPC)” algorithm to solve a cooperative coverage path planning problem for multiple robots in two-dimensional target environment. The target environment is divided into cell areas according to the detection range of robot, and the cell matrix is given correspondingly. The values in the cell matrix are defined as cell potential, which represents the number of times each cell is detected by robots. The priority of the robot’s neighbor cell is called the motion pattern. At different moments, robots can choose within different motion patterns. Genetic algorithm (GA) is used to optimize the combination of motion patterns. By taking account obstacle avoidance and collision avoidance into consideration, the CPMPC algorithm adopts a double-layer choice strategy driven by cell potential and motion pattern to generate the next waypoint. Furthermore, this algorithm contains two optimal strategies: avoiding collision and jumping out of the detected area. Compared with the pattern-based genetic algorithm, the results obtained by us show that the CPMPC algorithm could solve the multi-robot coverage path planning (MCPP) problem effectively with guarantee of complete coverage, and improved makespan.