## 6 Material and Method
### Building the Graph  
In this stage of the framework, the environment is discretized as a vertical superposition of horizontal grids of nodes above the 3D terrain. The nodes represent the position that can be occupied by the UAVs whereas the edges between the nodes represent the line segments that can be travelled by the UAVs. The number of superposed grids \(N_{g}\) is configurable and set by the user, and all grids are vertically equally spaced. In all cases, the highest grid is positioned at \(Z_{max}\), the highest elevation of the terrain plus the minimum flying altitude of the UAV. The lowest grid is positioned at \(Z_{min}\), the lowest elevation of the terrain plus the minimum flying altitude of the UAV. If there are to be \(N_{g}\) grids stacked between the two limiting altitudes, the spacing between them has to be \(\Delta H=(Z_{max}-Z_{min})/N_{g}\). An example for five grids is illustrated in Figure 5.  
on the optimization objective used and can be the distance between the nodes, the time needed to travel the edges at optimal speed or the energy required to travel the edges, also at optimal speed. The result is a connectivity graph that is used at the next step by the SSSP algorithm to compute optimal paths connecting every pair of DPs. One drawback of using a graph built as explained so far is that there is no way for the SSSP algorithm to minimize the number of turns. It is common for such algorithm to generate a zig-zag type of path which is much less efficient to fly than a straight path. In order to minimize the number of turns in the path, the technique described in [26] is implemented. The technique consists of overlaying multiple grids at the same altitude. On each grid, the UAV is allowed to travel in a single direction. At any points on a grid, the UAV is allowed to change grid by incurring a penalty. This is illustrated in Figure 6b for only four directions. In this work, there are 18 grids overlaid at every altitude where there used to be a single grid. On a grid, a node is connected to a single neighbor located physically at the different location. However, at a same location, a node is connected to the 17 other nodes belonging to the 17 other grids that are overlaid. To calculate the cost associated with changing grid, i.e., changing direction, the time, or energy needed to reduce the speed before taking the turn is calculated. For the case of going from a horizontal segment to another horizontal segment, the values plotted in Figure 3 are used to determine the speed reduction in percent. The incoming speed is assumed to be the optimal speed of the UAV. Based on the percent value, the actual reduced speed can be calculated. Assuming the deceleration before the turn starts at \(t_{1}=0\), the polynomial interpolation for the inverse time vs speed function is used to get \(t_{2}\), the time at which the UAV reaches the reduced speed. The same approach is used to find \(t_{3}\), the time during acceleration where the UAV is at the reduced speed, and \(t_{4}\), the time when the UAV reaches back optimal speed. The time used for the deceleration and acceleration are then calculated as follows:  
\[t_{a}=(t_{2}-t_{1})+(t_{4}-t_{3}) \tag{6}\]  
By evaluating the integral, which is quite easy due to the speed being modeled as a polynomial function, the distance traveled by the UAV during the deceleration and acceleration can be calculated using Equation (7). The same can be done for the energy consumption using Equation (8). \[D_{a}=\int_{t_{1-0}}^{t_{2}}S_{dec}(t)+\int_{t_{3}}^{t_{4}}S_{acc}(t) \tag{7}\]  
\[E_{a}=\int_{t_{1-0}}^{t_{2}}P_{dec}(t)+\int_{t_{3}}^{t_{4}}P_{acc}(t) \tag{8}\]  
Figure 6: **(a)** Grid showing the connection between a node and its 18 neighbors. **(b)** Representation of the multiple grids superposed in the same plane where each grid allows travel in a single direction. To calculate a penalty cost associated with the turn, the time, and energy needed to travel this same distance, but at optimal speed are calculated as follows as a reference.