# UAV Swarm Real-Time Rerouting by Edge Computing D* Lie Algorithm
## 2 Methods and Materials
### Optimum Path Programming  
Unmanned vehicle mission target points were randomly assigned. A lack of a trajectory plan will lead to inefficient task performance and an increased workload. The system's route planning algorithm addresses this issue by planning multiple paths and selecting the optimal route. Figure 6 shows a single-path (single UAV) solution, while Figure 7 shows a multi-path (three UAVs) solution. In Figure 7, although a set of optimized paths with minimum distance without touching the no-fly zone is generated, it is obvious that an unexpected obstacle (a tree) still lies on the red path. This is also one of the problems that this research aims to solve.  
In 2017, the Autonomous Unmanned Vehicles Laboratory (AUV Lab) at National Formosa University (NFU) completed the multi-vehicle path planning algorithm [14], combining the rules and principles of the tabu search method, the 2-Opt exchange method, and the A* search method to multi-load the multi-traveling salesperson problem with performance that exceeded the traveling salesman problem library (TSPLIB) in terms of convergence effect. However, only the avoidance distance of a single UAV is considered when avoiding the restricted navigation zone; thus, in performing group tasks, it is impossible to effectively prevent wingman drones from crossing into the restricted navigation zone. The 2019 version of the Mission Planner ground guidance station developed by AUV Lab was successfully applied for the path planning of drone groups, using various wireless data transmission modules to simultaneously issue control commands to multiple vehicles, with feasibility verified using five UAVs [15]. The star-shaped topology established by the ground control system, combined with wireless communication transmission, allows the drone cluster to be controlled for path-planning tasks. This task mode has had a profound impact on this research, but because the task is completely reliant on ground-based guidance and control, drones are still restricted from performing many tasks.  
Changing the control architecture allows drones to perform tasks autonomously. When encountering obstacles while flying in an unknown environment, drone flights are  
Figure 6: Single-route solution.  
Figure 7: Multi-route solution.  
divided into two phases using the real-time mission path. The first phase is the group path controlled by the ground station. Planning includes two algorithms: the tabu algorithm for group UAV path planning and the A* search algorithm for no-fly zone avoidance. The second stage is autonomous task execution and real-time path redrawing, so that the UAV can complete the task autonomously in an uncertain task environment without relying on the ground station, using the D* Lite search algorithm to redraw the task path in real time based on the received obstacle information and achieve avoidance. Then, according to the rotorcraft action mode, the D* Lite algorithm's moving method is modified to allow the dynamic programming algorithm to be reasonably applied to the drone mission in the real environment. The D* Lite dynamic programming algorithm flow is shown in Figure 8.