# Research on Lazy Theta+
## 4 Lazy Theta* Algorithm Based on Grid Point Optimization
### Theta* Algorithm  
In order to search for solutions, A* uses a grid-based heuristic method. Researchers have made several tweaks to the A* algorithm to increase its search efficiency, but the current variants still suffer from many issues. Theta* is an improvement of the A* algorithm that takes into account a visual inspection to produce a more accurate route prediction [35].  
As can be seen in Figure 11a, the paths generated by the A* algorithm can only advance in grid units, hence the route that has been planned does not meet the genuine path condition depicted in Figure 11b.  
Equation (20) shows the cost function of the A* algorithm.  
\[f(s)=g(s)+h(s) \tag{20}\]  
In this case, where \(h(s)\) corresponds to the cost estimated from the current node to the target, and \(g(s)\) refers to the path cost from start node \(s_{start}\) to the current one \(s\), the path cost includes the path length cost and threat cost in some threat areas. There are two lists in algorithm A*: _open list_ and _close list_, one to hold the current points and the other to rank the order in which nodes should be extended. The A* algorithm updates \(g(s)\) and the current node \(s\) to the un-extended neighbor \(st\), and updates the parent nodes \(parent(st)\) and \(g(s)\) of \(st\) by comparing the new path while the shortest present one is in effect.  
Similarly, the Theta* algorithm's cost function is conveyed via Equation (20). In contrast to the A* technique, the parent node of the current node in Theta* can be any vertex. The specific calculation steps are described below [36]:  
1. Initialize _open list_ and _close list_; put \(s_{start}\) to _open list_.
2. When the _open list_ is empty, the search cannot determine the shortest route.
3. Choose the smallest node \(f(s)\) in the _open list_ and insert it into the _close list_ and make it the current node.
4. Given a current node \(s\) with a target node \(s_{goal}\), determine the route from the original point to the final destination using \(s\)'s parent node \(parent(s)\), and the search terminates. If s is not the destination node, step 5 is executed.
5. Search the _close list_ with each nearby node \(st\) to \(s\). If \(st\) is in the lists, disregard \(st\). If not, go to step 6.
6. Compute the cost of \(st\), then check the visibility of the \(parent(s)\) and \(st\).
7. When there are two visible points: the route cost of \(s_{start}\rightarrow\cdots\to parent(s)\to s\to st\) is recorded as \(g(st)\), and the path cost of \(s_{start}\rightarrow\cdots\to parent(s)\to st\) is recorded as \(g(parent(s))+g(st)\), where \(g(st)\) is the path cost of \(parent(s)\to st\). If \(g(parent(s))+g(st)\), then check the visibility of the \(parent(s)\) and \(st\).  
Figure 11: Comparison of the expected path of A* algorithm and actual shortest path. (**a**) A* algorithm-based route planning and (**b**) True shortest path.  
\(g^{\prime}(s\prime)<g(s\prime)\), update \(g(s\prime)=g(parent(s))+g^{\prime}(s\prime)\). If \(s\prime\) already appears on the _open list_, update \(s\prime\). If not, add \(s\prime\) to _open list_.
8. There are two points that are not visible. Check whether \(s\prime\) is present already in the _open list_; if so, write down the cost of \(s_{start}\rightarrow\cdots\to s\to s\prime\) as \(g(s)+g^{\prime}(s\prime)\) and the cost of \(s_{start}\rightarrow\cdots\to s\) as \(g(s\prime)\), if \(g(s)+g^{\prime}(s\prime)<g(s\prime)\), \(g(s\prime)=g(s)+g^{\prime}(s\prime)\). Otherwise, add \(s\prime\) to the _open list_.
9. Sort nodes in the _open list_ based on the path cost, and go to step 2.  
According to Figure 12, path 2 uses the A* algorithm from \(s\) to \(s\prime\) and path 1 uses the Theta* algorithm, checking the visibility of \(s\prime\) and \(parent(s)\). It can be observed that path 1 has a lower path cost.