## 5 Autonomous Navigation Technology
### Path Planning
#### 5.2.1 Global Path Planning  
Global path planning means searching an optimal route between the origin and the terminal for the underground intelligent scraper to drive autonomously in a known environment. 1. A* algorithm The A* algorithm is a heuristic search algorithm, which guides and determines the search direction, mainly through an evaluation function [86]. As long as the optimal distance from the node to the target point is determined, an optimal path must be obtained [87]. However, it is necessary to conduct a traversal search around the nodes on the path to optimize the path and save cost, resulting in large calculation amount, poor real-time performance and long operation time. Moreover, as the number of nodes increases, the algorithm search efficiency decreases [12]. In order to improve the efficiency for the optimal path searching and reduce the searching time, [PERSON] et al. [88] used a jumping point search method based on the A* algorithm and introduced the angle evaluation function into the cost function in the A* algorithm. The number of inflection points on the path obtained by the combined method was minimized compared with that by the original A* algorithm and quick optimal path search was achieved with speed faster than that of the traditional A* algorithm. [PERSON] et al. [89] proposed a navigation path planning method for articulating underground LHD based on the improved A* algorithm, through introducing the collision treat cost into the evaluation function, in order to avoid the LHD from scraping the narrow roadway walls. According to the specific requirements of the path planning for unmanned underground LHD, [PERSON] et al. [90] proposed an improved A* algorithm modeled with extended nodes and introduced the collision threat cost into the evaluation function to avoid the scraper from collision onto the tunnel walls. Simulation tests were also conducted and it was verified that the modified A* algorithm method could enhance the search process, improve the safety of the scraper and prevent collisions. 2. Fast Random Search Tree Algorithm The fast search random tree algorithm is an incremental search algorithm based on probability sampled data. The basic idea is to take the starting point of the automatic LHD as the root node of the random tree, then find a tree node closest to the root one and expand a step length. If collision occurs, the node is discarded and a new expanding direction is set randomly from the current tree node to find the next tree node. The cycle is repeated until a new direction is found. The advantages of this method include high search efficiency, strong search ability, wide search range and no specific requirements for the scene. However, it faces the following shortcomings: nonautonomous search, low utilization rate for the evenly allocated random sampling points, irregular and time-consuming planned path and easily falling into dead zones and causing local minima for searches in complex maps [12; 86]. 3. Bioinspired Intelligent Algorithm Compared with traditional algorithms, the advantages of bioinspired intelligent algorithms are mainly reflected in the ability to solve multi-objective optimization problems effectively, anti-interference strongly, obtain the global optimal value quickly without limitation of local optimal value and the initial value, etc. [91]. It can be mainly divided into genetic algorithm, particle swarm algorithm, ant colony algorithm, etc. [85]. 4. Genetic Algorithm Genetic algorithm Genetic algorithm is an intelligent optimized algorithm based on biological genetic evolution theory in nature. It is the mainstream of robot path planning research and has great research prospects [92]. This algorithm shows good compatibility with other intelligent algorithms, attributed to easy improvement and excellent iterative evolution. The method is flexible in search with the generation of initial population and introduction of crossover and mutation operators and also capable for global optimal path determination.