# Late Line-of-Sight Check and Prioritized Trees for Path Planning
## 6 Experiment
### Virtual Scenes  
We implemented the four planners on the basis of the famous motion planning library, OMPL [51]. It provides low-level data structures and modules, such as the state generation and collision detection, which are essential for high-level motion planning algorithms. Moreover, it also collects a known set of benchmark problems for the comparison of different planners. In practice, OMPL could cooperate with ROS (Robot Operating System) [58], which plays an important role in robotic research and industry. Figure 1 shows a classic scene of the piano mover problem. Figure 9 and Figure 11 show the planning trajectories of the four algorithms on the maze map #1 and #2, respectively, and the size of the two maps is 90 \(\times\) 90.  
Table 3 shows several parameters of the planning results of the maze test #1 in Figure 9, including the number of generated states, LoS-Check amount, simple-check amount, path length, and execution time. We did 500-times testing on the maze scenario, and the execution time for each test is shown in Figure 10. The simple-check represents the collision check between two neighbor vertices that are close to each other. Considering that LoS-Check may be performed between two vertices that are far  
Figure 9: The planning results for an animated character using A* (**a**), Theta* (**b**), Lazy Theta* (**c**), and LLA* (**d**) on Maze #1. The extension details and final composite moving trajectories are shown in red color.  
away from each other, the time spent on the simple-check was shorter than that on LoS-Check on average. Therefore, more LoS-Check will cost more execution time, which is what we want to reduce. It is easy to find that LLA* cost the least time to complete the path planning, which was followed by Lazy Theta*, A*, and Theta*. Meanwhile, the path cost of LLA* was shorter than that of A* and Lazy Theta*, but slightly longer than that of Theta*.  
Table 3 shows that Theta* performed LoS-Check 6027 times, while LLA* performed it 2451 times. It is easy to understand that the path cost of LLA* was longer than that of Theta*, but the execution time was the opposite because Theta* performed more LoS-Check operations. Meanwhile, when comparing with Lazy Theta*, LLA* generated fewer states and performed less LoS-Check and simple-check. Therefore, LLA* was faster than Lazy Theta*. However, it is interesting that the path cost of LLA* was also less than that of Lazy Theta*. Moreover, because LLA* performed less simple collision detections than A*, LLA* was slightly faster than A* as well. In brief, LLA* behaved well in both the path length and the planning speed.  
Table 4 shows the results of the maze test #2 in Figure 11. We also did 500-times testing on this maze scenario, and the execution time for each test is shown in Figure 12. The planning results in the maze test #2 were in accord with those in the maze test #1. [PERSON]* was still the fastest among the four planners.  
Figure 10: The execution time of 500 times of the maze test #1 using the four planners. [PERSON]* is the fastest among these planners on average.  
\begin{table}
\begin{tabular}{c c c c c} \hline \hline  & **A*** & **Theta* & **Lazy Theta* & LLA* \\ \hline states & 2831 & 2681 & 2681 & 2676 \\ LoS-Check & 0 & 6027 & 2609 & 2451 \\ simple-check & 8186 & 3133 & 7699 & 7290 \\ path cost & 127.38 & **125.26** & 125.89 & **125.52** \\ time (ms) & 2.335 & 4.191 & 2.240 & **1.779** \\ \hline \hline \end{tabular}
\end{table}
Table 3: Planning results of the maze test #1.  
Figure 11: The planning results for an animated character using A* (**a**), Theta* (**b**), Lazy Theta* (**c**), and LLA* (**d**) on Maze #2. The extension details and final composite moving trajectories are shown in red color.  
Figure 12: The execution time of 500 times of the maze test #2 using the four planners. LLA* is the fastest among these planners on average.