# Research on Lazy Theta+
## 4 Lazy Theta* Algorithm Based on Grid Point Optimization
### Grid Point-Based Lazy Theta* Algorithm  
Based upon the Theta* algorithm, the Lazy Theta* algorithm is enhanced, reducing unnecessary visibility calculations; i.e., it directly judges that \(s\prime\) is visible to \(parent(s)\), and puts it directly in \(open\ list\). When \(s\prime\) is removed from the _open list_ for expansion, check the visibility of \(s\prime\) with the \(parent(s)\). If it is visible, the next neighboring point will be located. Otherwise, it looks for a neighboring parent node in the _close list_[37].  
A* can swiftly compute a route associated to a grid edge; in many cases, the planned route is constrained by the form of the grid. However, the Theta* algorithm can design a route at any angle [38]. However, there is a cap on the possible routes between nodes because of the number of vertices in the square grid. Therefore, grid point-based route planning may not only enhance the accuracy of planned routes and enable better danger avoidance, but it can also expand the range of aircrafts and give a more practical method for planning better routes.  
Lazy Theta* grid path planning is shown in Figure 13a. If the aircraft makes a turn when it hits an obstruction while it is still within the red zone, it will crash into the black circle. Figure 13b depicts the grid environment at level \(N\)= 2 and then employs the Lazy Theta* algorithm to plan the path. The pilot completes the steering of the aircraft before striking the red barrier. This avoids obstacles and collisions. There are also more paths to choose from that are closer to the true flight path.  
After a grid point Lazy Theta* has been designed, the previous grid's vertex are replaced with grid points, and the visibility of the \(parent(p)\) and the neighboring grid point \(p\prime\) is checked if the present grid point \(p\) is expanded. If they are visible to each other, the route keeps growing using \(p\prime\) as the present grid point until it reaches the desired grid point [39; 40].  
It is common practice to use the distance between the starting and ending grid points as a proxy for the projected cost involved in moving from one grid point to another. When the moving distance of the aircraft is short, combined with the characteristics of the grid point, we use the heuristic function given by [PERSON] [41], which is written as:  
\[h(s)=\sqrt{\left(x_{goal}-x_{i}\right)^{2}+\left(y_{goal}-y_{i}\right)^{2}+ \left(z_{goal}-z_{i}\right)^{2}} \tag{21}\]  
Figure 12: A* Algorithm and Theta* Algorithmic Planning Path Comparison.  
where \((x_{goal},y_{goal},z_{goal})\) are the destination point coordinates and \((x_{i},y_{i},z_{i})\) are the current point coordinates.  
When the aircraft is far away from the target point, affected by the curvature of the earth, the calculation of the straight-line distance between the two points is no longer applicable. At this time, the Haversive distance is used as the heuristic function, which is written as:  
\[hav(\frac{d}{R})=hav(\varphi_{2}-\varphi_{1})+\cos(\varphi_{1})\cos(\varphi_{2 })hav(\lambda_{2}-\lambda_{1}) \tag{22}\]  
In Equation (22), \(d\) represents the distance between two places, \(R\) is the radius of the earth, and \((\varphi_{1},\lambda_{1})\) and \((\varphi_{2},\lambda_{2})\) are the latitude and longitude coordinates of two points, respectively. The Haversive distance allows you to calculate the distance between two latitude and longitude coordinates, suitable for long flight distances.