# Late Line-of-Sight Check and Prioritized Trees for Path Planning
## 4 LLA* with Prioritized Trees
It can be foreseen that the successors of \(v_{5}\) may be extended with priority compared to the successors of \(v_{4}\) and \(v_{6}\), which will speed up the planning. Figure 3: The planning process of LLA\({}^{\star}\) (\(v_{5}\) is to be extended). Firstly, perform LoS-Check between \(v_{3}\) (parent of \(v_{5}\)) and \(v_{start}\) (grandparent of \(v_{3}\)). Then, use the updated \(g(v_{3})\) to only update \(g(v_{5})\), making \(g(v_{5})\) even less than \(g(v_{4})\) and \(g(v_{6})\). In Section 3, we mentioned that A* algorithm is both resolution complete and resolution optimal, which means that it could find the optimal path on the grids. However, A* cannot find the real shortest path because the path is constrained to the grid edges. Meanwhile, LoS-Check connects two non-adjacent vertices, which could relax the constraints to grid edges and finally generate shorter paths. Theta* employs LoS-Check, and it could find shorter paths than A*, but it is not optimal. If we want to find the optimal solution in a graph, it is necessary to guarantee that the solution cost estimate (i.e., the \(f\) value) from a parent to its child state must be monotonically increasing [34]. Thus, the expansion of the new state should be based on the monotone condition, which ensures that the final path is optimal upon the given graph. The \(g\) value of states in the Theta* algorithm may be decreased, which does not satisfy the monotone condition. Thus, Theta* is not optimal. The Lazy Theta* and LLA* algorithms are both variants of Theta*, which are not optimal either. However, \"non-optimal\" does not mean that the algorithm cannot generate shorter paths. The key idea of LLA* is further delaying the LoS-Check operation of a vertex until its successor expands and discriminatively updates the \(g\) values. LLA* is complete and could always find better paths than A*. For example, in each iteration, with the help of LoS-Check, LLA* will result in a smaller cost for the current state (the state that is chosen to expand new states) when compared with A*. Then, the original state with the least \(f\) value in the _open_ list of A* will now get an even smaller cost in LLA*. LLA* does not change the framework of A*, and the worst case for LLA* is degrading into A*. In fact, LoS-Check is a greedy strategy; it connects two states if the path cost could become smaller. However, in some extreme conditions, such as the corner of the blocked cells, LoS-Check will not work because the line-of-sight is blocked by the obstacles [2]. LLA* reduces the amount of LoS-Check, which gains a trade-off between the execution time and path length. LoS-Check is a kind of long-distance collision detection, which will cost a longer time than the simple check. LLA* employs less LoS-Check than Theta* and Lazy Theta*, so it runs faster. Because of less LoS-Check, LLA* employs a weaker greedy strategy to some degree, which will not be trapped in the extreme conditions at the obstacle corner. Thus, LLA* could find better paths than Lazy Theta* on average and even find better paths than Theta* sometimes (we will show an example in Figure 6). Moreover, the discriminatory updating used in the LLA* algorithm is also a kind of greedy strategy, and it truly works. After LoS-Check, LLA* only updates the \(g\) value of the successor state, which has the potential to generate better solutions. This operation could accelerate the planning procedure, and the worst case is degrading into searching paths as A* does. In other words, if the greedy search methods fail, LLA* will still search the paths like A*. Therefore, the LLA* algorithm will run faster than A* on average.