Optimal Placement of UAVs to Provide Surveillance Coverage for a Ground Vehicle in a Collaborative Search-and-Rescue Operation

1.

Introduction

This research is oriented to a scenario where a swarm of UAVs provides persistent surveillance coverage for a ground vehicle (Figure 1) in a collaborative search-and-rescue mission. The ground vehicle needs to detect and overcome multiple environmental complications, e.g., road conditions, obstacles, moving objects, and other contingent situations, and to detect and locate rescue targets [1, 2]. If deployed alone, the ground vehicle has a limited sensing capability due to the limited detection range of sensors and obstructions by surrounding objects [1, 2]. Sensing from the air and being able to cover a larger ground area by collaboration [3–5], the UAVs can support the ground mission by conducting continuous surveillance around the ground vehicle to inform road and weather conditions, alert to contingent and dangerous conditions, and detect humans who need help, etc. This can vastly extend the sensing capability of the ground vehicle and largely improve the efficiency and safety of the mission [4, 5]. Meanwhile, the ground vehicle can serve as a supporting unit for the UAVs, carrying them to the regions of interest and functioning as a service hub for recharging and replacing the UAVs. This can largely enhance the persistence of UAV operations [5].

One effective strategy to provide persistent UAV surveillance coverage for the navigating ground vehicle is to initially form a UAV coverage around the ground vehicle at the starting point and then control the UAV formation to follow the moving ground vehicle. The work of this paper focuses on the formation of UAV coverage for the ground vehicle and introduces an approach to determine an optimal placement of UAVs for seamless surveillance coverage around the ground vehicle, with a comprehensive consideration of the energy efficiency, sensing capability, positioning constraint, communication range, and availability of UAVs.

The collaboration between UAVs and ground vehicles has attracted substantial research efforts recently, categorized as drone-truck combined operations (DTCO) [6, 7]. The most researched DTCO application is the delivery of items using a drone-truck delivery system, where the associated research problems are mainly the traveling salesman problem with drones (TSPD) and vehicle routing problem with drones (VRPD) [6, 7]. Research has also been carried out in the context of area coverage. Mathew et al. studied the problem of path planning for unmanned ground vehicles (UGVs) to recharge UAVs following pre-planned surveillance paths, modeling it using a partitioned directed acyclic graph and solving it using the approaches of integer linear programming and graph transformations [8, 9]. In a DTCO scenario, where a UGV carried a UAV to a set of locations and the UAV took off at each location to do a local area coverage, Tokekar et al. modeled the UAV path planning problem using a metric graph and solved it as an orienteering problem [10]. Sujit et al. discussed a DTCO operation involving a team of autonomous underwater vehicles (AUVs) and a UAV [11], where the AUVs carried out the exploration mission and periodically surfaced to communicate with the UAV which flew over the AUVs and served as a messenger between them and a base station.

More references on area coverage using UAVs are found in the context of optimizing the placement of UAVs carrying cameras/sensors to monitor targets or cover an area on the ground (Table 1). Pugliese et al. considered the number of UAVs and total energy consumption as cost metrics, formulated the problem using an integer linear model and a mixed integer non-linear optimization model, and solved it using the heuristic algorithms including C-SDLP, K-means, C-MDLP, and L-MDLP [12, 13]. With the objective to minimize the number of UAVs, Saeed et al. formulated an oriented line segment coverage (OLSC) problem and solved it using the greedy approximation approach [14]. Hammond et al. determined the optimal locations for the smallest set of cameras monitoring all the points using the set-covering algorithms including traditional greedy, reverse greedy, carousel greedy, linear programming, particle swarm optimization (PSO), simulated annealing, genetic, and ant colony optimization [15]. To optimally deploy a set of UAVs to monitor agricultural fields, Issad et al. formulated a constrained multi-objective optimization problem to minimize energy consumption, maximize total coverage, maintain connectivity, and minimize overlaps, and solved it using the heuristic algorithms including multi-objective artificial bee colony, multi-objective PSO, non-dominated sorting genetic algorithm II, strength Pareto evolutionary algorithm II, and non-dominated sorting genetic algorithm III [16]. Cao et al. targeted the maximization of coverage rate, point-level clarity, uniform clarity, and resource utilization rate of a UAV camera network, and planned the 3D placement of those UAVs using an improved constrained two-archive evolutionary algorithm [17]. Wang and Gu used an adaptive multiple pruning search method based on a grid model of the target area to solve for the 2D placement of a set of UAVs that maximized the coverage of the given area [18]. To achieve a tradeoff between the signal coverage and interference for using UAVs to inspect a pipeline network, Ma et al. determined the number and 3D placement of UAVs using a two-phase evolution algorithm based on a 3D pipeline graph model [19]. Munawar et al. used the PSO algorithm to plan the 2D placement of a given number of drones that maximized the number of covered targets [20].

The optimal deployment of UAVs is also a major research problem associated with the application of UAVs to provide communication network coverage for users and stations on the ground (Table 2). Huang and Savkin determined the 2D placement of a set of drones that maximized the coverage of users subject to the constraint of communication range, based on the graphs of communication connectivity and locations [21]. Huang et al. extended their work to the 3D placement of UAVs subject to the constraints of safe positions and quality of service, using a greedy algorithm on the discretized 3D space [22]. Reina et al. used a multi-layout multi-subpopulation genetic algorithm to solve for the placement of a set of UAVs, in order to provide optimal network coverage for a given number of ground nodes with a consideration of maximum coverage, fault tolerance, and redundancy [23]. Sawalmeh et al. used the Circle Packing Theory to determine the optimal placement for a swarm of UAVs that maximized the coverage area and coverage density [24]. Chou et al. targeted the maximization of total amount of data transmitted by UAVs with a consideration of the trade-off among flight altitude, energy expense, and travel time, and solved for the deployment of UAVs using Lagrangian dual relaxation and a heuristic approach using interior-point and subgradient projection methods [25]. To deploy a number of UAVs as aerial base stations (ABSs) to provide network coverage for user equipment (UEs), Hydher et al. determined the optimal positions of UAVs and assignment of UEs to each ABS that maximized the total spectral efficiency of the network while maintaining a minimum quality of service requirement, using K-means clustering and a stable marriage approach [26]. To use UAVs to provide wireless coverage for Voice over WiFi service to a set of ground users, Mayor et al. determined the optimal placement of UAVs that minimized the ratio between the number of UAVs and energy efficiency, using the genetic algorithm and PSO [27]. To use UAV small cells (UAV-SCs) to augment or temporarily restore service to an ultra-dense cellular network, Zamani et al. formulated an optimization problem to minimize the overall power consumption of the network by jointly optimizing the number of UAV-SCs, their placement, associations, and the power allocation, subject to user quality of service, transmit power, and front haul capacity constraints, and solved it using a metaheuristic method based on PSO [28]. Zhang and Duan used binary search and dynamic programming algorithms to determine the optimal deployment for a number of UAVs that maximized the minimum leftover energy storage among all the UAVs after their deployment, to provide wireless coverage to ground users [29]. With the purpose of utilizing a limited number of UAVs to improve the performance of aerial mesh networks, considering target coverage, quality of service, and energy consumption, Gupta and Varma formulated a multi-objective optimization problem and solved it using the metaheuristic-based algorithms including multi-objective PSO, non-dominated sorting genetic algorithm II, strength pareto evolutionary algorithm 2, and pareto envelope-based selection algorithm II [30]. Shakoor et al. determined the 2D placement of a given number of UAVs at a computed optimal altitude that maximized the number of users served by UAV base stations subject to the constraints of path-loss compensation factor, minimum mean and edge throughput, ABS height, and transmit power budget, using a modified K-means algorithm [31]. Valiulahi and Masouros planned the horizontal positions of a set of UAVs using a mean-shift algorithm and the altitudes using a successive convex approximation algorithm, with the objective of maximizing the system throughput of each user [32]. Ye et al. determined the 3D placement of a set of UAVs that maximized the network throughput subject to the constraints of locations, UAV-device associations, scheduling, communication, and time, using a Dinkelbach-based algorithm [33]. Zhong et al. targeted to maximize the number of served users subject to user data-rate requirements and base station capacity limit, and determined the number and horizontal positions of UAVs using the genetic algorithm [34]. Chen et al. planned the 2D placement of a set of UAVs that maximized the user coverage, using an algorithm based on PSO and virtual repulsive force [35]. Liu et al. planned the horizontal positions of a given number of UAVs using a proximal stochastic gradient descent based alternating algorithm, with the objective to maximize the fair coverage versus energy consumption subject to the backhaul constraints [36]. Mayor et al. determined the 3D placement of drones that minimized the number of drones subject to the constraints of coverage and service quality, using the PSO algorithm [37]. Wang et al. determined the horizontal positions of a given number of UAVs using a virtual force field based algorithm and the altitudes using the PSO algorithm, with the objective to maximize the total network throughput [38].

The work of this paper targets a novel application of DTCO search-and-rescue mission and emphasizes continuous and seamless area coverage around a ground vehicle. This imposes new challenges in formulating and solving the research problem of finding an optimal deployment, including both the number and positions, of UAVs to provide surveillance coverage. The cited references on coverage using UAVs are effective in providing solutions to their specific optimization problems associated with their specific applications respectively. However, a vast majority of them deal with covering discrete targets or discretized spaces [12–15, 17–23, 25–28, 30–38], where the ways of formulation and solution provide inspiration but cannot be adopted directly by the work of this paper which deals with continuous and seamless area coverage. Meanwhile, those references which deal with continuous area coverage focus on finding optimal placement of a given number of UAVs [16, 24, 29], while the work of this paper is to find both the optimal number and positions of UAVs to form the coverage. Finding the optimal positions of a given number of UAVs is a fixed-length optimization problem, where the number of input variables is constant during the search process. Most existing optimization algorithms deal with fixed-length problems. Finding both the optimal number and positions of UAVs is a variable-length optimization problem, where the number of input variables is variable during the search process. Such a problem is more challenging to solve. Some studies, which deal with the minimization of the number of UAVs, formulate their optimization problems into fixed-length problems based on the definition of a binary association function between the UAVs and targets [12, 13, 28]. Though this approach works effectively with discrete targets, it is not directly applicable to the continuous area coverage problem of this study.

This study addresses the challenge and develops an effective approach for determining the optimal number and positions of UAVs in order to provide continuous and seamless UAV surveillance coverage around a ground vehicle. The main contributions of this study are summarized as follows:

• The research problem of planning the deployment of UAVs, associated with the novel application of DTCO search-and-rescue mission, is modeled as a new constrained variable-length optimization problem. This optimization problem determines the optimal number and 3D positions of UAVs that minimize energy consumption in deploying and collecting those UAVs, subject to a comprehensive set of constraints on the operations of UAVs, at both individual and swarm levels, specifically including the available number of UAVs, permissible range of UAV altitude, allowable energy consumption for deploying and collecting each UAV, communication ranges of UAVs and ground vehicle, safety distance between UAVs for collision and interference avoidance, and seamless coverage.

• A bi-layer optimization solution process is proposed to solve the formulated constrained variable-length optimization problem, with an outer layer searching through the allowable numbers of UAVs and an inner layer searching for the optimal positions for each specific number of UAVs. The optimal number and positions of UAVs are chosen by comparing among those solutions for different numbers of UAVs. This bi-layer strategy provides an effective algorithmic framework, which can work with any suitable fixed-length optimization algorithm on the inner layer, for solving the targeted variable-length optimization problem. This study specifically chooses the genetic algorithm (GA) as the inner layer algorithm to work with the bi-layer process. This combination provides an effective optimization algorithm for this constrained variable-length optimization problem.

• The proposed optimization formulation and solution approach is validated through a simulation study. The simulation settings, including the UAV energy constants, visibility angle, altitude, and communication range, adopt the representative realistic values from the cited literature, as shown in a later section of this paper.

The remaining parts of this paper are organized as follows. Section 2 presents the formulation of the associated optimization problem. Section 3 discusses the solution procedure of the optimization problem. Section 4 deals with the simulation results. Section 5 concludes the study and discusses the future work.

2.

Formulation of optimization problem

In order to form an efficient and reliable UAV swarm surveillance coverage around a ground vehicle, an optimization problem is formulated with the objective of finding an optimal deployment of UAVs from the perspective of energy efficiency, subject to the relevant constraints in UAV positioning, communication, and coverage.

The research problem is defined with the following assumptions:

• The involved UAVs are homogenous, with the same capabilities of kinematics, sensing, communication, and energy.

• The involved UAVs are modeled as point UAVs with omni-directional flight capability, which applies to a wide range of helicopter-like single-rotor and multi-rotor UAVs.

• The ground vehicle has sufficient energy capacity to support the ground mission and provide recharging or replacement to UAVs.

• Each UAV is fully charged when it leaves the ground vehicle.

• The region of interest does not interfere with no-fly zones.

• A desirable ground coverage is specified as a circular area centered at the ground vehicle.

In this research, an effective deployment of UAVs means a number of UAVs being placed for seamless surveillance coverage over a ground area with a desirable radius around the ground vehicle. Here, the desirable radius of coverage is denoted by R_desirable, the number of UAVs used is denoted by N, and the position of the ith UAV is represented using the polar coordinates p_i =  (r_i, 𝛼_i, z_i), where r_i denotes the radial coordinate, 𝛼_i denotes the angular coordinate, and z_i denotes the altitude of the UAV. The positions of UAVs are defined in the reference frame centered at the ground vehicle, where the ground vehicle is located at the origin with the polar coordinates (0, 0, 0).

Each UAV has a finite energy capacity. With less energy spent in deploying and collecting a UAV, more energy is available for the UAV to carry out its service activities including flight, hovering, sensing, and wireless communication. From the perspective of energy efficiency, a deployment of UAVs which requires the minimal amount of energy for the UAVs to fly to their monitoring positions for surveillance and fly back to the ground vehicle for recharging or replacement is considered an optimal deployment. Thus, the optimization problem takes the following objective function

where N^∗ denotes the optimal number of UAVs used, denotes the optimal position of the ith UAV, and E_{overhead, i} denotes the overhead energy consumption for the deployment and returning of the ith UAV. To estimate E_{overhead, i} for the purpose of planning the placement of UAVs, it is assumed that a UAV will fly to its monitoring position from the ground vehicle by first climbing to the altitude z_i vertically and then translating to the position (r_i, 𝛼_i) horizontally, and return to the ground vehicle by first translating to the position (0, 0) horizontally and then descending to the ground vehicle at the altitude 0. Thus, E_{overhead, i} can be represented as where E_{asc, i} denotes the energy consumed by the ith UAV during the ascending process, E_{des, i} denotes the energy for descending, and E_{trans, i} denotes the energy for translation. In particular, E_{trans, i} is doubled in Equation (2) to account for a UAV flying to its monitoring position and returning to the ground vehicle. It is also assumed that the UAV will travel horizontally and vertically at constant speeds, though the horizontal speed and vertical speed can be different. Accordingly, it is considered that E_{trans, i}, E_{asc, i}, and E_{des, i} are linear functions of the UAV traveling distances in the associated directions at constant speeds [26, 29, 39, 40], and ascending consumes more energy than descending [40]. Thus, they can be formulated as where 𝜂_trans, 𝜂_asc, and 𝜂_des denote the UAV energy consumption per distance for translation, ascending, and descending respectively. In accordance with Equations (2) and (3), E_{overhead, i} is thus considered a function of the monitoring position of the ith UAV relative to the ground vehicle, i.e. E_{overhead, i}(p_i), as indicated in Equation (1). While the objective function is defined as minimizing the total overhead energy consumption of the UAVs used to form the surveillance coverage around the ground vehicle, it also implies using fewer UAVs if possible because less total overhead energy consumption is expected with fewer UAVs.

Moreover, the optimization problem is subject to several constraints which can be categorized into the bounds for the input variables and constraints defined upon the input variables. The bound constraints for the input variables include:

• The allowable range for the number of UAVs in use, N ∈ [N_min, N_max]: This constraint sets the bounds of search for the number of UAVs used for surveillance coverage. The upper bound N_max is defined by the number of available UAVs. The lower bound N_min is defined by rounding the ratio between the area of the desirable coverage around the ground vehicle and the maximal area of coverage by one UAV.

• The allowable range for the position of a UAV, p_i: The altitude of a UAV should be kept within the range, i.e. z_i ∈ [h_min, h_max], where the lower bound h_min and upper bound h_max are specified mainly with a consideration of the balance between the size and resolution of UAV surveillance coverage. The horizontal position of a UAV should be inside the desirable radius of coverage, i.e. r_i ∈ [0, R_desirable] while 𝛼_i ∈ [0, 360°]. This constraint with the polar coordinates is more convenient to the optimization problem, compared with the corresponding nonlinear constraint that would result from the Cartesian coordinates. These bound constraints in r_i, 𝛼_i, and z_i set the basic search range for the positions of UAVs.

The constraints defined upon the input variables include:

• The constraint on the allowable overhead energy consumption for each UAV, E_{overhead, i} ≤ E_omax: Besides the energy consumed for deploying and returning, each UAV should reserve enough energy for service activities. This constraint enforces that in the resulting deployment, each UAV should have enough energy for service, by limiting its overhead energy consumption. The upper bound of the allowable overhead energy consumption E_omax for a UAV is usually set as a percentage of the total energy capacity E_cap of a UAV, i.e. E_omax = p% ∗ E_cap. By representing E_{overhead, i} as a function of the monitoring position of a UAV in accordance with Equations (2) and (3), this constraint can be written as

  (4)
  Benefitting from the adoption of the polar coordinates, the overhead energy consumption of a UAV becomes a linear function of its altitude z_i and radial coordinate r_i.

• The constraint on the communication ranges among the UAVs and ground vehicle: Communication connectivity is needed for data transfer and coordination among the UAVs and between the UAVs and ground vehicle. The wireless communication range of a UAV or ground vehicle is always limited. To efficiently use UAVs for surveillance coverage, a networking strategy is adopted, where each UAV forms communication links with only a few closest neighbors which include other UAVs and/or the ground vehicle. In this way, the UAVs do not need to stay within the communication range of the ground vehicle and thus can spread out to form larger coverage, while the communications between the ground vehicle and farther UAVs are accomplished through networking. Accordingly, those UAVs in the neighborhood of the ground vehicle should connect to the ground vehicle, i.e.

  (5)
  where A_GV denotes the neighborhood of the ground vehicle, R_UAV−GV denotes the smaller between the communication range of the ground vehicle and that of a UAV; moreover, each UAV should connect to the other UAVs inside its own neighborhood, i.e.
  (6)
  where A_i denotes the neighborhood of the ith UAV, and R_UAV denotes the communication range of a UAV. Equation (6) indicates that this constraint is nonlinear.

• The constraint on the distance between UAVs for collision and interference avoidance: In order to avoid collisions, aerodynamic interference, and communication interference among UAVs, a constraint on the horizontal distance between any two neighboring UAVs is considered as

  (7)
  where d_min denotes the minimum permissible horizontal distance between UAVs. Equation (7) indicates that this constraint is nonlinear.

An additional constraint that the optimization problem is subject to is the seamlessness of the resulting surveillance coverage. The ground coverage of a UAV is considered to be related to its altitude [13, 14, 16, 24] as

where R_i denotes the radius of the ground coverage of the ith UAV, and 𝜃 is the cone angle known as the visibility angle which defines the field of view of a UAV. While the desirable ground coverage C_desirable is a circular area centered at the ground vehicle with a radius of R_desirable, the resulting coverage C_i of the ith UAV is a circular area on the ground centered at the horizontal position of the UAV with a radius of R_i. By considering C_desirable and C_i as sets of positions on the ground, this constraint can be written as

To summarize, the optimization problem of finding an optimal deployment of UAVs subject to the relevant constraints is defined as

subject to

3.

Solution of optimization problem

Algorithm 1 proposes a procedure structure to solve the optimization problem formulated in the previous section, for a seamless UAV swarm surveillance coverage around a ground vehicle with the consideration of energy efficiency and the relevant constraints in UAV positioning, communication, and coverage.

The goal of the optimization procedure is to find the optimal number and positions of UAVs seamlessly covering the desirable area around the ground vehicle. Thus, both the number of UAVs and positions of UAVs are input variables to the objective function, as shown in Equation (10). However, because the number of position variables for UAVs is determined by the number of UAVs, the total number of input variables is not pre-defined for the optimization procedure. This situation makes it challenging to use the number of UAVs and associated position variables as a whole set of input variables in a single optimization algorithm, due to the fact that most optimization algorithms only work with a fixed number of input variables. To deal with this situation, the proposed optimization procedure adopts a bi-layer hierarchical structure, consisting of an outer and inner layer. On the outer layer, the procedure iterates through an allowable range of numbers of UAVs, i.e. N ∈ [N_min, N_max]; on the inner layer, for each specific number of UAVs, N, with the corresponding specific number of position variables, , the procedure seeks the optimal positions for those UAVs. On completing the bi-layer process, the ultimate optimal number, N^∗, and positions of UAVs, , are picked through comparison of solutions for different numbers of UAVs. Of the constraints included in Equation (11), the search range for the number of UAVs is applied to the outer layer of the optimization procedure in search of the optimal number of UAVs, while the others are applied to the inner layer in search of the optimal positions of a specific number of UAVs.

On the inner layer of the optimization procedure, the optimal positions of a specific number of UAVs are searched for to minimize the total overhead energy consumption of those UAVs subject to the constraints in Equation (11). Local optimization algorithms including nonlinear programming [41] and pattern search [42] were tested initially. Starting the search from an initial guess of the values of the input variables, these local optimization algorithms turned out to have relatively low time complexity but very often failed to find feasible solutions which satisfy all the constraints. This situation is attributed to the high dimensionality of the solution space and the high complexity of the constraints. In particular, the implementations of those constraints on the communication range (defined by Equations (5) and (6)), collision and interference avoidance distance (defined by Equation (7)), and seamless coverage (defined by Equation (9)) are highly complex. Constraints (5), (6), and (7) depend on the recognition of neighboring UAVs, while Constraint (9) cannot be directly represented as a function of the input variables. This situation increases the complexity of the optimization problem. To deal with this issue, a global optimization algorithm—genetic algorithm (GA) [43] was also tested. Compared to local optimization algorithms, GA starts the search from a population of randomly generated candidate solutions and had much better performance in obtaining feasible solutions which satisfy all the constraints, though with higher time complexity. Thus, in this study, GA is adopted as the optimization algorithm on the inner layer of the proposed optimization procedure.

Moreover, the positions of UAVs resulting from the inner-layer optimization algorithm such as GA may indicate the existence of redundancy in the number of UAVs. This redundancy is reflected by the fact that some UAVs are placed at the lower-bound altitude (i.e. z_i = h_min) and their ground coverages are completely contained by the other UAVs’ ground coverages. This is because the input number of UAVs, N, is higher than the number of UAVs that the optimization algorithm finds necessary. The proposed optimization procedure uses a post-process after the optimization algorithm on the inner layer to check the individual ground coverage associated with each resulting UAV position and eliminate redundant UAVs. The remaining number of non-redundant UAVs and their optimal positions make a valid solution. Accordingly, the total overhead energy consumption for this valid solution is re-estimated for those non-redundant UAVs only. After the optimization procedure collects the valid solutions throughout the allowable range of the input number of UAVs (i.e. ∀N ∈ [N_min, N_max]), they are compared according to the total overhead energy consumption, and the one with the minimal total overhead energy consumption is chosen as the optimal solution.

During the optimization procedure, the implementation of the seamless coverage constraint (Equation (9)) requires to check in each iteration if the union of the ground coverage of UAVs provides a seamless coverage of the desirable area around the ground vehicle. It would be highly challenging to implement, if the desirable coverage and individual UAV coverages are treated as continuous areas, due to the lack of methods to represent the union of continuous areas, which could be a highly irregular shape and/or disconnected, as well as checking the overlap of continuous areas with irregular shapes. To deal with this issue, the proposed optimization procedure discretizes the desirable and individual coverage areas, and checks the seamlessness of the resulting coverage during each iteration by checking if any grid element inside the desirable coverage is not covered by any UAV. This turns out to be an effective and conceptually simple approach. Similarly, during the post-process of the inner layer, the redundancy of a UAV is determined by checking if all the grid elements inside the individual UAV coverage are covered by other UAVs.

4.

Simulation results and discussions

The proposed optimization procedure for planning the optimal deployment of UAVs to provide seamless surveillance coverage around a ground vehicle is programmed and tested using MATLAB.

The settings of the simulation include:

• UAV energy terms: In accordance with [29, 39], the UAV energy consumption constant for horizontal translation is set to be 𝜂_trans = 21. 6 kWh/m, the energy consumption constant for ascending 𝜂_asc = 5𝜂_trans, and the UAV energy capacity E_cap = 0.777 kWh; in accordance with [40], the energy consumption constant for descending is set to be 𝜂_des =  𝜂_asc∕4; moreover, the maximum permissible overhead energy consumption for each UAV is set to be E_omax = 20%E_cap.

• UAV field of view: In accordance with [16, 30], the visibility angle of UAVs is set to be 𝜃 = 60°.

• UAV altitude: In accordance with [25, 27], the lower and upper bounds of UAV altitude are set to be h_min = 10 m and h_max = 50 m respectively.

• Communication range of UAVs and ground vehicle: In accordance with Wi-Fi (IEEE 802.11), the communication ranges of the ground vehicle and UAVs are set to be R_UAV = R_GV = 50 m. In this simulation, each vehicle is required to maintain communication connection with at least 2 nearest neighbors.

• Safety distance between UAVs: To avoid collisions, signaling interference, and wind effects, the minimum permissible horizontal distance between UAVs is set to be d_min = 10 m.

• Target ground coverage: The desirable coverage around the ground vehicle is set to be a circular area centered at the ground vehicle with a radius of R_desirable = 30 m.

• Search range for the number of UAVs: The number of available UAVs is set to be N_max = 15; the lower bound N_min is determined by rounding up the ratio between the desirable coverage area and the maximum coverage area by one UAV, i.e.

  (12)
  and thus N_min = 2 with the above-set values of R_desirable, h_max, and 𝜃.

With the above simulation settings, the optimization procedure iterates through a sequence of N from 2 to 15. For each N, the inner-layer GA algorithm searches for the optimal positions of N UAVs that minimize the total overhead energy consumption and satisfy all the constraints in Equation (11); then the post-process checks and eliminates the redundant UAVs whose ground coverage are contained by other UAVs. Table 3 reports the resulting effective number of UAVs and associated total overhead energy consumption for each iteration after the redundant UAVs are eliminated.

It is noticeable from Table 3 that, for several iterations, the situation of no feasible solution is reported, which means that GA fails to find an optimal solution for the positions of those N UAVs that satisfies all the constraints. The possible reasons causing this situation include:

• When N is at the lower bound N_min, e.g. N = 2 in this simulation, though the total area of the maximum individual ground coverages of those UAVs is mathematically equal to or greater than the area of the desirable ground coverage, those UAVs may not be able to make their coverages seamless while satisfying the other constraints such as the safety distance. This means that there is truly no feasible solution available.

• More often, when N is sufficiently large to provide seamless coverage under the constraints applied, e.g. N ≥ 3 in this simulation, GA still reports no feasible solution. It is known that, as N increases, the dimensionality of the solution space increases (the number of UAV position variables increases by 3 when N increases by 1), and the optimization problem has a higher number of local minima. Moreover, complex constraints such as communication range, safety distance, and seamless coverage largely enhance the complexity of the constrained solution space, and the complexity of those constraints also increases as N increases. In such a situation, even a global optimization algorithm like GA converges from time to time to a local minimum which may not satisfy all the constraints.

The situation of convergence to local minima is also observed from those iterations with feasible solutions in Table 3. By comparing among the resulting valid solutions with only non-redundant UAVs and associated total overhead energy consumptions, it is clear that, in this simulation, it is sufficient to use 3 UAVs to provide seamless coverage over the desirable area with a minimum total overhead energy consumption. This solution is obtained when N = 4, by eliminating a redundant UAV. However, the other iterations with feasible solutions end up with more UAVs even after the redundant UAVs are removed. Moreover, a general trend is that the valid solution tends to have a higher number of non-redundant UAVs as N increases. This situation reflects that, due to the high complexity of the optimization problem, GA tends to converge to a local minimum, and, as N increases, the dimensionality of the solution space increases and so does the number of local minima.

During each outer-loop iteration of the optimization procedure, GA searches for the optimal positions of a specific number N of UAVs that minimize the total overhead energy consumption subject to the involved constraints. If GA finds N UAVs are more than sufficient, even when converging to a local minimum, its output indicates the redundancy in the number of UAVs. Such a redundancy is reflected by two factors:

• The ground coverage of a redundant UAV is completely covered by the other UAVs;

• A redundant UAV is placed at the lowest permissible altitude h_min in order to minimize its overhead energy consumption.

Figures 2 and 3 present two examples of such redundancy for N = 7 and 10, respectively. Correspondingly, the resulting positions of UAVs are reported in Tables 4 and 5, respectively. It is clear from the figures and tables that those redundant UAVs are placed at the lowest permissible altitude (z_i = h_min = 10 m in this simulation), and correspondingly, their ground coverages are minimal (with a radius R_i = 5.77 m calculated from Equation (8)), which are contained by the ground coverage of the other UAVs. Because redundant UAVs do not add more coverage, they are removed from the planning result, to reduce the number of UAVs used and total overhead energy consumption. This is reflected by the difference between the iterated N and resulting number of non-redundant UAVs N_NR in each iteration as reported in Table 3.

As indicated in Table 3, in this simulation, the resulting optimal coverage, which has the minimal total overhead energy consumption and satisfies all the involved constraints, is provided by 3 UAVs. Figure 4 shows the resulting ground coverage by these UAVs, and Table 6 presents the resulting optimal positions of the UAVs. Compared with the desirable coverage around the ground vehicle, these UAVs provide seamless coverage, as shown in Figure 4. Moreover, it is verified that the resulting positions of UAVs satisfy all the constraints, as shown in Table 6. This simulation provides a validation of the proposed formulation and solution approach for planning an optimal placement of UAVs to provide seamless surveillance coverage around a ground vehicle.

5.

Conclusion and future work

The problem of optimal placement of UAVs for seamless surveillance coverage around a ground vehicle in a collaborative search-and-rescue operation is being studied. A new constrained variable-length optimization problem is formulated to determine the optimal number and positions of UAVs, with a comprehensive consideration of DTCO, energy efficiency, seamless coverage, and positioning and communication constraints. A novel bi-layer optimization process is introduced to provide an algorithmic framework which works with fixed-length optimization algorithms to solve variable-length optimization problems. The bi-layer process, along with the genetic algorithm provides an effective optimization algorithm to solve the targeted constrained variable-length optimization problem, by checking the optimal placements for different numbers of UAVs and picking the best solution with the best energy efficiency. The proposed optimization formulation and solution approach is validated through a simulation study. In order to carry out the simulation study with realistic settings of UAVs, critical parameters, such as UAV energy constants, visibility angle, altitude, and communication range, use the representative values presented in the well-received literature, as cited in Section 4. The simulation results show that the proposed approach is effective in planning the optimal number and positions of UAVs to provide seamless surveillance coverage for a ground vehicle.

As discussed in Section 1, a vast majority of the cited references on coverage using UAVs deal with discrete targets or discretized spaces [12–15, 17–23, 25–28, 30–38], and the references, which deal with continuous area coverage, focus on finding optimal placement of a given number of UAVs [16, 24, 29]. This study deals with forming continuous and seamless area coverage around a ground vehicle, and the proposed approach finds the optimal number and positions of UAVs to provide continuous area coverage subject to comprehensive constraints. Therefore, compared with the existing works, this study contributes to the optimization formulation as well as solution approach. Moreover, the proposed bi-layer algorithmic framework brings in a novel strategy for using available fixed-length optimization algorithms to solve challenging variable-length optimization problems. This idea can be generalized and applied to a broader scope of optimization problems.

Further research will be carried out in the following aspects:

• Priority is to understand the complexity of the solution space and improve the global optimality of the solution.

• Another interesting problem is the scalability of the solution algorithm to significantly increased number of UAVs for large area coverage, depending on the need of the targeted application. The general understanding is that the scalability of the bi-layer optimization procedure is determined by the scalability of both the outer layer and inner layer. While the outer layer iterates through the number of UAVs and thus is linearly scalable, the inner layer scalability depends on the adopted inner-layer optimization algorithm. Future study will test the scalability with GA and other different inner-layer algorithms.

• The current research is carried out based on the assumption that the involved UAVs are homogenous, with the same capabilities of kinematics, sensing, communication, and energy, and are omni-directional helicopter-like single-rotor or multi-rotor UAVs, in order to lay the foundation. Future study will address this limitation and extend to more generic and heterogeneous situations involving UAVs of different types and capabilities.

• Further research will look into the problem of controlling the UAV formation to follow the ground vehicle. Control approaches robust against the time delay, system disturbance, and modeling errors, e.g., like those in [44–46], will be explored. Moreover, the problem of malfunctioning or out-of-power UAVs will be addressed in the phase of real-time operations and control of UAVs. While monitoring the state of each UAV, any malfunctioning or out-of-power UAV will return to the ground vehicle which serves as the service hub for UAVs, and a replacement UAV will fly from the ground vehicle to the corresponding position to fill the gap.

The approach discussed in this paper is well applicable to search-and-rescue operations in different environments including ground, urban, battlefield, as well as water. It can also be applied to other domains beyond search-and-rescue, such as agriculture monitoring, smart agriculture, wildlife tracking, and environmental exploration, where UAVs and ground vehicles collaborate to carry out DTCO operations and UAVs are used to provide area/surveillance coverage.

Conflict of interest

The authors declare no conflict of interest.

Acknowledgments

Effort sponsored by the Air Force under PIA FA8750-19-3-1000. The U.S. Government is authorized to reproduce and distribute copies for Governmental purposes notwithstanding any copyright or other restrictive legends.

The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of the Air Force or the U.S. Government.