## 2 Related Work  
### Path Planning Methods  
In recent years, great progress has been made in the field of general automatic driving and path planning. Current methods can already plan and process more than 90% of planar moving targets, which can be roughly divided into search-based (for example, A*, Dijkstra and Jump Point Search) [16], sampling-based (for example, RRT, RRT* and S-RRT) [17; 18] and reinforcement Learning-based (such as Q-learning and Monte Carlo) [19; 20] methods. The representative detectors of the three common path planning methods are detailed as follows:  
Figure 1: Illustration of an example. Boxes with red lines and blue block are main scan area. We show path planning result by HDPP (ours), sampling-based methods and search-based methods. Noticeably, the proposed HDPP has generated the least waypoints, also the most efficient in high-dimensional space. In addition, we show comparison before and after optimization in order to clearly see the effect of HDPP’s gradient optimization operation. * Search-based. The research for search-based path planning has been studied broadly (for example, A*, Dijkstra, LPA* etc.) [16; 21; 22; 23]. These algorithms are based on heuristic functions that calculate the prior loss at different locations on the map and thus search for the optimal path; but this is usually a static, flat search. [PERSON] et al. [21] propose a multi-heuristic framework to guide the search along the relevant classes for dynamic inspection. [PERSON] et al. [22] built an efficient, Bezier curve-based approach for the path planning in a dynamic field using a Modified Genetic Algorithm (MGA), which aims to boost the diversity of the generated solutions of the standard GA. [PERSON] et al. [23] present a novel search-based strategy for autonomous graph-based exploration path planning in subterranean environments. These search-based methods break the limitations of being limited to static searches;
* Sampling-based. Similarly to search-based methods, sampling-based path planning also has been widely used (for example, RRT, RRT*, S-RRT) [17; 24; 25; 26; 27; 28]. It uses an incremental method to build a search tree to gradually improve the resolution ability without setting any resolution parameters. This sampling-based strategy has a good effect on dynamic programming. [PERSON] [24] propose a distributional, robust incremental sampling-based method--DR-RRT--for dynamic motion planning under uncertainty. [PERSON] et al. [25] propose a novel framework--PDMP--that uses bijective and differentiable mappings or diffeomorphisms to transform sampling distributions of sampling-based motion planners. Some researchers use multilevel abstractions to solve motion planning problems involving high-dimensional state spaces and develop novel multilevel motion planning algorithms, which are called QRRT* and QMP* [26; 27]. Those algorithms are proved to be probabilistically complete and almost-surely asymptotically optimal. Meanwhile, a learning method based on Monte-Carlo Tree Search is proposed to learn assignment orders for the variable-subsets [28]. The strategy can efficiently compute a set of diverse valid robot configurations for model-switches within sequential manipulation tasks, which are waypoints for subsequent trajectory optimization or sampling-based motion planning algorithms;
* Reinforcement Learning-based. With the development of deep learning, many methods [29; 30; 31; 32; 33] have been proposed for robot's path planning with reinforcement learning strategy (for example, Q-learning, Monte Carlo, DQN, C51, HER etc.). [PERSON] et al. [30] propose a path planning and manipulating approach based on Q-learning, which can drive a cargo ship by itself without requiring any input from human experiences. STAPP [31]--a multi-agent reinforcement learning algorithm is proposed for multi-UAV target assignment and path planning (MUTAPP) based on a multi-agent deep deterministic policy gradient. [PERSON] et al.