Efficient Multi-UAV Path Planning Using Locally Refinable Channel Graph in Cluttered Environments

In multi-unmanned-aerial-vehicle (UAV) collaborative task scenarios, congestion in cluttered environments significantly hinder operational efficiency, leading to the multi-UAV path planning problem. To reduce the scale of the search space while ensuring the quality of the planned paths, this paper proposes a locally refinable channel graph (LRCG) model to describe the accessible region of the occupancy grid maps, aiming to address the issue of large search spaces adversely affecting planning efficiency. As the basic element of the LRCG, the channel edge represents the local accessible region in the form of an intersecting circle sequence, and can be expanded into multiple collision-free sub-paths in a targeted manner. An LRCG hybrid conflict-based search (LRCG-HCBS) algorithm is proposed to refine the LRCG oriented to conflicts and plan a set of initial collision-free paths. Further, this paper designs a post-processing optimization algorithm for a single path, a constrained dynamic programming search (CDPS) algorithm, which is also employed for the preprocessing refinement of the LRCG. Simulation results show that, compared with existing algorithms, the LRCG-based planning algorithm proposed in this paper demonstrates higher computational efficiency.