Research and optimization of conflict search algorithm for multi-agent path planning based on incremental heuristic

Conflict Based Search(CBS) is used for multi-agent Pathfinding (MAPF) to enable each Agent to reach the target node. The CBS algorithm uses the heuristic algorithm A* search to calculate the MAPF solution, and the path planning uses forward search, which cannot explore the path of the unknown region. On this basis, this paper proposes that, in the case of unknown map and changing environment at any time, when encountering new obstacles, the information obtained from previous search should be used without completely replanning the path. Because of the idea of incremental programming, the number of reprogramming times and the number of affected nodes can be reduced. The optimized algorithm consumes less time and memory, and improves the efficiency of path planning