# 3D Global Path Planning Optimization for Cellular-Connected UAVs under Link Reliability Constraint
## 3 Methodology
### Optimization Algorithms
#### 3.3.1 Particle Swarm Optimization  
In the PSO algorithm, first, all particles are scattered randomly in the search space, and every particle calculates the objective function based on its position in the search space. Then, each particle computes its next movement direction based on a combination of information about its current position, the best position it has experienced so far, its current velocity, and information from one or more of the best particles in the swarm. Then, particles move, one step of the algorithm ends, and in case of necessity, the above steps are iterated until the algorithm meets the termination criteria. To formulate the behavior of particles, assume that there are \(n_{pop}\) particles in the swarm, where the position and velocity of the \(i^{th}\) particle at time \(t\) are denoted as \(x^{i}\) and \(v^{i}\), respectively, for \(i\in\{\}\). \(x^{i,\ best}[t]\) is the best position that the \(i^{th}\) particle has experienced so far, and \(x^{best}[t]\) is the position of the swarm's best experience. In every iteration, the swarm updates its best position (based on objective value), which is known as global best; also each particle updates its best solution (aka personal best) and computes its next position as follows:  
\[v^{i}[t+1]=wv^{i}[t]+c_{1}r_{1}\Big{(}x^{i,\ best}[t]-x^{i}[t]\Big{)}+c_{2}r_{ 2}\Big{(}x^{gbest}[t]-x^{i}[t]\Big{)}, \tag{15}\]  
\[x^{i}[t+1]=x^{i}[t]+v^{i}[t+1], \tag{16}\]  
where \(w\) is the inertia coefficient; \(c_{1}\) and \(c_{2}\) are cognitive and social acceleration coefficients, respectively; and \(r_{1}\) and \(r_{2}\) are random numbers with a uniform distribution, \(r_{1},r_{2}\sim u(0,1)\). The adjustment of \(w\), \(c_{1}\), and \(c_{2}\) plays an important role in the performance of the PSO algorithm, which directly affects the convergence speed of the algorithm to the best cost function. Small values of \(w\) result in rapid convergence and enhance the risk of trapping in a local minimum, and large values of \(w\) result in random behavior or particles. In other words, a small value of \(w\) helps exploitation, and a large value of \(w\) helps exploration. Exploration is the capability of finding new solutions, and exploitation is the capability of developing/improving existing solutions. A pure exploration results in a random search, and a pure exploitation results in a local search. In addition, small values of \(c_{1}\) and \(c_{2}\) help exploitation, and large values of \(c_{1}\) and \(c_{2}\) help exploration. The coefficients need to be appropriately set to make a tradeoff between exploration and exploitation. To set the coefficients efficiently, we used the proposed constriction coefficients by [PERSON] [53] as  
\[ \begin{array}{c}w=\chi,\\ c_{1}=\chi\phi_{1},\\ c_{2}=\chi\phi_{2},\end{array}  \tag{17}\]  
where \(\phi_{1},\phi_{2}>0\) and \(\phi\equiv\phi_{1}+\phi_{1}>4\), and  
\[\chi=\frac{2}{\phi-2+\sqrt{\phi^{2}-4\phi}}. \tag{18}\]  
According to [54], the optimal values for the above parameters are \(\phi_{1}=\phi_{2}=2.05\), \(w=0.7298\), and \(c_{1}=c_{2}=1.4962\). To improve the performance of the algorithm, the inertia weight damping ratio, \(w_{damp}\), was added into the algorithm as  
\[w=w\times w_{damp},\text{ where }w_{damp}<1, \tag{19}\]  
in which, first, the algorithm starts with a high exploration rate. By updating \(w\) at the end of each iteration, \(w\) gradually decreases, which consequently reduces the exploration rates and enhances exploitation ability. In simulations, \(w_{damp}\) was set to 0.99. The velocity limitation was also applied to the algorithm as  
\[V_{min}<v^{i}[t]<V_{max}, \tag{20}\]  
where  
\[V_{max}=-V_{min}=0.1\times(x_{max}-x_{min}). \tag{21}\]  
In the simulation, the number of function evaluations (NFE) was used as the termination criteria, in which the PSO algorithm stops its execution when meeting the criteria.