# AidA*-RL: Anytime Graph-Based Path Planning with Deep Reinforcement Learning for an Autonomous UAV
## 2 Proposed iADA*-RL Planning Algorithm
### Global Path Planning and Re-Planning iADA* Algorithm  
The first stage in this research involves global path planning and a re-planning focus on developing an efficient path planning algorithm iADA*[12] for a single UAV system. The iADA* algorithm is based on anytime path planning algorithms and can improve the calculation of the path lengths and decrease the frequency with which the path needs to be calculated throughout the search, which makes the algorithm significantly faster. Furthermore, it has a simultaneous re-planning capacity to avoid obstacles, which also reduces the computational time. The iADA* algorithm improves the calculation of the path lengths and decreases the calculating frequency of the path throughout the search, making it significantly faster than the existing anytime dynamic A* (ADA*) algorithm. The algorithm is designed to provide an efficient solution to a complex, dynamic search environment when the locally changes are affected. One of the main features of the iADA* algorithm is allowing the state recalculation during the iteration after the initial path was generated. When there are changes affecting the environment, the algorithm uses a search method for rearranging the states list to reduce the frequency of calculating the path throughout the search. This step makes it significantly faster compared with current algorithms for solving concurrent path planning and re-planning problems. Additionally, new constraints are introduced via creating a virtual wall, in order to prevent the UAV from traveling across complicated obstacles, such as a U-shaped obstacle. Moreover, if necessary, the UAV will not move again on the same grid. The constraint also protects the path from traversing between two obstacles,  
Figure 3: Proposed architecture of the hybrid path planning system. especially when the obstacles are facing each other. The new method's improvements over the original ADA* include the method of cost calculation, search time, and total time to arrive at the goal. The iADA* has an improved feature compared with the current path planning algorithms such as D*Lite, D*Extra Lite, MPGAA*, and ADA* algorithms [12]. Path planning on a random map has demonstrateda successful solution of concurrent path planning and re-planning problems. From the data obtained, iADA* provides an optimum path for the UAV with faster calculation. This algorithm is implemented in the global path planning and re-planning module. The first module provides a pre-planned path that includes a set of waypoints for the initial stage of the mission, a database of fully or partially known static obstacles, and a terrain map. If obstacles are found within the segments that connect the given waypoints, an obstacle-free path that satisfies certain specific optimization criteria, such as a minimum distance, is provided in the form of a waypoint matrix. During execution of the mission, the path following module is responsible for following the pre-planned path. As the path is executed, the RMP system provides current sensor data, and the position and velocity of the UAV to the local planning and collision avoidance module. Pseudo-code for the iADA* path planning algorithm is given in Algorithm 1. ```
1 Begin
2 Function Key(\(s\)):
3 if\((g(s)>\gamma(s))\)then
4 return\([v(s)+\varepsilon\cdot h(s_{\text{i.s.t.