# Path Planning of Underground Robots via Improved A* and Dynamic Window Approach
## 2 Improved A* Algorithm
### Adaptive B-Spline Curve Smoothing  
It can be seen from Figure 4 that the global path planned by the classical A* algorithm is not smooth, and there are many spikes at the inflection point, which may lead to sharp turns and poor dynamic environment adaptability, which is not conducive to the actual movement of mobile robots. Therefore, a smoothing algorithm is needed to smooth the global path. Both B-spline curves and Bezier curves can be used to smooth curves. However, Bezier curve has poor local control ability when dealing with curve smoothing, and it is difficult to express complex routes efficiently through a Bezier curve. Therefore, the B-spline curve is selected to smooth the global path to generate a continuous and smooth road, thereby improving the driving performance of the robot. Set \(n+1\) control points \(P_{0}\), \(P_{1}\), \(P_{2}\), \(\ldots\). These control points are used to define the direction and boundary range of the spline curve. The definition of the \(k\)-order B-spline curve with \(n\) control points is  
\[P(u)=[P_{0}\ P_{1}\ \ldots\ P_{n}] \begin{bmatrix}B_{0,k}(u)\\ B_{1,k}(u)\\ \ldots\\ B_{n,k}(u)\end{bmatrix} \sum_{i=0}^{n}B_{i,k}(u)P_{i} \tag{7}\]  
In the formula, \(B_{i,k}(u)\) is the \(i-th\)\(k\)-order B-spline basis function, corresponding to the control point \(P_{i}\). \(u\) is the independent variable. The two key indicators of B-spline curves are order \(k\) and smoothing factor \(k\). \(k\) defines the degree of polynomial segments. The larger \(k\) is, the smoother the curve is, but the key turning points and details in the path may be lost. Lower \(k\) may lead to more inflection points in the curve. The larger \(s\) makes the curve smoother but may deviate from the original control point, and the smaller \(s\) closely fits the original path, but it is difficult to effectively eliminate noise and small fluctuations. Therefore, how to choose the values of \(k\) and \(s\) is very important for the smoothing effect of B-spline curves. At the same time, if fixed \(k\) and \(s\) are used, then there will be obvious limitations in the diversification path. The path may be too smooth when the path is simple, resulting in deviation and loss of key features; when the path is complex, the smoothness is insufficient, and the turning and fluctuation cannot be effectively eliminated, which affects the coherence and execution efficiency of the path. Therefore, it is necessary to design an adaptive B-spline curve smoothing strategy to dynamically adjust the parameters according to the complexity and characteristics of the path, so that the path can achieve the best smoothing effect in different scenarios. When the path complexity is high, higher parameters are selected to generate smoother and more coherent curves and reduce the turning frequency. Whenthe path complexity is low, the lower parameters are selected to avoid the path deviation caused by excessive smoothing. The flow chart of the adaptive B-spline curve smoothing method is shown in Figure 8.  
This method first needs to verify whether the number of points in the original path is more than four, because the order of the B-spline curve is equal to the degree of the polynomial segment. For \(n-order\) B-spline curves, at least \(n+1\) control points are required. In view of the fact that the minimum 3-order B-spline curve is used in the adaptive smoothing method, and the 3-order B-spline curve requires at least four control points, it is necessary to verify whether the number of original path points is greater than four. Then, four key features are extracted from the original path (path length, mean curvature, fluctuation degree, and direction change rate), and these eigenvalues are normalized to the interval of 0 to 1. The normalized values of the four path features are \(L_{norm}\) (path length), \(C_{norm}\) (mean curvature), \(F_{norm}\) (fluctuation degree), and \(R_{norm}\) (direction change rate), respectively. The corresponding weights are \(w_{L},w_{C},w_{F},w_{R}\), and the sum of their weights is one.