Conflict-based strategy combined integrated optimal conflict avoidance algorithm

摘要

This paper presents a Conflict-Based Strategy - Combined Integrated Optimal Conflict Avoidance (CBS-CIOCA) algorithm for more efficient multi-robot path planning. The algorithm first refines the conflict types in the high-level model of the traditional CBS algorithm and introduces two conflict categories: avoidable conflicts and unavoidable conflicts. Next, the low-level model of the traditional CBS algorithm is improved, transforming the path search process into two distinct algorithms with different focuses. Finally, based on the different conflict categories, two optimized algorithms are proposed: a space-time A* algorithm enhanced by diagonal improvements and a dynamic adaptive space-time A* algorithm incorporating dynamic adaptive factors. Experimental results demonstrate that, compared to the traditional CBS algorithm, the CBS-CIOCA algorithm achieves maximum reductions of 97.37% and 94.99% in time and node expansion, respectively, in both traditional warehouse and fishbone-shaped warehouse environments, as well as 88.37% and 88.41% in a dynamic large-obstacle environment.