# High-Efficiency Navigation of Nonholonomic Mobile Robots Based on Improved Hybrid A* Algorithm
## 4 Results and Discussions  
Figure 11 shows the simulation results of mapping and path planning in MATLAB. The results of the improved hybrid A* algorithm were evaluated and compared to those of the traditional A* algorithm. The obstacle ratios of the maps used in the simulation were 0.2 and 0.3, respectively. The blue lines in the figures represent the paths planned by the conventional A* algorithm, and the red lines stand for those from the improved hybrid A* algorithm. It was found that the conventional A* algorithm searched the concave obstacles by scanning the eight surrounding nodes. This increased the search time and distance and reduced the algorithm's efficiency, although it did not result in the local minimum problem. Moreover, the sharp corners of the paths generated by the conventional A* algorithm were not suitable for nonholonomically constrained Ackermann chassis. In contrast, the path generated by the improved hybrid A* algorithm was shorter and smoother. This significantly reduced the total length of the path as well as the turning radius at the boundary of the obstacles, facilitating the movement of the Ackermann chassis. Figure 12 shows the difference between the A* algorithm and improved algorithm in the simulation experiments. It can be seen that the path charted by the A* algorithm possesses a large corner, displaying a tendency to collide with the boundary of the obstacles. This problem was caused by the algorithm's manner of node expansion in eight directions without considering motion constraints and the actual size of the robot. This makes the A* algorithm unsuitable for actual navigation. Conversely, the path planned by the improved algorithm is notably smoother with a small corner, presenting a more feasible performance than that of the conventional A* algorithm. This is because the application of the Chebyshev distance optimized the node expansion when the transverse angle was larger than 90\({}^{\circ}\). The performance of both algorithms was evaluated using a grid map at the two obstacle ratios. The comparison of the improved algorithm and the traditional algorithm is shown in Figure 13. The values of the average searching length and time consumption of the two algorithms are listed in Tables 3 and 4. The results obtained from the simulation and experiment demonstrate that the improved algorithm is advantageous in the path selection. Specifically, the average searching length with the improved hybrid A* algorithm was about 9% less at both obstacle ratios of 0.2 and 0.3. This is because the improved hybrid A* algorithm avoids the generation of nodes that were generated by the conventional A* algorithm. The smoother path generated via the improved hybrid A* algorithm contributed to the overall increase in the efficiency of the algorithm, which was reflected by the average searching time. As listed in the tables, the average search times using the improved hybrid A* algorithm were 12.62% and 24.5% when the obstacle rates were 0.3 and 0.2, respectively. This indicates the better efficiency of the improved algorithm, but the time reduction became less significant when the obstacle rate was increased. Figure 12: The difference between A* algorithm and improved algorithm in simulation experiments. Figure 14 shows a map of passable and impassable areas and obstacles. In this context, the black regions represent impassable areas and obstacles, whereas the gray regions signify passable areas. The starting point and end point for the comparison experiment remain the same. The path planned by the A* algorithm is shown in Figure 14a, while the path planned by the improved hybrid A* algorithm is shown in Figure 14b. It is evident from the image that the improved hybrid A* algorithm effectively circumvents the robot's entry into concave areas while searching for the optimal path. This approach results in a shorter path length, smoother trajectory, and reduced likelihood of collisions.