# Improved Analytic Expansions in Hybrid A-Star Path Planning for Non-Holonomic Robots
## 3 An Improved Method
### Experiments in Benchmark Maps  
In this section, the workspace is standard 2-D grid benchmark maps in common sources [28,29]. We use three different benchmark maps, _map12_, _den520d_ and _ost003d_, with the size of \(433\times 541\) pixel, \(1000\times 1000\) pixel, and \(1000\times 1000\) pixel, respectively. These three benchmark maps are re-scaled to maximum 128 pixels per dimension with a resolution of 1 m per pixel. Figures 8a, 9a and 10a show full routes obtained by the improved method in the three benchmark maps. To see clearly the improved paths, we zoom in parts of the forward search phase (blue lines) before tunings and parts of the improved RS paths (green lines) as shown in Figures 8c,e, 9c,e and 10c,e. The corresponding sections of the forward search phase after tunings and the original RS paths are arranged in Figures 8b,d, 9b,d and 10b,d to compare between them.  
Figure 8: Improved hybrid A-star in a benchmark map _map12_. (**a**) Improved hybrid A-star. (**b**) Before tunings. (**c**) After tunings. (**d**) Original RS path. (**e**) Improved RS path.  
Figure 7: Tuning the improved hybrid A-star path planning. (**a**) Grid map A. (**b**) Grid map B.  
As it can be seen from the data in Table 2, a smaller curvature value is chosen in both cases in the improved RS path. Consequently, the cost of risk of the improved RS path is reduced by 24% in _map12_ and 10% in map _den520d_ compared to the original RS path in the hybrid A-star algorithm. The RS paths generated by bigger curvatures in Figures 8d, 9d and 10d are closer to obstacles than those generated by smaller curvatures in Figures 8e, 9e and 10e. On the other hand, the lengths of the RS paths in the improved method are not always shorter than those in the original method when safety is preferentially considered (there are no significant differences in lengths). This result is consistent with the properties of RS curves, as presented in Section 3. However, the computation time is a drawback of this method, and more time is required to compute RS paths as curvature resolution increases. The reason is that the original method produces only RS curves using extreme curvature values. Whereas the proposed method needs to generate multiple RS curves in curvature range with some step size. Therefore, the computation time increases at most linearly proportional to the step size of the curvature. And by the fine-tuning, we reduce the motion primitives, which means the discretization of x and y axes increases, respectively, so that the computation time increases proportionally. Another noticeable point is the number of turning points reduced from 12 to 10, 12 to 9, and 6 to 5  
Figure 10: Improved hybrid A-star in a benchmark map _ost003d_. (**a**) Improved hybrid A-star. (**b**) Before tunings. (**c**) After tunings. (**d**) Original RS path. (**e**) Improved RS path.  
Figure 9: Improved hybrid A-star in a benchmark map _den520d_. (**a**) Improved hybrid A-star. (**b**) Before tunings. (**c**) After tunings. (**d**) Original RS path. (**e**) Improved RS path.  
after tunings in the three maps (see Figures 8b,c, 9b,c and 10b,c). These paths nearly do not have unnecessary turning points and keep a comfortable distance from obstacles. In summary, in terms of safety criteria, the results indicate that the improved method can reduce the risk of collision and select a safer path to the destination.