## 3 Four-Dimensional Dynamic Cooperative Path Planning Algorithm
### Dynamic Priority RRT* Algorithm
The generation of the cooperative path can be divided into two stages; namely, the planning sequence sequencing and the single machine cooperative path planning. At the same time, it should be noted that the existing priority planning algorithms and their derivative algorithms have not involved in-depth research on the 4D cooperative path planning problem. Therefore, in order to eliminate the impact of considering both time and space cooperation constraints

Figure 16: Time tolerance for all UAVs to reach the goal in the second replanning. on the performance of the algorithm, we uniformly set the cooperation constraints that the path needs to meet in terms of 4D cooperation constraints in comparison with related algorithms to more accurately compare and analyze the performance of the DPRRT* algorithm. In the context of the scenario of cooperative path planning based on the decoupling method, we introduced the prioritized A* algorithm [31], the traditional priority planning algorithm (RPP) [26], and the coupling degree-based heuristic prioritized planning algorithm (CDH-PP) [46] for comparison. This simulation compares the two types of mission scenarios mentioned in Sections 4.2 and 4.3. To fully analyze the performance of the DPRRT* algorithm in both the Normal Scenario and the Complicated Scenario, four algorithms are used for 4D cooperative path planning of three groups of UAVs with different numbers, where the number of UAVs is set as [2,4,6]. In the two scenarios, the starting and goal nodes of all UAVs are randomly generated in the planning space and 30 random problem situations are generated for each scenario. The characteristics of the four comparisons are as follows:

1. The longest running time, the shortest running time, and the median running time of the algorithm (analyzing the computational efficiency and robustness of the algorithm). 2. Compared with the RPP algorithm (the single UAV planning layer uses the RRT* algorithm based on 4D constraints), the acceleration ratio is used to evaluate the impact of different heuristic priority ranking strategies or different underlying algorithms on the cooperative planning algorithm. The formula for calculating the acceleration ratio is \(\frac{t^{RPP}_{i}}{t^{LLO}_{i}}\). Where \(t^{RPP}_{i}\) represents the running time of the RPP algorithm and \(t^{ALG}_{i}\) represents the running time of the comparison algorithm. 3. The ETA time difference is used to evaluate the quality of the path planned by the algorithm. The calculation formula is \(t^{ALG}_{\text{max}ETTA}-t^{ALG}_{\text{min}ETTA}\), where \(t^{ALG}_{\text{max}ETA}\) represents the maximum flight time of the planned path of the four algorithms and \(t^{ALG}_{\text{min}ETA}\) represents the minimum flight time of the planned path of the four algorithms. 4. The success rate can be used to verify the effectiveness of the algorithm. It can be seen from the comparison of the running time in Figure 17 that the median running time of the DPRRT* algorithm is the shortest and the difference between the maximum and minimum running times is relatively small. In addition, DPRRT* has the highest acceleration ratio. The comparison results of DPRRT* with RPP and CDH-PP prove that the heuristic prioritization strategy based on time cooperation constraints is more reasonable, efficient, and robust. In addition, the running time comparison between DPRRT* and Prioritized A* proves that the single machine cooperative path planning algorithm based on 4 DPRRT* in DPRRT* has higher efficiency and stability than the A* algorithm. Since the four algorithms have the ability to find the optimal solution, there is little difference in the ETA. In addition, the four algorithms are decoupled algorithms, so they all have a high success rate. The comparison results of the four algorithms are shown in Figure 6:0

#### 4.4.2 Comparative Simulation and Performance Analysis of the Local Anti-Collision Planning Layer

We simulated the three improvements of the HAPF algorithm and compared them to the classic APF algorithm.