# Safe Path Planning of Mobile Robot Based on Improved A* Algorithm in Complex Terrains
## 3 Improvement of A* Algorithm
### Performance Analysis of the Improved A* algorithm  
To analyze the improvement effect, we applied the method proposed in [PERSON]. [PERSON] et al. (2016) to search for the optimal path in the same environment. Risk zones around the vehicle were established to keep the path away from obstacles. The vehicle was assumed to be point-size and occupied only one state at a time. The risk zones around the vehicle consisted of three zones, as shown in Figure 8a. The function of the risk zones is presented as follows.  
\[Risk(q)=\left\{\begin{array}{ll}1.6,&\quad\quad\quad\quad if\ Collision(zone_{1})\\ 1.4,&\quad\quad\quad if\ Collision(zone_{2})\\ 1.2,&\quad\quad\quad if\ Collision(zone_{3})\\ 1,&\quad\quad if\ not\ Collision(any\ zone)\end{array}\right.q=[x,y,\psi]^{T} \tag{6}\]  
For the RRT* algorithm (Please find additional detail in [PERSON] et al. (2016)), the radius of the set _Xnear_ of vertices is eight, the parameter \(\eta\) of the function _Steer_ is set to two, and the number of iterations is set to 1000. Because of the random nature of the sampling process, the improved RRT* algorithm planned different paths each time. Large amounts of simulation were executed and the optimal path we obtained is shown in Figure 8b.  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Path** & **Path** & **Turning** & **Sum of Turning** & **Length of** & **Length of** \\  & **Length (m)** & **Times (Times)** & **Angles (Degree)** & **Risky Path (m)** & **Dangerous Path (m)** \\ \hline Before & 70.25 & 12 & 540.0 & 13.31 & 5.24 \\ smoothing & After & 66.49 & 9 & 168.89 & 12.89 & 5.16 \\ smoothing & & & & & \\ \hline \hline \end{tabular}
\end{table}
Table 2: Path comparison before and after smoothing process.  
Figure 8: Planned path of the improved RRT* algorithm: **(a)** Risk zones; **(b)** Planned path.  
Figures 2, 7, and 8b show the paths generated by using the conventional A* algorithm, the improved A* algorithm, and the improved RRT* algorithm, respectively. The performance comparisons of the three algorithms are shown in Table 3.  
Table 3 shows us the comparisons of the conventional A* algorithm, the improved RRT* algorithm and the improved A* algorithm. Compared to the conversional A* algorithm, although the improved A* algorithm increased the path length by 0.5% and computation time by a factor of three, it reduced the turning time and sum of turning angles by 35.7% and 73.2%, respectively. It also reduced the length of the risky and dangerous paths by 69.0% and 83.3%, respectively. Compared to the improved RRT* algorithm, the improved A* algorithm increased the path length and the sum of turning angles by 1.2% and 35.8%, respectively; however, it reduced the turning time by 18.2% and also reduced the length of the risky and dangerous path by 33.0% and 38.9%, respectively. In these simulations, the improved RRT* algorithm produced the shortest path; however, as it needed to check for collision for each sampled configuration and the intermediate steps when connecting to others, the computation time of the improved RRT* algorithm was two orders of magnitude larger than that of the other two algorithms.  
The comparison result shows that, compared to the conventional A* algorithm and the improved RRT* algorithm, the improved A* algorithm can determine a better path for the actual movement of the robot. It also proves the feasibility and effectiveness of the improved A* algorithm.