# Late Line-of-Sight Check and Prioritized Trees for Path Planning
### Related Work and Motivation  
The purpose of this paper is to design an algorithm that can generate better paths within less time, and the relevant techniques include Line-of-Sight Check (LoS-Check), the lazy evaluation strategy, discriminatory updating, and prioritized trees.  
LoS-Check is a kind of path shortcutting method, which is usually performed to validate whether there is a straight connection between two non-adjacent states. LoS-Check is commonly employed in graph-based path planning algorithms, such as Theta*[2] and Lazy Theta*[32], which have been mentioned in the prior subsection. Of course, this kind of online path optimization method is also used widely in sampling-based path planning. The RRT*-Smart[38] algorithm employs LoS-Check and intelligent sampling to accelerate the converging rate and reach a better solution at a faster speed. RRT*-gp[39] uses the LoS-Check to connect new states with their grandparents, which makes the final solution cost converge faster to the optimum. LoS-Check helps the planners generate better solutions at a faster speed, but it could still be improved. There are also many other path optimization methods similar to LoS-Check[40; 41; 42].  
The lazy evaluation strategy has been successfully used to reduce the computation on the collision detection. Collision detection is the bottleneck of the path planning problems, and it will make the solving process become slow, especially in high-dimensional spaces. In fact, some collision detection is not necessary in the planning process, which could be delayed or omitted. Lazy PRM[43] is a variant of PRM[10], which delays the collision detection until it is necessary, and it shows faster speed than PRM. Lazy Theta*[32] is the variant of Theta*[2], which shares a similar strategy as Lazy PRM, and it shows faster speed, especially in 3D grid maps. The Fast Marching Trees (FMT*)[44] algorithm performs the lazy strategy through dynamic programming recursion, which only detects the collision of the state connection that could improve the current solution. Lower Bound Tree-RRT (LBT-RRT)[45] employs the lower bound value to delay the collision detection, which runs faster and generates shorter paths when compared with RRT*. Batch Informed Trees (BIT*)[46] uses a candidate edge queue as a buffer to delay the collision detection of the edges.  
Motivation: LoS-Check is a kind of long-distance collision detection, which enlarges the range of path optimization. However, it will cost much time in high-dimensional spaces. Meanwhile, the lazy evaluation strategy is often used to reduce the collision detection, which could save time. In this paper, we combine LoS-Check with the lazy evaluation strategy on the basis of the A* algorithm and construct a prioritized tree to choose which state should be performed with LoS-Check.  
Moreover, the A* algorithm has many variants, which could use LoS-Check as well. The D*[47] algorithm is the Dynamic version of the A* algorithm and plans the path from the goal state to the start state. D* is applicable in unknown, partially-known, and dynamic environments. The focused D*[48] algorithm is an extension to the D* algorithm, which focuses the re-planning process to decrease the total execution time when the environment changes. Lifelong Planning A* (LPA*)[49] is an incremental search algorithm, and it does not need to be restarted when the environment changes. Thus, LPA* is suitable for a dynamic environment as well. The D* Lite[50] algorithm combines the dynamic feature of the D* algorithm with the incremental search feature of the LPA* algorithm, showing better performance in practice. LoS-Check with discriminatory updating could be employed in the planning process of these variants of A* as well. We hope this kind of discriminatory principle could give some reference and inspiration to peers in the field of robotic planning.