# Late Line-of-Sight Check and Prioritized Trees for Path Planning
## 4 LLA* with Prioritized Trees  
The lazy evaluation strategy in Lazy Theta* reduces LoS-Check greatly, saving much computation. Actually, the delayed strategy was firstly used in Lazy PRM very early [43], which delays the collision detection until it is truly necessary. Lazy Weighted A* [55] also takes the lazy evaluation, which focuses on reducing the number of times checking the expensive-to-evaluate edges. We are inspired by Lazy Theta* and present Late LoS-Check A* (LLA*) to further delay the LoS-Check operation. However, if we only reduce the amount of LoS-Check, the generated path will be longer. Therefore, we introduce the prioritized trees to update discriminatively the \(g\) values of different successors after LoS-Check. The main idea of LLA* (Algorithm 3) has two parts: reducing LoS-Check more and updating the \(g\) value with discrimination. Assume the current vertex is \(v\) and the parent vertex of \(v\) is \(u\). Furthermore, we define the grandparent vertex of \(u\) as \(gp\). To reduce LoS-Check more, we delay the LoS-Check between \(u\) and its grandparent vertex \(gp\) until \(v\) is chosen to be extended. When \(v\) is to be extended, we firstly perform LoS-Check between \(u\) and \(gp\), and if the line-of-sight exists, set \(gp\) as the parent of \(u\). Updating the \(g\) value with discrimination means that we only update the \(g\) value of the current vertex \(v\) with the new \(g(u)\), but not the \(g\) value of every successor of \(u\). As a result, among all the successors of \(u\), vertex \(v\) will own even smaller cost, meaning that the successors of \(v\) will also have the priority to be extended. As shown in Figure 3, when vertex \(v_{5}\) is to be extended, LLA* firstly updates the parent of \(v_{3}\). There exists the line-of-sight between \(v_{3}\) and its grandparent vertex \(v_{start}\), so \(v_{start}\) becomes the parent of \(v_{3}\), and the \(g\) value of \(v_{3}\) is updated. Then, LLA* will just update the \(g\) value of \(v_{5}\) (the only successor of \(v_{3}\) chosen to be extended) and ignore other successors (without updating their \(g\) values). That is to say, the real cost from \(v_{start}\) to \(v_{5}\), which is also denoted as \(g(v_{5})\), will be even smaller than \(g(v_{4})\) and \(g(v_{6})\), being as \(g\) values of other successors of \(v_{3}\). As a result, the successors of \(v_{5}\) may be chosen with priority to be extended, which can speed up the planning toward the goal. Figure 2: The extension processes of Theta* (**left**) and Lazy Theta* (**right**): the dashed lines are line-of-sight paths. Lazy Theta* performs less LoS-Check than Theta*. ```
1\(g(v_{start})\gets 0\); \(\quad\)\(closed\leftarrow\varnothing\); \(\quad\)\(open\leftarrow\varnothing\);
2\(open\).Add(\(v_{start}\), \(g(v_{start})+h(v_{start})\));
3 while\(open\
eq\emptyset\)do
4 current \(\leftarrow\)\(open\).Pop_least(); // pop the vertex with the least \(f\) value
5 pa \(\leftarrow\)\(Parent\)(current)
6 pa \(\leftarrow\) UpdateParent(pa); // late LoS-Check
7\(g\)(current) \(\gets\)\(g\)(pa) + Cost(pa, current) // discriminatory updating
8 if current == goal then
9 return\(path\);
10\(closed\).Add(current);
11 foreach\(v\in\) Succ(current) do
12 if\(v\
otin\)\(closed\)then
13 if\(v\
otin\)\(open\)then
14\(g(v)\leftarrow\infty\);
15\(Parent(v)\leftarrow\) NULL;
16 UpdateNode(\(v\), current);
```  
**Algorithm 3**LLA\({}^{\star}\)  
In facts, Theta\({}^{\star}\) and Lazy Theta\({}^{\star}\) treat different successors of the same vertex equally. For example, in Theta\({}^{\star}\) or Lazy Theta\({}^{\star}\), the set of \(\{v_{4},v_{5},v_{6}\}\) is all the successors of \(v_{3}\), and they get the same \(g\) value from \(v_{3}\). However, in LLA\({}^{\star}\), we want to propagate a smaller \(g\) value from \(v_{3}\) to \(v_{5}\) because \(v_{5}\) has a smaller \(h\) value, which can reduce the total cost more \(f(v_{5})=g(v_{5})+h(v_{5})=g(v_{3})+Cost(v_{3},v_{5})+h(v_{5})\).