# EAOA: Energy-Aware Grid-Based 3D-Obstacle Avoidance in Coverage Path Planning for UAVs
## 3 Energy-Aware Grid-Based 3D-Obstacle Avoidance (EAOA)
### Determining the Next Position of the Drone  
In this section, we aim to determine the closest location where the drone has to move to, in order to avoid an obstacle on its way. The main steps are described below:  
Figure 3: 3D view. * Step 1: A heatmap of the frame \(F\) is generated. To exemplify, Figure 4 shows a 24 \(\times\) 40 heatmap of a tree in the frame: \[\Gamma=\{v_{ij}\mid v_{ij}\in[0,1],i\in[1,b],j\in[1,a]\}\] (3) where \(v_{ij}\) represents a grid cell element in \(\Gamma\). We denote \(\Gamma^{w}\) the set of zero-cells in the grid: \[\Gamma^{w}=\{v_{ij}\mid v_{ij}=0\}\] (4) We denote \(\Gamma^{c}\) the set of non zero-cells in the grid ( \(\Gamma^{c}=\Gamma\setminus\Gamma^{w}\)): \[\Gamma^{c}=\{v_{ij}\mid v_{ij}\in]0,1]\}\] (5)
* Step 2: To recall, M is the projection of A in the frame. We check its position in the grid. If M is located in a cell in \(\Gamma^{w}\), then no obstacle is on the drone's way. The current path will not be modified. However, if M is located at a non-zero cell (i.e., a cell in \(\Gamma^{c}\)), then the obstacle exists on the drone's way. Hence, the path should be modified. For this purpose, we will investigate the list of cells surrounding M to find a loophole for the drone and make a detour. We denote \(\mathcal{N}_{ij}\) the neighbors of a grid-cell \(v_{ij}\). It is the list of cells that directly surround \(v_{ij}\): \[\mathcal{N}_{ij}=\{v_{pq}\mid p\in[i-1,i+1],q\in[j-1,j+1]\}-\{v_{ij}\}\] (6) We denote \(B_{m}\) the nearest non-zero cells to M that are in \(\Gamma^{c}\) (see Equation (7)). We call them boundary cells. We denote d(v1,v2) the Euclidean distance between two points v1 and v2: \[B_{m}=\{v_{ij}\in\Gamma^{c}\mid\forall v_{pq}\in\Gamma^{c},d(v_{ij},M)=min\{d (v_{pq},M)\}\wedge\exists v\in\mathcal{N}_{ij}\mid v\in\Gamma^{w}\}\] (7) We aim to find the nearest \(v_{ij}\) to M and \(B_{m}\) such that \(v_{ij}\) belongs to \(\Gamma^{w}\). We denote \(S_{n}\) the set of solutions, where \(n\) represents the number of white cells that directly surround \(B_{m}\): \[S_{n}=\{v_{ij}\in\mathcal{N}_{B_{m}}\cap\Gamma^{w}\mid\forall v_{pq}\in \mathcal{N}_{B_{m}}\cap\Gamma^{w},d(v_{ij},M)=min\{d(v_{pq},M)\}\}\] (8) To find the list of solutions \(S_{n}\), we loop in a reverse spiral mode from M (see Figure 5) until we reach a shell that contains cells with \(v_{ij}=0\). Figure 4: Example of a tree Heatmap in the frame. The drone position is (12, 13). The red box represents boundary cells, and the purple box represents solution cells. To illustrate, in Figure 4, the projection of the drone is located at cell (12, 13) in the grid. The set of boundary cells \(B_{m}\) is represented by the red boxes ( \(\mid B_{m}\mid=3\)). The set of possible solutions \(S_{n}\) is represented by the purple boxes ( \(\mid S_{n}\mid=3\)). It should be noted that, if \(S_{n}=\emptyset\), the planner has to increase the frame dimensions. * Step 3: To choose from \(S_{n}\) the most convenient solution. We denote \(G=B_{m}\cup S_{n}\); see Figure 6. Then, divide each cell into four sub-cells (see Figure 7a). The reason behind this is to have better understanding of the obstacles' location in order to determine the nearest next position of the drone. After applying the sub division, a new solution set \(S^{\prime}\subset S_{n}\) is generated (see Figure 7b). The dashed red box represents the cell where the drone has to move to in order to avoid the obstacle. The flowchart in Figure 8 summarizes the main steps in our work. Algorithm 1 checks the current drone's cell-position (named M) in the facing area. If M is located in a zero-value cell, it becomes the new drone's position. Otherwise, the algorithm checks the neighboring cells to find the nearest non-zero value cell. Figure 5: Determine set of Solutions \(S_{n}\). \[\Gamma=\{v_{ij}\mid v_{ij}\in[0,1],i\in[1,b],j\in[1,a]\}\]0 Group of obtained cells \(G\). \[\Gamma=\{v_{ij}\mid v_{ij}\in[0,1],i\in[1,b],j\in[1,a]\}\]1 Finding the new position of the drone.