# Node and Edge Surveillance Using Drones Considering Required Camera Altitude and Battery Charging

Ivan Kristianto Singgih, Jonghwa Lee, Byung-In Kim

► To cite this version:

Ivan Kristianto Singgih, Jonghwa Lee, Byung-In Kim. Node and Edge Surveillance Using Drones Considering Required Camera Altitude and Battery Charging. IFIP International Conference on Advances in Production Management Systems (APMS), Aug 2018, Seoul, South Korea. pp.172-180, 10.1007/978-3-319-99707-0_22. hal-02177871

HAL Id: hal-02177871

https://inria.hal.science/hal-02177871

Submitted on 9 Jul 2019

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Node and Edge Surveillance Using Drones Considering
Required Camera Altitude and Battery Charging

Ivan Kristianto Singgih¹, Jonghwa Lee², and Byung-In Kim³✉

1,2,3 Department of Industrial and Management Engineering, Pohang University of Science and Technology (POSTECH), Pohang, Republic of Korea

¹ Department of Industrial Engineering, Sepuluh Nopember Institute of Technology, Surabaya, Indonesia

ivanksinggih@postech.ac.kr¹, jet226@postech.ac.kr²,
bkim@postech.ac.kr³

**Abstract.** In this study, a drone routing problem is studied, in which several drones are used to perform an initial surveillance on an area after a disaster. During the surveillance, observations are performed by taking photos of nodes representing populated areas and road segments in the network using cameras installed on the drones from two different altitudes. More target nodes and edges can be observed by the drones from the higher altitude, but with low photo quality, while high photo quality can be obtained from the lower altitude, but within a smaller observation range. Each drone has a limited battery capacity and may need to return to the base for charging. Developed methods for the well-known arc-routing and vehicle routing problems cannot be directly used to solve the considered problem. This study aims to route the drones efficiently to perform the observation and satisfy the required photo quality for all target nodes and edges, while minimizing the total time required to perform the surveillance. This paper is the first study which considers the multiple-drone routing problem with different flying altitudes and battery charging process. The problem is formulated as a mixed integer programming model and numerical experiments are provided. Various important future research topics in this drone surveillance routing problem are also identified, which are necessary for providing basics for the development of algorithms to deploy the drones efficiently.

**Keywords:** Drone Routing, Battery Charging, Altitude, Photo Quality, Surveillance.

# 1 Introduction

In this study, a multiple drone node-and-arc-routing problem is investigated. In the problem, each of the target nodes and edges must be observed by taking photos with low or high quality photo using drones. The target nodes and edges can be observed by drones at two altitudes [1]. Flying at the lower altitude allows the drones to obtain photos with high quality, but within a smaller observation range. Meanwhile, flying at the higher altitude restrict the drones to only produce observation photos with low quality,
but allows the drones to capture more target nodes and edges. Performing observations
of target nodes and edges at appropriate altitudes can reduce the total surveillance times
and this is important in this post-disaster surveillance.

The problem is related to the arc routing problems, which have been studied by many researches including [2-5]. However, only few papers including [1, 6-7] have studied drone observation at multiple altitudes. Waharte and Trigoni [1] and Zorbas et al. [7], the most related researches, proposed heuristic algorithms to perform search and rescue operations using drones and studied an optimal drone placement to minimize the cost while assuring the complete surveillance of all targets.

Different with the previous researches, we explicitly consider the drone routing
problem at two altitudes by modeling all drone movements throughout the network.
This paper is the first study on the drone routing problem at two altitudes for observing
nodes and edges, which considers required observation quality and battery recharging.
This paper focuses on introducing this new routing problem, in which different altitudes
of drone flying determine the captured photo quality. This problem is different from
well-known arc routing problem and vehicle routing problem because in those previous
problems, any target node or edge requires direct visit, whereas the considered problem
of this paper assumes that target nodes and edges require indirect visit (camera watch-
ing) and multiple observations of nodes and edges are possible from a single point visit.
In addition, changing the flying altitude allows to change the observed area, which al-
lows faster surveillance process.

This paper is organized as follows: The problem is defined in Section 2. The math-
ematical model is presented in Section 3. Numerical experiments are presented in Sec-
tion 4. Finally, conclusions are given in Section 5.

2 Problem Definition

In this study, a network (S, E) is considered, where S={1,2,...,ψ} and E={1,2,...,e}
represent the sets of target nodes and edges on the ground that must be observed. In a
disaster area, the nodes to be observed in S are distribution centers, residential area, and
road intersections. The edges in E are roads connecting the nodes. After a disaster oc-
currence, it is necessary to deliver supplies from the distribution centers to the residen-
tial areas. It is necessary to perform the surveillance on the nodes in order to assess the
availability of the supplies at the distribution centers, the magnitude of disaster at resi-
dential areas along with the number of people in those area, and the possibility to use
the roads and intersections in the post-disaster period. The surveillance is performed by
taking photos using several drones. Photos with high quality must be captured for im-
portant nodes and edges, while other nodes and edges with less importance can be ob-
served using photos with low quality.

The drones travel on a network (N, A), where N is the set of the depot and points,
and A is the set of arcs. Set N includes the depot indices (0 for start depot and 2s+1 for
end depot), a set of drone observation points at the lower altitude (S<sub>low</sub>={1,2,...,s}), and
another set of drone observation points at the higher altitude (S<sub>high</sub>={s+1,s+2,...,2s}).
Observation points in S<sub>low</sub> and S<sub>high</sub> have the same horizontal positions with the target
nodes on the ground. The set of arcs, $A$, includes a set of arcs for observation at lower altitude ($E_{low}$), a set of arcs for observation at higher altitude ($E_{high}$), arcs connecting both depot indices, arcs connecting each depot index with each observation point, and arcs connecting observations points at different altitudes.

Observations using drones are performed at two altitudes with different sizes of covered areas, as shown in Fig. 1. Travelling at a lower altitude allows the drones to observe less number of target nodes and edges, and drone movements at a higher altitude enable the drones to observe more number of target nodes and edges. The observation of some target edges may not be possible from any point. In that case, drones are required to flight through arcs above them to perform the observation. The required photo quality for each target node and edge must be satisfied. The total observation time must be minimized while each drone's flight duration is limited by its battery level.

<figure><img src="image_2.png" /><figcaption>Fig. 1. Drone observation at two altitudes with different sizes of covered areas.</figcaption></figure>

## 3 Mixed Integer Programming Model

The problem is formulated as a mixed integer programming (MIP) model as follows:

Sets:

$K$ set of drone routes, $K=\{1,2,...,ld\}$

$R$ set of individual drones, $R=\{1,2,...,l\}$

$O_i$ set of target nodes covered when a drone performs the observation at point $i$, $i \in S_{low} \cup S_{high}$, $O_i \subseteq S$

$P_i$ set of target edges covered when a drone performs the observation at point $i$, $i \in S_{low} \cup S_{high}$, $P_i \subseteq E$

$\pi_{ij}$ set of target edges covered when a drone performs the observation at arc($i,j$) at the higher altitude, $(i,j) \in E_{low}$, $\pi_{ij} \subseteq E$

$\mu_{ij}$ set of target edges covered when a drone performs the observation at arc($i,j$) at the higher altitude, $(i,j) \in E_{high}$, $\mu_{ij} \subseteq E$
Parameters:

b battery charging time at the depot

d maximum possible number of routes per individual drone

$f_{0,k}$ initial battery level of a drone for route k at depot 0

$g_{ij}$ reduced battery level during movement from depot or point i to depot or point j

$q_h$ 1, if the required photo quality captured for node h is high; 0, otherwise, $h \in S$

$r_{qy}$ 1, if the required photo quality captured for edge $(q,y)$ is low; 0, otherwise, $(q,y) \in E$

$t_{ij}$ required time for a drone to travel from depot or point i to depot or point j, $i \in \mathbb{N}\{2s+1\}, j \in \mathbb{N}\{0\}$

Decision variables:

$a_{ik}$ the arrival time of a drone in route k at the depot or point i

$c_{qy}$ 1, if edge $(q,y)$ is covered by a drone observation at its higher altitude; 0, otherwise, $(q,y) \in E$

$f_{ik}$ the battery level of a drone in route k at the depot or point i

$m_{qy}$ 1, if edge $(q,y)$ is covered by a drone observation at its lower altitude; 0, otherwise, $(q,y) \in E$

$n_{qy}$ 1, if edge $(q,y)$ is covered by a drone visit to any depot or point at the higher altitude; 0, otherwise, $(q,y) \in E$

$u_h$ 1, if the photo quality captured for node h is high; 0, otherwise, $h \in S$

$v_{qy}$ 1, if the photo quality captured for edge $(q,y)$ is high; 0, otherwise, $(q,y) \in E$

$w_{qy}$ 1, if edge $(q,y)$ is covered by a drone visit to any depot or point at the lower altitude; 0, otherwise, $(q,y) \in E$

$x_{ijk}$ 1, if a drone travels from stop i to stop j in route k; 0, otherwise, $i \in \mathbb{N}\{2s+1\}, j \in \mathbb{N}\{0\}, i \neq j$

$z$ the latest arrival time of drones at depot $2s+1$

$\alpha_h$ 1, if node h is covered by any drone; 0, otherwise, $h \in S$

$\beta_{qy}$ 1, if edge $(q,y)$ is covered by any drone; 0, otherwise, $(q,y) \in E$

$\gamma_{ih}$ 1, if node h is covered by a drone visit at point i at the lower altitude; 0, otherwise, $i \in S_{low}, h \in S$

$\delta_{ih}$ 1, if node h is covered by a drone visit at point i at the higher altitude; 0, otherwise, $i \in S_{high}, h \in S$

$\epsilon_{iqy}$ 1, if edge $(q,y)$ is covered by a drone visit at point i at the lower altitude; 0, otherwise, $i \in S_{low}, (q,y) \in E$

$\theta_{iqy}$ 1, if edge $(q,y)$ is covered by a drone visit at point i at the higher altitude; 0, otherwise, $i \in S_{high}, (q,y) \in E$

The formulated MIP is as follows:

$$ \min z \qquad (1) $$

$$ \text{s.t.} \quad \gamma_{ih} \ge x_{ijk}, \quad \forall i \in S_{low}, j \in \mathbb{N}\{0\}, k \in K, h \in O_i \quad (2) $$

$$ \gamma_{ih} \ge x_{jik}, \quad \forall i \in S_{low}, j \in \mathbb{N}\{2s+1\}, k \in K, h \in O_i \quad (3) $$

$$ \sum_k \left( \sum_{j \in \mathbb{N}\{0\}} x_{ijk} + \sum_{j \in \mathbb{N}\{2s+1\}} x_{jik} \right) \ge \gamma_{ih}, \quad \forall i \in S_{low}, h \in O_i \quad (4) $$
$$ \gamma_{ih} = 0, \qquad \forall i \in S_{\text{low}}, h \in S - O_i \quad (5) $$

$$ u_h \ge \gamma_{ih}, \qquad \forall h \in S, i \in S_{\text{low}} \quad (6) $$

$$ \sum_{i \in S_{\text{low}}} \gamma_{ih} \ge u_h, \qquad \forall h \in S \quad (7) $$

$$ \alpha_h \ge u_h, \qquad \forall h \in S \quad (8) $$

$$ u_h + \sum_{i \in S_{\text{high}}} \delta_{ih} \ge \alpha_h, \qquad \forall h \in S \quad (9) $$

$$ \varepsilon_{iqy} \ge x_{ijk}, \qquad \forall i \in S_{\text{low}}, j \in \mathcal{N}\{0\}, k \in K, \quad (10) $$

$$ w_{qy} \ge \varepsilon_{iqy}, \qquad \forall i \in S_{\text{low}}, j \in \mathcal{N}\{2s+1\}, k \in K, \quad (11) $$

$$ \sum_k \left( \sum_{j \in \mathcal{N}\{0\}} x_{ijk} + \sum_{j \in \mathcal{N}\{2s+1\}} x_{jik} \right) \ge \varepsilon_{iqy}, \qquad \forall i \in S_{\text{low}}, (q,y) \in P_i \quad (12) $$

$$ \varepsilon_{iqy} = 0, \qquad \forall i \in S_{\text{low}}, (q,y) \in E - P_i \quad (13) $$

$$ w_{qy} \ge \varepsilon_{iqy}, \qquad \forall (q,y) \in E, i \in S_{\text{low}} \quad (14) $$

$$ \sum_{i \in S_{\text{low}}} \varepsilon_{iqy} \ge w_{qy}, \qquad \forall (q,y) \in E \quad (15) $$

$$ m_{qy} \ge x_{ijk}, \qquad \forall (i,j) \in E_{\text{low}}, (q,y) \in \pi_{ij}, k \in K \quad (16) $$

$$ \sum_k \sum_{(i,j); (q,y) \in \pi_{ij}} x_{ijk} \ge m_{qy}, \qquad \forall (i,j) \in E_{\text{low}} \quad (17) $$

$$ v_{qy} \ge w_{qy}, \qquad \forall (q,y) \in E \quad (18) $$

$$ v_{qy} \ge m_{qy}, \qquad \forall (q,y) \in E \quad (19) $$

$$ w_{qy} + m_{qy} \ge v_{qy}, \qquad \forall (q,y) \in E \quad (20) $$

$$ \beta_{qy} \ge v_{qy}, \qquad \forall (q,y) \in E \quad (21) $$

$$ \beta_{qy} \ge w_{qy}, \qquad \forall (q,y) \in E \quad (22) $$

$$ \beta_{qy} \ge m_{qy}, \qquad \forall (q,y) \in E \quad (23) $$

$$ v_{qy} + n_{qy} + c_{qy} \ge \beta_{qy}, \qquad \forall (q,y) \in E \quad (24) $$

$$ \alpha_h \ge 1, \qquad \forall h \in S \quad (25) $$

$$ \beta_{qy} \ge 1, \qquad \forall (q,y) \in E \quad (26) $$

$$ u_h \ge q_h, \qquad \forall h \in S \quad (27) $$

$$ v_{qy} \ge r_{qy}, \qquad \forall k \in K \quad (28) $$

$$ \sum_{j \in \mathcal{N}\{0\}} x_{0,j,k} = 1, \qquad \forall k \in K \quad (30) $$

$$ \sum_{i \in \mathcal{N}\{2s+1\}} x_{imk} - \sum_{j \in \mathcal{N}\{0\}} x_{mjk} = 0, \qquad \forall k \in K, m \in S_{\text{low}} \cup S_{\text{high}} \quad (31) $$

$$ a_{ik} + t_{ij} \le a_{jk} + M(1 - x_{ijk}), \qquad \forall i \in \mathcal{N}\{2s+1\}, j \in \mathcal{N}\{0\}, k \in K \quad (32) $$
$$z \geq a_{2s+1,k}, \qquad \forall k \in K \qquad (33)$$

$$f_{ik} - g_{ij} \geq f_{jk} - M(1 - x_{ijk}), \qquad \forall i \in \mathbb{N}\{2s+1\}, j \in \mathbb{N}\{0\}, k \in K \qquad (34)$$

$$a_{2s+1,r+wl} + b \leq a_{0,r+(w+1)l}, \qquad \forall r \in R, w \in \{0,1,\dots,d-1\} \qquad (35)$$

$$f_{ik}, a_{ik} = \text{positive integer} \qquad (36)$$

$$c_{qy}, m_{qy}, n_{qy}, v_{qy}, w_{qy}, \beta_{qy}, u_h, a_h, x_{ijk}, \gamma_{ih}, \delta_{ih}, \varepsilon_{iqy}, \theta_{iqy} = \text{binary} \qquad (37)$$

The objective function (1) minimizes the total time required to perform observations of all nodes and edges. Constraints (2)-(7) assure photo quality captured at each node and constraints (15)-(25) ensure photo quality captured at each edge. In order to check whether target nodes are observed from points at the higher altitude, some constraints are written as same as Constraints (2)-(6), except that $\gamma_{ih}$ is replaced with $\delta_{ih}$ and $S_{low}$ with $S_{high}$. These constraints together with Constraints (2)-(9) and (25) ensure that each node is observed by at least one drone. In order to check whether target edges are observed from points at the higher altitude, some other constraints are written as same as Constraints (10)-(17) and Constraint (22)-(23), respectively, except that $\varepsilon_{iqy}$ is replaced with $\theta_{qy}$, $w_{qy}$ with $n_{qy}$, $m_{qy}$ with $c_{qy}$, $\pi_{ij}$ with $\mu_{ij}$, $S_{low}$ with $S_{high}$, and $E_{low}$ with $E_{high}$. These constraints with Constraints (10)-(24) and (26) enforce that each edge is observed by at least one drone. Constraints (27) and (28) restrict that the requested photo quality at each target node and edge must be satisfied. Constraints (29) and (30) indicate that each drone should start and finish its travel at the depot. Constraints (31) are the flow conservation constraints. Constraints (32) update the arrival time of drone k at depot or point j if the drone travels from depot or point i to depot or point j. Constraints (33) obtain the completion time of all drone operations. Constraints (34) measure the battery level of drone k after its travel from depot or point i to depot or point j. Constraints (35) ensure that the next departure time of drone k is larger than its previous arrival time at depot and its required battery charging time. Constraints (36)-(37) are the binary and integer constraints.

# 4 Numerical Experiments

In this study, advantages of considering two altitudes for drone movements (LH case) are shown by contrasting it with their movements in the lower altitude only (L case), in which observations with high quality are assured. Comparison with cases in which the drones only travel at the higher altitude is not considered because in this case, the drones can only obtain photos with low quality and more travel time is required to visit the points at the higher altitude. Moreover, this case is already considered as a part of the LH case.

Two data sets with different characteristics are considered. Each data set consists of five instances. In the first and second data sets, four and five target nodes are observed, as shown in Table 1. In both sets, two drones are considered and each drone can travel twice. Required photo qualities for nodes and edges are randomly generated. Target points and edges that can be observed from points are preset. It is assumed that a drone
travels through an arc can observe the target edge below the travelled arc. Networks of target nodes and edges, and drones' travels for Instance 10 are presented in Fig. 1.

Parameters used in both experiments are listed as follows: $\lambda$ in Fig. 1 is 60° [7] and $f_{0,k}$ is 360 minutes [8]. The drones are considered to fly at 44 m and 70 m altitudes in order to perform observations on target nodes within a spherical area with radius of 14 and 22 meter from the observation point, as shown in Fig. 1. Values for $q_h$, $r_{qy}$, and $t_{ij}$ are randomly generated between 0 and 1, 0 and 1, and [7, 27] minutes, meanwhile values for $g_{ij}$ are assumed to be equivalent with $t_{ij}$. Value of $b$ is set to 1 minute. The MIP solutions are obtained using CPLEX 12.6.0. All experiments were performed on an Intel® Core™ i5-6400 CPU at 2.70 GHz with 8 GB RAM. Computational time for each instance is limited to 30 minutes. The experiment results are presented in Table 2. It is necessary to understand that optimal solutions in L cases are only optimal for the cases in which the lower altitude in the drone network is considered. In LH cases, drones visit more points at the higher altitude, which allows the drones to observe more target nodes and edges and reduces the total required travel times to observe all target nodes and edges, while satisfying the required photo qualities for target nodes and edges. The advantage of performing observation in lower and higher altitudes to reduce the total observation time is proven, with average gap equal to -4.6%, compared when the observations are performed only at lower altitude.

<table><caption>**Table 1.** Parameter settings for data sets</caption><thead><tr><th>Data set</th><th>Set of target nodes</th><th>Set of depot indices</th><th>Set of observation points at lower altitude</th><th>Set of observation points at higher altitude</th></tr></thead><tbody><tr><td>Data Set 1<br>(Instances 1-5)</td><td>{1,2,3,4}</td><td>{0,9}</td><td>{1,2,3,4}</td><td>{5,6,7,8}</td></tr><tr><td>Data Set 2<br>(Instances 6-10)</td><td>{1,2,3,4,5}</td><td>{0,11}</td><td>{1,2,3,4,5}</td><td>{6,7,8,9,10}</td></tr></tbody></table>

<table><caption>**Table 2.** Experiment results</caption><thead><tr><th>Instances</th><th>L</th><th>LH</th><th>Gap(%)</th></tr></thead><tbody><tr><td>1</td><td>93(Optimal)</td><td>93(UB), 1(LB)</td><td>0</td></tr><tr><td>2</td><td>163(Optimal)</td><td>163(UB), 1(LB)</td><td>0</td></tr><tr><td>3</td><td>155(Optimal)</td><td>147(UB), 1(LB)</td><td>-5.2</td></tr><tr><td>4</td><td>95(Optimal)</td><td>95(UB), 1(LB)</td><td>0</td></tr><tr><td>5</td><td>112(Optimal)</td><td>112(UB), 1(LB)</td><td>0</td></tr><tr><td>6</td><td>165(Optimal)</td><td>165(UB), 1(LB)</td><td>0</td></tr><tr><td>7</td><td>285(UB), 175(LB)</td><td>185(UB), 1(LB)</td><td>-35.1</td></tr><tr><td>8</td><td>136(Optimal)</td><td>145(UB), 1(LB)</td><td>6.6</td></tr><tr><td>9</td><td>126(Optimal)</td><td>126(UB), 1(LB)</td><td>0</td></tr><tr><td>10</td><td>165(Optimal)</td><td>145(UB), 1(LB)</td><td>-12.1</td></tr><tr><td>Average</td><td></td><td></td><td>-4.6</td></tr></tbody></table>
# 5 Conclusions

In this study, a multiple drone routing problem at two different altitudes are discussed. The drones perform observations of target nodes and edges that require minimum or maximum photo qualities. In addition, the drones have limited battery level and need to return to depot for a battery charging process. The objective was to minimize the total observation times. An MIP model was developed. Experiment results show the advantages of performing observations at two altitudes instead of only at the lower altitude. Efficient heuristic algorithms will be developed in the near future.

For further researches related with drone routing, a drone network design problem is necessary to be studied. In this drone network design, various decision variables can be considered, such as observation altitudes and horizontal positions of the observation points at each altitude. Finding the best observation altitude is also necessary to determine the best observation range and the appropriate altitude that allow the drones to visit those points, while performing the observations in a short time. Possible collisions between the drones must be avoided, especially if the visited points are located close to each other.

# References

1. Waharte, S., Trigoni, N.: Supporting search and rescue operations with UAVs. In: Proceedings of the International Conference on Emerging Security Technologies, pp. 142–147. IEEE Computer Society, Washington, DC, United States (2010). doi:10.1109/EST.2010.31

2. Damodaran, P., Krishnamurthi, M., Srihari, K.: Lower bounds for hierarchical chinese postman problem. International Journal of Industrial Engineering 15(1), 36–44 (2008).

3. Prins, C., Labadi, N., Reghioui, M.: Tour splitting algorithms for vehicle routing problems. International Journal of Production Research 47(2), 507–535 (2009). doi:10.1080/00207540802426599

4. Liu, T., Jiang, Z., Geng, N.: A memetic algorithm with iterated local search for the capacitated arc routing problem. International Journal of Production Research 51(10), 3075–3084 (2013). doi:10.1080/00207543.2012.753165

5. Chen, L., Chen, B., Bui, Q.T., Hà, M.H.: Designing service sectors for daily maintenance operations in a road network. International Journal of Production Research 55(8), 2251–2265 (2017). doi:10.1080/00207543.2016.1233363

6. Symington, A., Waharte, S., Julier, S., Trigoni, N.: Probabilistic target detection by camera-equipped UAVs. In: Proceedings of 2010 IEEE International Conference on Robotics and Automation, pp. 4076–4081. IEEE, Alaska, United States (2010). doi:10.1109/ROBOT.2010.5509355

7. Zorbas, D., Pugliese, L.D.P., Razafindralambo, T., Guerriero, F.: Optimal drone placement and cost-efficient target coverage. Journal of Network and Computer Applications 75, 16–31 (2016). doi:10.1016/j.jnca.2016.08.009

8. Donateo, T., Ficarella, A., Spedicato, L., Arista, A., Ferraro, M.: A new approach to calculating endurance in electric flight and comparing fuel cells and batteries. Applied Energy 187, 807–819 (2017). doi:10.1016/j.apenergy.2016.11.100