# Ellipsoidal Path Planning for Unmanned Aerial Vehicles
## 2 Approximating the Distance Function with Neural Networks  
Our goal was to develop a path planning algorithm to work with the ellipsoidal maps to take advantage of these maps being compact-in-memory yet rich-in-information. The hypothesis to achieve the above goal was to design an algorithm that could compute a path using the distance between the envelope ellipsoids of the obstacles, and the ellipsoid that models the UAV. The computed path maintains the vehicle safe free space between itself and the occupied places. To know how much free space exists between ellipsoids, we needed to solve the non-trivial key problem of finding a method to compute the distance between them due to the fact that there is not a closed way to do it. We propose a machine learning method to solve the above computation using neural networks to overcome the problem that represents the great computational costs of using iterative algorithms to calculate distances in maps, where the number of ellipsoids is large. To solve this problem efficiently, we use a dense neural network to estimate the distance between two ellipsoids. One ellipsoid will represent a small UAV and the other will represent an obstacle. We can train a neural network for the regression problem. To generate a dataset for training, we randomly generate a pose for the UAV (yaw, pitch and roll). We fix the semi-axes of the ellipsoid representing the UAV with \((0.5,0.5,0.3)\) in meters. Furthermore, we generate a random ellipsoid around the UAV. We calculate a cloud mesh for every ellipsoid and estimate the distance between the UAV by using a brute force approach. In Figure 2, we present an example of generated samples and their estimated distance. One problem with this approach is to find a correct normalization of the data. If the input data of a neural network is not well normalized it could lead to slow or biased  
Figure 2: Examples of random generated samples for training. learning. In the following, we describe a novel normalization method that achieves good results on the neural network performance. Firstly, the small UAV is represented by an ellipsoid with fixed semi-axes. These semi-axes are not considered in the learning problem, because the neural network can learn them as well. We will fix the UAV position at the center of the 3D space. Then, the position and the semi-axes are not input data for the neural network. The UAV is represented only with the angles \((yaw,pitch,roll)\in[0,2\pi]^{3}\). In the second instance, the 3D points on the map representing the obstacles are mapped using ellipsoids. As we presented in [10], we applied a clustering technique to the cloud point. Each cluster is a set of 3D points \(\left\{[x_{i},y_{i},z_{i}]^{T}\right\}_{i=1}^{n}\), with center of mass \([\mu_{x},\mu_{y},\mu_{z}]^{T}\). We can also calculate the pair-wise covariance between two variables; for example, for \(x\) and \(y\) coordinates, the covariance is calculated with (1):  
\[\sigma_{xy}=\sigma_{yx}=\sum_{i=1}^{n}\frac{(x_{i}-\mu_{x})(y_{i}-\mu_{y})}{n}. \tag{1}\]  
With the pair-wise covariances, we construct the covariance matrix is defined with (2). The parameters \((c_{1},\dots,c_{9})\) carry the information of an ellipsoid that covers all non-outlier data points. \[\Sigma= \begin{bmatrix}\sigma_{xx}&\sigma_{xy}&\sigma_{xz}\\ \sigma_{xy}&\sigma_{yy}&\sigma_{yz}\\ \sigma_{xz}&\sigma_{yz}&\sigma_{zz}\end{bmatrix} = \begin{bmatrix}c_{1}&c_{2}& c_{3}\\ c_{4}&c_{5}&c_{6}\\ c_{7}&c_{8}&c_{9}.\end{bmatrix}  \tag{2}\]  
The obstacle ellipsoids will be represented with the normalized covariance matrix. This parametrization is chosen because it is the output of the multi-ellipsoidal mapping algorithm presented in [10]. Other parametrizations lead to a high computational cost; for instance, one could use the angles of rotation and the semi-axes, but this will require the spectral decomposition of the covariance matrix. In Figure 3, we present a 2D scheme of the maximum and minimum distances between two ellipses.