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

Date Published: March 21, 2018

Publisher: Public Library of Science

Author(s): He Luo, Zhengzheng Liang, Moning Zhu, Xiaoxuan Hu, Guoqiang Wang, Bo An.

http://doi.org/10.1371/journal.pone.0194690

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.

Partial Text

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].

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.

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.

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

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

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.

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.

 

Source:

http://doi.org/10.1371/journal.pone.0194690