Optimal Multi-Agent Map Coverage Path Planning Algorithm

Multi-agent path planning is one of the important research directions of multi-agent cooperative control, among which multi-agent covering path planning (mCPP) is a hot topic at present. Nowadays, many researchers have put forward relevant algorithms, but in some specific cases, problems such as low success rate of planning and low computational efficiency have appeared. In this paper, a hybrid algorithm based on the combination of the initial position partitioning algorithm and Two-pass algorithm is proposed for map pre-scanning and map full coverage path planning. Before the coverage path planning, this algorithm firstly scans the complex environment, calculates an evaluation coefficient, then divides the map according to the initial position of multiple agents, and finally carries out path planning in each area to complete the map's full coverage path planning. Compared with the traditional method, the designed algorithm can prescan the map without dividing the region through multiple iterations, which has higher computing efficiency and solves the shortcoming of low success rate of the traditional algorithm under special circumstances. It ensures the security, integrity and robustness of covering path planning without collision of multiple agents.