# Late Line-of-Sight Check and Prioritized Trees for Path Planning  
[PERSON]  
1 College of Computer, National University of Defense Technology, Changsha 410073, China 12 State Key Laboratory of High Performance Computing, National University of Defense Technology, Changsha 410073, China 2  
[PERSON]  
3 Faculty of Engineering, The University of Hong Kong, Hong Kong 999077, China 3  
[PERSON]  
1 College of Computer, National University of Defense Technology, Changsha 410073, China  
Sampling-based planning discretizes the continuous planning domain by randomly sampling the state space, avoiding constructing maps for the entire environment [8]. Therefore, sampling-based planners can generate a feasible path fast, especially in a high-dimensional space. However, the biggest problem of these methods is that they almost cannot find the optimal solution easily, such as RRT [9] and PRM [10]. RRT* [11] is a variant of RRT, and it employs many local rewiring operations to optimize the path. RRT* could asymptotically obtain the optimal solution as the number of iterations increases, but the efficiency is not quite ideal. Sampling-based planners have good performance in robotic manipulation [12] and mobile robots [13]. There are many other kinds of path planning algorithms as well. Artificial Potential Field (APF) [14] is a kind of real-time planner, which divides the planning environment into different fields of forces. The goal position is considered as an attractive field, which guides the agent to move ahead. Meanwhile, the obstacles are described as repulsive fields, which forbid the agent from getting close. The motivation of APF is very easy to understand, and it has many variants. The most important problem of APF is how to avoid being trapped in local minima. Reinforcement Learning (RL) [15] is also a kind of popular technique for path planning. RL-based planning uses the Markov Decision Process (MDP) [16; 17] to construct the model and introduces a reward mechanism. When the agent reaches a good place, it will return a reward. Otherwise, it will get a punishment. The goal of RL is to get the biggest rewards. Value iteration and policy iteration are two main methods to solve MDP [18]. Q-learning [19] is a simple method for agents to learn to act optimally, and it can converge to the optimum action values with probability one because every state in the domain could be visited. Reinforcement learning often uses deep neural networks for feature extraction, which is often called Deep Reinforcement Learning (DRL). Deep Q-Network (DQN) [20] is a representative of the DRL model, which only uses pixels and game scores to play the Atari 2600 games. The Value Iteration Network (VIN) [21] uses a convolutional neural network to approximate the value iteration, and it is shown to generalize better to the new planning domain. The Value Prediction Network (VPN) [22] combines model-free and model-based RL methods, outperforming DQN on several Atari games. These DRL-based methods have been successfully applied in path planning, but a common problem is that they cannot deal with the large scale of maps quickly. How to generate a safe and high-quality path for the robots or animated characters is a popular issue in the path planning problems. A classical scene is moving a 3D model of a piano from one corner to another corner in a room, which is shown in Figure 1. The sampling-based RRT algorithm has been successfully used in the robotic planning and character animation [23]. Meanwhile, the bidirectional version of RRT, which is called RRT-Connect [24], was also applied to generate collision-free motions for the robots. Similarly, the A* algorithm was used to generate realistic motions for moving robots or animated characters, and these motions are abstracted as high-level behaviors [25]. Precomputed Search Trees (PST) [26] is an efficient approach to synthesize motions for animated characters navigating in given environments, and it is faster than A*.