Multi-UAV reconnaissance task allocation for heterogeneous targets using an opposition-based genetic algorithm with double-chromosome encoding

Zhu WANG,Li LIU,Teng LONG,*,Yonglu WEN

aSchool of Aerospace Engineering,Beijing Institute of Technology,Beijing 100081,China

bKey Laboratory of Dynamics and Control of Flight Vehicle,Ministry of Education,Beijing 100081,China

1.Introduction

Unmanned Aerial Vehicles(UAVs)play an increasingly important role in military and civilian applications,such as intelligence gathering,area surveillance,environmental monitoring,search and rescue,etc.However,limited by its size and capability,a single UAV can hardly complete complex and persistent tasks.1Thus,a team of UAVs is expected to perform tasks cooperatively.To achieve cooperation between UAVs,task allocation is necessary to make them conduct tasks in a good order and maximize the performance of the UAV team.

The basic task allocation problem can be formulated as a Travelling Salesman Problem(TSP),2which aims to find the shortest path for a salesman to visit all the cities.In the classic TSP,the path length between two cities is usually measured by the Euclidean distance.To consider the kinematic constraints of UAVs,the Dubins3model was introduced into the UAVs task allocation problem,and the Dubins path was applied to compute the length between two task points.Thus,the task allocation of UAVs was formulated as a Dubins Travelling Salesman Problem(DTSP).4Furthermore,Zhang et al.5considered the effective range of UAVs’sensors and formulated the problem as a Dubins Travelling Salesman Problem with Neighborhood(DTSPN).In the DTSPN,each target was treated as a region,and a UAV could complete the task when it got into the region.Additionally,a Cooperative Multiple Task Assignment Problem(CMTAP)6,7was built up for heterogeneous UAVs performing classification,attack,and verification tasks.

The above studies of UAV task allocation concentrated on the features of UAVs(e.g.,heterogeneity,kinematic constraints,and resource limitations),but the features of targets were ignored or considered to be homogeneous.In this article,we focus on the reconnaissance task allocation problem for UAVs,where ground targets with different features and sizes are considered.To describe the problem,a novel multiple cooperative UAVs reconnaissance task allocation model,i.e.,the extended Multiple Dubins Travelling Salesmen Problem(MDTSP),is presented.In the problem,heterogeneous targets are divided into point targets,line targets,and area targets,according to a target’s feature and a sensor’s performance.To accomplish the reconnaissance task,UAVs must cover all the heterogeneous targets using the equipped sensors.

The extended MDTSP is a typical NP-hard combinatorial optimization problem.A number of algorithms have been developed to solve combinatorial optimization problems,such as Mixed Integer Linear Programming(MILP),8–10Branch and Bound(BNB),11tree search,12and Genetic Algorithm(GA).6,7,13Traditional deterministic search algorithms(e.g.,MILP and BNB)can obtain locally optimal solutions for low-dimensional problems.Nevertheless,as the number of UAVs and targets grows,the computational cost of solving the MDTSP increases exponentially,and traditional deterministic algorithms can hardly find feasible solutions.On the contrary,stochastic search algorithms14,15can efficiently explore the design space to acquire feasible solutions by using random operations and heuristic mechanism.As a widely used heuristic algorithm,GA has been successfully applied forthe MDTSP7,13and verified to be potential to find superior solutions to the MDTSP.Thus,GA is employed in this article to solve the extended MDTSP.To improve the performance of GA on the extended MDTSP,an Opposition-based Genetic Algorithm with Double-chromosomes Encoding and Multiple Mutation Operators(OGA-DEMMO)is developed.The double-chromosomes encoding mechanism can reduce the search space to enhance the efficiency of the algorithm.Opposition-based learning and multiple mutation operators are introduced to improve the variety of population and increase the probability of converging to the optimal solution.

The remainder of this paper is organized as follows.Section 2 presents the basic models of a multi-UAV reconnaissance problem with heterogeneous targets.In Section 3,the combinatorial optimization model of the multi-UAV reconnaissance task allocation problem is established.In Section 4,an efficient GA with double-chromosomes encoding,opposition-based learning and multiple mutation operators is developed.In Section 5,numerical simulations are provided to validate the effectiveness of the proposed method.Finally,conclusions are summarized in Section 6.

2.Basic models

In this section,the model of sensors,the models of targets,and the motions equations of UAVs are established.The paths of covering different targets and the methods to generate Dubins paths are also discussed.

2.1.Sensor model

In this work,UAVs equipped with sensors are required to cooperatively reconnoiter ground targets.If a ground target is fully covered by a sensor’s field of view,the reconnaissance task on this target is finished.

The field of view of a sensor is assumed to be a circle region below the UAV,as illustrated in Fig.1.In Fig.1,His the flight altitude,ris the radius of the field of view,Xb-Yb-Zbdenotes the body coordinate system of the UAV,andd=2ris the reconnaissance width of the sensor.To simplify the problem,it is assumed that the sensor’s field of view is not influenced by the flight altitude and attitude of the UAV.

2.2.Targets model

In a real-world mission environment,reconnaissance targets have different features and shapes, and some targets usually conduct their missions in particular regions,such as ships travelling in rivers and trains moving on railways.Thus,reconnaissance targets are classified into point targets, line targets, and area targets in this paper,according to the features of a target’s geometry and a sensor’s field of view.

2.2.1.Point targets

A point target represents a target whose size is smaller than the field of view of a UAV.When a UAV flies over the center of a point target,the target can be fully covered by the sensor.Typical point targets include buildings and ground vehicles.

Point targets are further classified into two types,according to whether the reconnaissance direction of a target is limited.For a point target without a direction constraint(e.g.,targetT1in Fig.2),it can be found by a UAV flying over the target in any direction.However,for a point target with direction constraints(e.g.,targetT2in Fig.2),it can only be found when a UAV flies over the point target along a specific direction.

2.2.2.Line targets

A line target represents a target whose length is longer than a UAV’s reconnaissance widthd,but whose width is shorter than the UAV’s reconnaissance width.When a UAV flies over the center line along the longer side,a line target can be covered by the UAV’s sensor.Typical line targets include highways,rivers,railways,aircraft runways,etc.

As shown in Fig.3,the optimal reconnaissance path of a line target for a UAV is to fly over the center line along the longer side of the line target.Note that there are two entrances(L1andL2in Fig.3)for a line target.Different entrances lead to completely reverse reconnaissance directions.The lengths of reconnaissance paths from different entrances are the same,but the connecting paths between this target and other targets vary with the entrances.For the reconnaissance task allocation problem in this paper,the entrances of line targets also need to be allocated.

2.2.3.Area targets

An area target represents a target whose length and width are both longer than a UAV’s reconnaissance width.To accomplish the reconnaissance task,a UAV must cover area targets with zigzag paths.Typical area targets include squares,lakes,and other wide-area targets.In this paper,area targets are simplified as rectangles,and it is assumed that there is no constraint on the reconnaissance direction.

To generate the coverage path of area targets for UAVs,the parallel pattern16,17producing zigzag coverage paths with a minimum length is employed.The illustration of the parallel pattern is shown in Fig.4,wherePentryrepresents the entry point andPexitrepresents the exit point.Note that there are four entrances to generate different coverage paths with the same length,but the lengths of the paths to reach this target for different entrances are different.Thus,the entrances of area targets also need to be selected in the considered reconnaissance task allocation problem.

Fig.2 Schematic diagram of point targets.

Fig.3 Schematic diagram of a line target.

Fig.4 Illustration of a coverage path for an area target.

2.3.Dubins model for UAVs

In the considered problem,a number of heterogeneous targets need to be reconnoitered by multiple UAVs subject to the kinematic constraints.In this article,we assume that(1)the velocity of each UAV is constant;(2)the UAVs perform the reconnaissance task at a given altitude;(3)the UAVs fly at different altitudes to avoid inter-UAV collision;(4)each UAV carries enough fuel to accomplish the task.Moreover,the Dubins vehicle model3is used to describe each UAV’s motion constraints,given as follows:

where(x,y)is the horizontal position in the Cartesian inertial reference frame;θ is the heading angle;vis the flight speed;rminis the minimum turning radius;cis the control input.c＞0 means that the UAV turns left,c＜0 means that the UAV turns right,andc=0 means that the UAV goes straight.c=±1 means that the UAV turns with the minimum turning radius.In addition,the triplet(x,y,θ)defines the configurationqof the UAV.

2.4.Dubins path generation

Dubins paths are used to generate the connecting paths between targets.Considering the reconnaissance direction constraints of different targets,two kinds of Dubins paths are considered,i.e.,Dubins path with a terminal heading constraint and Dubins path without a terminal heading constraint.

2.4.1.Dubins path with a terminal heading constraint

A Dubins3path with a terminal heading constraint is the shortest path for a Dubins vehicle moving from the initial configuration to the final configuration.The shortest path is composed of two arcs with a radiusrminand one line segment,and it must be one candidate from the path set{RSL,LSR,RSR,LSL,RLR,LRL}3,whereRdenotes the clockwise arc,Ldenotes the counterclockwise arc,andSdenotes the line segment.

Fig.5 provides an example of the Dubins path set.3In Fig.5,Ois the initial position;Tis the final position;ORandOLare the centers of the clockwise and counterclockwise arcs.Meanwhile,the origin is the UAV’s initial position;the direction of thex-axis is from the initial position to the final position;the arrows indicate the moving directions of the vehicle.The length of each one in the path set can be computed using geometry methods.18,19After the length of each feasible path is acquired,the shortest path is selected as the desired Dubins path.

2.4.2.Dubins path without a terminal heading constraint

For a reconnaissance target without an entry direction constraint,a Dubins path without a terminal heading constraint is generated as the optimal path to reach the target.According to the relation between the initial and final positions,the path pattern of the Dubins path without a terminal heading constraint is determined.20Fig.6 provides different patterns of the Dubins path for targets located at the upper half plane.Considering the symmetry of Dubins paths with respect to thex-axis,paths can be generated in a similar way for targets located at the lower half plane.In Fig.6,the origin is the initial position of the UAV and the direction of thex-axis is along the initial heading of the UAV.When the pattern of the Dubins path is decided,the length of the Dubins path without a terminal heading constraint can be computed using geometry methods.

Fig.5 Dubins paths with a terminal heading constraint.3

Fig.6 Dubins paths without a terminal heading constraint for targets located at the upper half plane.20

3.UAVs reconnaissance task allocation model

In this section,the problem of multiple UAVs reconnaissance task allocation is firstly formulated as an extended MDTSP.Then,a detailed method to compute the length of the UAV’s reconnaissance path is presented.

3.1.Extended MDTSP model

The multi-UAV reconnaissance task allocation problem aims at finding the best target assignment result to UAVs,which maximizes the overall reconnaissance effectiveness.

Suppose that U={U1,U2,...,UNU}denotes a set ofNUUAVs and T={T1,T2,...,TNT}denotes a set ofNTground targets.The UAVs are expected to complete the reconnaissance on all the targets in a minimum time with minimum consumptions.Thus,the task execution time and the UAVs’total consumption are selected as two sub-objectives,and the objective function is defined as follows:

where α,β ∈ ［0,1］are the weight factors of the two subobjectives,which are subjected to α+ β =1;tuis the time of completing the allocated tasks for theuthUAV,andtuis determined by the path length and the flight speed,as given in the following equation:

For example,a possible set of decision variables and a length matrix for 2 UAVs and 4 targets is demonstrated in Fig.7.In Fig.7(a),the value ‘1” in the first column means the UAV translates fromU1toT1,the ‘1” in the third column means the UAV translates fromT1toT3,and the ‘1” in the fifth column means the UAV translates fromT3toU1.Thus,Fig.7(a)indicates that UAV 1 reconnoiters targets 1 and 3,and then returns to its initial configuration.Similarly,Fig.7(b)indicates that UAV 2 reconnoiters targets 2 and 4,and then returns to its initial configuration.Fig.7(c)is the length matrix w(qi,qj)between different configurations.In Fig.7(c),the terms marked in bold are the lengths need to be counted according to the decision matrices in Fig.7(a)and(b).

Additionally,the constraints in the following equations are imposed on the problem to ensure that all the targets are reconnoitered and each target is only assigned to one UAV,respectively:

Fig.7 Example of decision matrices and a length matrix.

3.2.Reconnaissance path length computation

Suppose that the number of targets assigned to a UAV to reconnoiter ism,and the target sequence is denoeted as{T1,T2,...,Tm},then the reconnaissance path of this UAV includes the following four parts:(A)the path from the UAV’s initial configuration to the first target’s entry configuration;(B)all the connecting paths from the exit configuration of current targetTjto the entry configuration of next targetTj+1,j=1,2,...,m-1;(C)the coverage paths of all the assigned targets;(D)the path from the exit configuration of the last target to the UAV’s initial configuration.Thus,the total length of the reconnaissance path of the UAV is calculated as follows:

where(x0,y0,θ0)is the initial configuration;(xj,yj,θj)is the entry configurationqjof targetTj;(x′j,y′j, θ′j)is the exit configurationq′jof targetTj;d(qi,qj)denotes the path length from con figurationqito con figurationqj;ljis the length of the coverage path for targetTj.

The length of the coverage path for a target has been discussed in Section 2.2.Meanwhile,the connecting path between targetTjand targetTj+1can be calculated in the following four situations according to the heterogeneity of targets.

(1)IfTj+1is a point target with a reconnaissance direction constraint,the Dubins path with a terminal heading constraint is applied to calculate the connecting path,as shown in Fig.8.

(2)IfTj+1is a point target without reconnaissance direction constraints,the Dubins path without a terminal heading constraint is employed,as shown in Fig.9.

Fig.8 Connecting path for a point target with a reconnaissance direction constraint.

Fig.9 Connecting path for a point target without a reconnaissance direction constraint.

Fig.10 Two possible connecting paths for a line target.

(3)IfTj+1is a line target,there are two possible entry configurations,as shown in Fig.10.For each entry con figuration,the Dubins path with a terminal heading constraint is employed to generate the connecting path.Then,the shorter one is chosen as the reaching path of this target.The entry and exit configurations are also determined.

(4)IfTj+1is an area target,there are four entry configurations,denoted asPentry1,Pentry2,Pentry3andPentry4,as shown in Fig.11.For each entry configuration,the length of the reconnaissance path of the target is the same,but the length of the connecting path from the previous target to this target depends on the entry configuration.The Dubins path with a terminal heading constraint is employed to calculate the connecting path length for each entry con figuration,and then the shortest one is selected as the reaching path.The entry and exit con figurations of the target are also determined.

Fig.11 Four possible connecting paths for an area target.

4.Modified GA for extended MDTSP

In this section,a modified genetic algorithm,i.e.,Opposition based Genetic Algorithm using Double-chromosomes Encoding and Multiple Mutation Operators (OGADEMMO)is tailored to solve the extended MDTSP.

4.1.Procedure of OGA-DEMMO

Genetic algorithm is a stochastic global optimization method based on the natural evolution mechanism.14In GA,a population of individuals is generated and each individual represents a solution candidate.The population is evolved with genetic operations including selection,crossover,and mutation to find the optimal solution.The evolution process is repeated until the termination condition is satisfied.

To enhance the performance of GA on the extended MDTSP,a double-chromosomes encoding method is developed to describe the relationships between targets and UAVs.Opposition-based learning and multiple mutation operators are introduced to increase the population diversity and accelerate the convergence speed.The pseudo-codes of OGADEMMO are shown in Algorithm 1 and the procedure of OGA-DEMMO is detailed as follows.

Algorithm 1.OGA-DEMMO for extended MDTSP.Begin 1 initialize population P with NPindividuals 2 compute the fitness of all the individuals in P 3 for each individual Pi,i=1,2,...,NPin P 4 compute the opposite individual^Pi 5 compute the fitness of the opposite individual 6 end for

7 select the best half individuals P′from P andP^8 while the stopping criteria is not satis fied 9 perform selection on P′to generate parent set PP 10 for each individual Pi,i=1,2,...,NPin PP 11 if δ ＜ pc(pcis the crossover probability and δ is a random number within(0,1))12 keep individual Piin parental set 13 else 14 move individual Piinto offspring set 15 end if 16 end for 17 perform crossover on remaining individuals in parental set to generate another part of offspring 18 if δ ＜ pm(pmis the mutation probability and δ is a random number within(0,1))19 perform multiple mutation on offspring set 20 end if 21 compute fitness of individuals in offspring set 22 for each individual Piin the offspring set 23 compute the opposite individualP^i 24 compute fitness of the opposite individual 25 end for 26 select the best half individuals from offspring and opposite populations as the next generation P′27 end while End

Step 1.Initialization(lines 1–2).An initial population withNpindividuals is randomly generated considering the constraints,and the fitness values of these individuals are calculated based on Eq.(2).

Step 2.Opposition(lines 3–7).An opposite population is computed by calculating each opposite individual using the method in Section 4.3,and the fitness values of individuals in the opposite population are calculated based on Eq.(2).Then,half of the individuals with better fitness are chosen from the initial and opposite population as the first generation.

Step 3.Selection(line 9).The roulette wheel selection method is used to obtain the parental population.Individuals with better fitness have a higher probability to be selected into the parental population.The selection process terminates when the size of the parental population reaches the size of the current population.

Step 4.Crossover(lines 10–17).Crossover is to combine the traits of two parental individuals to generate a new individual,which is probably better than both of the parents by inheriting the promising characteristics from each parent.The partially mapped crossover2operator is used here,as described in Section 4.4.1.

Step 5.Mutation(lines 18–20).With the mutation operation,the genes of individuals are probabilistically perturbed to make changes.The detailed mutation operator is given in Section 4.4.2.After mutations,the offspring are generated.

Step 6.Opposition(lines 21–26).The opposite individuals of the offspring are calculated,and fitness values of the offspring and their opposite individuals are computed.Then,half of the individuals with better fitness from the offspring and opposite populations are selected as the new population.

Step 7.Termination(lines 8 and 27).If the termination condition is satisfied,the iteration process stops;otherwise,the process jumps to Step 3.

4.2.Double-chromosome encoding

Considering the constraints of the multi-UAV reconnaissance task allocation problem,a double-chromosomes encoding method is developed,where both chromosomes are encoded by integers.The first one(chromosome I)represents the target sequence.The second one(chromosome II)represents the cut position of the target sequence in chromosomes I.In chromosome I,each gene represents the index of a reconnaissance target.Thus,the genes in chromosome I must be different from each other,and the total number of genes isNT.In chromosome II,the value of any gene must not be smaller than those of the genes ahead of it.In addition,the number of genes in chromosome II isNU-1 so that the target sequence in chromosome I is cut intoNUsub-sequences.

Several examples of double-chromosomes encoding for 10 targets and 4 UAVs are shown in Fig.12.

Example 1:chromosome II is(3,5,8),so the genes in chromosome I,i.e.,(8,1,6,3,5,7,10,4,2,9)are cut into four subsequences after the 3rd,5th,and 8thgenes.Then,four subsequences(8,1,6),(3,5),(7,10,4),and(2,9)represent the target sequences for UAVs 1,2,3,and 4,respectively.

Example 2:chromosome II is(0,5,8),so the genes in chromosome I are cut after the 0th,5th,and 8thgenes.Then,three sub-sequences(8,1,6,3,5),(7,10,4),and(2,9)represent the target sequences for UAVs 2,3,and 4,respectively.Note that no target is assigned to UAV 1 in this example.

Example 3:chromosome II is(4,7,10),so the genes in chromosome I are cut after the 4th,7th,and 10thgenes.Then,three sub-sequences(8,1,6,3),(5,7,10),and(4,2,9)represent the target sequences for UAVs 1,2,and 3,respectively.

Example 4:chromosome II is(4,4,7),so the genes in chromosome I are cut after the 4th,4th,and 7thgenes.Then,three sub-sequences(8,1,6,3),(5,7,10),and(4,2,9)represent the target sequences for UAVs 1,3,and 4,respectively.Note that UAV 2 does not reconnoiter any target in this example.

Example 5:chromosome II is(4,4,4),so the genes in chromosome I are cut after the 4th,4th,and 4thgenes.Then,two sub-sequences(8,1,6,3)and(5,7,10,4,2,9)represent the target sequences for UAVs 1 and 4,respectively.Note that no target is assigned to UAVs 2 and 3.

Fig.12 Examples of double-chromosomes encoding.

4.3.Opposition-based learning

The idea of opposition-based learning21,22is built upon common observations from the real world,e.g.,the opposition of a weak person is strong compared to him/her.By using the opposition-based learning strategy in OGA-DEMMO,an opposite population is generated after initialization and mutation operations to improve the probability of finding better solutions.

For a variablezwithin the interval of[a,b],its opposition^zis defined as

For a point P=(z1,z2,...,zD)in the space,its opposition point^P= （^z1,^z2,...,^zD）is generated by calculating the opposition value in each dimension,as given in the following equation:

In OGA-DEMMO,chromosome I of an individual is regarded as a multidimensional point to compute its opposition.For example,chromosome I is(1,7,8,4,5,3,6,2).The lower and upper bounds of all genes are 1 and 8,respectively.Then,the opposition of chromosome I is(8,2,1,5,4,6,3,7).

4.4.Genetic operators

4.4.1.Crossover operator

A crossover operator is used to create a pair of offspring chromosomes from a pair of parent chromosomes.It should be noted that the crossover operator is only applied to chromosome I in this paper,while chromosome II remains unchanged in the process of crossover.This work uses the partially mapped crossover(PMX)operator,2where a portion of one parent’s genes is exchanged with a portion of the other parent’s genes,and the remaining genes are copied or regenerated by mapping.

Fig.13 Example of the partial-mapped crossover operator.3

An example of the PMX operator is illustrated in Fig.13.Firstly,two cut points are randomly selected as:(1)the point between the third and fourth genes;(2)the point between the sixth and seventh genes.Then,two mapping sections(4,5,6)and(1,6,8)are decided,and mappings 4?1,5?6,and 6?8 are also defined.Secondly,the mapping section in parent I(parent II)are copied to offspring II(offspring I).After that,the remaining genes of the two offspring are filled up by copying the genes from the corresponding parents or regenerating by the mappings.For example,the first gene of offspring I is 1 by directly copying the first gene from parent I.However,this gene(i.e.,1)already exists.Hence,the first element of offspring I is reset to 4 according to the mapping 4?1.The second,third,and seventh genes of offspring I can be copied directly from parent I.By copying from parent I,the last gene of offspring I is 8,which already exists.According to the mappings 6?8 and 5?6,it is mapped to be 5.Hence,offspring I is(4,2,3,1,6,8,7,5).In a similar way,offspring II can be generated as(3,7,8,4,5,6,2,1).

4.4.2.Multiple mutation operators

A mutation operation is an important mechanism in GA to prevent a population from being trapped into local minima and to improve the global convergence of the algorithm.In OGA-DEMMO,multiple types of mutation operators are combined to increase the diversity of a population and enhance the capability of global exploration.Because double-chromosomes encoding is employed and the two chromosomes have different meanings for an individual,we apply different mutation operators for the two chromosomes.The detailed mutation operators for chromosome I and chromosome II are described as follows.

(1)Mutation operators of chromosome I

Flip mutation operator.Two positions on chromosome I are firstly randomly generated.Then,the genes between the two points are reversed.An example of the flip mutation operator is shown in Fig.14.

Swap mutation operator.Two positions on chromosome I are firstly randomly selected.Then,the two genes on the selected points are exchanged,as shown in Fig.15.

Slide mutation operator.Two positions on chromosome I are firstly randomly selected.Then,the gene on the first selected point is moved to the end of the selected substring,and the remaining genes of the selected substring slide forward.An example of the slide mutation operator is given in Fig.16.

Fig.14 Flip mutation operator example.

Fig.16 Slide mutation operator example.

Table 1 Eight offspring after multiple mutation operations.

(2)Mutation operator of chromosome II

Regenerate mutation operator.The regenerate mutation operator is to randomly regenerate each gene of chromosome II.Note that the constraints of chromosome II must be satisfied in the regeneration process.

(3)Combined multiple mutation operators

Since chromosome I or II can remain unchanged,there are four types of mutation operations for chromosome I,i.e.,remain, flip,swap,and slide,and two types of mutation operations for chromosome II,i.e.,remain and regenerate.Thus,by combining mutation operators for chromosome I and chromosome II,eight mutation operation results for double chromosomes encoding can be produced.

For example,suppose that chromosome I is(1,2,3,4,5,6)and chromosome II is(2,4).The two random positions are on the 2nd and 5thgenes of chromosome I,and chromosome II becomes(3,5)using the regenerate mutation operator.Then,eight offspring individuals can be generated by multiple mutation operations,as shown in Table 1.

In the mutation process of OGA-DEMMO,the population after the crossover operation is divided into multiple groups,and each group includes eight individuals.Then,the best individual of each group is mutated to generate eight new individuals.

5.Simulation experiments

In this section,numerical simulations are conducted to demonstrate the effectiveness of the established models and the proposed method.The tests are run in the MATLAB environment on a PC equipped with Intel(R)Core(TM)2 Duo CPU E7500 2.93 GHz and 4 GB RAM.All the parameters of the simulations are normalized.The task region is limited in a square area[0,100]×[0,100].The reconnaissance width of each UAV is 4.The probabilities of crossover and mutation are set to be 0.9 and 0.1,respectively.The weight factors α and β of sub-objectives are both set to be 0.5.

5.1.Simulation I

In this simulation,the effects of UAVs’kinematics on the reconnaissance task are tested in four different scenarios.The detailed information of each scenario is given in Table 2,whereTpoint1represents a point target without a terminal heading constraint,Tpoint2represents a point target with a terminal heading constraint,Tlinerepresents a line target,andTarearepresents an area target.Since the minimum turning radius greatly influences the length of the Dubins path,the tests are conducted with different turning radii for each scenario.In the simulations,the iterations of OGA-DEMMO are terminated when the Number of Function Evaluations(NFE)exceeds the maximum limitation(i.e.,80).The tests of each scenario with a given turning radius are run 20 times and the average path length is computed.

Fig.17 shows the reconnaissance paths for the above scenarios when the minimum turning radius is 6.It can be seen that the proposed method generates the shortest reconnaissance paths for all the scenarios.The positions of the targets are the same in scenarios I and II,but the reconnaissance directions of targets 3 and 4 are constrained in scenario II.From Fig.17(b),the generated path makes extra turns to reach the targets and satisfies the reconnaissance constraints for scenario II.From Fig.17(c)and(d),the generated paths can achieve a coverage of the line and area targets in scenarios III and IV,which meets the requirements of the targets reconnaissance.

Table 2 Scenarios information of simulation I.

Fig.17 Reconnaissance paths for the illustrative scenarios.

Fig.18 Variations of the average path length with the minimum turning radius.

Fig.18 shows the variation of the average reconnaissance path length with respect to the minimum turning radius in different scenarios.It can be found that the length of the reconnaissance path increases with the minimum turning radius for all the scenarios.The increasing trend of the path length of scenario IV is obviously larger than those of the other three scenarios.This is because there exists an area target in scenario IV and the zigzag paths of covering the area target involves multiple turns.Moreover,for scenario IV,the path length withrmin=12 is about 1.6 times of that withrmin=2.Thus,the kinematics of UAVs can have great effects on the path length and must be considered to compute an accurate reconnaissance path.

Table 3 Scenarios information of simulation II.

Fig.19 Optimal task allocation results for different scenarios.

5.2.Simulation II

To verify the effectiveness and optimality of the proposed method in solving multi-UAV task allocation problems,OGA-DEMMO is compared with an ordinary GA using Double-chromosomes Encoding(GA-DE),Ant Colony Optimization(ACO),23and Random Search(RS)on different scenarios.The detailed information of scenarios is listed in Table 3.The minimum turning radius of each UAV is set to be 4.All the algorithms employ the same stopping criterion,i.e.,the NFE exceeds the maximum limitation,and each algorithm is performed 100 times for each scenario to generate statistical results.

The optimal task allocation results and reconnaissance paths by OGA-DEMMO for different scenarios are given in Fig.19.It can be seen that all the targets are visited by UAVs in each scenario.The generated paths can guide the UAVs to cover the line and area targets.Meanwhile,the UAVs paths satisfy the reconnaissance direction constraints of different targets and the kinematics constraints of the UAVs.Besides,the reconnaissance sequences of the assigned targets for the UAVs are in a good order.Thus,OGA-DEMMO can obtain satisfied task allocation results for multi-UAV cooperative reconnaissance problems on heterogeneous targets.

The detailed allocation results of the multi-UAV reconnaissance task are provided in Table 4,where the total length indicates the consumptions of the UAVs and the longest length indicates the execution time of the reconnaissance task.From the allocation results,the targets are appropriately assigned to different UAVs,and the UAVs can cooperatively accomplish the reconnaissance task to reduce the task execution time.

The statistical results of 100 tests for different algorithms are presented in Table 5,where min and max indicate the minimum and maximum values among the optimized objective values of 100 runs,respectively,avg indicates the average objective values of 100 runs,andnis the times of finding the optimal solution among 100 runs.Note that the optimal solution here means the best solution found by all the algorithms in 100 tests.The best results among different algorithms for each scenario are highlighted in bold in Table 5.

Fig.20 Standard deviation of objective values of 100 runs.

According to the minimum objective values obtained from 100 tests,OGA-DEMMO can obtain optimal solutions for all the four scenarios,while GA-DE and RS cannot find the optimal solution in scenario VIII,and ACO only finds the optimum in scenarios V and VI.Because the dimensions of the problem for scenarios V and VI are not large,all the tested algorithms can easily find the optima.However,for scenarios VII and VIII which are large-scale problems,GA-DE,ACO,and RS can hardly find the optimal solutions,while the tailored OGA-DEMMO still has the ability to obtain the optimal solutions.Thus,OGA-DEMMO provides a better global exploration capability than GA-DE,ACO,and RS.From the average objective values of 100 tests,OGA-DEMMO always produces lower values than the other three algorithms.Thus,it is verified that OGA-DEMMO is better than the other algorithms from the optimality of the results.Besides,according to the times of finding optimal solutions among 100 tests,OGA-DEMMO has the highest probability to obtain the best solutions for each scenario,which demonstrates the favorable robustness performance of our proposed OGA-DEMMO.

Additionally,the standard deviations of optimized objective values from 100 runs of different algorithms are shown in Fig.20.It can be seen that the standard deviations of objective values from OGA-DEMMO are always smaller than those from GA-DE,ACO,and RS in each scenario.Thus,by using opposition-based learning and tailored genetic operators,OGA-DEMMO can provide stronger robustness for multi-UAV reconnaissance task allocation problems with heterogeneous targets.

Table 4 Multi-UAV reconnaissance task allocation results of simulation II.

Table 5 Comparison results between different algorithms.

6.Conclusions

(1)A novel multi-UAV reconnaissance task allocation model is presented,which considers the heterogeneity of targets and the constraints of UAVs and targets.The optimization objective is to minimize the weighted sum of the task execution time and the total UAV consumption.

(2)A modified genetic algorithm(i.e.,OGA-DEMMO)is developed to solve the extended MDTSP.Double chromosomes encoding is developed to describe the allocation results of targets to UAVs.Opposition-based learning and multiple mutation operators are used to improve the optimality and convergence efficiency.

(3)The effectiveness of OGA-DEMMO is validated by numerical experiments of different scale scenarios.Comparison results show that OGA-DEMMO can provide a better global exploration capability and a stronger robustness performance for multi-UAV reconnaissance task allocation problems with heterogeneous targets.

Acknowledgements

This study was co-supported by the National Natural Science Foundation of China (Nos.51675047,11372036,and 51105040)and the Aeronautical Science Foundation of China(No.2015ZA72004).

1.Shima T,Rasmussen S.UAV cooperative decision and control:challenges and practical approaches.Philadelphia:Society for Industrial and Applied Mathematics;2009.

2.Larranaga P,Kuijpers CMH,Murga RH,Inza I,Dizdarevic S.Genetic algorithms for the travelling salesman problem:a review of representations and operators.Artif Intell Rev1999;13(2):129–70.

3.Dubins LE.On curves of minimal length with a constraint on average curvature and with prescribed initial and terminal positions and tangents.Am J Math1957;79(3):497–516.

4.Savlak K,Frazzolie E,Bullo F.Traveling salesperson problems for the Dubins vehicle.IEEETAutomat Contr2008;53(6):1378–91.

5.Zhang X,Chen J,Xin B,Peng Z.A memetic algorithm for path planning of curvature-constrained UAVs performing surveillance of multiple ground targets.Chin J Aeronaut2014;27(3):622–33.

6.Edison E,Shima T.Integrated task assignment and path optimization for cooperating uninhabited aerial vehicles using genetic algorithms.Comput Oper Res2011;38(1):340–56.

7.Deng QB,Yu JQ,Wang NF.Cooperative task assignment of multiple heterogeneous unmanned aerial vehicles using a modified genetic algorithm with multi-type genes.Chin J Aeronaut2013;26(5):1238–50.

8.Richards A,Bellingham J,Tillerson M,Jonathanet H.Coordination and control of multiple UAVs.Proceedings of the AIAA Guidance,Navigation and Control Conference;2002 Aug 5–8;Monterey,USA.Reston:AIAA;2002.

9.Schumacher C,Chandler P.Constrained optimization for UAV task assignment.Proceedings of the AIAA Guidance,Navigation,and Control Conference;2004 Aug 16–19;Providence,USA.Reston:AIAA;2004.

10.Darran M.Multiple UAV dynamic task allocation using mixed integer linear programming in a SEAD mission.Infotech@Aerospace Conference;2005 Sept 26–29;Arlington,USA.Reston:AIAA;2005.p.1–11.

11.Hoai An LT,Duc Manh N,Tao PD.Globally solving a nonlinear UAV task assignment problem by stochastic and deterministic optimization approaches.Optim Lett2012;6(2):315–29.

12.Rasmussen SJ,Shima T.Tree search algorithm for assigning cooperating UAVs to multiple tasks.Int J Robust Nonlin2008;18(2):135–53.

13.Shima T,Rasmussen SJ,Sparks AG,Pasino KM.Multiple task assignments for cooperating uninhabited aerial vehicles using genetic algorithms.Comput Oper Res2006;33(11):3252–69.

14.Goldberg DE.Genetic algorithms in search,optimization and machine learning.Boston:Addison-Weseley;1989.

15.Michalewicz Z,Fogeld DB.How to solve it:modern heuristics.Heidelberg:Springer;2004.p.139–55.

16.Maza I,Ollero A.Multiple UAV cooperative searching operation using polygon area decomposition and efficient coverage algorithm.Proceedings of the7thInternational Symposiumon Distributed Autonomous Robotics Systems;2004 Jun 23–25,Toulouse,France.Tokyo:Springer;2004.p.221–30.

17.Nigam N.The multiple unmanned air vehicle persistent surveillance problem:a review.Machines2014;2(1):13.

18.Lavalle SM.Planning algorithms.Cambridge:Cambridge University Press;2006.

19.Tsourdos A,White B,Shanmugavel M.Cooperative path planning of unmanned aerial vehicles.Chichester:Jone Whiley&Sons;2011.p.29–63.

20.Boissonnat JD,Bui XN.Accessibility region for a car that only moves forward along optimal paths.Janvier:INRIA;1994.p.1–19.

21.Wang H,Wu Z,Rahamayan S,Liu Y,Ventresca M.Enhancing particle swarm optimization using generalized opposition-based learning.Inform Sci2011;181(20):4699–714.

22.Iqbal MA,Khan NK,Mujtaba H,Baig AR.A novel function optimization approach using opposition based genetic algorithm with gene excitation.Int J Innovat Comput Inform Control2011;7(7B):4263–76.

23.Martinovic G,Bajer G.Solving the task assignment problem with ant colony optimisation incorporating ideas from the clonal selection algorithm.Int J Bio-Inspir Com2015;7(2):129–43.