# High-Efficiency Navigation of Nonholonomic Mobile Robots Based on Improved Hybrid A* Algorithm
## 2 Path Planning for Nonholonomic Robots
### Path Planning Based on Improved Hybrid A* Algorithm
#### 2.3.2 Global Path Planning Based on Improved Hybrid A* Algorithm  
Robot path planning consists of global path planning and local path planning. As mentioned before, the processing efficiency of conventional A* algorithm is limited when the areas of the obstacles are complex. Therefore, the hybrid A* algorithm [30] was used for the global path planning. The algorithm improved the specification of the heuristic function and the searching method to achieve better results. For the heuristic search-based path planning, the effectiveness of the heuristic function \(h(x)\) is critical. In  
Figure 2: Robot self-positioning. conventional A* algorithm, \(h(x)\) is usually the Euclidean distance between the two nodes (\(x_{n}\), \(y_{n}\)) and (\(x_{g}\), \(y_{g}\)), as presented in Equation (5). \[h(x)=\sqrt{\left(x_{n}-x_{g}\right)^{2}+\left(y_{n}-y_{g}\right)^{2}} \tag{5}\]  
However, this approach causes the traversal of unnecessary nodes and an increase in the redundancy of the path planning when the distance calculated via \(h(x)\) is smaller than the actual path. To address the limitations of the Euclidean-distance heuristic function, Chebyshev distance \(d_{q}\), which was expressed in Equation (6), was applied. The improved algorithm is presented in Equation (7). \[d_{q}=max\left\{\left|x_{n}-x_{g}\right|,\left|y_{n}-y_{g}\right|\right\} \tag{6}\]  
\[\left(\mathrm{n}\right)=\mathrm{g}(\mathrm{n})+\mathrm{w}\cdot h(\mathrm{n}) \tag{7}\]  
\[\mathrm{w}=\exp\left(\frac{1}{\alpha\mathrm{d}_{n}+\beta}\right) \tag{8}\]  
\[d_{n}=\frac{max\{\left|x_{n}-x_{s}\right|,\left|y_{n}-y_{s}\right|\}}{max\{ \left|x_{g}-x_{s}\right|,\left|y_{g}-y_{s}\right|\}} \tag{9}\]  
Value \(d_{n}\) in Equation (9) is the ratio of the Chebyshev distance from the starting point of the current node to the full Chebyshev distance. Value \(\mathrm{w}\) is the weighting coefficient, which dynamically weights the heuristic function. Values (\(x_{s}\), \(y_{s}\)) are the horizontal and vertical coordinates of the starting point (\(x_{g}\), \(y_{g}\)) are the horizontal and vertical coordinates of the target point, and (\(x_{n}\), \(y_{n}\)) are the horizontal and vertical coordinates of the current node. The weighting coefficient \(\alpha\) (typically 5-9) is used to obtain better results, depending on the distribution of obstacles in the map. The obstacle ratio \(\beta\) represents the proportion of the area occupied by obstacles to the total area of the map. By weighting the heuristic function with the Chebyshev distance (Equation (8)), a balance between planning efficiency and effectiveness can be achieved; it reduced the gap between the heuristic function \(h(x)\) and the actual path length, the number of nodes traversed, and eventually the search time. Figure 3: A virtual map generated via the grid mapping approach: the dark squares are obstacles; yellow and purple squares are the starting and end points, respectively. The smoothing of the path is necessary for the vehicle (the Ackermann-steered mobile platform) and the position of each target point, especially the position of the vehicle at the starting and ending points on the path, which should be appropriately designed in order to minimize the total length of the path. The determination of the position of the vehicle at each point is presented in Figure 4. If the angle formed by a target vertex and its two adjacent points is less than \(90^{\circ}\) (Figure 4), the scheme of entering and exiting the opposite direction with an angular bisector position will be adopted. On the other hand, if the angle is greater than \(90^{\circ}\) (Figure 4), the one-way entry-exit method with the stop position being the vertical line of the angular bisector line will be adopted. This approach allows for smoother movement and efficient transverse of the vehicle. To improve the searching efficiency and meanwhile satisfy the condition of the heuristic function, Reeds-Shepp curve was applied at the end of the global path planning process.