Conflict-Free 3D Path Planning for Multi-UAV Based on Jump Point Search and Incremental Update

To address the challenges of frequent path conflicts and prolonged computation times in path planning for large-scale multi-UAV operations within urban low-altitude airspace, this study proposes a conflict-free path planning method integrating 3D Jump Point Search (JPS) and an incremental update mechanism. A hierarchical algorithmic architecture is employed: the lower level utilizes the 3D-JPS algorithm for efficient single-UAV path planning, while the upper level implements a conflict detection and resolution mechanism based on a dual-objective cost function and incremental updates for multi-UAV coordination. Large-scale UAV path planning simulations were conducted using a 3D grid model representing urban low-altitude airspace, with performance comparisons made against traditional methods. The results demonstrate that the proposed algorithm significantly reduces the number of path search nodes and exhibits superior computational efficiency for large-scale UAV path planning. Specifically, under high-density scenarios of 120 UAVs per square kilometer, the proposed DOCBS + IJPS method can reduce the conflict-free path planning time by 35.56% compared to the traditional CBS + A* conflict search and resolution algorithm.