# 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
(**a**) the heatmap after subdivision—set of new solutions after subdivision; (**b**) the dashed box is the best solution. ```
0: M : Cell, F: Frame
0: new Drone's position denoted \(S_{position}\)
1:\(S_{n}:Cell[]\)
2:if\(M.getvalue()==0\)then
3:\(S_{position}\gets M\)
4:else
5:\(shellNumber\gets 1\)
6:\(CheckNeighborCells(M,shellNumber,S_{n},F)\)
7:\(PossibleDronePos\gets FilterSolution(M,S_{n})\)
8:\(B_{m}\gets FindBoundaryCells(PossibleDronePos,F)\)
9:\(G\gets B_{m}\uplus S_{n}\)
10: {Perform subdivision on \(G\) }
11: {Group every 4 subcells after subdivision in one vertex (denote it \(v^{{}^{\prime}}\))}
12: {We denote \((S_{n})^{{}^{\prime}}\) the list of vertices \(v^{{}^{\prime}}\)}
13:\(S_{position}=FilterSolution(M,(S_{n})^{{}^{\prime}})\)
14:endif
15: return \(S_{position}\)
```  
**Algorithm 1** getDronePosition  
Algorithm 2 (_CheckNeighborCells_) looks for the list of possible solutions \(S_{n}\) around M in the surrounding shells in a spiral mode starting from M. The list of solutions is filtered by Algorithm 3 (\(FilterSolution\)) to choose the nearest possible solution cell \(S^{\prime}\) to M which could be the next drone's position. \[\Gamma=\{v_{ij}\mid v_{ij}\in[0,1],i\in[1,b],j\in[1,a]\}\]2 Flow chart of the obstacle detection and avoidance. ```
0: M: Cell, shellNumber : int, \(S_{n}\) : Cell[], F :Frame
0: List of possible Solutions \(S_{n}\)
1:\(n1\leftarrow(M.getI()-shellNumber)\)
2:\(n2\leftarrow(M.getI()+shellNumber)\)
3:\(m1\leftarrow(M.getK()-shellNumber)\)
4:\(m2\leftarrow(M.getK()+shellNumber)\)
5:\(Celltemp=null\)
6:\(a=F.getLength()\)
7:\(b=F.getWidth()\)
8:if\((n2\leq b\wedge m2\leq a)\)then
9: [look into the current shell for a solution (check each cell \(v_{ik}\))]
10:for\(i\gets n1\) to \(n2\)do
11:for\(k\gets m1\) to \(m2\)do
12:if\((i!=M.getI()\wedge k!=M.getK())\)then
13:if\((v_{ik}==0)\)then
14:\(S_{n}.add(v_{ik})\)
15:endif
16:endif
17:endfor
18:if\((S_{n}.isEmpty())\)then
19:\(CheckNeighborCells(M,++shellNumber,S_{n},F)\)
20:endif
21:endfor
22:endif
```  
**Algorithm 2** CheckNeighborCells  
```
0: M : Cell, \(S_{n}\) : Cell[]
0: The nearest solution to cell M denoted \(S^{\prime}\)
1:\(x2\gets M.getI()\)
2:\(y2\gets M.getK()\)
3:for\(index\gets 0\) to \(S_{n}size()\)do
4:\(x1\gets S_{n}.get(index).getI()\)
5:\(y1\gets S_{n}.get(index).getK()\)
6: [Find distance to M]
7:\(distance\leftarrow\sqrt{(x2-x1)^{2}*W+(y2-y1)^{2}*L}\)
8:if\((index==0)\)then
9:\(old=distance\)
10:endif
11:if\((old>distance)\)then
12:\(old\gets distance\)
13:\(minIndex\gets index\)
14:endif
15:endfor
16:\(S^{\prime}\gets S_{n}.get(minIndex)\)
17:return \(S^{\prime}\)
```  
**Algorithm 3** FilterSolution  
In order to locate the boundaries of the obstacle around \(S^{\prime}\), Algorithm 4 (\(FindBoundaryCells\)) finds the list of boundary cells (denoted \(B_{m}\)). We combine \(S_{n}\) and \(B_{m}\) in a group box \(G\), and to decide whether the drone will pass safely through the solution cell, we perform a subdivision on the cells. This helps with finding a better solution nearest to M than the one found before the subdivision. Wegroup every four zero-value subcells in one vertex (denoted \(v^{{}^{\prime}}\)). The list of these vertices is denoted \((S_{n})^{{}^{\prime}}\) and is filtered later using Algorithm 3 to find the exact drone position (denoted \(S_{position}\)). In the next section, we evaluate the performance of our approach. ```
0:\(S^{\prime}\): Cell, F :Frame
0: List of boundary cells \(B_{m}\) to \(S^{\prime}\)
1:\(B_{m}:cell[]\)
2:\(n1\leftarrow(S^{\prime}.getI()-1)\)
3:\(n2\leftarrow(S^{\prime}.getI()+1)\)
4:\(m1\leftarrow(S^{\prime}.getK()-1)\)
5:\(m2\leftarrow(S^{\prime}.getK()+1)\)
6:for\(i\gets n1\) to \(n2\)do
7:for\(k\gets m1\) to \(m2\)do
8:if\((i!=S^{\prime}.getI()\wedge k!=S^{\prime}.getK())\)then
9:if\((v_{ik}>0\wedge v_{ik}<=1)\)then
10:\(B_{m}.add(v_{ik})\)
11:endif
12:endif
13:endfor
14:endfor
15:return \(B_{m}\)
```  
**Algorithm 4** FindBoundaryCells