# Global Path Planning for Differential Drive Mobile Robots Based on Improved BSGA* Algorithm
## 3 Improved BSGA* Algorithm
### Improved Heuristic Functions
```
1 Initialization
2 Puff up obstacles in the grid map
3 Determine the starting point \((X_{s},Y_{s})\) and target point \((X_{e},Y_{e})\) \((X_{s},Y_{s})\)\(\rightarrow\)\(CloseList\_forward\), \((X_{e},Y_{e})\)\(\rightarrow\)\(CloseList\_backward\), set CloseList_forward\(\_cost=0\), CloseList_backward\(\_cost=0\) \(Child\_nodes\_forward\)\(\rightarrow\)\(OpenList\_forward\), Child_nodes_backward \(\rightarrow\)\(OpenList\_backward\)
6 Flag\(=1\) \(while\)\(=Flag\) If \((Child\_nodes\_forward\)\(\subset\)\(OpenList\_forward)\(\cap\)\((Child\_nodes\_backward\)\(\subset\)\(OpenList\_backward)\(\
eq\)\(1\)
7 Add nodes to the corresponding set Calculate the \(f_{forward}\) of all nodes in \(OpenList\_forward\), \(\min\_n_{f}\)\(\rightarrow\)\(CloseList\_forward\), set \(n_{f}\)\(=\)\(current\_forward\), \(f_{forward}\)\((n_{f})\)\(\rightarrow\)\(CloseList\_forward\) Calculate the \(f_{backward}\) of all nodes in \(OpenList\_backward\), \(\min\_n_{b}\)\(\rightarrow\)\(CloseList\_backward\), set \(n_{b}\)\(=\)\(current\_backward\), \(f_{backward}\)\((n_{b})\)\(\rightarrow\)\(CloseList\_backward\_cost\)
8 ifcurrent_forward \(=\)\(current\_backward\) Flip the elements in \(CloseList\_backward\) and add them to \(CloseList\_forward\)
9 \(Cost\)\(=\)\(CloseList\_forward\_cost(end)+CloseList\_backward\_cost(end)\)
10  Generate the optimal path \(Flag=0\)
11 else
12 Non-obstacle sub-nodes \(current\_forward\)\(\rightarrow\)\(OpenList\_forward\)
13  Non-obstacle sub-nodes \(current\_backward\)\(\rightarrow\)\(OpenList\_backward\)
14 end if
15 endwhile
```  
**Algorithm 1**  
As shown in Figure 7c, the BS structure is introduced to dynamically switch and adjust the starting point and target point in the search process, so that the current node always keeps the trend of being close to the target point. In this process, \(f(n)\) decreases rapidly until the two paths meet and falls to the lowest value. The values of the upper and lower levels of the encounter grids represent the total cost, actual cost, and heuristic cost of forward search and reverse search at this node, respectively. The introduction of the BS structure effectively solves the problem of repeatedly searching nodes when avoiding obstacles and reaching the target point, and improves the efficiency of search. In order to verify the performance of the BSGA* algorithm, as shown in Figures 8-10, the A* algorithm, GA* algorithm, and BSGA* algorithm were executed 50 times on the maps of 10 \(\times\) 10, 20 \(\times\) 20, and 30 \(\times\) 30, respectively. It can be seen that, in the case of large obstacles between the starting point and the target point, the BSGA* algorithm searches fewer nodes compared to the A* algorithm and the GA* algorithm. Figure 8: Performance of A* algorithm with a large area of obstacles: (**a**) Map size is \(10\times 10\). (**b**) Map size is \(20\times 20\). (**c**) Map size is \(30\times 30\). Figure 10: Performance of BSGA* algorithm with a large area of obstacles: (**a**) Map size is \(10\times 10\). (**b**) Map size is \(20\times 20\). (**c**) Map size is \(30\times 30\). Figure 9: Performance of GA* algorithm with a large area of obstacles: (**a**) Map size is \(10\times 10\). (**b**) Map size is \(20\times 20\). (**c**) Map size is \(30\times 30\). According to Table 3, it can be seen that, on the 10 \(\times\) 10 grid map, compared with the A* and GA* algorithms, the calculation time of BSGA* is reduced by 61.44% and 21.04% and the number of search nodes is reduced by 28.13% and 9.80%, respectively, but there is no significant advantage in the total turning angle. On the 20 \(\times\) 20 grid map, compared with the A* algorithm and GA* algorithm, the calculation time of BSGA* is reduced by 59.48% and 41.25%, the number of search nodes is reduced by 45.16% and 28.17%, and the total turning angle is reduced by 20% and 20%, respectively.