# Ellipsoidal Path Planning for Unmanned Aerial Vehicles
## 1 Introduction  
Autonomous Unmanned Aerial Vehicles (UAVs) play an important role in both military and civilian applications. In contrast with manned aircrafts, UAVs are able to perform complex and dangerous tasks with high maneuverability and low cost [1, 2]. An important problem to solve in order to achieve a certain level of autonomy is path planning. In the past, the best path was selected as the shortest distance to a goal; now, the best path is associated with the traveled distance and energy consumption [3]. If more parameters, besides distance, are considered, the path planning problem can been stated as an optimization problem, and population based algorithms have been used in many cases to solve it successfully [4, 5, 6, 7, 8]. In [9], we described a novel algorithm for path planning, which uses conformal geometric algebra to generate maps using spheres. By using spheres, we gain in terms of the number of parameters needed for representing the maps and these maps are rich in information. For example, we need the same number of parameters for representing a sphere as for a plane, but the plane also needs an extra number of parameters for bounding the plain. Moreover, the spheres are easy to operate in conformal geometric algebra. The algorithm employs the characteristics of the spheres described in this algebra to navigate through the maps by combining them with Teaching-Learning Based Optimization (TLBO). In this paper, we compared different evolutionary optimization algorithms where TLBO had the best result. On the other hand, we also explored approaching the robotic mapping problem by using ellipsoidal representations [10]. These ellipsoidal geometric entities are coded inthe geometric algebra \(G_{6,3}\). The resulting map is compact and rich in information as we showed in [10]. The problem of robotic mapping consists of constructing a spatial representation of the environment, which is helpful for the robot [11]. There are classic mapping abstractions, such as grid occupancy [12], where cubes represent the objects. This abstraction is memory efficient but discretizes the environment; furthermore, it is useful for office-like environments but is not adequately suited for outdoor environments. We can also find variable size grid occupancy [13], where we can change the resolution of the grid. With particular modification, we can model dynamic maps with this abstraction [14]. There are other map abstractions such as multiplanar maps [15], landmarks, and points of obstacles [16]. A mapping algorithm called OctoMap was proposed in [17; 18]. OctoMap has variable resolution grid occupancy representation with a probabilistic construction. We include in Table 1 a qualitative comparison between ellipsoidal maps and Octomap. In Figure 1, we present an example of a cloud point (left) [19] and its ellipsoidal map (right). In this work, we present a novel algorithm for path planning in 3D environments for small UAVs. This algorithm works on ellipsoidal mapping provided by the algorithm in [10]. There is no closed form for calculating the distance between two ellipsoidal surfaces and using an iterative algorithm will be computational expensive. We propose to solve this problem by training a dense neural network for approximating the distance between two ellipsoids. We propose a new fitness function to find the path with the TLBO algorithm. The TLBO algorithm was chosen because it obtained the best performance in a similar problem presented in [9]. We refer the reader to [9] for a performance comparison on metaheuristics for similar path-planning. \begin{table}
\begin{tabular}{l c c} \hline \hline
**Property** & **EMA** & **OctoMap** \\ \hline Basic geometric entity & Ellipsoids & Cubes \\ Variate granularity & Yes & Yes \\ Construction scheme & Any clustering algorithm & Hierarchical \\ Robust to outliers & Yes & Yes \\ \hline \hline \end{tabular}
\end{table} 
Table 1: EMA and OctoMap properties. Figure 1: Example of an ellipsoidal map generated with the ellipsoidal mapping algorithm presented in [10].