# Late Line-of-Sight Check and Prioritized Trees for Path Planning
## 7 Conclusions  
Line-of-Sight Check (LoS-Check) is efficient for any-angle path planning, which has been successfully used in Theta*. In the high-dimensional environment, there will be too many LoS-Checks in Theta*, which may cost much computation. Lazy Theta* introduces delayed evaluation into Theta*, reducing the LoS-Check amount obviously. Inspired by Lazy Theta*, we presented Late LoS-Check A* (LLA*) to further delay the LoS-Check and update the g value of different successor vertices with discrimination, which is different from Lazy Theta* or Theta*. If we just delayed LoS-Check, the path planned by LLA* would never be shorter than that of Lazy Theta*. Therefore, the key of LLA* was introducing the discriminatory strategy in LoS-Check operations. It could further reduce the real cost (g value) of the node that is chosen to be extended.  
We implemented LLA* on the basis of a tree structure, and it was especially useful for planning under differential constraints. LoS-Check is performed between two non-adjacent vertices in grid-based path planning, which will cost much time with the map size increasing. LLA* updates the cost of the vertex, which has a better estimation of the total path cost, and this is based on the structure of prioritized trees. LLA* is not strictly optimal, but truly results in a shorter path than A* and Lazy Theta*. The experiment showed that LLA* ran faster and planned a shorter path than Lazy  
\begin{table}
\begin{tabular}{c c c c c} \hline \hline  & **A*** & **Theta* & **Lazy Theta* & **LLA* \\ \hline states & 3654 & 3616 & 3615 & 3592 \\ LoS-Check & 0 & 8114 & 3545 & 3478 \\ simple-check & 10232 & 4080 & 10161 & 9747 \\ path cost & 281.75 & **274.31** & 274.63 & **274.58** \\ time (ms) & 2.639 & 4.218 & 2.432 & **2.091** \\ \hline \hline \end{tabular}
\end{table}
Table 4: Planning results of the maze test #2.  
Theta*; furthermore, the path planned by LLA* was just slightly longer than that of Theta*, while costing less time. The algorithms in this paper was integrated in the Open Motion Planning Library (OMPL), which could be used in practice.  
Our future work will be focused on optimal planning algorithms and multi-agent path planning. In addition, we will improve the LLA* algorithm and apply it to nonholonomic path planning as well. This paper gives an attempt to employ LoS-Check with discriminatory updating in the grid-based A* algorithm, and it could be applied in other 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.  
Conceptualization, C.Z. and Y.T.; methodology, C.Z.; writing-original draft preparation, C.Z.; writing-review and editing, Y.T.; supervision, H.L.; project administration, L.Z.  
This research was funded by the National Natural Science Foundation of China under Grant 61602496.  
We would like to thank the developers of the Open Motion Planning Library (OMPL) for their open source codes and benchmark scenarios.  
The authors declare no conflict of interest.  
The following abbreviations are used in this manuscript:  
Los-Check Line-of-Sight Check  
LLA* Late LoS-Check A*  
RRT Rapidly-exploring Random Tree  
PRM Probabilistic Road Map  
APF Artificial Potential Field  
RL Reinforcement Learning  
MDP Markov Decision Process  
DRL Deep Reinforcement Learning  
DQN Deep Q-Network  
VIN Value Iteration Network  
VPN Value Prediction Network  
PST Precomputed Search Trees  
RTS Real-Time Strategy  
FMT* Fast Marching Trees  
LBT-RRT Lower Bound Tree-RRT  
BIT* Batch Informed Trees  
LPA* Lifelong Planning A*  
OMPL Open Motion Planning Library  
WA* Weighted A*  
LoSS Line-of-Sight Slider  
ROS Robot Operating System