# Global Path Planning for Differential Drive Mobile Robots Based on Improved BSGA* Algorithm
## 2 Materials and Methods
### Procedure of A* Algorithm  
As a heuristic path planning algorithm, the A* algorithm is used to find the optimal path in the static environment [32]. This algorithm searches from the starting point according to the predetermined search strategy, calculates the actual cost of each feasible node around the current node to the starting point and the heuristic cost to the target point, and selects the node with the minimum total cost as the next extended node. The algorithm ends when the extended node is overlapped with the target point [33]. The core of the A* algorithm lies in the cost function, which is as follows:  
\[\mathrm{f}(n)=g(n)+h(n) \tag{4}\]  
where \(f(n)\) represents the total cost from the starting point \((X_{s},Y_{s})\) to the target point \((X_{e},Y_{e})\) through the current point \((X_{n},Y_{n})\); \(g(n)\) represents the actual cost from the starting point \((X_{s},Y_{s})\) to the current point \((X_{n},Y_{n})\); and \(h(n)\) represents the heuristic cost from the current point \((X_{n},Y_{n})\) to the target point \((X_{e},Y_{e})\). The traditional A* algorithm adopts the 4-neighborhood search strategy. Because DDMRs can realize in-place turning, it can be reasonably considered to complete the diagonal movement of the grids. In order to make the path generated by the A* algorithm more realistic, the search neighborhood is extended to 8 neighborhoods, as shown in Figure 3, with 8 turning angles \((0^{\circ},45^{\circ},-45^{\circ},90^{\circ},-90^{\circ},135^{\circ},-135^{ \circ},180^{\circ})\). There are mainly three heuristic functions, in  
Figure 2: Obstacle puffing process. They should be listed as follows: (**a**) Before puffing process; (**b**) After puffing process.  
cluding Euclidean distance function:  
\[h(n)=\sqrt{\left(X_{e}-X_{n}\right)^{2}+\left(Y_{e}-Y_{n}\right)^{2}} \tag{5}\]  
Chebyshev distance function:  
\[h(n)= |X_{e}-X_{n}|+|Y_{e}-Y_{n}| \tag{6}\]  
Manhattan distance function:  
\[h(n)=\max(|X_{e}-X_{n}|,|Y_{e}-Y_{n}|) \tag{7}\]  
For the heuristic function, if \(h(n)\) is the same as the actual cost \(P(n)\) from the \((X_{n},Y_{n})\) to the \((X_{e},Y_{e})\), all nodes extended by the A* algorithm are on the optimal path, it will not expand any remaining unarticulated points, and the search speed is the fastest at this time, but this is difficult to achieve. For the Manhattan distance, its value is often less than \(P(n)\), although the optimal path can be found, the search speed will decrease. For the Chebyshev distance, its value is often greater than \(P(n)\), although it searches faster, there is no guarantee that the optimal path can be found. Since the 8-neighborhood search strategy is adopted in this study, \(h(n)\) obtained by using Euclidean distance is closer to \(P(n)\), which ensures that the search speed can be improved on the basis of finding the optimal path. Therefore, Euclidean distance is adopted as the heuristic function.  
The A* algorithm divides all extended nodes into two sets:  
_OpenList_: Stores all extension nodes to be detected in the search process, and sorts them according to the \(f(n)\).  
_CloseList_: Stores all detected extension nodes in the search process to prevent repeated search.  
On the basis of the above concepts, the steps of the A* algorithm are shown in Figure 4.  
Figure 3: Extended search neighborhood. They should be listed as: **(a)** 4 search neighborhood; **(b)** 8 search neighborhood.