# Safe Path Planning of Mobile Robot Based on Improved A* Algorithm in Complex Terrains
## 1 Introduction  
Path planning is one of the fundamental problems in robotics [1; 2]. It is typically defined as finding a sequence of state transitions for a robot from its initial state to some desired goal state. According to the information of obstacles, the working environment of a robot can be categorized as a completely known environment, a partially known environment, a completely unknown environment, and a dynamic environment [3]. The planned path of the robot can be evaluated according to path length, movement time, energy consumption, or risk level [4; 5]. There have been numerous algorithms proposed for path planning of intelligent robots and navigational objects [6], such as the probabilistic roadmap method (PRM) [7], the rapidly exploring random trees algorithm (RRT) [8], the expansive space trees algorithm (EST) [9], the rapidly exploring random trees star (RRT*) algorithm [10], the artificial potential field method (APF) [11; 12], the model predictive control method (MPC) [13], fuzzy logic approach [14; 15], the artificial neural networks algorithm (ANN) [16], the genetic algorithm (GA) [17], ant colony optimization (ACO) [18; 19], particle swarm optimization (PSO) [20], and other new nature-inspired meta-heuristic algorithms [21; 22]. Compared to these algorithms, A* algorithm has been widely investigated and applied because of its advantages such as its simple principle, easy realization, high efficiency, and its ability to find the optimal solution. To further increase the applicability of A* algorithm, many scholars have improved the conventional A* algorithm. First, the evaluation function of A* algorithm has been improved so that the planned path can meet specific requirements [23; 24; 25]. [PERSON] et al. [23]took the distance and direction as two heuristic elements of the evaluation function and solved the problem of non-uniform units by normalization; thus, the search efficiency of A* algorithm was improved. [PERSON] et al. [24] introduced the gravity navigation information into the evaluation function so that the improved A* algorithm could enhance the performance of gravity-aided inertial navigation. [PERSON] et al. [25] took the flight altitude, detected probability, and flight length into consideration to search for the optimal flight path between two waypoints so that the planned path could be a significant distance away from the danger zone. Second, in the path planning process, the grid states to be expanded are selected based on new rules to improve the search's efficacy or the path performance [26; 27; 28]. [PERSON] et al. [26] presented a novel path planning approach called Sparse A* Search; the approach removed the unfeasible search space of the current track point according to the track constraint. As a result, search time was shortened and the memory space was reduced. [PERSON] et al. [27] only selected those neighboring states which satisfy dynamic motion constraints, including maximum turning angle and maximum climb/glide slope angle of the vehicle; thus, the search space was diminished and search efficiency was improved. In [PERSON] et al. [28], the search state was defined as the grid line instead of the grid center; accordingly, the number of searchable neighbor states was extended from eight to infinity. As a result, the planned path was much shorter and the number of turning states was greatly reduced. Third, the path generated by A* algorithm was smoothed to reduce the length, turning times, and turning angle to be more in line with the actual motion requirements of the robot [29; 30; 31]. [PERSON] et al. [29] established a smoothing A* model by traversing all the states on initial path planned by A* algorithm and deleting the states which prolonged the length of initial path as no obstacles existing on the line connected by forward and after states. [PERSON] et al. [30] applied a key optimization process to simplify the global path, which was planned by the conventional A* algorithm, to be connected among a series of key points.