# Mobile Robot Path Planning Considering Obstacle Gap Features
## 2 Path Planning Method with Clearance Characteristics
### Global Path Planning Based on Gap Map
#### 2.1.1 The Improvement of Heuristic Function  
As it is difficult to judge whether the current optimal cost is a feasible path, too many edge points far from the target path will be retrieved in the search process of the A* algorithm. If the estimated value of the heuristic function is less than the actual cost value, the optimal path can be obtained, but there will be too many search nodes, which reduces the efficiency. On the contrary, if the estimated value of the heuristic function is larger than the actual cost value, it will be difficult to obtain the optimal path, but fewer nodes will be searched. And the highest search efficiency is achieved when the estimated value of the heuristic function is equal to the actual cost value. Since the Euclidean distance is adopted by the heuristic function for judging, the role of the heuristic function at this time is only to provide the search algorithm with an estimated optimal path cost and in order to guide the search process to select the most promising nodes for expansion. However, based only on the straight-line distance between two points and ignoring the obstacles or any other constraints, the A* algorithm tends to explore the path directly connected to the target node first to speed up the search process in some cases. However, the Euclidean distance may overestimate the cost of the actual path when there are obstacles or unwalkable areas. That may cause the A* algorithm to choose to scale through the path of the obstacle instead of a longer path around the obstacle, and the resulting generated path could not meet the practical feasibility requirements. Meanwhile, more nodes may be expanded by the A* algorithm, thus increasing the computational overhead. In some cases, a more precise heuristic function may guide the search better and reduce unnecessary node expansion. Based on the above, the Chebyshev distance is introduced in this study to provide a more accurate path cost estimation and a variable weight heuristic function is designed  
Figure 1: Global Map and Global Map of Obstacle Gaps (**a**) Global Map; (**b**) Global Map of Obstacle Gaps. for the computational complexity problem to reduce the search nodes while ensuring the effectiveness of the cost of the heuristic function. The heuristic function [20] is shown as Equation (1), the Euclidean distance [21] as Equation (2), and the Chebyshev distance [22] as Equation (3). \[h(n)=h_{1}(n)+h_{2}(n) \tag{1}\]  
\[h_{1}(n)=\sqrt{(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}} \tag{2}\]  
\[h_{2}(n)=\frac{max(|x_{2}-x_{1}|,|y_{2}-y_{1}|)}{2} \tag{3}\]  
At the same time, the weight of \(h(n)\) should be adjusted timely to improve efficiency. And the estimated value will approach the actual value gradually as the current point approaches the target. In order to increase the accuracy and reliability of the search and avoid the failure of finding the optimal path due to the excessive estimate, the estimated value is weighted also. In summary, the improved cost function is shown in Equation (4). \[f(n)=g(n)+(1+\frac{r}{R})h(n) \tag{4}\]  
where, \(r\) is the distance between the robot and the middle point of the obstacle gap, and \(R\) is the distance between the robot and the target point. The final design of the heuristic function for the A* algorithm is given by Equation (5), as follows:  
\[f(n)=g(n)+(1+\frac{r}{R})h(n) \tag{5}\]  
By introducing the dynamic weighting factor \(w\), the heuristic factor can be strengthened. When the heuristic factor is too large, the shortest path may not be found. And if the heuristic factor is too small, the A* algorithm will degenerate into the Dijkstra algorithm, which takes too long. At the same time, the heuristic value of \(h(n)\) will bring negative effects when there are too many passable gaps. And only if the count of passable gaps is small, the heuristic value of \(h(n)\) can be increased to avoid searching redundant grids and enhance the efficiency of the overall pathfinding process.