Obstacle Conflict-based Search Method for Dynamic Obstacle Avoidance in Multi-agent Pathfinding

The conflict-based search (CBS) algorithm has been widely used in the field of multi-agent pathfinding, which consists of both low-level and high-level structures. However, most obstacle avoidance algorithms focus on the low-level structure, which usually causes incompatibility with the variant algorithms of CBS. In this paper, an obstacle conflict-based search (OCBS) method is proposed, in which the obstacle avoidance algorithm is designed in the high level of CBS. By imposing spatio-temporal constraints on the root node, the proposed OCBS method can better adapt to various variant algorithms. Then, the optimality of the path planning of the proposed method in the grid environment is theoretically analyzed. Finally, the effectiveness of the proposed method is verified by simulation result.