# Late Line-of-Sight Check and Prioritized Trees for Path Planning
## 5 LoS-Slider Smoothing  
The path of A* is often constrained to the grid edges, which looks unrealistic. LoS-Check has been used for post-processing (smoothing) in path planning [56], and it can make the path of A* much shorter. In this paper, we design a smoothing algorithm called Line-of-Sight Slider (LoSS), and this kind of post-processing method will not cost much time.  
According to the moving direction of the current node, the LoSS algorithm is divided into two types: backward-LoSS and forward-LoSS. In a given path, every node has only one parent node and only one successor node. When the current node moves from the goal node to the start node, it is called the backward-LoSS algorithm, and when the current node moves from the start node to the goal node, it is called the forward-LoSS algorithm. When the _current_ node moving direction is determined, its successor node, which is called _child_, and the child's successor, which is called _grandchild_, will be both determined as well. At this time, the _slider_ node recurrently slides from node _grandchild_ to node _child_ by a small stepsize, and LoS-Check is performed between the _slider_ node and the _current_ node each time. When it is successful, stop the _slider_ from sliding, and set the _slider_ node as the successor node of the _current_ node. Subsequently, set the successor of the _current_ node as the new _current_ node for the next round of checking.  
Figure 4 (top) shows the backward-LoSS diagram; the node C is selected as the current node, which moves from the goal node to the start node, with the node B as the child of C and the node A as the grandchild of C. According to the rule of LoSS, the slider node slides from A to B, and after one iteration, the LoS condition between C and slider is satisfied, meaning that this round of smoothing is complete. As a result, the node slider becomes the successor node of C. It can be found that the length of the newly-generated route {A, slider, C} is shorter than that of the original path {A, B, C}. For the forward-LoSS of Figure 4 (bottom), the principle is the same as backward-LoSS, with only the opposite direction. The specific implementation of the LoSS algorithm can be seen in Algorithm 4, which can be used several times to get even shorter paths. In Line 10 of Algorithm 4, the function Slide_From_To(slider, child, stepsize) is based on the linear interpolation of the segment between the slider and child. The parameter stepsize decides the interpolation resolution. The interpolation generates many intermediate points, and the slider will move to these points one by one. The moving direction is set from the grandchild to the child, and the slider will be updated each time. If we set the parameter _stepsize_ as a smaller value, the final smoothed path will have a shorter length.  
Figure 4: Backward-LoSS (top) and forward-LoSS (bottom). The slider node recurrently slides from the grandchild of the current node to the child of the current node by a small stepsize. In backward-LoSS, the current node moves from the goal node to the start node. In forward-LoSS, the current node moves from the start node to the goal node.