# Late Line-of-Sight Check and Prioritized Trees for Path Planning
## 6 Experiment
### Complex Street Test
\begin{table}
\begin{tabular}{c c c c c c c c c c c} \hline \hline  & & & & & & & & & & & \\ \cline{3-10} \multirow{2}{*}{\(\mathbf{\lambda}\)} & \multirow{2}{*}{**Algorithms**} & \multirow{2}{*}{**LoSS**} & \multicolumn{2}{c}{**Game**} & \multicolumn{2}{c}{**Maze**} & \multicolumn{2}{c}{**Random**} & \multicolumn{2}{c}{**Street**} \\ \cline{3-10}  & & & **Length** & **Time** & **Length** & **Time** & **Length** & **Time** & **Length** & **Time** \\ \hline \multirow{6}{*}{0.5} & \multirow{2}{*}{A*} & No & 45.64 & 0.437 & 45.98 & 0.409 & 42.21 & 0.321 & 49.59 & 0.416 \\  & & Yes & 43.35 & 0.455 & 44.14 & 0.432 & 41.03 & 0.344 & 47.15 & 0.434 \\ \cline{2-10}  & \multirow{2}{*}{Theta*} & No & **43.32** & 0.191 & **44.09** & 0.431 & **40.42** & 0.232 & **47.11** & 0.215 \\  & & Yes & 43.32 & 0.202 & 44.06 & 0.446 & 40.36 & 0.248 & 47.11 & 0.226 \\ \cline{2-10}  & \multirow{2}{*}{Lazy Theta*} & No & 43.35 & 0.201 & 44.18 & 0.366 & 40.65 & 0.227 & 47.18 & 0.216 \\  & & Yes & 43.34 & 0.211 & 44.12 & 0.381 & 40.55 & 0.243 & 47.15 & 0.227 \\ \cline{2-10}  & \multirow{2}{*}{LLA*} & No & **43.33** & **0.168** & **44.15** & **0.291** & **40.58** & **0.181** & **47.14** & **0.176** \\  & & Yes & 43.32 & 0.178 & 44.09 & 0.306 & 40.49 & 0.197 & 47.12 & 0.187 \\ \hline \multirow{6}{*}{0.7} & \multirow{2}{*}{A*} & No & 45.76 & 0.074 & 46.73 & 0.161 & 42.92 & 0.069 & 49.93 & 0.084 \\  & & Yes & 43.36 & 0.085 & 44.23 & 0.176 & 41.22 & 0.086 & 47.18 & 0.097 \\ \cline{2-10}  & \multirow{2}{*}{Theta*} & No & **43.38** & 0.101 & **44.31** & 0.214 & **41.60** & 0.078 & **47.25** & 0.112 \\  & & Yes & 43.36 & 0.106 & 44.18 & 0.224 & 41.37 & 0.091 & 47.19 & 0.121 \\ \cline{2-10}  & \multirow{2}{*}{Lazy Theta*} & No & **43.39** & 0.078 & 44.34 & 0.169 & **41.68** & 0.071 & **47.27** & 0.087 \\  & & Yes & 43.36 & 0.084 & 44.21 & 0.179 & 41.42 & 0.082 & 47.21 & 0.095 \\ \hline \multirow{6}{*}{LLA*} & No & **43.39** & **0.071** & **44.33** & **0.141** & **41.68** & **0.064** & **47.27** & **0.078** \\  & & Yes & 43.36 & 0.076 & 44.20 & 0.151 & 41.43 & 0.076 & 47.21 & 0.086 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Cont. \begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline \multirow{2}{*}{**Complex Street Test**} & \multicolumn{6}{c}{**City**} \\ \cline{2-9}  & & **Berlin** & **Boston** & **London** & **Milan** & **Moscow** & **Paris** \\ \hline \multirow{6}{*}{A\({}^{*}\)} & Length & 1456.95 & 1465.51 & 1640.66 & 1395.68 & 1110.97 & 1462.37 \\ \cline{2-9}  & Time (s) & 0.116 & 0.137 & 0.142 & 0.075 & 0.106 & 0.062 \\ \cline{2-9}  & LoS-Check & 0 & 0 & 0 & 0 & 0 \\ \hline \multirow{6}{*}{\(\text{Theta}^{*}\)} & Length & **1377.12** & **1416.24** & **1563.75** & **1308.36** & **1056.04** & **1402.11** \\ \cline{2-9}  & Time (s) & 0.269 & 0.276 & 0.301 & 0.138 & 0.183 & 0.097 \\ \cline{2-9}  & LoS-Check & 20240 & 21766 & 27027 & 12561 & 17841 & 8714 \\ \cline{2-9}  & Length & 1389.07 & 1428.86 & 1593.02 & 1312.56 & 1063.10 & 1407.96 \\ \cline{2-9}  & Time (s) & 0.134 & 0.153 & 0.179 & 0.076 & 0.102 & 0.061 \\ \cline{2-9}  & LoS-Check & 3044 & 3156 & 3752 & 1679 & 2476 & 1369 \\ \hline \multirow{6}{*}{\(\text{LLA}^{*}\)} & Length & **1381.41** & **1418.19** & **1573.08** & **1306.33** & **1057.57** & **1401.32** \\ \cline{2-9}  & Time (s) & **0.112** & **0.106** & **0.131** & **0.062** & **0.076** & **0.045** \\ \cline{2-9}  & LoS-Check & **2347** & **2136** & **2628** & **1314** & **1737** & **958** \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Path planning results on six complex street maps. Figure 8: The path planning results using the LLA\({}^{*}\) algorithm on six complex street maps. These street maps were chosen from the benchmark maps in Section 6.1, and they are thumbnails of the real streets in six different cities. The size of these maps is 1024 \(\times\) 1024. The start position and goal position are both set at some narrow corners, making the planning task more difficult to solve. The final paths are shown as orange solid lines.