Multi-robot coverage path planning based on elastic balance and dynamic programming

Coverage path planning (CPP) serves as the basis for a variety of practical robotic applications. The use of multiple robots can significantly improve coverage efficiency and enhance system robustness. However, most multi-robot CPP (MCPP) approaches face challenges such as unbalanced task allocation and reduced efficiency caused by redundant invalid paths. To address these issues, this paper proposes a heuristic MCPP method that incorporates elastic balance (EB) mechanism and a dynamic programming (DP) mechanism. The EB mechanism models the path-splitting problem of a loop as an elastic adjustment process. By identifying the state of elastic equilibrium, it determines the optimal segmentation, thereby effectively balancing the workload among robots. The DP mechanism models the problem of minimizing round-trip charging as a dynamic programming problem and searches the entire solution space to minimize the cost of non-working paths. Comparative experiments demonstrate that the proposed method achieves the minimum coverage time in simulation environments and real-world scenarios.