# 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
The Reeds-Shepp curve is a cost-optimized path curve that has been proven to be optimal for nonholonomically constrained robots in a general-purpose environment free from obstacles [31]. During the global path planning, the improved hybrid A* algorithm with Chebyshev distance attempted to generate a Reeds-Shepp curve from the current node to the target node if a node was expanded during the loop search. If such a curve was generated between the two points without encountering any obstacles, the curve would be combined with the result in the closed list to generate the optimal path. The adoption of Reeds-Shepp curve significantly increased the efficiency of the algorithm. The flowchart depicting the final global planning algorithm is presented in Figure 5. Figure 6 shows the pseudocode of the global path planning algorithm in the improved hybrid A* algorithm. Figure 4: Robot motion path diagram in global planning. \[h(x)=\sqrt{\left(x_{n}-x_{g}\right)^{2}+\left(y_{n}-y_{g}\right)^{2}} \tag{5}\]0 Flowchart of global path planning algorithm. input:  
Cumulative cost function \(g(n)\), Heuristic function \(h(n)\), Dynamic weighting coefficient \(w\). Origin state \(S_{i}\), Target point state \(S_{e}\). Child nodes extend the discrete space set \(\{U\}\)  
Output:  
Optimal globally planned path node sequence closed list initialization:  
A matrix set is built to store all nodes to be expanded open list--\(\{S_{i}\}\)  
Build a heuristic function for each node in the map \(\{\)H\(\}\)  
Initializes the cumulative cost function for all nodes g(\(S_{i}\))--\(\{\)O\(\}\)  
Child nodes extend the discrete space set \(\{U\}\)--\(\{u\}\)$\(\{w\}\)  
A collection of adjacent nodes \(\{S\}\)  
Start of algorithm:  
1 While _openlist_ \(\
eq\phi\) do  
2 The F(n) minimum cost node in the open list is displayed  
3 Expand adjacent nodes according to discrete space set  
4 If the target point belongs to a set of adjacent nodes, return closed list; break;  
5 END If  
6 For i=1 to size(closed list) do  
7 if g(\(S_{\mathrm{a}}\))=infinite  
8 Push node \(S_{\mathrm{a}}\) into the closed list  
9 END If  
10 END For  
11 If \(S_{\mathrm{a}}\) can be connected to \(S_{e}\) by a reed-sheep curve  
12 RES=reed-sheep(\(S_{\mathrm{a}}\),\(S_{e}\),\(R_{\mathrm{min}}\))  
13 return {closed list+RES};break; END IF  
End while  
14 Return {s}  
**Figure 6**. Pseudocode of global path planning algorithm. cess [32]. The real-time update of the environment changes (e.g., new obstacles or changes in the existed trajectory) can be realized by the MPC-based local path planning. MPC is a specialized form of control that generates the current control action by solving an open-loop optimal control problem within a finite time horizon [33; 34]. It provides a more adaptive and robust control strategy for mobile robots, ensuring safe and efficient navigation in dynamic environments. In the improved hybrid A* algorithm, the total cost \(f(n)\) of a node n is expressed as \(f(n)=g(n)+h(n)\), where \(g(n)\) and \(h(n)\) are the actual cost from the start of the path to node n and the estimated cost from node n to the goal. Specifically, \(g(n)\) is the stage cost determined by the current state and controlling input, which is calculated using the following formula: \(g(n)=g(\text{parent})+c(\text{parent},\,n)\), where \(g(\text{parent})\) is the actual cost from the start of the path to the parent of node n, and c(parent, n) is the actual cost from the parent to node \(n\). Value \(h(n)\) is the terminal cost according to the predicted future state, and it is obtained by using a heuristic cost estimate function that estimates the cost from node n to the goal. As a result, it can be seen that the optimal control via MPC is directly influenced by \(g(n)\) and \(h(n)\). With regard to Ackermann steering chassis, the MPC is particularly suitable for local path planning because it can effectively handle the nonholonomic constraints that are unique to the chassis.