Integrated optimization of unmanned aerial vehicle task allocation and path planning under steady wind

Abstract

Wind has a significant effect on the control of fixed-wing unmanned aerial vehicles (UAVs), resulting in changes in their ground speed and direction, which has an important influence on the results of integrated optimization of UAV task allocation and path planning. The objective of this integrated optimization problem changes from minimizing flight distance to minimizing flight time. In this study, the Euclidean distance between any two targets is expanded to the Dubins path length, considering the minimum turning radius of fixed-wing UAVs. According to the vector relationship between wind speed, UAV airspeed, and UAV ground speed, a method is proposed to calculate the flight time of UAV between targets. On this basis, a variable-speed Dubins path vehicle routing problem (VS-DP-VRP) model is established with the purpose of minimizing the time required for UAVs to visit all the targets and return to the starting point. By designing a crossover operator and mutation operator, the genetic algorithm is used to solve the model, the results of which show that an effective UAV task allocation and path planning solution under steady wind can be provided.

About the Authors:

He Luo

Roles Conceptualization, Data curation, Formal analysis, Funding acquisition, Investigation, Methodology, Writing – original draft, Writing – review & editing

* E-mail: [email protected]

Affiliations School of Management, Hefei, Anhui, China, Key Laboratory of Process Optimization & Intelligent Decision-making, Ministry of Education, Hefei, Anhui, China

ORCID http://orcid.org/0000-0003-2062-5510

Zhengzheng Liang

Roles Formal analysis, Investigation, Methodology, Visualization, Writing – original draft, Writing – review & editing

Affiliations School of Management, Hefei, Anhui, China, Key Laboratory of Process Optimization & Intelligent Decision-making, Ministry of Education, Hefei, Anhui, China

Moning Zhu

Roles Methodology, Software, Validation, Writing – original draft

Affiliations School of Management, Hefei, Anhui, China, Key Laboratory of Process Optimization & Intelligent Decision-making, Ministry of Education, Hefei, Anhui, China

Xiaoxuan Hu

Roles Funding acquisition, Resources, Writing – original draft

Affiliations School of Management, Hefei, Anhui, China, Key Laboratory of Process Optimization & Intelligent Decision-making, Ministry of Education, Hefei, Anhui, China

Guoqiang Wang

Roles Software, Writing – original draft, Writing – review & editing

Affiliations School of Management, Hefei, Anhui, China, Key Laboratory of Process Optimization & Intelligent Decision-making, Ministry of Education, Hefei, Anhui, China

Introduction

At present, unmanned aerial vehicles (UAVs) are widely used by the military and civilians. They are able to fulfill a variety of tasks, such as target reconnaissance [1], target tracking [2], intelligence gathering [3], post-earthquake rescue [4], and geological exploration [5]. For instance, when multiple UAVs are applied to cooperative target reconnaissance, it is necessary to allocate reconnaissance targets for each UAV reasonably, and to plan optimal flight path for each UAV. This involves the integrated optimization of task allocation and path planning constrained by multiple factors [6–8], which is also a NP-hard (non-deterministic polynomial-time hard) problem [9].

For UAVs, one of the largest disturbances in flight is wind, as it affects the flight posture [10] and flight path [11] of UAV, thus resulting in changes in flight time. In a windless environment, UAV airspeed is equivalent to UAV ground speed. However, in a windy environment, ground speed is affected by both airspeed and wind speed. Therefore, although UAV can fly along the pre-planned path in a windy environment by adjusting its flight speed and heading angle, the actual arrival time and fuel consumption will be higher than estimated [12], and the flight time will no longer be the shortest.

The integrated optimization of UAV task allocation and path planning under steady wind can be described as follows: In a windy environment, UAVs depart from the common starting point to visit multiple targets, and each target can only be visited once by one UAV. Constrained by factors such as physical characteristics [13] of UAV, the task allocation scheme and the optimal flight path are obtained, which enable UAVs to complete all the tasks and return to the starting point in the shortest time. In this paper, based on the classical vehicle routing problem (VRP) model, a variable-speed Dubins path vehicle routing problem (VS-DP-VRP) model is established with minimum flight time as the objective function. The following two factors are taken into account in the modeling:

First, given the flight dynamics constraints of UAV, the VRP model is extended to a Dubins path VRP model (DP-VRP). When flying between different targets, UAVs are constrained by flight dynamics and must change flight direction with the minimum turning radius. Thus, the obtained flight distance is not the Euclidean distance, but rather the Dubins distance. In addition, the Euclidean distance between two targets is constant in the VRP model, but the Dubins distance between the two targets in the DP-VRP model will change with the angle when a UAV visits the target.

Second, in light of the influences caused by wind, the DP-VRP model is further extended to the VS-DP-VRP model. In the standard VRP model, the time of a vehicle moving between two targets is constant or quantitatively changes according to the traffic conditions between the two points [14]. In the VS-DP-VRP model, on the other hand, because of the real-time changes in direction of UAV airspeed vector, as well as in the ground speed vector affected by both airspeed and wind speed, flight time of UAV between two targets is determined by real-time ground speed and Dubins distance between the two targets.

Currently, the heuristic algorithm is used to solve the VRP model. In particular, the genetic algorithm (GA) has been proved to be effective [15] in solving the bench mark dataset, and better results can be obtained by adjusting parameters. When solving practical problems, the GA has also been used as an efficient algorithm with which to solve the problem of task allocation and path planning [9]. In most cases, it is better than other algorithms [16] and requires shorter computation time [17]. In this paper, based on the GA framework, the VS-DP-VRP model is solved by designing a crossover operator and mutation operator.

The remainder of this paper is organized as follows: research related to this problem is introduced in the next section, and the VS-DP-VRP model is presented in the Section 3. Then, a GA is proposed for solving the VS-DP-VRP in Section 4. The model and algorithm are analyzed using example comparison in Section 5 and the parameter sensitivity experiment and simulation experiments are described in Section 6. Conclusions and the future prospects of this study are provided in Section 7.

Related work

When UAVs are on a mission, the impact exerted by wind cannot be ignored, especially in terms of UAV task allocation and path planning [18, 19], because wind changes flight time and flight path [20–22] of UAV. At present, the modeling of wind can be divided into three ways: the first is the steady wind, which is of constant speed and direction [23–25]; the second is to model the wind according to the cause of wind [26], such as pressure, temperature, humidity, terrain, altitude, etc.; the third way is to estimate the status data of the current wind by analyzing historical data. Among these three methods, the steady wind is the typical one chosen for UAVs. It is believed that the speed and direction of wind influencing UAVs are constant. Aiming at UAV path planning in the steady wind, Zhang et al. [25] took into account the impact of steady wind on flight path of UAV, and set a virtual target, then the problem became the path planning for UAV that would cost the least time to reach the virtual target in a windless environment. Techy et al. [27] suggested linking straight and trochoidal path segments to form a feasible path and choosing the scheme that costs the least time from the result set.

Actually, when UAVs are in a steady wind, if they have a constant airspeed, their actual speed and direction are always changing relative to the ground [27], as they are under the influence of wind. That means their ground speed is changing all the time. In this case actual flight path of UAV no longer meets the estimated result of the plan and flight time changes as well. To keep the constant ground speed of UAV, airspeed and direction must be changing constantly under steady wind according to the vector relation [28] between UAV ground speed and airspeed. Although it can be guaranteed that UAV will fly along the pre-planned route, flight time changes. Thus, in steady wind, the time UAVs require to accomplish the task does not conform to the pre-planned time, no matter which flight control strategy is adopted. Affected by the wind, the optimization objective of UAV task allocation and path planning is to minimize execution time.

At present, in terms of UAV task allocation and path planning, the travelling salesman problem (TSP) model, team orienteering problem (TOP) model, and VRP model are usually adopted for the modeling. In particular, when all targets need to be visited, the optimization is often to minimize flight path, and the TSP model can be used for modeling. For example, Sathyan et al. [29] changed the UAV task allocation problem to the multiple travelling salesman problem (MTSP), and put forward a cluster-first approach in which each UAV is distributed to a target subset. Ernest et al. [30] extended the MTSP of multiple UAVs visiting multiple sites to the multi-depot polygon visiting Dubins MTSP, with a view to accounting for the constraint of UAV minimum turning radius.

However, in the case in which not all targets need be visited, the TOP model can be used to transfer the problem of the shortest flight path to the problem of maximizing profits. For example, Evers et al. [31] established a standard orienteering problem (OP) extended model, with a view of time windows and time-sensitive targets, with the purpose of solving the UAVs task allocation problem. Considering the impact on UAV flight time caused by sensor allocation, Mufalli et al. [32] established a TOP model to maximize the profits. The VRP model is generally used for modeling in consideration of the time used by UAVs to visit all targets. In a study conducted by Faie et al. [33], a VRP model was established with minimum flight time of each UAV as the cost function. In the meantime, it was pointed out that in the cases where wind could be ignored, the minimum flight time of UAV has the same meaning as the minimum path length. Guerrero J A et al. [19] took into account the wind and UAV energy constraints, and established a capacitated vehicle routing problem (CVRP) model targeting time minimization.

In the VRP standard model and extended model [34], it is believed that targets and their distances are constant. However, constrained by flight dynamics like minimum turning radius, the shortest flight distance of UAV is the length of the Dubins path rather than the Euclidean distance. The Dubins path is the feasible path [35] of minimum length, which moves along a bounded curve path with a constant speed. Moreover, it is a UAV’s shortest flight path in either a windless [36, 37] or windy environment [38]. According to the method of calculating the Dubins path [36], if the ground speed heading angles when a UAV visits two targets are equally divided into 360 parts, there are 6×360×360 = 777600≈7×105 solutions in the Dubins path between these two targets. Therefore, optimizing the Dubins path on the basis of optimizing the standard VRP is required.

At present, integer programming or a heuristic method is generally adopted to solve the standard or extended VRP model, but the calculation time of integer programming grows exponentially with the expansion of scale. The solution can be quickly acquired on the premise of ensuring the quality of the solution by designing a heuristic algorithm [39]. The common heuristic algorithm includes the GA [40], tabu search (TS) [41], particle swarm optimization (PSO) [42–43], differential evolution (DE) [44] etc. Among these, the GA can obtain a good solution in a shorter time [45–47], especially in solving UAV task allocation [48] and path planning [49, 50]. The GA has obtained a better effect not only in experiments, but also in engineering applications [51, 52].

Problem description and modeling

In this section, wind, UAVs, targets, airspeed, and ground speed are described, and an integrated optimization model of UAV task allocation and path planning under steady wind is established. The symbols and nomenclature are shown in Table 1.

[Figure omitted. See PDF.]

Table 1. The nomenclature.

https://doi.org/10.1371/journal.pone.0194690.t001

Wind

Let(1)be the wind vector. V_w denotes wind speed; that is, the distance wind travels relative to the ground in unit time. β_w denotes the direction of wind, which refers to the direction of ambient air’s motion, and it is described by angle.

In this paper, west wind (W) is defined as 0°, and south wind (S), east wind (E), and north wind (N), respectively, correspond to angles of 90°, 180°, and 270°, as depicted in Fig 1. Meanwhile, only the steady wind is taken into account. To be specific, the speed and direction of wind are constant in the given environment.

[Figure omitted. See PDF.]

Fig 1. Wind direction.

https://doi.org/10.1371/journal.pone.0194690.g001

UAVs

Let(2)be the set of N_U cooperating fixed wing UAVs. We assume that the vehicles spatial configuration can be defined by three states(3)with the following equations of motion:(4)(5)(6)where and are a UAV’s coordinates in a Cartesian inertial reference system; represents the ground speed of UAV; denotes the heading angle of ground speed; denotes the angular velocity of airspeed; c is the steering command, such that |c|≤1; and Ω_max is the maximum angular velocity of UAV. The definition and relationship between and will be explained in the Airspeed and ground speed section. Moreover, the UAVs mentioned in this paper also meet the following conditions: (1) all UAVs have the same minimum turning radius r_min; (2) all UAVs are equipped with a collision-avoidance function; and (3) all UAVs fly at constant altitude with constant airspeed value.

Targets

Let(7)be the set of N_T targets, with known positions, and each point can only be visited once. denotes T₀ the common starting point. According to Shima [8], continuous heading angle of UAV when visiting a target can be equally divided into 36 parts, which can guarantee accuracy and make the solving process less complex. Therefore, the ground speed heading angle discretization set is defined as(8)

The shortest distance between two targets is the Euclidean distance. However, constrained by flight dynamics, UAVs must be moved at the minimum turning radius, resulting in the actual flight path is Dubins path. According to the method of calculating the Dubins path, the Dubins path between two targets can be the combination of arc paths and straight path. There are six combinations [9], namely D = {LSL,RSR,RSL,LSR,RLR,LRL}. L represents an arc path of a UAV turning left with radius r_min; R represents an arc path of a UAV turning right with radius r_min; and s represents a UAV flying along a straight line. For example, when a UAV starts from T₀ with β_g = 0° to T₁ with β_g = 30°, all the possible Dubins paths can be described in Fig 2. With the changes in ground speed heading angles of two targets, there are a total of 6×36×36 = 7776 kinds of Dubins paths between the two targets.

[Figure omitted. See PDF.]

Fig 2. Dubins path.

https://doi.org/10.1371/journal.pone.0194690.g002

Airspeed and ground speed

Let(9)be the airspeed vector. V_a is the airspeed and β_a is the airspeed heading angle. In accordance with the flight envelope of UAV, there are upper and lower bounds [27] for its airspeed when flying at constant altitude with a constant load; namely, V_a ⊂[V_{a_min},V_{a_max}]. V_{a_min} and V_{a_max} represent, respectively, the minimum and maximum value of the airspeed at the specified height.

Let(10)be the ground speed vector; that is, speed relative to the ground under the influence of wind. V_g is the ground speed and β_g denotes its heading angle. The ground speed vector can be obtained by formula (11) using the airspeed vector and wind speed vector .

(11)

The relationship between the three speed vectors is shown in Fig 3. It can be easily seen that in a windless environment the airspeed of UAV is the same as the ground speed, namely V_w = 0m/s, , and .

[Figure omitted. See PDF.]

Fig 3. Relationship between speed vectors.

https://doi.org/10.1371/journal.pone.0194690.g003

For instance, the ground speed vector of UAV at point X (100,330) when flying in a south wind can be obtained by formula (10), , as shown in Fig 4.

[Figure omitted. See PDF.]

Fig 4. Ground speed vector at point X (100,330).

https://doi.org/10.1371/journal.pone.0194690.g004

The time used by UAV U_i departing from a target T_j at a ground speed heading angle β_gj to reach target T_k at a ground speed heading angle β_gk is calculated using(12)where Δθ is the angular rotation and V_g(θ) is the ground speed when the UAV’s ground speed heading angle is θ.

A UAV’s actual flight time between two targets is determined by both the ground speed vector and the Dubins distance between the two targets.

VS-DP-VRP modeling

The integrated optimization of UAV task allocation and path planning under steady wind is essentially the planning of order and angle for each UAV to visit a series of targets. In this paper, the VS-DP-VRP model is established with the minimum time used by UAVs to visit all targets and return to the starting point as the objective function:(13)(14)where is the decision variable. If UAV U_i depart from target T_j at ground speed heading angle β_gj and reach target T_k at ground speed heading angle β_gk, ; otherwise, ;

The constraints of the model are as follows:

1. Visit constraint for targets: All targets can be visited only once;(15)

2. UAV path constraints: Each UAV departs from the starting point, and then returns to the starting point after visiting a number of targets;

(16)(17)

GA-based optimization algorithm

By designing the crossover and mutation operator, the GA is used to solve the VS-DP-VRP model.

Encoding

A chromosome represents a feasible solution to the problem. In this paper, a chromosome encodes by three parts: the targets, the ground speed heading angles and the UAVs, where targets belong to set T, ground speed heading angles belong to set H and UAVs belong to set U.

The chromosome shown in Fig 5 represents a feasible solution for two UAVs to visit three targets. This feasible solution means U1 departed from the starting point and then returned to the starting point after visiting T3 with β_g = 300°, while U2 departed from the starting point to visit T1 with β_g = 100°, and then returned to the starting point after visiting T2 with β_g = 200°.

[Figure omitted. See PDF.]

Fig 5. Encoding of chromosome.

https://doi.org/10.1371/journal.pone.0194690.g005

Crossover

The population diversity can be increased by a crossover operation. For the VS-DP-VRP model, a new crossover operator is designed in this paper, and its pseudocode is shown in Fig 6.

[Figure omitted. See PDF.]

Fig 6. The pseudocode of crossover operator.

https://doi.org/10.1371/journal.pone.0194690.g006

Fig 7 shows the crossover process of the parent chromosomes Parent A and Parent B. The third gene in Parent A is exchanged with the first gene in Parent B to generate two new chromosomes, namely ProtoChild A and ProtoChild B. Since all UAVs encoding in ProtoChild B are U2. In the next step, the second gene, which is selected randomly, in ProtoChild B is changed with the third gene in ProtoChild A to complete the cross operation to generate OffSpring A and OffSpring B.

[Figure omitted. See PDF.]

Fig 7. Crossover process of two chromosomes.

https://doi.org/10.1371/journal.pone.0194690.g007

Mutation

Mutation can prevent the GA from local optimum. In this paper, three kinds of mutation operators are designed; namely, the mutation of targets, ground speed heading angle mutation, as well as mutation in UAV allocation. Since the above three mutations do not have a correlation, the roulette method has been used to determine whether the above mutations occurred. Moreover, we allow all three mutations to be applied on each chromosome concurrently. The pseudocode of the three kinds of mutation operators is shown in Figs 8–10.

[Figure omitted. See PDF.]

Fig 8. The pseudocode of target mutation operator.

https://doi.org/10.1371/journal.pone.0194690.g008

[Figure omitted. See PDF.]

Fig 9. The pseudocode of angle mutation operator.

https://doi.org/10.1371/journal.pone.0194690.g009

[Figure omitted. See PDF.]

Fig 10. The pseudocode of UAV mutation operator.

https://doi.org/10.1371/journal.pone.0194690.g010

Fig 11 shows the procedure of selecting the third gene in chromosome P for the UAV mutation operator. Firstly, change the UAV U2 in this gene into a random UAV U1 to generate Pro-Chromosome P. Since all UAVs encoding in Pro-Chromosome P are U1, then the second gene, which is selected randomly, in Pro-Chromosome P is changed to U2, which is different from the original number U1, thereby the mutated chromosome Pʹ is generated.

[Figure omitted. See PDF.]

Fig 11. Process of UAV mutation for chromosome.

https://doi.org/10.1371/journal.pone.0194690.g011

The pseudocode of the GA-based optimization algorithm is shown in Fig 12.

[Figure omitted. See PDF.]

Fig 12. The pseudocode of the GA-based optimization algorithm.

https://doi.org/10.1371/journal.pone.0194690.g012

Illustrative example

In the case of Ref. [9], the shortest path in which a UAV visited three targets, i.e., T₁ (50, 300), T₂ (150, 350), and T₃ (100, 150), was 1483 m. The optimal task allocation and flight route of which are shown in Fig 13.

[Figure omitted. See PDF.]

Fig 13. Optimal flight path for visiting three targets in a windless environment.

https://doi.org/10.1371/journal.pone.0194690.g013

As the impact of wind was not taken into consideration, it could be regarded as a windless environment in which the ground speed of UAV was equivalent to its airspeed. When the airspeed was 10 m/s, the flight time of the UAV in the path of , , and can be calculated according to formula (12). However, the ground speed of the UAV may not be the same as the airspeed due to the impact of wind. Under four different steady winds of south wind, west wind, north wind, and east wind, with the same wind speed of 5 m/s, the flight time along the above path can be calculated according to formula (12), as shown in Table 2. Therefore, it can be concluded that the flight time of a UAV along the same planned route varies under different winds.

[Figure omitted. See PDF.]

Table 2. UAV flight times along a fixed path under different winds.

https://doi.org/10.1371/journal.pone.0194690.t002

Furthermore, there are six different orders for a UAV to reach the three above-mentioned targets, the optimal task allocation results and the shortest flight distance are provided in Ref. [9]. In the light of the above analysis, the flight time of UAV in six different paths under windless and four other different winds (east wind, south wind, west wind, and north wind, with a wind speed of 5 m/s) can also be calculated, as shown in Table 3. In the windless, west wind, east wind, and north wind, the shortest flight time for a UAV to reach the three targets are, respectively, 148.3, 173.3, 182.0, and 118.4 s, the task allocations scheme of which are all P2, while in the south wind environment, the shortest flight time for a UAV to reach the three targets is 165.6 s with a task allocation scheme P6. Obviously, task allocation of a UAV’s shortest flight time varies under different winds.

[Figure omitted. See PDF.]

Table 3. UAV flight time in different visiting orders and different winds.

https://doi.org/10.1371/journal.pone.0194690.t003

In fact, the task allocation schemes provided in Table 3 are the different choices for a UAV to reach the three above-mentioned targets with shortest flight time in the windless environment. However, the assigning of task and path planning of a UAV in the wind is not merely a choice among these six schemes in the windless environment, but rather a re-optimization in consideration of the impact of wind on the flight time. According to the VS-DP-VRP model built for this study, the shortest flight time and its corresponding optimal task allocation results of a UAV under four different winds (east, south, west, and north, with a wind speed of 5 m/s) can be calculated based on the GA-based optimization algorithm, as shown in Fig 14. For instance, in south wind with a wind speed of 5 m/s, the shortest flight time is 154.4 s and the optimal task allocation result is T3(20°), T2(270°), and T1(310°). Although this scheme is not included in Table 3, it is better than the overall schemes in Table 3.

[Figure omitted. See PDF.]

Fig 14. Flight path using minimum time for U1 to visit three targets under four different winds.

https://doi.org/10.1371/journal.pone.0194690.g014

Experiments

For the integrated optimization of UAV task allocation and path planning under steady wind, simulation experiments of multi-UAVs visiting multi-targets are carried out, aiming at analyzing the shortest time for all of the UAVs to finish the task of visiting the targets and return to the starting point. All of the experiments are run on MATLAB on a 3.4-GHz CPU with 4 G memory; the detailed parameters of the experiments are shown in Table 4. Since the fixed-wing UAVs took off from the airport at the starting point, taxiing of UAVs would be restricted by the airport runway, as a result of which the ground speed heading angle in the experiment must be 90° when UAVs depart and return; otherwise, the UAVs cannot land on the runway.

[Figure omitted. See PDF.]

Table 4. Parameter settings.

https://doi.org/10.1371/journal.pone.0194690.t004

In order to determine the optimal allocation of the crossover probability and mutation probability in the algorithm, all of the possible parameter combinations are tested. Among them, the crossover probability ranges from 0.5 to 0.9, the mutation probability ranges from 0.1 to 0.5, and the population sizes for these ranges are 200, 400, 600, and 800. In this experiment, two UAVs are in the east wind with a wind speed of 5 m/s, and the generation of the algorithm was 200. Since there are some random uncertainties in the process of calculating the optimal solution, the result of each experiment might be different. Therefore, all the experimental results are the average of 20 experiments under the same experimental parameters.

With different population size, crossover probability, and mutation probability, the result for the shortest time solved by the algorithm is shown in Fig 15. As the population size increased, the shortest time with the same crossover probability and mutation probability gradually decreased. Under a fixed population size, if the population size is small, the average of the shortest time after iterating the same number of times is different under different crossover and mutation probability, and if the population size is large, the average of the shortest time differed slightly after iterating the same number of times under different crossover and mutation parameter configurations and it is close to the optimal solution of the problem. As a result, the crossover and mutation probability has some relationship with the population size on the results on the algorithm.

[Figure omitted. See PDF.]

Fig 15. Minimum time in east wind field with wind speed of 5 m/s obtained by using different population sizes and crossover and mutation probabilities “Table in S1 Table”.

https://doi.org/10.1371/journal.pone.0194690.g015

In the same scenario, 20 experiments are performed for each crossover probability, mutation probability and population size. When the mutation probability and the population size are fixed and the crossover probability is 0.5, 0.6, 0.7, 0.8, and 0.9, there are totally 100 experimental results, the average of which is defined as the average minimum time under the given configuration. Fig 16(A) shows the average minimum time with the variation of population size at different mutation probabilities. It can be concluded that the result becomes better with increasing mutation probability under different scales, which is more obvious when the population size is smaller. While the population reached a certain scale, the solutions became less sensitive to the mutation probability. With the same experimental method, the average minimum time with the change of population size at different crossover probability can also be obtained. The average minimum time in Fig 16(B) are also relatively sensitive to the population size, and better results can be obtained as the population size increases. However, the crossover probability has little effect on the solutions under larger populations.

[Figure omitted. See PDF.]

Fig 16. Effect of crossover and mutation probabilities on the results of the algorithm under different population sizes “Table in S2 Table”.

https://doi.org/10.1371/journal.pone.0194690.g016

Therefore, it can be concluded that the crossover and mutation probabilities have a positive relationship with the effect of the algorithm results; that is, the larger the value of the crossover or mutation probability, the smaller the value of average minimum time. When the population size exceeds a certain scale, the crossover and mutation probabilities still has a positive effect on the algorithm, but the influence is obviously reduced.

In order to intuitively reflect the difference of the algorithm results in different populations and for different crossover and mutation probabilities, the three configurations of crossover and mutation probabilities are selected for population sizes of 400 and 800. 20 experiments are carried out under the same experimental configurations, and the results of the average minimum time, which varies with generation, is shown in Fig 17. When the population size is 400, the results of the three configurations are significantly different, and when the crossover probability is 0.9 and the mutation probability is 0.5, the algorithm has its best performance. When the population size increased to 800, the results among the three configurations are not significant difference, especially when the generation exceeds 90. It should also be noted that smaller population size can reduce the time cost of the algorithm’s operation at the same generation. After a comprehensive consideration of the above experimental process and results, in following experiments the crossover probability will be set to 0.9, the mutation probability to 0.5, the population size to 400, and the generation to 200.

[Figure omitted. See PDF.]

Fig 17. Algorithm solving process when given two population sizes and three kinds of crossover and mutation probability configurations “Table in S3 Table”.

https://doi.org/10.1371/journal.pone.0194690.g017

On this basis, the method described in Ref. [9] and that outlined in this study are both adapted to analyze the minimum time during which two UAVs finished their task of visiting the targets and returning to the starting point under four different winds (south wind, west wind, north wind, and east wind, with a constant wind speed of 5 m/s), and the results are shown in Table 5.

[Figure omitted. See PDF.]

Table 5. Results of task allocation and path planning under four different winds.

https://doi.org/10.1371/journal.pone.0194690.t005

It can be concluded that, the actual flight time of UAV will be changed greatly along the path which is planned without consideration of the influence of wind. For the method proposed in this paper, the allocation of tasks and the planning of the route are integrated and optimized under the influence of the wind, the result of which is the best possible solution in the wind. Compared to the results in Ref. [9], the actual flight time will be reduced by 35.06% in the wind.

Furthermore, experiments are performed with different wind speeds ranges from 1 to 8 m/s in the east wind, the results of which are shown in Table 6. Similarly, the actual flight time in the wind will be reduced by 36.86%. The flight routes when the wind speed is 2, 4, 6 and 8 m/s are shown in Fig 18.

[Figure omitted. See PDF.]

Fig 18. Minimum time paths for two UAVs to visit three targets in east wind with different wind speeds.

https://doi.org/10.1371/journal.pone.0194690.g018

[Figure omitted. See PDF.]

Table 6. Results of task allocation and path planning in East wind at different wind speeds.

https://doi.org/10.1371/journal.pone.0194690.t006

Conclusions and future works

Wind is a vitally important external factor in the actual flight of UAV. Different wind speeds and wind directions cause changes in heading angle and ground speed of UAV in actual flight. In this paper, in order to integrated optimize the task allocation and path planning of fixed-wing UAV, the steady wind environment was introduced into the optimization model, and the VS-DP-VRP model was established considering the dynamic constraints of UAV. The optimization objective of this model is to minimize the time required by UAVs to complete all of the tasks. Thus, the distance between any two targets was described by a Dubins path, and a method was proposed that combines the wind speed with the airspeed of UAV to calculate its ground speed. Considering that the VS-DP-VRP is still a NP-hard problem, the GA was chosen to solve this problem. The crossover operator in the GA and three kinds of mutation operators—namely, the mutation of targets, ground speed heading angle number mutation, and mutation in UAV allocation—were redesigned based on the characteristics of this problem. In addition, the feasibility and validity of the method were analyzed by an illustrative example, and the sensitivity of the influence caused by parameters such as population size, crossover probability, and mutation probability on the algorithm was analyzed. Moreover, the problem of multiple UAVs visiting multiple targets were comparatively analyzed, the results of which show that the proposed model and its algorithm can effectively provide a UAV task allocation and path planning scheme under steady wind. The wind direction and wind speed can be regarded as a steady wind as they are generally the same within a certain area. Yet changes in wind speed and wind direction cannot be ignored when the area is further expanded. In the future research, we will further consider the cases where wind speed and wind direction are constantly changing. Combined with UAV flight control strategy in variable wind, the integrated optimization of UAV task allocation and path planning under the influence of wind will be further explored.

Supporting information

[Figure omitted. See PDF.]

S1 Table. Minimum time in east wind field with wind speed of 5 m/s obtained by using different population sizes and crossover and mutation probabilities.

https://doi.org/10.1371/journal.pone.0194690.s001

(XLSX)

S2 Table. Effect of crossover and mutation probabilities on the results of the algorithm under different population sizes.

https://doi.org/10.1371/journal.pone.0194690.s002

(XLSX)

S3 Table. Algorithm solving process when given two population sizes and three kinds of crossover and mutation probability configurations.

https://doi.org/10.1371/journal.pone.0194690.s003

(XLSX)

Citation: Luo H, Liang Z, Zhu M, Hu X, Wang G (2018) Integrated optimization of unmanned aerial vehicle task allocation and path planning under steady wind. PLoS ONE 13(3): e0194690. https://doi.org/10.1371/journal.pone.0194690

References

1. Shames I, Fidan B, Anderson B D O. Close Target Reconnaissance Using Autonomous UAV Formations. IEEE Conference on Decision and Control. 2008:1729–1734.

2. Quintero S. A. P., Papi F., Klein D. J., Chisci L. Optimal UAV coordination for target tracking using dynamic programming. IEEE Conference on Decision and Control. 2010:4541–4546.

3. Price A., Pyke J., Ashiri D., Cornall T. Real time object detection for an unmanned aerial vehicle using an FPGA based vision system. IEEE International Conference on Robotics and Automation ICRA. 2006:2854.

4. Achille C., Adami A., Chiarini S., Cremonesi S., Fassi F., Fregonese L., et al. Uav-based photogrammetry and integrated technologies for architectural applications—methodological strategies for the after-quake survey of vertical structures in mantua (italy). Sensors, 2015,15(7):15520–15539. pmid:26134108

5. Vasuki Y., Holden E. J., Kovesi P., Micklethwaite S. Semi-automatic mapping of geological structures using uav-based photogrammetric data: an image analysis approach. Computers & Geosciences, 2014, 69(4):22–32.

6. Boutayeb M., Richard E., Rafaralahy H., Ali H. S., Zaloylo G. A simple time-varying observer for speed estimation of uav. IFAC Proceedings Volumes, 2008, 41(2):1760–1765.

7. Wan M, Dai Z, Chu W. Turning path planning for UAV in region coverage with scanline. Systems Engineering and Electronics,2014,36(9): 1750–1754.

8. Jiayi Sun, Jun Tang, Songyang Lao. Collision avoidance for cooperative UAVs with optimized artificial potential field algorithm. IEEE Access, 2017, vol. 5: page 18382–18390.

9. Edison E, Shima T. Integrated task allocation and path optimization for cooperating uninhabited aerial vehicles using genetic algorithms. Computer & Operations Research, 2011,38(1SI):340–356.

10. Rhudy, M. B., Larrabee, T., Chao, H., Gu, Y., Napolitano, M. UAV Attitude, Heading, and Wind Estimation Using GPS/INS and an Air Data System. AIAA Guidance Navigation and Control Conference.2013.

11. Chakrabarty A, Langelaan J. UAV Flight Path Planning in Time Varying Complex Wind-field. Proceedings of the American Control Conference. 2013: 2568–2574.

12. Akhtar N, Whidborne J F, Cooke A K. Real-time optimal techniques for unmanned air vehicles fuel saving. Proceedings of The Institution of Mechanical Engineers Part G-Journal of Aerospace Engineering, 2012, 226(G10):1315–1328.

13. Chen G., Zhen Z., Gong H., Sun Y. Constraints for unmanned aerial vehicles formation flight path. Guidance, IEEE Navigation and Control Conference. 2014:1106–1109.

14. Wen L, Eglese R. Minimum cost VRP with time-dependent speed data and congestion charge. Computers & Operations Research, 2015,56:41–50.

15. Montoya-Torres J. R., Franco J. L., Isaza S. N., Jiménez H. F., Herazo-Padilla N. A literature review on the vehicle routing problem with multiple depots. Computers & Industrial Engineering, 2015, 79:115–129.

16. Roberge V, Tarbouchi M, Labonte G. Comparison of Parallel Genetic Algorithm and Particle Swarm Optimization for Real-Time UAV Path Planning. IEEE Transactions on Industrial Informatics, 2013, 9(1):132–141.

17. Pehlivanoglu Y V. A new vibrational genetic algorithm enhanced with a Voronoi diagram for path planning of autonomous UAV[J]. Aerospace Science And Technology, 2012,16(1):47–55.

18. Doshi A. A., Postula A. J., Fletcher A., Singh S. P. N. Development of micro-uav with integrated motion planning for open-cut mining surveillance. Microprocessors & Microsystems, 2015, 39(8):829–835.

19. Guerrero J A, Bestaoui Y. UAV Path Planning for Structure Inspection in Windy Environments[J]. Journal of Intelligent & Robotic Systems, 2013,69(1-4SI1):297–311.

20. Fu Y., Ding M., Zhou C., Hu H. Route planning for unmanned aerial vehicle (uav) on the sea using hybrid differential evolution and quantum-behaved particle swarm optimization. IEEE Transactions on Systems Man & Cybernetics Systems, 2013,43(6):1451–1465.

21. Otte M, Silva W, Frew E. Any-Time Path-Planning: Time-Varying Wind Field plus Moving Obstacles. IEEE International Conference on Robotics and Automation ICRA. 2016:2575–2582.

22. Ceccarelli N., Enright J. J., Frazzoli E., Rasmussen S. J. Micro UAV Path Planning for Reconnaissance in Wind. IEEE American Control Conference, 2007:5310–5315.

23. Selecky M, Vana P, Rollo M, Meiser T. Wind Corrections in Flight Path Planning. International Journal of Advanced Robotics Systems, 2013,10(248).

24. Shiga K, Kumon M. Online path optimization for unmanned aerial vehicles under steady wind. IEEE/SICE International Symposium on System Integration (SII), 2012:138–143.

25. Zhang X, Chen J, Xin B. Path planning for unmanned aerial vehicles in surveillance tasks under wind fields. Journal of Central South University, 2014, 21(8):3079–3091.

26. Turkoglu K. Real-Time Guidance Strategies for Optimizing Aircraft Performance in Stochastic Wind Conditions. IEEE Proceedings of the American Control Conference. 2014:2480–2485.

27. Techy L, Woolsey C A. Minimum-Time Path Planning for Unmanned Aerial Vehicles in Steady Uniform Winds. Journal of Guidance Control and Dynamics, 2009,32(6):1736–1746.

28. Rucco A., Aguiar A. P., Pereira F. L., Sousa J. B. D. A Predictive Path-Following Approach for Fixed-Wing Unmanned Aerial Vehicles in Presence of Wind Disturbances. Advances in Intelligent Systems and Computing. 2016:623–634.

29. Sathyan A, Boone N, Cohen K. Comparison of Approximate Approaches to Solving the Travelling Salesman Problem and its Application to UAV Swarming. International Journal of Unmanned Systems Engineering, 2015,3(1):1–16.

30. N. Ernest, K. Cohen. Fuzzy clustering based genetic algorithm for the multi-depot polygon visiting Dubins multiple traveling salesman problem. AIAA Infotech@Aerospace, no. AIAA-2012- 2562.

31. Evers L., Barros A. I., Monsuur H., Wagelmans A. Online stochastic uav mission planning with time windows and time-sensitive targets. European Journal of Operational Research, 2014, 238(1):348–362.

32. Mufalli F, Batta R, Nagi R. Simultaneous sensor selection and routing of unmanned aerial vehicles for complex mission plans. Computer & Operations Research, 2012,39(11):2787–2799.

33. Faied M, Mostafa A, Girard A. Vehicle Routing Problem Instances: Application to Multi-UAV Mission Planning. AIAA Conference on Guidance, Navigation, and Control, 2010.

34. Eksioglu B, Vural A V, Reisman A. Survey: The vehicle routing problem: A taxonomic review. Computers & Industrial Engineering, 2009, 57(4):1472–1483.

35. Turkoglu K. Real-Time Strategies for Enhancing Aircraft Performance in Wind. Dissertations & Theses—Gradworks, 2012.

36. Owen M., Beard R. W., Mclain T. W. Implementing Dubins Airplane Paths on Fixed-Wing UAVs*. Springer Netherlands.2015.

37. Gao C, Zhen Z, Gong H. A self-organized search and attack algorithm for multiple unmanned aerial vehicles. Aerospace Science & Technology, 2016, 54:229–240.

38. Bakolas E, Tsiotras P. Time-Optimal Synthesis for the Zermelo-Markov-Dubins Problem: the Constant Wind Case. IEEE Proceedings of the American Control Conference, 2010:6163–6168.

39. Zhang Y, Ji G, Wang S, Phillips P, Wang W, Lee E. An Improved GA for solving multiple depot VRP. ACSR-Advances in Comptuer Science Research. 2015:551–554.

40. Individual T H. A Rule-Based Model for Bankruptcy Prediction Based on an Improved Genetic Ant Colony Algorithm. Mathematical Problems in Engineering, 2015, 2013(2):1–10.

41. Phuong K N, Crainic T G, Toulouse M. A tabu search for Time-dependent Multi-zone Multi-trip Vehicle Routing Problem with Time Windows. European Journal of Operational Research, 2013,231(1):43–56.

42. Zhang Y., Wang S., Phillips P., Ji G. Binary pso with mutation operator for feature selection using decision tree applied to spam detection. Knowledge-Based Systems, 2014, 64:22–31.

43. Du WB, Gao Y, Liu C, Zheng Z, Zhen W. Adequate is better: particle swarm optimization with limited-information. Applied Mathematics and Computation, Vol. 268:pp. 832–838, 2015.

44. Yit K K, Parvathy R. Differential-Evolution Control Parameter Optimization for Unmanned Aerial Vehicle Path Planning. Plos One, 2016, 11(3):e0150558. pmid:26943630

45. Karakatic S, Podgorelec V. A survey of genetic algorithms for solving multi depot vehicle routing problem[J]. Applied Soft Computing, 2015,27:519–532.

46. Arostegui M A, Kadipasaoglu S N, Khumawala B M. An empirical comparison of Tabu Search, Simulated Annealing, and Genetic Algorithms for facilities location problems. International Journal of Production Economics, 2006,103(2):742–754.

47. Youssef H, Sait S M, Adiche H. Evolutionary algorithms, simulated annealing and tabu search: a comparative study. Engineering Applications of Artificial Intelligence, 2001,14(2):167–181.

48. Tian J, Shen L, Zheng Y. Genetic algorithm based approach for multi-UAV cooperative reconnaissance mission planning problem. Lecture Notes In Artificial Intelligence. 2006:101–110.

49. Oz I, Topcuoglu H R, Ermis M. A meta-heuristic based three-dimensional path planning environment for unmanned aerial vehicles. Simulation-Transactions of The Society for Modeling and Simulation International, 2013,89(8):903–920.

50. Savuran H, Karakaya M. Efficient route planning for an unmanned air vehicle deployed on a moving carrier. Soft Computing, 2016,20(7):2905–2920.

51. Pehlivanoglu Y V. A new vibrational genetic algorithm enhanced with a Voronoi diagram for path planning of autonomous UAV. Aerospace Science and Technology, 2012,16(1):47–55.

52. Roberge V, Tarbouchi M, Labonte G. Comparison of Parallel Genetic Algorithm and Particle Swarm Optimization for Real-Time UAV Path Planning[J]. IEEE Transactions on Industrial Informatics, 2013,9(1):132–141.