Multiob jective evolutionary ight planning of autonomous unmanned aerial vehicles for exploration and surveillance

Abstract

This article presents a multiobjective evolutionary approach for computing ight plans for a eet of unmanned aerial vehicles to perform exploration and surveillance missions. The static o -line planning subproblem is addressed, which is useful to determine initial ight routes to maximize the explored area and the surveillance of points of interest in the zone. A speci c ight planning solution is developed, to be applied in low-cost commercial Bebop 2. The experimental analysis is performed in realistic instances of the surveillance problem. Results indicate that the proposed multiobjective evolutionary algorithm is able to compute accurate ight plans, signi cantly outperforming a previous evolutionary method applying the linear aggregation approach.

1. Introduction

In the last years, Unmanned Aerial Vehicles (UAVs) have developed as useful vehicles to perform di erent important activities and provide diverse services in smart cities [ 1 ]. A wide range of applications have been addressed in logistics and infrastructure inspection, agriculture, photography, rescue and disaster management, and also security and surveillance [ 2 ]. Since UAVs can be controlled remotely or programmed to follow speci c ight routes, they can be used in situations where manned ight is dangerous. Furthermore, for routine missions, an autonomous ight system an be implemented, without involving human control or a centralized control infrastructure [ 3 ]. This paradigm is commonly applied for controlling a eet of UAVs, by implementing a cooperative approach for surveillance, which provides several bene ts: robustness, since multiple agents perform the task at the same time, improvement on the ight time and battery utilization, and improvement of the quality of service of the system (providing an expanded coverage and better surveillance).

Developing an e ective cooperative model for exploration and surveillance heavily relies on successfully computing accurate ight plans that account for the problem objectives. The ight route planning problem for UAVs is NP-hard, as it is a variant of the classic Orienteering Problem [ 4 ]. Computational intelligence methods have been proposed to generate reliable and fast ight routes for UAV eets, to ful ll speci c missions autonomously [ 5 ]. In this context, heuristics and metaheuristics [ 6 ] are applied to nd accurate routes in reasonable execution times, especially to be implemented in real time missions.

In this line of work, this article presents a Multiobjective Evolutionary Algorithm (MOEA) to solve the o -line problem of route planning for a eet of UAVs to maximize exploration and surveillance. The problem formulation considers an area to explore and speci c points of interest (PoI) to be surveyed periodically. PoI can be static or move across the area, following a predetermined pattern. The main goal of the proposed MOEA is to compute accurate plans with good compromise between the explored area and the monitoring of PoI. Computed solutions are useful for practical surveillance and can also be extended to address more dynamic situations, e.g. by applying agent oriented programming to perform slight modi cations to the route of each UAV to deal with unexpected events.

2. Multiobjective ight planning for UAVs

The considered optimization problem proposes nding a set of routes for UAVs in the eet to simultaneously maximize the explored area and maximize the surveillance of PoI.

The problem formulation considers the following elements:

A set of UAVs, U = fu1; : : : ujUjg, able to ight at a maximum speed vD.

A mission time period T , discretized in s uniform time steps; T =< t1; t2; : : : ts > A set of PoI to surveil O = fo1; : : : ; ojOjg. Two types of PoI are considered: static (do not move) and mobile (move at maximum speed vO).

A bene t vector P = (p1; p2; : : : pjOj), where pi is the bene t associated to surveil PoI oi. An object position matrix OP (dimension jOj oi in timestep tj .

A coverage radius ro and a circumscribed coverage square with side ro = 2ro=p2. An area to explore (dimensions H W ), which is considered to be discretized in regions, i.e., squares of length ro to determine the sequence of ight paths. s). OPij indicates the coordinates of PoI

The goal of the problem is to determine a ight planning for the eet of UAVs, i.e., a function f p : U T ! Q that simultaneously maximizes two functions:

The bene t of monitoring PoIs (as de ned by function (p), in Eq. 2). This function takes into account PoIs that are covered, i.e., they are within the coverage radius of each UAV. The bene t for exploring (as de ned by function (p), in Eq. 2), which accounts for the the explored surface of the eet, de ned as the union of the surfaces explored by each UAV in its route in the planned time. The area covered by a UAV at a given time is determined by a circumference of coverage radius that has it as its center, which is directly related to the eld view of the UAV on-board camera. The bene t for exploring is evaluated by the Spatial Exploration Ratio metric [ 7 ].

with p(qi; tj ) = (x; y) = ajx;y = qi and D(c1; c2) =

d rHo e d Wro e jT j (p) = X X X E(x; y; j)

Without loss of generality, the problem model assumes that all UAVs depart and return for charging to a base B, located at coordinates (xB; yB), within the area to explore.

3. The proposed MOEA for ight planning

This section describes the proposed algorithmic approach for multiobjective UAV ight planning.

3.1. Algorithmic approach

The proposed solution for multiobjective UAV ight planning is based on the NSGA-II algorithm, a traditional MOEA for solving real-world problem in di erent application areas [ 8 ]. Speci c modi cations to the general skeleton of NSGA-II were included to solve the considered problem. The main implementation details are presented in the following subsections.

3.2. Solution encoding

Solutions to the multiobjective UAV ight planning problem are represented by a matrix-based encoding. A graph is built considering the discretization of the area to explore and the zones visited by each UAV. The graph connects the center of each zone, for each UAV route, in a Cartesian coordinate system. In the matrix encoding, each row encodes a route, i.e., the sequence of coordinates of the center of each zone for each route. Each element (i; j) in the matrix is a pair (xij ; yij ) that represents the position of UAV i at timestep j. The null value (-1, -1) is used to ll those unused elements in the matrix, since some routes may be larger than others. The dimension of the matrix encoding is jU j s.

Figure 1 presents an example of encoding for a simple solution where two routes are de ned for two UAVs (represented by the green nodes and the blue nodes in the graph in Figure 1(a)). Both UAVs depart from the base located at (xB; yB) = (1; 0).

1 1 1 B 1 1 2 2 2 (1; 0) (2; 1) (2; 2) (1; 2) (1; 1) (0; 2) (1; 0) (2; 0) (3; 1) (4; 0) (2; 0) (-1; -1) (a) A sample solution with two routes (b) Matrix encoding ( rst row: green route; second row: blue route)

3.3. Fitness assignment and stopping criterion

The traditional dominance rank method applied in NSGA-II is used to de ne the tness of solutions, considering the problem objectives. Then, Pareto ranking is applied over normalized values of both objectives for solutions in the population. A stagnation stopping criterion is applied: the search stops when no new non-dominated solutions are computed in a generation.

3.4. Evolutionary operators

Speci c evolutionary operators are applied to account for the problem objectives (exploration and alerts from PoIs) [ 9 ]. The proposed evolutionary operators are as follows: (i) Initialization: Two methods were applied for population initialization: i) random path initialization and ii) seeded initialization, where the route of each UAV is generating by starting at (xB; yB) and moving in a direction determined by angle i 2 1=u + j 2 1=(u Z), where i 2 [0; u 1] is the UAV identi er, j 2 [0; Z] is the ordinal of the candidate solution, and Z is the population size of the MOEA. (ii) Selection: The classic tournament selection operator in NSGA-II was replaced by Stochastic Universal Sampling with sigma escalation (SUS+ ) in the proposed MOEA. This decision was motivated by three useful properties of SUS+ : i) it is less biased to high quality solutions; ii) helps avoiding premature convergence caused by dominance of a group of solutions; and iii) helps amplifying small di erences in advanced stages of the search. (iii) Recombination: The Single Point Crossover operator was applied for recombination, as it provided an appropriate search pattern in preliminary con guration experiments. The operator is directly applied over the proposed solution encoding, but it can generate infeasible solutions (e.g., long jumps in UAV routes). In this case, the correction operator described in item (v) is applied. (iv) Mutation: A speci c mutation operator, based on modifying information on the encoded routes, was designed for the problem. The number of positions to be modi ed is selected with a uniform distribution in the interval ([1; u st ]). After that, a new direction is de ned for the movement of the corresponding UAV, according to a uniform distribution in the seven di erent possible directions (excluding the one already traveled in the original solution). The speed of the UAV in this new direction is also selected according to a uniform distribution between (0; vD). The proposed mutation operator may generate infeasible solutions. In this case, the correction operator described in item (v) is applied. (v) Correction of infeasible solutions: Infeasible solutions can be generated by the evolutionary operators in two cases. In the case of the path of a UAV has two consecutive positions that are more distant than it can travel in a time interval, the correction operator modi es the position from which it is not possible to reach the nearest one when the UAV ies at maximum speed. A second type of infeasible solutions are those that do not allow the UAV to return to the base for recharging after nishing a route. In this situation, the correction operator truncates the route in the last movement where it is still possible to return to the base with the available battery charge.

4. Experimental evaluation

This section reports the experimental evaluation of the proposed MOEA for UAV ght planning.

4.1. Scenarios and instances.

The proposed MOEA was evaluated in real and synthetic scenarios that include features of real facilities to perform surveillance. Five scenarios were considered: one small-sized scenario (#0) used for parameter calibration, one real scenario (#1) studied with low-cost Parrot Bebop 2 UAVs, two medium-size and one large-size scenario, whose details are presented in Table 1. scenario

H W

(xB,yB) jU j #0 #1 #2 #3 #4

For each synthetic scenario, ten problem instances were created varying the locations of PoI and obstacles. Overall, 50 problem instances were used for the evaluation of the proposed MOEA. Figure 2 presents two sample scenarios and their discretizations. The base is marked with a blue square and obstacles are marked with gray squares. PoIs are located at random location and motion is generated by applying Rapidly-exploring Random Tree, an e cient strategy for multi-dimensional space searching, biased towards unexplored sections of the search space. (a) Scenario #0 (dimension 50 50) (b) Scenario #1 (dimension 100 100)

Scenarios #2 to #4 were studied using a distributed simulation approach, implemented over Sphinx, the o cial simulator for Parrot UAVs. Experiments were executed on Xeon Gold 6138 processors with 128 GB of RAM memory from National Supercomputing Center, Uruguay [ 10 ]. Parametric con guration experiments were performed over scenario #0.

4.2. Numerical results

Table 2 reports the results computed by the best compromise solution (i.e., the nearest solution to the ideal vector) of the proposed MOEA. Results are compared with the single-objective Evolutionary Algorithm (EA) for the problem using a linear aggregation of objectives [ 11 ]. The best improvements over the reference EA are marked in bold: up to 26.7% for the exploration objective and up to 22.3% for the surveillance objective. The best results were computed for the largest problem instance, suggesting that the proposed MOEA scales properly to large scenarios. Table 2. Results of the proposed MOEA and improvement over linear aggregation approach [ 11 ].

MOEA

PoI monitoring ( ) exploration ( )

Linear aggregation EA [11]

PoI monitoring ( ) exploration ( ) best coverage, best surveillance

MOEA

MOEA best coverage, best surveillance 18;000

MOEA

MOEA 16;000 14;000

EA 12;000 2;000 MOEA EA

MOEA 10;000 11;000 12;000 13;000

5. Conclusions and future work

This article presented a multiobjective evolutionary approach for UAV ight planning to optimize exploration and surveillance of a prede ned set of PoI. A custom NSGA-II including speci c routing-based evolutionary operators was proposed for the problem.

The experimental evaluation was performed on real and synthetic scenarios, modeling the surveillance of real facilities. Results demonstrate that the proposed MOEA improved over a previous EA approach in up to up to 26.7% (exploration) and up to 22.3% (surveillance).

The main lines for future work are related to extending the experimental evaluation and integrating more sophisticated control methods in the UAV hardware.

References

[1] Al-Turjman F (ed) 2020 Unmanned Aerial Vehicles in Smart Cities (Springer International Publishing)

[2] Zeng Y , Zhang R and Lim T 2016 Communications Magazine 54 36 { 42

[3] Garate B , D az S , Nesmachnow S , Iturriaga S , Shepelev V and Tchernykh A 2020 Frontiers Robotics and AI

[4] Shi H , Sun X , Sun C , Chen D and An Y 2006 Research of the path planning complexity for autonomous mobile robot under dynamic environments 6th IEEE Intelligent Systems Design and Applications pp 216 { 219

[5] Valavanis K 2007 Advances in Unmanned Aerial Vehicles (Springer Netherlands)

[6] Nesmachnow S 2014 International Journal of Metaheuristics 3 320

[7] Wietfeld C and Daniel K 2014 Cognitive networking for UAV swarms Handbook of Unmanned Aerial Vehicles (Springer Netherlands) pp 749 { 780

[8] Deb K , Pratap A , Agarwal S and Meyarivan T 2002 IEEE Transactions on Evolutionary Computation 6 182 { 197

[9] Behak S , Rondan G , Zanetti M , Iturriaga S and Nesmachnow S 2020 Distributed greedy approach for autonomous surveillance using unmanned aerial vehicles High Performance Computing Communications in Computer and Information Science (Springer International Publishing) pp 1 { 15

[10] Nesmachnow S and Iturriaga S 2019 Cluster-UY : Collaborative Scienti c High Performance Computing in Uruguay 10th Int . Conf. on Supercomputing in Mexico (Springer) pp 188 { 202

[11] Gaud n A , Madruga G , Rodr guez C , Iturriaga S , Nesmachnow S , Paz C , Danoy G and Bouvry P 2020 Autonomous ight of unmanned aerial vehicles using evolutionary algorithms High Performance Computing Communications in Computer and Information Science (Springer International Publishing) pp 337 { 352