Optimal Deployment of Charging Stations for Aerial Surveillance by UAVs with the Assistance of Public Transportation Vehicles

Abstract

To overcome the limitation in flight time and enable unmanned aerial vehicles (UAVs) to survey remote sites of interest, this paper investigates an approach involving the collaboration with public transportation vehicles (PTVs) and the deployment of charging stations. In particular, the focus of this paper is on the deployment of charging stations. In this approach, a UAV first travels with some PTVs, and then flies through some charging stations to reach remote sites. While the travel time with PTVs can be estimated by the Monte Carlo method to accommodate various uncertainties, we propose a new coverage model to compute the travel time taken for UAVs to reach the sites. With this model, we formulate the optimal deployment problem with the goal of minimising the average travel time of UAVs from the depot to the sites, which can be regarded as a reflection of the quality of surveillance (QoS) (the shorter the better). We then propose an iterative algorithm to place the charging stations. We show that this algorithm ensures that any movement of a charging station leads to a decrease in the average travel time of UAVs. To demonstrate the effectiveness of the proposed method, we make a comparison with a baseline method. The results show that the proposed model can more accurately estimate the travel time than the most commonly used model, and the proposed algorithm can relocate the charging stations to achieve a lower flight distance than the baseline method.

1. Introduction

Among the various promising applications of unmanned aerial vehicles (UAVs), aerial surveillance is the one that has attracted the greatest attention in recent years; it can be used for the protection of assets, people or objects, the investigation of crimes, and intelligence gathering. Aerial surveillance systems based on UAVs have become increasingly mature in these application tasks. They are not only cost-efficient, but also demonstrate high reliability and security [1]. This kind of multi-robot system can quickly explore large areas, such as mountainous regions, that are hard to reach for humans. It can significantly reduce the labour cost [2]. Thus, they have become an advanced means with which to replace human beings, efficiently and safely, in repeated surveillance missions [3]. Another main advantage of using UAVs for surveillance is the high probability of having a line-of-sight (LoS) with ground objects, which may be difficult to achieve with ground-based sensing units [4]. Extensive research has been conducted on the topics relevant for aerial surveillance, such as UAV video/image processing [5,6,7] and the deployment of UAVs [8,9,10,11]. The video/image processing techniques provide the visual sensing information required in various applications, and the approaches to the deployment of UAVs enable UAVs to find optimal/sub-optimal positions from which to conduct surveillance.

Although UAVs can achieve a high surveillance performance compared to other existing means, a challenging issue is the constrained flight time. In general, most of the commercial UAV products are powered by an onboard battery. Since the payload of a UAV is limited, the onboard battery cannot be very large, which results in a limitation of the capacity. Without carrying any other payload, a typical DJI Matrice 600 Pro model can only fly for 40 minutes with a fresh battery [12]. While improving the battery capacity and efficiency is indeed a solution, some other solutions have been investigated to increase the flight duration of UAVs. One promising solution is to install solar panels, which would enable UAVs to harvest solar energy [13] for flight time improvement. However, it is difficult to apply in complex environments, such as urban environments, due to the presence of many buildings. These can create shadows, and when UAVs fly into the shadows, their energy-harvesting rate reduces significantly. Another approach considers the usage of mobile chargers [14,15,16]. This method provides UAVs with the opportunity to replenish their battery, and it is more reliable than the solar-power harvesting approach. These mobile chargers, which are usually carried by some ground vehicles, are also controllable. However, in urban environments, these vehicles may create other issues—for example, finding where to park. Moreover, these vehicles may further worsen congested roads, if widely used. To alleviate the drawback of using mobile chargers, a method exploiting public transportation vehicles (PTVs) such as buses, trams and trains has been proposed [17,18,19,20]. Similar to human transportation within a city, a UAV can also travel with these vehicles as a passenger (on the roof of the vehicles). Differently to the mobile-charger approach, PTVs are existing vehicles travelling within urban areas. As such, this approach does not introduce extra vehicles to congested roads. When travelling with these vehicles, a UAV can simply turn off the motors to save energy. Thus, this approach has the potential to significantly improve the effective flight distance of UAVs.

We consider the example of using UAVs to survey several sites in a large-scale area. Practical applications include information broadcasting when wireless communication infrastructures are down, security/policing, traffic management, and parcel delivery [21,22]. We can classify the sites into three groups, based on their locations. The first group consists of sites that are within the flight range of UAVs departing from their depot. Any site in this group can be surveyed by a UAV without any other support. Roughly speaking, the sites in this group are located within a disk centred at the depot (see Figure 1); we call these sites the close sites. The second group consists of the sites that cannot be reached directly by UAVs from their depot, but can be reached with the support of PTVs. These sites are close to the routes of PTVs. If we assume that the UAVs can only leave and return to PTVs when the latter stops, and that the energy consumption when travelling with PTVs is negligible, the sites in the second group are roughly within the disks centred at these stops (see Figure 1). The sites in the second group are called relatively far sites. The sites in the third group are those cannot be reached, even with the support of PTVs. In other words, these sites are outside of the disks centred at the depot and the stops; see Figure 1. These are called far sites.

In this paper, we pay special attention to the surveillance of far sites, and we propose an approach that exploits PTVs and charging stations. In this approach, it is required to compute the travel time of UAVs from the depot to the sites. The travel time can be divided into two parts: one is the time spent travelling with PTVs, and the other is time spent travelling, with utilisation of the deployed charging stations, to reach the sites themselves. Considering that the travel time of PTVs is uncertain (due to various road traffic conditions), we can use the Monte Carlo method [23] to estimate the expected travel time with PTVs. Special attention is then paid to the deployment of charging stations. We propose a new coverage model to compute the travel time when UAVs travel through the charging stations to reach the sites. With this model, we formulate the optimal deployment problem with the goal of minimising the average travel time of UAVs from the depot to the sites, which can be regarded as a reflection of the quality of surveillance (QoS) (the shorter the better). We then propose a sub-optimal algorithm that relocates the charging stations iteratively. We show that this algorithm ensures that any movement of a charging station leads to a decrease in the average travel time of UAVs. To demonstrate the effectiveness of the proposed method, we make a comparison with a baseline method. The results show that the proposed model can more accurately estimate the travel time than the commonly used model, and the proposed algorithm can relocate the charging stations to achieve a lower flight distance than the baseline method.

The main contributions of this paper are summarised as follows:

• A new coverage model that can compute the travel time of UAVs from the depot to the sites more accurately than the commonly used model.
• A sub-optimal deployment method that guarantees that any relocation of a charging station leads to a decrease in the average travel time of UAVs.

The rest of the paper is organised as follows. Section 2 discusses the relevant publications, and we sketch where this paper stands in the literature. Section 3 introduces the system model and formulates the studied problem. Section 4 presents the proposed charging station deployment methods. Section 5 presents simulation results to demonstrate the effectiveness of the proposed methods. Finally, Section 6 concludes the paper and presents future research directions.

2. Related Work

In this section, we review the relevant publications and clarify the difference between the current paper and existing work.

There is a rich literature on UAV-based aerial surveillance on various types of targets, ranging from stationary areas to moving objects such as vehicles and humans [4,8,9,11]. For stationary areas, interesting theoretical research results have been presented in [8] for the deployment of UAVs to monitor objects in a given bounded area. An asymptotically optimal deployment, based on construction, is presented, which guarantees a minimum number of UAVs required to fully monitor the area of interest. For moving targets, with local knowledge but no global information, only locally optimal coverage of the moving targets can be achieved [11].

The problem considered in this paper relates to charging facility deployment for electric vehicles [24] and patrol station deployment for conventional vehicles. In general, the deployment of such facilities takes into account geographical conditions, because the facilities are relatively large. Alternatively, geographical conditions may not be necessary in the deployment of charging stations for UAVs—since such a charging station is small [25], it can even be deployed by roads. Charging facilities for electric vehicles are usually deployed in redundancy. That is, a charged electric vehicle can travel a distance that is much longer than the average distance between two charging facilities. Such redundancy is generally due to competition between different suppliers. In contrast, we deploy the charging stations for UAVs in a way that does not lead to unnecessary redundancy.

A UAV can either recharge or replace its battery at a charging station. It can then fly further, either to continue its current mission or to conduct other missions. Targeting the parcel-delivery application, the authors of [26] focus on a UAV station deployment problem. They consider a scenario where the customers are located far from a warehouse. A single UAV station is equipped with a fleet of UAVs, and it can be activated by the arrival of a truck that has parcels to be delivered. Then, the UAVs deliver the parcels to customers. The reference [27] formulates a charging station deployment optimisation problem with the goal of maximising the coverage of customers in a given area following the mixed-integer programming framework. A heuristic algorithm is presented for the setting where the feasible positions of charging stations are given by a discretised set. The work in [28] considers a similar problem, but the objective is to minimise the total system cost, including the charging stations, UAV ownership, service congestion, etc. In a different approach to [27,28], the paper [29] considers the deployment of charging stations in a continuous space, and a decentralised method is presented which can achieve the locally optimal coverage of customers. Targeting the application of inspecting a given set of sites, the reference [30] considers deploying charging stations at some sites so that a UAV can complete all the inspection tasks using the smallest amount of time; the authors additionally pay attention to the route planning problem for the UAV.

The problem that we will consider relates to the coverage control problem. Coverage control is a type of system partitioning and is an interesting problem in coordinated networks of mobile robots for environmental monitoring. A network of mobile robots is required to cover a region so that the event detection rate is maximised or the detection time is minimised [31]. The region of interest is often partitioned into a number of sub-regions (which is equal to the number of robots), and the robots can be optimally deployed in each sub-region [32]. Researchers have also investigated the coverage control for a group of heterogeneous robots [33]. The deployment of charging stations for UAVs shares the spirit of coverage control, in that all the sites in the area of interest should be reachable from at least one charging station. However, in the charging station deployment problem, the objective is to minimise the average time to reach the sites from the depot. Thus, the charging station deployment problem has a tree-like structure, while the general coverage control problem can be fully distributed.

In a different, yet related context, i.e., UAV video/image processing, existing publications have studied processing the videos taken by UAVs when they are at some fixed position. From simple to complex, several typical problems have been investigated, such as road detection [34], vehicle detection and tracking [35], and traffic parameter extraction [36]. Popular methods include the use of convolutional neural networks (CNNs) [37] to analyse individual frames, as well two consecutive frames, of a UAV’s footage [38]. However, these approaches are only suitable for the case where the UAV can hover at a certain attitude. Indeed, this state is often difficult to achieve, especially when there is a wind gust. To address this, some researchers have investigated the ego-motion issue as generated either intentionally, by a remote operator, or as an external factor, such as caused by the wind. The first approach to this problem is called the image registration [39]. This is a method that attempts to turn the moving background into a fixed background, which allows traditional methods for background subtraction to be used. The second approach is based on optical flow [40], which extracts the motion pattern from videos and is often combined with unsupervised learning for estimating the UAV ego-motion. Thus, the video/image processing approaches provide fundamental application-dependent sensing information.

3. Problem Statement

We consider an aerial surveillance system with several key components: a depot, a fleet of UAVs, a set of sites, PTVs, and charging stations. The UAVs are energy-constrained. We assume that a PTV can accept one UAV on its roof. The sites to be surveyed are distributed in an urban area, and they are classified into three groups as discussed in Section 1. We only focus on the surveillance of the sites in the third group.

Table A1. Main symbols used in the paper.

Symbol	Meaning
D	Depot of UAVs
R	Flight distance corresponding to half of the onboard battery
n	Number of charging stations to be deployed
$p_i$	Location of charging station i
S	The set of sites to be surveyed
s	Position of site s
G	Graph formed by vehicle stops, depot, sites and charging stations
${\rho }_s\left(t\right)$	The probability that the site s needs to be surveyed at time t of a day
${\lambda }_s$	The weight of site s
$\tau (u,v,t)$	Travel time from node u to node v when the UAV starts at time t
${\mathcal{T}}_s(p_1,\dots ,p_n)$	The average travel time of UAV to survey site s

summarises the main symbols used in the paper.

The problem under investigation is the optimal deployment of charging stations, so that the sites of interest can be surveyed by UAVs in the shortest time (a reflection of the QoS). In particular, we consider a remote area that contains a vehicle stop. Departing from the depot (denoted by D), a UAV can reach this stop by boarding some number of PTVs. We focus on deploying a number n of charging stations in this remote area. For simplicity, an additional charging station (denoted by $p_0$) is deployed at the vehicle stop. Suppose that a fully charged battery allows a UAV to fly for a distance of $2R$. The charging station at the vehicle stop serves the sites in a circular area centred at $p_0$ of radius R—see the blue area in Figure 1. Then, our focus is on finding locations for the other n charging stations. Let $p_1,\dots ,p_n$ denote the locations of these n charging stations, which are to be decided. It is worth pointing out that this paper focuses on the high-level planning problem. The relevant low-level control issues, such as the UAV dynamics, the accuracy of UAV positioning and landing, and external disturbances (gust and wind) are not considered in the paper.

The public transportation network, the depot, the deployed charging stations, and the sites form a graph, which can be used to plan paths for UAVs to survey the sites. Let $G(V,E)$ denote this graph. The vertex set V consists of the depot D, the vehicle stops, charging stations $p_1,\dots ,p_n$, and the sites. The edge set E contains directed links from one stop node to another, representing public transportation services between them. It also contain undirected links between any two stop nodes, any two charging station nodes, and any pair of a charging station node and a site node—these represent UAV flight between these locations. It is worth mentioning that if two charging station nodes $p_i$ and $p_j$ ($i\ne j,i,j\in [0,n]$) are connected in the graph G, we have

$$|p_i,p_j|\le 2R,$$

(1)

where $|·,·|$ gives the standard Euclidean distance between two points. It is also worth mentioning that any site node is connected to a charging station node within range R. Note that the flight range R corresponds to flight along straight lines. If a UAV encounters some obstacle, such as a building, this straight line assumption is not valid. However, we can avoid this issue by setting the flight altitude to be higher than any local buildings.

Moreover, a site node can be connected with another charging station node if the sum of distances to the two charging station nodes is no larger than $2R$. In the example shown in Figure 2, the top site $s_1$ only connects with the charging station node $p_2$, while the bottom site $s_2$ connects with the charging station nodes $p_1$ and $p_2$. We note that if a site connects with two charging stations, it is located inside an ellipse with these charging stations as the foci and passes the intersection points of the circles centred at these charging stations of radius R; see Figure 2. In the graph G, a site is reachable from any charging station connecting with the site. In Figure 2, $s_1$ can be reached from the charging station $p_2$, while $s_2$ can be reached from the charging stations $p_1$ and $p_2$. Constructing the graph G in this way leads to a shorter delivery time for sites such as $s_2$ in Figure 2. If $s_2$ is not connected with $p_1$, but only with $p_2$, in the graph G, a UAV has to fly to $p_2$ and then to $s_2$. Certainly,

$$|p_1,p_2|+|p_2,s_2|\ge |p_1,s_2|.$$

(2)

Note that connecting $s_2$ with $p_1$ does not mean that we can disconnect $s_2$ and $p_2$. The link between $s_2$ and $p_2$ is necessary, as it enables the UAV to return after completing the delivery. This is because,

$$|p_1,s|+|s,p_2|\le 2R.$$

(3)

Let S denote the set of sites in the area of interest. Let ${\rho }_s\left(t\right)$ denote the probability that a request to survey site $s\in S$ is placed at time t of a day. This probability is highly application-dependent and can be easily obtained from historical data. Let $t_s$ and $t_f$ be the earliest time and the latest time of placing a survey request, respectively. Then, we have ${\int }_{t_s}^{t_f}{\rho }_s\left(t\right)dt=1$. In addition, let ${\lambda }_s$ be the weight of the site $s\in S$. This weight is the frequency of surveying the site. For two sites, the weight of the more important site is larger, and as such it needs to be surveyed more frequently than the other. We assume that both the probability and the weight of a site are known.

We now introduce a function, $\tau (u,v,t)$, which computes the shortest travel time from node $u\in V$ to node $v\in V$ when a UAV departs from node u at time t. If the nodes u and v are not connected, neither directly nor via any other nodes in G, $\tau (u,v,t)=\infty ,\forall t$. In practice, the travel time of an edge in the graph G can be different at different times. Even at the same time on different days, the duration of travel can be different due to the stochastic nature of public transportation networks. Since the travel time of the shortest path between two nodes may vary over time and be uncertain, so too for the graph G. The time-variance of G can be reflected by the timetables of public transportation services. The uncertainty of these services, due to factors such as congestion, can be modelled as random noise. We follow the label-setting algorithm used in [20] to construct the shortest path between two nodes, and then adopt Monte Carlo simulations [23] to account for the uncertainty. The Monte Carlo method is an ideal method for computing probabilities and expectations when the analytical integration is impossible or impractical. Although the Monte Carlo estimation is not exact, we understand that when a sufficiently large number of random variables are generated, the error of approximation can become arbitrarily small. In the considered context, by generating a sufficient number of simulations, we can obtain the mean travel time between nodes u and v for a particular starting time t. Without introducing a new symbol, we use $\tau (u,v,t)$ in the rest of the paper to represent this mean travel time. We consider that a UAV replaces its battery at a charging station, and that the charging stations organise the charging of the used battery during spare time. Since the time for such a replacing operation can be much shorter than the flight time between two charging stations or the travel time between two vehicle stops, it is assumed to be negligible.

With this function, we can represent the average time required to survey a site when departing from the depot. Specifically, the average time for a UAV to reach a site s, when the UAV leaves the depot at time t, can be represented by $\tau (D,s,t)$. As the starting time, i.e., the time a site surveillance request is activated, may be uncertain, we consider the mathematical expectation of the average travel time for surveying site s, which is denoted by ${\mathcal{T}}_s(p_1,\dots ,p_n)$ and is given as follows:

$${\mathcal{T}}_s(p_1,\dots ,p_n)={\int }_{t_s}^{t_f}{\rho }_s\left(t\right)\tau (D,s,t)dt.$$

(4)

Here, $[t_s,t_f]$ is the time window during which a site surveillance request can be activated. Note that the average travel time for a site s, i.e., ${\mathcal{T}}_s(p_1,\dots ,p_n)$, is now represented by a function of the locations of charging stations, i.e., $p_1,\dots ,p_n$. It is also worth noting that such an average travel time also depends on the edges in G, which represent the public transportation services. The reason for not including this factor as an adjustable variable is that the public transportation services are not controllable by a supplier. Instead, from the point of a supplier, only the locations of the charging stations, i.e., $p_1,\dots ,p_n$, can be controlled.

Problem Statement: The charging station deployment problem aims to find the locations of the charging stations, i.e., $p_1,\dots ,p_n$, that minimise the weighted average travel time of the sites. It can be formulated as follows:

$$\underset{p_1,\dots ,p_n}{min}\sum _{s\in S}{\lambda }_s{\mathcal{T}}_s(p_1,\dots ,p_n).$$

(5)

There are some constraints that the deployment needs to satisfy. Firstly, any site s must be covered by at least one charging station, i.e.,

$$|s,p_i|\le R,\exists i\in [1,n],\forall s\in S.$$

(6)

Moreover, every charging station is connected with $p_0$, i.e.,

$$\tau (p_i,p_0,0)<\infty ,\forall i\in [1,n].$$

(7)

Note that in (7) we can set the time, i.e., the third entry of the function $\tau (u,v,t)$, as any value—not only zero.

Remark 1.

Note that for a site, the charging station that covers it is not necessarily on the shortest path for a UAV to serve it. For example, in Figure 2, a UAV serves the site $s_2$ via $p_1$, not $p_2$. Connecting $s_2$ with $p_2$ enables the UAV to return after completing the delivery, because $|p_1,s|+|s,p_2|\le 2R$. Moreover, constructing the graph G in the aforementioned way leads to a shorter travel time for sites such as $s_2$ in Figure 2. We can imagine that if $s_2$ is not connected with $p_1$, but only with $p_2$, in the graph G, a UAV has to fly to $p_2$ and then to $s_2$. This would lead to a longer travel time; see (2). This issue requires us to clarify the charging station via which each site is surveyed by a UAV in the shortest time.

4. Proposed Method

In this section, we discuss the proposed method to address the problem presented by (5)–(7). We start with the introduction of two basic concepts used throughout the development of our approach (Section 4.1). Then, we propose the deployment method for the simple case with a single charging station (Section 4.2), then for the complex case with multiple charging stations (Section 4.3).

4.1. Coverage Models

We introduce the following two fundamental concepts.

Definition 1

(The charging stations that cover a site). A site s is said to be covered by a charging station $p_i$ if one of the below two conditions holds:

• The distance between the site s and the charging station $p_i$ is no more than R, i.e., $|p_i,s|\le R$ [41].
• There exists another charging station $p_j$ such that the summation of the distances between the two charging stations and the site is no greater than $2R$, i.e., $|p_i,s|+|p_j,s|\le 2R$.

Definition 2

(The charging station to survey a site). A site s is said to be surveyed from a charging station $p_i$ if the charging station $p_i$ is the last charging station on the shortest path from the depot to the site s in the graph G.

From the above two definitions, we can see that there may exist multiple charging stations that cover a site. However, generally, there is only one charging station surveying a site, since the charging station that surveys a site should be the last one on the shortest path–see Definition 2. We also understand that the charging station via which a site is surveyed also covers the site. However, the charging station that covers a site is not necessarily the one via which to survey the site. Typical examples are given in Figure 2. The site $s_1$ is covered by the charging station $p_2$, and the site $s_2$ is covered by the charging stations $p_1$ and $p_2$. The site $s_1$ is surveyed via the charging station $p_2$ (the only charging station that covers $s_1$), while the site $s_2$ is surveyed via the charging station $p_1$ (one of the charging stations that cover $s_2$).

Definition 1 reveals an interesting and useful property. That is, if a site is located within an ellipse formed by two charging stations (with the positions of the two charging stations as the foci, and with the ellipse passing the intersection points of the two R-radius circles that centred at the charging stations), this site can be covered by more than one charging station. Again, taking Figure 2 as an example, site $s_2$ is inside such an ellipse (see the red one around $p_1$ and $p_2$), while site $s_1$ is not. Thus, site $s_2$ is covered by two charging stations.

It should be pointed out that Definition 1 is superior to other existing definitions, which are based on only the first condition of Definition 1 (see [41] and the references therein), with respect to the travel time of a UAV from the depot to a site. This is crucial when the site is located within one of the aforementioned ellipses, i.e., being covered by more than one charging station, because the second condition promises to result in a shorter path through which a UAV can conduct the surveillance mission. In particular, if only the first condition of Definition 1 is considered, the site $s_2$ in Figure 2 is covered by the charging station $p_2$. Then, when we plan the path for a UAV to survey the site $s_1$, we will find the path $D\to \cdots \to p_0\to p_1\to p_2\to s_2$. However, with the second condition of Definition 1, the site $s_2$ is also connected with $p_1$ in the graph G. Thus, the path for a UAV can be $D\to \cdots \to p_0\to p_1\to s_2$. Clearly, $|p_1,p_2|+|p_2,s_2|\ge |p_1,s_2|$, where the equality holds only when $s_2$ is located on the line segment connecting $p_1$ and $p_2$. With Definition 2, no matter how many nodes are connected to a site s in the graph G, we can deduce the charging station via which to survey the site.

In the subsequent sections, we will use these definitions to develop our approach for deploying charging stations.

4.2. Deployment of a Single Charging Station

In this section, we present the method for deploying a single charging station.

As mentioned in Section 3, $p_0$ has already been deployed at a vehicle stop near the area of interest. Thus, we consider the deployment of the second charging station $p_1$. One necessary assumption in this simple scenario is that the sites to be surveyed are located somewhere such that there exist feasible positions for the second charging station to serve the sites. Otherwise, there is no solution to the deployment problem. A geometric view of this assumption is that the sites are close to a vehicle stop, and they are not distributed very sparsely. Moreover, there are some sites that are outside the disk with radius of R centred at $p_0$. Otherwise, the charging station $p_0$ is sufficient to serve them.

Given the positions of $p_0$ and $p_1$, we first construct the circles centred at $p_0$ and $p_1$ with the radius of R, which are denoted by $O_0$ and $O_1$, respectively. As discussed in Section 4.1, we can construct an ellipse with $p_0$ and $p_1$ as the foci which passes through the intersections of the circles $O_0$ and $O_1$—see Figure 3. Such an ellipse divides the disk centred at $p_1$ into two parts. The first one is the part inside the ellipse, denoted by A—see the yellow part in Figure 3. The second one is the part outside the ellipse, denoted by B—see the blue part in Figure 3. By Definition 1, the sites in A are covered by both $p_0$ and $p_1$, while those in B are only covered by $p_1$. For the sites in A, according to Definition 2, it is $p_0$ that serves them, while for those in B, it is $p_1$ that serves them.

For a site $s\in A$, the average travel time can be computed by:

$$\begin{array}{cc}\hfill {\mathcal{T}}_s\left(p_1\right)& ={\int }_{t_s}^{t_f}\tau (D,p_0,t)dt+{\int }_{t_s}^{t_f}{\rho }_s\left(t\right)|p_0,s|dt\hfill \\ \hfill & ={\int }_{t_s}^{t_f}\tau (D,p_0,t)dt+|p_0,s|.\hfill \end{array}$$

(8)

In (8), ${\mathcal{T}}_s\left(p_1\right)$ is the average flight time from the depot D to site $s\in A$. We only take $p_1$ as an input, since we consider the deployment of this single charging station. $\tau (D,p_0,t)$ is the travel time from the depot D to the charging station $p_0$ when the UAV departs at time t. Then, ${\int }_{t_s}^{t_f}\tau (D,p_0,t)dt$ gives the mathematical expectation of this travel time. Moreover, ${\int }_{t_s}^{t_f}{\rho }_s\left(t\right)|p_0,s|dt=|p_0,s|$, because $|p_0,s|$ is independent of time t and ${\int }_{t_s}^{t_f}{\rho }_s\left(t\right)dt=1$.

Similarly, for a site $s\in B$, the average travel time can be computed by:

$$\begin{array}{cc}\hfill {\mathcal{T}}_s\left(p_1\right)& ={\int }_{t_s}^{t_f}\tau (D,p_0,t)dt+{\int }_{t_s}^{t_f}{\rho }_s\left(t\right)\left(\right|p_0,p_1|+|p_1,s\left|\right)dt\hfill \\ \hfill & ={\int }_{t_s}^{t_f}\tau (D,p_0,t)dt+|p_0,p_1|+|p_1,s|.\hfill \end{array}$$

(9)

Then, the weighted average travel time for all sites in S is given by:

$$\begin{array}{cc}\hfill & \frac{1}{\left|S\right|}(\sum _{s\in A}{\lambda }_s({\int }_{t_s}^{t_f}\tau (D,p_0,t)dt+|p_0,s\left|\right)+\sum _{s\in B}{\lambda }_s({\int }_{t_s}^{t_f}\tau (D,p_0,t)dt+|p_0,p_1|+|p_1,s|))\hfill \\ \hfill =& {\int }_{t_s}^{t_f}\tau (D,p_0,t)dt+\frac{1}{\left|S\right|}(\sum _{s\in A}{\lambda }_s|p_0,s|+\sum _{s\in B}{\lambda }_s\left(\right|p_0,p_1|+|p_1,s\left|\right))\hfill \end{array}$$

(10)

From (10) we can see that, given the first charging station $p_0$, the weighted average travel time for the sites in S only depends on the position of the second charging station $p_1$, since the mathematical expectation of the travel time from the depot D to $p_0$ is fixed when given $p_0$ and G.

Therefore, the problem of deploying one charging station is reformulated as:

$$\underset{p_1}{min}\frac{1}{\left|S\right|}(\sum _{s\in A}{\lambda }_s|p_0,s|+\sum _{s\in B}{\lambda }_s\left(\right|p_0,p_1|+|p_1,s\left|\right))$$

(11)

subject to

$$|s,p_1|\le R,\forall s\in S.$$

(12)

It should be pointed out that we only need to consider the sites that are outside the circle $O_0$. The reason is that, given $p_0$, the travel time for the sites in $O_0$ is known, which does not need to be optimised.

The main difficulty in addressing the above problem lies in its discontinuity. The variable $p_1$ not only determines the flight time in part B, but also impacts the parts A and B. $p_1$ is defined in a continuous space. A small change of $p_1$ may lead to different parts A and B, which may result in a large jump in terms of the travel time. Consider a site that is on the boundary of A and B. In this case, the site belongs to part A. However, when we move $p_1$ a small amount, it is possible that this site falls into part B. Clearly, this creates a jump in the travel time of this site, which further leads to a discontinuity in the overall weighted travel time.

To address the problem, we reformulate it as an integer linear problem (ILP). Suppose there is a set of candidate positions where we are allowed to deploy the charging station. Let $C=\{c_1,c_2,\dots ,c_m\}$ denote such a set. Let $x_k$ be a binary variable. $x_k=1$ if the charging station is located at the candidate $c_k$; $x_k=0$ otherwise. Moreover, given these candidates, we can constructs the parts A and B correspondingly. For the candidate $c_k$, let $A_k$ and $B_k$ denote the corresponding parts. Then, the problem is formulated as follows:

$$\underset{x_1,\dots ,x_m}{min}\sum _{k=1}^m{x}_k(\sum _{s\in A_k}{\lambda }_s|p_0,s|+\sum _{s\in B_k}{\lambda }_s\left(\right|p_0,p_1|+|p_1,s\left|\right))$$

(13)

subject to

$$\sum _{k=1}^m{x}_k=1,$$

(14)

$$x_k\in \{0,1\},\forall k=1,\dots ,m.$$

(15)

It is worth pointing out that the above formulation constraint (12) has already been taken into account in the process of constructing the parts $A_k$ and $B_k$. If a candidate position cannot enclose all the sites to be surveyed, it has already been removed from the candidate list.

Now, the problem is in the well-known form of an ILP, and many existing solvers are available for this purpose.

4.3. The Deployment of Multiple Charging Stations

In this section, we focus on the more challenging scenario with n charging stations, i.e., $p_1,\dots ,p_n$.

Suppose the charging stations are initially deployed at $p_1,\dots ,p_n$, and the two aforementioned conditions hold, i.e., all the sites are covered by at least one charging station (see (6)), and each charging station is connected with $p_0$ (see (7)). With these assumptions, we can construct a tree structure for the charging stations, including $p_0$. In particular, $p_0$ is the root of this tree, and any other vertex connects with $p_0$ via the shortest path. This is the so-called minimum spanning tree. For any vertex j in the tree, let $P_j$ denote the shortest path from the root $p_0$ to vertex j. Clearly, this path gives the shortest travel time for UAVs. Moreover, let $|P_j|$ denote the number of vertices on this path, and let $P_j\left[k\right]$ denote the kth vertex on the path. In particular, $P_j\left[1\right]=p_0$, and $P_j\left[\right|P_j\left|\right]=p_j$. With this symbol, the requirement that any charging station must connect with $p_0$ can be formulated as:

$$|P_j\left[k\right],P_j[k+1]|\le 2R,\forall k=1,\dots ,|P_j|-1.$$

(16)

Moreover, let $\varphi \left(j\right)$ denote the parent vertex of vertex j on the path $P_j$. It is clear that in the minimum spanning tree, any vertex other than the root has a unique parent vertex, while each vertex may have more than one child vertex. Let $\psi \left(j\right)$ denote the set of child vertices of vertex j.

Now, for any pair of child-parent vertices, we can construct the corresponding ellipse following the method discussed in Section 4.2. It is worth pointing out that there always exists such an ellipse for a pair of child-parent vertices if their distance is less than $2R$. For the extreme case, i.e., their distance equals $2R$, such an ellipse reduces to a line segment connecting the child and parent charging stations. Similarly to Section 4.2, let $O_j$ and $O_{\varphi \left(j\right)}$ denote the circles centred at $p_j$ and $p_{\varphi \left(j\right)}$ of radius R, respectively. Let $A_{\varphi \left(j\right)j}$ and $B_{\varphi \left(j\right)j}$ denote the two parts of $O_j$ separated by the ellipse constructed from $p_j$ and $p_{\varphi \left(j\right)}$, see Figure 4.

For the sites in the part of $A_{\varphi \left(j\right)j}$, the travel time for UAVs is broken down into three legs:

• from D to $p_0$,
• from $p_0$ to $p_{\varphi \left(j\right)}$,
• from $p_{\varphi \left(j\right)}$ to the sites.

For the sites in the part of $B_{\varphi \left(j\right)j}$, the travel time for UAVs is broken down into four legs:

• from D to $p_0$,
• from $p_0$ to $p_{\varphi \left(j\right)}$,
• from $p_{\varphi \left(j\right)}$ to $p_j$.
• from $p_j$ to the sites.

Similarly to Section 4.2, we only pay attention to the travel time from $p_0$ to the sites. For ease of presentation, let $F_1(p_0,p_{\varphi \left(j\right)})$ denote the travel time from $p_0$ to $p_{\varphi \left(j\right)}$. Let $S_j$ denote the subset of sites within the circle $O_j$. Let $F_2(p_{\varphi \left(j\right)},p_j)$ be the average travel time from $p_{\varphi \left(j\right)}$ to the sites in $S_j$. Then, we have

$$F_2(p_{\varphi \left(j\right)},p_j)=\frac{1}{|S_j|}(\sum _{s\in A_{\varphi \left(j\right)j}}|p_{\varphi \left(j\right)},s|+\sum _{s\in B_{\varphi \left(j\right)j}}\left(\right|p_{\varphi \left(j\right)},p_j|+|p_j,s\left|\right)).$$

(17)

The deployment of multiple charging stations can then be obtained by solving the below problem:

$$\underset{p_1,\dots ,p_n}{min}\frac{1}{n}\sum _{j=1}^n\left(F_1(p_0,p_{\varphi \left(j\right)})+F_2(p_{\varphi \left(j\right)},p_j)\right).$$

(18)

Clearly, (18) gives the average travel time of UAVs from $p_0$ to the sites.

The direct method to solve the above problem is to convert the problem to its discrete version, as used for the simple case with just one charging station. However, such a method may not greatly simplify the problem—in addition to the variables that decide which candidate locations are chosen for charging station deployment, we must also introduce variables to satisfy the connectivity requirement for each charging station. Clearly, this will make the corresponding ILP contain much more variables; as such, an existing ILP solver may take a very long time to finish analysing the problem. We therefore present a sub-optimal method that can solve the problem quickly.

We observe that the movement of a vertex in the constructed tree influences the travel time to the sites covered by itself, its child, and its downstream vertices. However, this movement does not impact that of the sites covered by upstream vertices. Thus, moving a vertex only affects the travel time of the sites covered by its branch; we will call the vertex that we consider the sub-root of the branch. Another observation is that the vertices in a branch can be classified into two groups: the neighbour vertices of the sub-root, that are directly connected with the sub-root (this group includes the sub-root itself); and the non-neighbour vertices, that are not connected with the sub-root directly. For non-neighbour vertices, the movement of the sub-root only affects the first part in (18), but not the second part. We can call this impact the indirect impact. For the neighbour vertices, the movement of the sub-root affects both parts in (18). In this case, the impact is named the direct impact. In the method to be presented, we relocate a vertex by taking into account both its direct and indirect impacts. In particular, a vertex is relocated to another position if the overall impact provides a decrease in the average travel time to the sites in its branch. We move the vertex to the position that can obtain the maximum decrease in the average travel time.

As per our discussion, the relocation of a leaf vertex (a vertex that does not have any child vertices ) can be achieved using the method discussed in Section 4.2 because a leaf vertex’s movement only impacts the sites covered by itself. However, the relocation of a non-leaf vertex is complex. To present the relocation method for the latter case, we need to introduce some more symbols. Let $N_i$ denote the number of the sites in the branch of vertex i which are indirectly impacted by vertex i. Let $G_i$ denote the average travel time from vertex i to these sites. If i is a leaf vertex or the parent of a leaf vertex, $N_i=0$ and $G_i=0$, because the sites in the branch of vertex i are all directly impacted by vertex i. Let $H_1\left(p_j\right)$ denote the average travel time from the parent of vertex j, i.e., $\varphi \left(j\right)$, to all the indirectly impacted sites in the branch of vertex j. If ${\sum }_{i\in \psi \left(j\right)}{N}_i=0$, $H_1\left(p_j\right)=0$; otherwise, $H_1\left(p_j\right)$ is computed as follows:

$$H_1\left(p_j\right)=\frac{{\sum }_{i\in \psi \left(j\right)}{N}_i(G_i+|p_i,p_j|+|p_j,p_{\varphi \left(j\right)}\left|\right)}{{\sum }_{i\in \psi \left(j\right)}{N}_i}.$$

(19)

In (19), the term $G_i+|p_i,p_j|+|p_j,p_{\varphi \left(j\right)}|$ gives the average travel time from vertex $\varphi \left(j\right)$ to the sites in the branch of vertex i (where $i\in \psi \left(j\right)$) that are indirectly impacted by vertex j. Clearly, $H_1\left(p_j\right)$ is a function of $p_j$, and other information in (19), including $N_i$, $G_i$, and $p_{\varphi \left(j\right)}$, is known if the downstream vertices and the parent vertex are fixed.

Let $H_2\left(p_j\right)$ be the average travel time from vertex $\varphi \left(j\right)$ to the sites that are in the branch of node j and are directly impacted by vertex j. These sites include the ones covered by vertex j and the child vertices of vertex j. The number of the sites is $|S_j|+{\sum }_{i\in \psi \left(j\right)}\left|S_i\right|$. Then, $H_2\left(p_j\right)$ is computed as follows:

$$\begin{array}{cc}\hfill H_2\left(p_j\right)=& \frac{1}{|S_j|+{\sum }_{i\in \psi \left(j\right)}\left|S_i\right|}[\sum _{s\in A_{\varphi \left(j\right)j}}|p_{\varphi \left(j\right)},s|+\sum _{s\in B_{\varphi \left(j\right)j}}\left(\right|p_{\varphi \left(j\right)},p_j|+|p_j,s\left|\right)+\hfill \\ \hfill & \sum _{i\in \psi \left(j\right)}\left(\sum _{s\in A_{ji}}|p_j,s|+\sum _{s\in B_{ji}}\left(\right|p_j,p_i|+|p_i,s\left|\right)+\sum _{s\in S_i}|p_j,p_{\varphi \left(j\right)}|\right)].\hfill \end{array}$$

(20)

The term ${\sum }_{S\in A_{\varphi \left(j\right)j}}|p_{\varphi \left(j\right)},s|+{\sum }_{s\in B_{\varphi \left(j\right)j}}\left(\right|p_{\varphi \left(j\right)},p_j|+|p_j,s\left|\right)$ in (20) gives the total travel time from vertex $\varphi \left(j\right)$ to the sites in $S_j$. The term ${\sum }_{s\in A_{ji}}|p_j,s|+{\sum }_{s\in B_{ji}}\left(\right|p_j,p_i|+|p_i,s\left|\right)+{\sum }_{s\in C_i}|p_j,p_{\varphi \left(j\right)}|$ in (20) gives the total travel time from vertex $\varphi \left(j\right)$ to the sites in $S_i$, where $i\in \psi \left(j\right)$. Clearly, $H_2\left(p_j\right)$ is a function of $p_j$, and other information in (20) is known if the downstream vertices and the parent vertex are fixed. Differently from $H_1\left(j\right)$, which can be zero, $H_2\left(j\right)>0$, because there exists a subset of sites that are directly impacted by vertex j. If this subset is empty, there is no need to have vertex j.

Let $H\left(p_j\right)$ denote the average travel time from vertex $\varphi \left(j\right)$ to all the indirectly and directly impacted sites covered by vertex j. Then,

$$H\left(p_j\right)=\frac{\left(\right|S_j|+{\sum }_{i\in \psi \left(j\right)}|S_i\left|\right)H_2\left(p_j\right)+{\sum }_{i\in \psi \left(j\right)}{N}_i{H}_1\left(p_j\right)}{|S_j|+{\sum }_{i\in \psi \left(j\right)}\left|S_i\right|+{\sum }_{i\in \psi \left(j\right)}{N}_i}.$$

(21)

Moreover, the average travel time from vertex 0 to all the sites in the branch of vertex j is given by $L(p_0,p_{\varphi \left(j\right)})+H\left(p_j\right)$, where $L(p_0,p_{\varphi \left(j\right)})$ denotes the travel time from vertex 0 to vertex $\varphi \left(j\right)$. If at any time we only move one vertex in the constructed tree, say vertex j, for the purpose of reducing the average travel time, we only need to consider $H\left(p_j\right)$, because $L(p_0,p_{\varphi \left(j\right)})$ is fixed. Therefore, we can relocate $p_j$ to a new place that minimises (21), provided that the topology of the constructed tree remains and vertex j does not lose any of its covered sites.

Moreover, since the values of N and G are required in the computation of $H_1\left(p_j\right)$ in (19), we need a general formula for them to relocate each node in a decentralised manner. Given the values of N and G of the child vertices of vertex j, we can compute these values for vertex j as follows:

$$N_j=\sum _{i\in \psi \left(j\right)}(N_i+\sum _{k\in \psi \left(i\right)}|S_k\left|\right),$$

(22)

$$\begin{array}{cc}\hfill G_j=\frac{1}{N_j}& \sum _{i\in \psi \left(j\right)}\left(N_i(G_i+|p_i,p_j\left|\right)+\sum _{s\in A_{ji}}|p_j,s|+\sum _{s\in B_{ji}}\left(\right|p_j,p_i|+|p_i,s\left|\right)\right).\hfill \end{array}$$

(23)

The values of N and G propagate in upstream order. For a certain vertex, these values can be computed once those of its child vertices have been computed.

Now, we have enough symbols to present our method. Suppose that at the initial positions $p_1,\dots ,p_n$, the n charging stations cover all the sites in S. We construct the minimum spanning tree for the vertices with $p_0$ as the root. Assume that all the edges in the tree are not longer than $2R$. With the initial positions, we can compute the subset of sites covered by each vertex. The main procedure of our method repeatedly relocates the vertices in sequence. When we relocate a vertex, the relocation of all its child vertices needs to be performed beforehand. In the case where two sibling vertices are to be relocated, either of them can be relocated first. With this rule, we start the relocation from the leaf vertices and then up to their parents. Specifically, for a leaf vertex, we find the position for this vertex as discussed in Section 4.2. For a non-leaf vertex, we find the position for the vertex by minimising (21) so that the topology of the constructed tree does not change when the vertex is moved, and the vertex does not lose any sites. After the relocation, the values of N and G of this vertex are updated by (22) and (23). After the relocation of all the nodes, we update the subset of sites covered by each vertex, as well as the sets A and B. These procedures repeat until the vertices can no longer be moved. The termination condition is that all the vertices stay at the previous positions in one round of relocation. This method is summarised in Algorithm 1.

Algorithm 1 Relocating the vertices in the minimum spanning tree

Input: $p_0,p_1,\dots ,p_n$      Output: $p_1,\dots ,p_n$ 1: Construct the minimum spanning tree with $p_0,p_1,\dots ,p_n$ by taking $p_0$ as the root. 2: Compute the subset of sites covered by each vertex. 3: Construct a relocating sequence. 4: while Termination condition is unsatisfied do 5:     for Each vertex j in the sequence do 6:         if Node j is a leaf vertex then 7:            Find the new position by solving the problem (13) subject to (14) and (15). 8:            $N_j\leftarrow 0$, $G_j\leftarrow 0$. 9:         else 10:            Find the new position by minimising (21) subject to that the topology of the tree does not change when vertex j relocates, and vertex j does not lose any sites. 11:            Update $N_j$ and $G_j$ by (22) and (23). 12:         end if 13:     end for 14:     Update the subset of sites covered by each vertex. 15: end while

For a given set of sites, Algorithm 1 ensures that any movement of a vertex leads to a lower average travel time; we prove this as follows. Algorithm 1 consists of two main procedures. One is the relocation of vertices in sequence, and the other is the update of customers covered by each vertex. For the former, we only relocate one vertex at any time, and we relocate it only if the average travel time reduces for downstream sites impacted by the vertex. As analysed above, such a relocation does not influence upstream sites. Thus, the relocation procedure ensures the decrease in the average travel time. Regarding the latter, for the given locations of any pair of parent-child vertices, the proposed grouping model ensures that any site can be served, and that the travel time for any customer is the lowest. Therefore, Algorithm 1 relocates the vertices to positions with a lower average travel time.

5. Simulation Results

In this section, we demonstrate the effectiveness of the proposed algorithms via several typical case studies.

We first show the superiority of the coverage models proposed in Definitions 1 and 2. To better understand the performance, we compare with a baseline method, which groups the sites based on the shortest distance between sites and charging stations, and then moves the charging station to the mass centre of the sites [41]. We consider two simple cases with one charging station to be deployed with some randomly placed sites in Figure 5 and Figure 6. Here, $R=15$ km. The resulting positions for the charging station found via the proposed method and the baseline method are shown. In the case shown in Figure 5, the average travel distance of the UAV from $p_0$ to the sites is 26.2 km for the proposed method. Given a certain flight speed, we can acquire the corresponding travel time. For the same set of sites, the average travel distance achieved by the baseline method is 30.8 km. In the case shown in Figure 6, the proposed method achieves an average travel distance of 21.7 km, while for the same set of sites, the baseline method achieves an average travel distance of 26.6 km. For these cases, we can see that the proposed coverage model leads to a shorter travel distance than the baseline method.

We also consider some complex cases with more charging stations, and the results are shown in Figure 7 and Figure 8. In Figure 7, we deploy four charging stations using both the proposed method and the baseline method. From the initial positions shown in Figure 7a, these two methods relocate the charging stations to those shown in Figure 7b,c, respectively. Figure 7d shows the average travel distance of UAVs from $p_0$ to the sites. Clearly, the proposed method achieves an average lower travel distance. We can also see a similar result in Figure 8.

6. Conclusions

In this paper, we considered an approach that exploits PTVs and charging stations to improve UAV flight time. In this approach, a UAV first travels with some PTVs, and then flies through any required charging stations to reach the remote sites to be surveyed. The travel time with PTVs can be estimated using the well-known Monte Carlo method. We mainly investigated the deployment problem of charging stations, which assist UAVs to conduct aerial surveillance. We proposed a new coverage model, which is based on elliptical regions. This model can accurately characterise the travel time of UAVs through the deployed charging stations. Based on such a model, we formulated the deployment problem and proposed a sub-optimal method. This is an iterative method, and we proved that, in each round of relocation, the average travel time of UAVs reduces. The effectiveness of the proposed method has been verified via computer simulations. One limitation of the current approach is that we relocate a charging station by numerically evaluating the candidate sites. An interesting and useful future research direction is to study the analytical solution to this issue.