# Ellipsoidal Path Planning for Unmanned Aerial Vehicles
## 4 Simulation and Results
#### Comparison with State of the Art Algorithms  
In order to validate the proposed method, we compared it with other evolutionary techniques and a well-known path planning algorithm. Firstly, we describe the Rapidly-exploring Random Tree Star (RRT*) [26]. The RRT* algorithm, presented in Algorithm 2, finds a free path from the initial point \(z_{init}\) to the final point \(z_{goal}\). We created a tree \(T\) with an initial node \(z_{init}\). Next, we grew the tree up for \(N\) attempts. ```
1:\(T\leftarrow\) InitializeTree()
2:\(T\leftarrow\) InsertNode(\(\emptyset\), \(z_{init}\), \(T\))
3:for\(i=1\) to \(N\)do
4:\(z_{rand}\leftarrow\) SampleSpace()
5:\(z_{nearest}\leftarrow\) Nearest(\(T\), \(z_{rand}\))
6:\((z_{new},U_{new})\leftarrow\) Steer(\(z_{nearest}\), \(z_{rand}\))
7:ifObstacleFree(\(z_{new}\)) then
8:\(z_{near}\leftarrow\) Near(\(T\), \(z_{new}\))
9:\(z_{min}\leftarrow\) ChooseParent(\(z_{near}\), \(z_{nearest}\),\(z_{new}\))
10:\(T\leftarrow\) InsertNode(\(z_{min}\), \(z_{new}\), \(T\))
11:\(T\leftarrow\) Rewire(\(T\), \(z_{near}\),\(z_{min}\),\(z_{new}\)) return\(T\)
```  
**Algorithm 2** Rapidly-exploring Random Tree Star (RRT*). To find the next node in the tree, we randomly sampled a point on the map \(z_{rand}\) that is not with an obstacle. We found the nearest node of the tree and renamed it \(z_{nearest}\). After steering from \(z_{nearest}\) to \(z_{rand}\), this function has heuristics about the robot's kinematics. Then we renamed \(z_{rand}\) as \(z_{new}\) and found a path \(U_{new}\). The ObstacleFree function search for collision with obstacles on the line from \(z_{nearest}\) to \(z_{new}\); if there were no collisions, we proceeded to add the \(z_{new}\) point. We collected the points close to \(z_{new}\) within a certain radius. Then we chose the parent node that carried the least cost and renamed \(z_{min}\). Finally, we added the link between \(z_{min}\) and \(z_{new}\) and rewired the tree to find the minimum cost. To apply the RRT* algorithm on an ellipsoidal map we developed a collision detection function. We used the Cholesky factorization of the covariance matrices that represent the obstacles. We show this in (11). In the case of the evolutionary algorithms, we can expect longer run-times because of the neural network prediction. \[\Sigma=LL^{T}. \tag{11}\]  
Using the triangular matrix \(L\), we can calculate if a point \(x\) is inside an ellipsoid on the map by using the inequality (12), where \(\mu\) is the center of the ellipsoid. \[||L^{T}(x-\mu)||_{2}\leq 1. \tag{12}\]  
In Figure 13, we show the resulting path of the RRT* algorithm in the same four maps. Notice that the found paths avoid the obstacles but do not consider the ellipsoid that represents the UAV. We used a maximum of 5000 iterations, but for the mean convergence on the four maps it was 1348 iterations. Furthermore, we also present experiments with other state-of-the-art evolutionary optimization algorithms. We ran the same tests for the the Differential Evolution (DE) [27] algorithm, the Particle Swarm Optimization (PSO) [28] algorithm, and the Firefly (FF) algorithm. All the evolutionary algorithms used the same fitness function presented in (7). All the proposed methods are non-deterministic. To ensure the validity of the results, we ran each algorithm experiment 30 times on the same computer. The start and endpoints were the same for all the experiments. In Table 3, we present the comparison of the different methods. Notice that the evolutionary schemes have the best mean performance for maps 1, 3, and 4. In Figure 14, we show the box-and-whisker plots for each map and each method.