# Salp Swarm Algorithm Optimized A* Algorithm and Improved B-Spline Interpolation in Path Planning
## 2 Path Planning Algorithm
### Improvement of the A* Algorithm
#### 2.2.2 Optimization Using the SSA
```
0: Grid map \(M\), original path \(P\)
0: Optimized path \(P\)/
1:BEGIN:
2: Initialize \(P^{\prime}\ \leftarrow\ P.copy()\), \(R\ \leftarrow\ \varnothing\)
3:\(i\ \leftarrow\ 0\)
4:while\(i<len(Pr)-1\)do
5:\(A\ \leftarrow\ P\)/\([i]\), \(B\ \leftarrow\ P\)/\([i+1]\)
6:\(x1\), \(y1\ \leftarrow\ A\); \(x2\), \(y2\ \leftarrow\ B\)
7:if\(|x1-x2|==1\)and\(|y1-y2|==1\)then // Diagonal move
8:\(C\ \leftarrow\ (x1\), \(y2\)), \(D\ \leftarrow\ (x2\), \(y1)\)
9:has_obstacle\(\ \leftarrow\ False\)
10:if\(C\ \in\ M.obstacles\ \vee\ D\ \in\ M.obstacles\)thenhas_obstacle\(\ \leftarrow\ True\)
11:ifhas_obstaclethen
12:\(R\ \leftarrow\ R\ \cup\ \{A,\ B\}\) // Mark nodes for removal
13:if\(C\ \
otin\ M.obstacles\)then
14:\(P\)/\(insert(i+1,\ C)\) // Insert intermediate point C
15:\(i\ \leftarrow\ i+1\) // Skip the new point
16:elseif\(D\ \
otin\ M.obstacles\)then
17:\(P^{\prime}\)/\(insert(i+1,\ D)\) // Insert intermediate point D
18:\(i\ \leftarrow\ i+1\)
19:endif
20:continue // Re-check current index
21:endif
22:endif
23:\(i\ \leftarrow\ i+1\)
24:endwhile
25:// Remove marked nodes
26:for\(p\)in\(P^{\prime}\)do
27:if\(p\ \in\ R\)and\(p\ \
otin\ \{P[0],P[-1]\}\)then
28: remove \(p\) from \(P^{\prime}\)
29:endif
30:endfor
31:return\(P^{\prime}\)
32:END
```

**Algorithm 2**Corner Avoidance Strategy

By applying \(Optimize(P)\), the adjustment of control points enables obstacle avoidance during turning processes. This optimization ensures that the generated path smoothly navigates around obstacles rather than intersecting them. The effectiveness of this method is illustrated in Figure 3.

Path obstacle avoidance refers to the process of fine-tuning the positions of all control points based on nearby obstacles to ensure the entire path avoids obstacles effectively. To achieve obstacle avoidance throughout the path, we adjust the positions of control points according to their proximity to obstacles. Therefore, we introduce the distance adjustment function \(f(d_{i})\) as (18), which modifies the position of a control point \(P(x,y)\) when there are \(N\) nearby obstacles. Given an obstacle \(O_{i}(x_{i},y_{i})\) located at a distance \(d_{i}\), the adjusted position of the control point is denoted as \(D_{i}\) and expressed in (19) and (20). \[f(d_{i})= \begin{cases}\frac{1}{a+b^{d_{i}}}-c&d_{i}<d_{0}\\ 0&otherwise\end{cases}  \tag{18}\]

\[\mathbf{u}_{i}=\frac{(x-x_{i}\,\ y-y_{i})}{d_{i}} \tag{19}\]

\[\mathbf{D}_{i}=\frac{1}{N}\cdot f(d_{i})\cdot\mathbf{u}_{i} \tag{20}\]

The pseudo-code for path obstacle avoidance is presented in Algorithm 3. ```
0: Optimized path \(P^{\prime}\); Grid map \(M\); Distance threshold \(d_{0}\); Parameters \(a,\ b,\ c\)
0: Final control point path \(P^{\prime\prime}\)
1:BEGIN:
2: Initialize \(P^{\prime\prime}\) as empty list
3:for\(p\) in \(P^{\prime}\)do
4:if\(p==P^{\prime}[0]\) or\(p==P^{\prime}[-1]\)then
5: append \(p\) to \(p^{\prime\prime}\)
6:continue
7:endif
8: Initialize \(D_{x}\gets 0\), \(D_{y}\gets 0\), \(N\gets 0\)
9:for each obstacle \(O_{i}(x_{i},\ y_{i})\) in \(M\).obstaclesdo
10:\(d_{i}\ \leftarrow\ sqrt\left(\left(x-x_{i}\right)^{2}+\left(y-y_{i}\right)^{2}\right)\)
11:if\(d_{i}<d_{0}\)then
12:\(f(d_{i})\ \leftarrow 1/\left(a+b\ *\ e^{x}\right)-c\)
13:\(D_{x}\ \leftarrow\ D_{x}+f(d_{i})\ *\ (x-x_{i})/d_{i}\)
14:\(D_{y}\ \leftarrow\ D_{y}+f(d_{i})\ *\ (y-y_{i})/d_{i}\)
15:\(N\ \leftarrow\ N+1\)
16:endif
17:endfor
18:if\(N>0\)then
```

**Algorithm 3**Path Obstacle Avoidance with Grid Map

Figure 3: The effect of corner avoidance optimization. (**a**) is the smoothed B-spline path; (**b**) is the improved smoothed B-spline path. By applying path obstacle avoidance to adjust control points, the B-spline smoothed path is optimized to ensure a safe distance from obstacles, enhancing the overall path safety. ## 4 Experimental Simulation

### Path Planning Algorithm Simulation Experiment

#### 4.1.1 Parameters for Path Planning Simulation

We use Python as the development environment.