# UAV Swarm Real-Time Rerouting by Edge Computing D* Lie Algorithm
## 2 Methods and Materials
### Dynamic Avoidance Algorithm  
In 2012, [PERSON] and [PERSON] [18] proposed a method that included both static and dynamic path planning methods, using the D* Lite calculus to allow multiple robots to avoid obstacles and reach the endpoint in a custom obstacle map. Although this task does not consider the traveling salesman problem of multiple target points, and the realization result is limited to simulation, it provides important inspiration for research on dynamic avoidance methods.  
D* Lite (Dynamic A* Lite) was developed by integrating the characteristics of lifelong planning A* and D*. The D* algorithm was re-implemented based on the LPA* algorithm. D* Lite has a high movement cost when the environment changes. The estimated function uses a starting point, a fixed target point, and a reverse direction search, constantly updating the current position to the new starting point to re-estimate the true vehicle movement cost of the vehicle to obtain a better path solution.  
In this study, the D* Lite search algorithm was also used in dynamic obstacle avoidance path planning. However, to apply the D* Lite algorithm to multiple quadcopter drones cooperating in a single task after group route planning, this study modified the traditional D* Lite to meet certain conditions. First, the movement method in the algorithm must be matched by the drone's actions. Latitudes and longitudes are used directly as the map coordinate system. If the original D* Lite is used to find the next point to generate the movement path, the computational loading of the edge device will greatly increase due to the excessive latitude and longitude coordinates. Due to the hardware limitations of the flight control board, the UAV will clearly decelerate when passing the target point in the guided mode, and excessive moving point density will unacceptably slow the UAV's flying speed. Therefore, this study referred to the vehicle movement mode along the obstacle apex in the D* Lite algorithm. As proposed by [PERSON] et al. in 2020, this study used the D* Lite algorithm to provide a shorter path that is more suitable for UAV applications [19]. Its characteristic is to change the vehicle's movement such that the vehicle is no longer limited to movement in eight directions but can move from any angle to the obstacle apex at the lowest cost. While avoiding the obstacle, it also avoids excessive turning points in the route, making it suitable for use in rotorcraft that cannot sustain excessive yaw movement. Combined with the method of expanding the no-fly zone to produce turning points and thus avoid restricted areas, this allows the UAVs to identify obstacles during mission execution, and complete avoidance along the obstacle apex, as shown in Figure 9.  
The improved D* Lite algorithm is applied to each drone flying along the mission route. Each drone uses received obstacle information and known information to identify obstacles blocking the route to the target point. This dynamic route planning allows the UAV to reach the target point smoothly. The algorithm flow chart is shown in Figure 10.