HU Lei ,XI Boqi ,YI Guoxing,* ,ZHAO Hui ,and ZHONG Jiapeng

1.School of Astronautics,Harbin Institute of Technology,Harbin 150000,China;2.HIT (Anshan) Institute of Industrial Technology,Harbin Institute of Technology,Anshan 114000,China

Abstract:Reconnaissance mission planning of multiple unmanned aerial vehicles (UAVs) under an adversarial environment is a discrete combinatorial optimization problem which is proved to be a non-deterministic polynomial (NP)-complete problem.The purpose of this study is to research intelligent multi-UAVs reconnaissance mission planning and online re-planning algorithm under various constraints in mission areas.For numerous targets scattered in the wide area,a reconnaissance mission planning and re-planning system is established,which includes five modules,including intelligence analysis,sub-mission area division,mission sequence planning,path smoothing,and online re-planning.The intelligence analysis module depicts the attribute of targets and the heterogeneous characteristic of UAVs and computes the number of sub-mission areas on consideration of voyage distance constraints.In the sub-mission area division module,an improved K-means clustering algorithm is designed to divide the reconnaissance mission area into several sub-mission areas,and each sub-mission is detected by the UAV loaded with various detective sensors.To control reconnaissance cost,the sampling and iteration algorithms are proposed in the mission sequence planning module,which are utilized to solve the optimal or approximately optimal reconnaissance sequence.In the path smoothing module,the Dubins curve is applied to smooth the flight path,which assure the availability of the planned path.Furthermore,an online re-planning algorithm is designed for the uncertain factor that the UAV is damaged.Finally,reconnaissance planning and re-planning experiment results show that the algorithm proposed in this paper are effective and the algorithms designed for sequence planning have a great advantage in solving efficiency and optimality.

Keywords:reconnaissance mission planning,sequence planning,path smoothing,combination optimization.

1.Introduction

Unmanned aerial vehicle (UAV) is an unmanned flight platform that can carry various payloads and can be expanded and recycled [1].With the development of science and technology,technologies such as robust control,endurance distance,and artificial intelligence of UAVs have made great progress.The application of UAVs has become indispensable technical support for military mission,natural exploration,disaster relief,etc.[2,3].In addition,UAV has the advantages of low cost,small size,reusability,zero casualties,and strong adaptability [4,5],which can replace human beings to perform the various dangerous and complicated missions.As a key technology for complex reconnaissance missions,multiple UAVs collaborative mission planning is a discrete combinatorial optimization problem,and its complexity increases geometrically with the increase of the number of UAVs and the number of targets,which is a non-deterministic polynomial (NP)-complete problem [6,7].Therefore,how to obtain the optimal solution or approximately optimal solution of multi-UAVs cooperative mission planning is a research hotspot [8,9].

It is widely known that multiple UAVs cooperative mission planning includes two aspects: mission assignment [10-13] and path planning [14-16].Many scholars have done a lot of research on multiple UAVs collaborative mission planning and put forward a variety of algorithms that can be divided into two types: optimization algorithm and heuristic algorithm.The exact optimization algorithm includes exhaust search algorithm,branch and bound algorithm [17],and dynamic programming algorithm [18,19],which can obtain the optimal solution[20].However,the calculation costs of these algorithms are huge when the optimization problem has hard side constraints [21].The heuristic algorithm includes simulated annealing algorithm [22],tabu search algorithm[23],particle swarm optimization algorithm [24,25],genetic algorithm [26,27],wolf swarm optimization algorithm [28],and ant colony optimization algorithm[21,29].In addition,game theory [30],reinforcement learning [31],and probability graph theory [32] are also applied to solve collaborative mission planning problems.

For the multiple UAVs mission planning problems,many scholars are dedicated to researching the diverse scenarios,such as disaster relief [6,15],Internet of Things services [11],reconnaissance and search [13,16],delivery system [14],and military mission [17,18,21].When human beings affected by flood require a time-critical help,the ground rescue operations are difficult to carry out.Instead,UAVs carrying rescue materials are available.Zafar et al.[6] proposed a distributed method to solve the rescue problem which includes the communication,cooperation,and monitoring of UAVs.Aiming at the communication loss problem in the urban area,Padilla et al.[15] developed an aerial communication relay platform,and the flight path of aircraft was planned by the Hermite-Simpson collocation method.Motlagh et al.[11] proposed a smart mechanism for the value-added Internet of Things service,which took UAV’s energy consumption and UAVs’ operation time into consideration,linear integer programming method,and bargaining game were combined to solve the problem.Chen et al.[13] built a time-window based reconnaissance mission scheme for heterogeneous targets with logical and physical constraints.Yao et al.[16] studied the coverage search mission in a river region which can be described as an offline route planning problem of UAV,positive/negative greedy method was proposed to expand or contract waypoints.Grippa [14] studied the framework for UAV-based delivery systems with impatient customers and built a novel model for the stochastic and dynamic pickup and delivery problem.Murray et al.[17] presented an improved branch and bound algorithm to solve the dynamic resource management problem.However,the branch and bound algorithm was proved to be time prohibitive for some large-scale problems.Huang et al.[18]proposed an approximate dynamic programming method to solve the decision-making problem in air confrontation.Zhen et al.[21] proposed an improved distributed ant colony optimization (IDACO) algorithm to solve a cooperative search-attack mission planning problem.

Many researchers concentrated on studying the various mission planning algorithms,Goez et al.[25] evaluated the energy and performance consumption of UAV which flew in an unknown environment,and the online particle swarm optimization (OPSO) algorithm was applied to real-time planning.Shivgan et al.[26] paid attention to the limited battery capacity and the flight time,and genetic algorithm with energy optimization and genetic algorithm with distance optimization (GADO)algorithms were proposed to minimize the energy consumption.Wu et al.[27] integrated the mission assignment and trajectory generation,and the distributed genetic algorithm was utilized to search for the optimal solution.Radmanesha et al.[28] constructed a distancebased value function,and a grey wolf optimization algorithm was applied to find the optimal UAV trajectory in presence of moving obstacles.Gao et al.[29] proposed a search-attack mission self-organization algorithm where the ant colony optimization algorithm was designed to generate the path points and the Dubins curve was used to connect the path points smoothly.Some practical methods are applied to deal with the mission planning problem.Li et al.[30] developed a game-theoretic formulation of multiple UAVs cooperation search and surveillance mission,and offered a flexible way to accommodate different global objectives.Thi et al.[33] compared the performance of the cross-entropy method and the branch and bound method in terms of solving the nonlinear UAV mission assignment problem.

In the complex and complicated military mission scenario,it is indispensable to plan the optimal reconnaissance mission sequence and detect the intelligence information.Although many researchers have done a lot of works for the UAV reconnaissance mission planning,to the best of the author’s knowledge,it is a fact that relevant research work which takes the following factors into consideration is lacking: (i) the numerous target quantity in mission scenario,and the different attributes of targets;(ii) the heterogeneous characteristics of UAVs,such as the voyage distance and the type of sensors;(iii) the health status of UAV during the reconnaissance process.Consequently,this paper is dedicated to solving the problem of multiple UAVs reconnaissance mission planning and re-planning under the premise of considering the above factors.The main contributions of this paper are depicted as follows.

(i) For the multiple-UAVs reconnaissance mission planning problem in wide areas,we not only consider the UAVs’ constraints such as minimum turning radius constraint and voyage distance constraint,but also the sensor type loaded in UAV,the type of target,etc.

(ii) A framework of multiple UAVs reconnaissance mission planning and re-planning is designed,which includes five modules,including intelligence analysis,sub-mission area division,mission sequence planning,path smoothing,and online re-planning.

(iii) Considering the voyage distance constraint and sensor constraint,one UAV may be not available for the reconnaissance mission of all targets scattered in mission area,an improvedK-means clustering algorithm is proposed to divide the large mission area into several small sub-mission areas.

(iv) Based on the idea of importance sampling and cross-entropy,the elaborative iteration process of the reconnaissance sequence planning is deduced,the sampling and iteration algorithms are given which can be utilized to acquire the optimal and approximately optimal reconnaissance sequence.

(v) To be realistic,the Dubins curve is applied to smooth the flight path,and in the process of carrying out the reconnaissance mission,the uncertain factor that UAV may be damaged and unable to continue its reconnaissance mission is considered,and an online re-planning algorithm is designed.

The rest of this paper is organized as follows: The reconnaissance mission planning and re-planning framework is presented in Section 2.Furthermore,the algorithms for the reconnaissance mission planning and replanning are designed in Section 3.Section 4 employs the simulation experiments to verify the rationality of the proposed framework and the performance of the proposed algorithms.Finally,conclusions are given in Section 5.

2.Multiple UAVs mission planning and re-planning framework

2.1 Scenario of reconnaissance mission

Relevant nomenclature in this paper is listed in Table 1.Supposing that there areNTtargets scattered in mission area,the attribute of each target is different.There areNRavailable UAVs,and each UAV carries disparate sensors in terms of number and type.The reconnaissance mission scenario is depicted in Fig.1.The red solid circle represents the reconnaissance UAV system (UAVS) base,the blue solid hexagonal star,diamond,square,triangle,and star represent five different types of targets.Relevant hypothesizes and definitions are given as follows.

Table 1 Nomenclature

Fig.1 Reconnaissance mission scenario

Hypothesis 1The flight altitude and speed of different types of UAVs are different,but the flight altitude and speed of the same type of UAV are constant.

Hypothesis 2Any two targets scattered in the mission area are mutually accessible,that is,the graph is complete.

Hypothesis 3UAV damage is a random event in the process of reconnaissance.

Definition 1Indicator functionp(i;ε) represents the type and number of sensors loaded in UAV.

Definition 2Indicator functionq(j;ε) represents the target type,and each target belongs to a certain type,that

Definition 3Indicator functionI(i;j) represents whether the UAViis capable of detecting targetj,andI(i;j)∈{0,1}.

Definition 4Indicator functionr(i;j) indicates whether the UAViperforms the reconnaissance mission of targetj.

Indicator functionI(i;j)=1 describes the reconnaissance applicability of UAVifor targetj,UAViis just a candidate for targetj,in other words,we propably do not use UAVito detect targetjdue to the other constraints such as voyage distance constraint.Indicator functionr(i;j)=1represents that the UAViis used to perform the reconnaissance mission of targetj.

Definition 5Indicator functionh(i;τ) indicates the healthy state of UAViat time τ.

wherepeis a random number andpe∈(0,1) ; δeis the probability used to describe the rare event that UAV is damaged or fails to work (we set δe=0.01);h(i;τ)=1 represents the UAViis healthy at time τ.

Furthermore,the following constraints are taken into consideration.

Maneuverability constraintC1The turning radiusri(τ) of UAViat time τ must be greater than the minimum turning radius.

Sensor constraintC2Only if the UAViloads the detective sensor that is capable to detect targetj,then UAVicould be utilized to detect targetj.

Reconnaissance times constraintC4Each target is detected only once.

2.2 Reconnaissance mission model

Let χRibe the set of all possible tours of UAVi,letSRi(XRi) be the Dubins path length of the tourXRi∈χRi,the voyage distance cost function of UAVican be depicted as follows:

It is noticeable that (10) depicts a discrete combination optimization problem,which is an extended traveling salesman problem.It is a hard problem that there are a lot of targets in the mission area,which cannot be detected by one UAV on consideration of voyage distance constraint and sensor type constraint.An intuitive idea is to divide the mission area into several sub-mission areas,each sub-mission area will be detected by one UAV that is satisfied with those considered constraints.Let there beKsub-mission areas,the total voyage distance cost function of the whole mission area can be denoted as follows:

whereSKis the total voyage distance cost function ofKUAVs,(14) is used to deal with the reconnaissance times constraintC4,and the number of targets detected byKUAVs isNT.

In this case,the reconnaissance mission planning and re-planning framework is designed,as shown in Fig.2.The fundamental intelligence analysis module analyzes the type and number of targets in the mission area,as well as the characteristic of UAVs,and gives the number of required UAVs to complete the reconnaissance mission.In the reconnaissance sub-mission area division module,we propose an improvedK-means clustering algorithm to divide the mission area,and each sub-mission is detected by one UAV which meets the voyage distance and sensor type constraints.Aiming at the sub-mission,the reconnaissance sequence planning algorithm based on cross entropy and importance sampling is developed in the mission sequence planning module.According to the planned reconnaissance sequence,the path smoothing module applies the Dubins curve to smooth the planned path.The online re-planning module deals with the uncertainty of UAV damage in the reconnaissance process.

Fig.2 Reconnaissance mission planning and re-planning framework

3.Reconnaissance mission planning and online re-planning algorithm

3.1 Dubins path

To make the work more realistic and reliable,the UAV is regarded as the Dubins car model,which is described by a ternary array ＜x,y,θ ＞,and its basic dynamic model[34] is depicted as follows:

wherevrepresents the velocity of Dubins car,and θ is the direction whose control quantity isuθ.

The minimum turning radius of Dubins car isrturn,then the angular rate is denoted as follows:

The UAV is regarded as the Dubins car model,then the flight height of UAV is constant,the flight speed is denoted asvand the changeable heading angle is denoted as θ.Given the positions of the initial and terminal points of the UAV,the Dubins path [35] is defined as the shortest path satisfying the curvature constraint in the twodimensional Euclidean plane,which is composed of arc and straight line.These paths include six forms as shown in Fig.3,that is,RSR,RSL,LSR,LSL,RLR,and LRL.Given the position and direction of UAV passing through any two target pointsPsandPf,the shortest Dubins path can be calculated as follows:

Fig.3 Dubins path diagram

whered(·,·) depicts the length of Dubins path corresponding to different turning modes,PsandPfare the starting point and the terminal point.Many scholars have studied how to calculate the distance of six Dubins paths,RSR,RSL,LSR,LSL,RLR,and LRL.Interested readers can get specific details from [36,37].

3.2 Reconnaissance sub-mission area division

As depicted in Fig.1,there are multitudes of targets scattered in the mission area.A single UAV cannot deal with the reconnaissance mission of all targets distributed over the wide area for the voyage distance constraint.In addition,it is a waste of time.In this case,an improvedKmeans clustering algorithm is designed to divide the reconnaissance mission area into several sub-mission areas,each sub-mission can be carried out by the appropriate UAV.That is,the targets described in Fig.1 can be detected by the cooperation of several UAVs.

There are many researchers who is dedicated to studying theK-means algorithm [38,39],however,it is hard to determine the initialKvalue and the initial clustering center of the standardK-means algorithm,which makes the clustering results uncertain.Aiming at these two problems,the initialKvalue selection (IKVS) algorithm and the initial clustering center selection (ICCS) algorithm are designed in this paper.

Let there beNTtargets,we can generateNMCtours based on Monte Carlo (MC) algorithm and compute the minimum Dubins path.The shortest voyage distance of all UAVs can be found based on the fundamental intelligence analysis module,which can be denoted asLmin,and then the initialKvalue can be computed as follows:

Let the location coordinates set of all targets be denoted aswherezis the normalized resultjof the position of targetj.The definition of the distance between targetiand targetjcan be denoted as follows:

where ker is the radial kernel-function.

The density of targetjin the δ-neighborhood of density ρ in feature space is defined as follows:

where Ψ(x) is the indicator function denotes as follows:

According to (20),the density of targetiis the number of the targets in the δ-neighborhood,and the dispersion of targetiis defined as the minimum distance from targetito other points whose density is greater than targeti.Consequently,we can get the specific definition of the dispersion of targeti.

The dimensions of ρ and ? are different,therefore it is of necessity to map ρ and ? into the fixed interval (0,1),denoted asand.We can get the comprehensive index of targeti.

where the bigger the comprehensive index ηiis,the better the global representativeness of targetiis.Then the initial clustering center selection algorithm can be given in Algorithm 2.

Forty points are randomly generated and standardK-means clustering and IKMC algorithms are implemented,results are depicted in Fig.4,it is obvious that the clustering results of the standardK-means algorithm are related to the initial clustering centers which means that the clustering results are uncertain.In order to handle the problem,the ICCS algorithm is designed to select the initialKvalue and the IKMC algorithm is developed to determine the initial clustering centers.If the factor α is given in advance,the clustering result of the proposed IKMC algorithm is deterministic.

Fig.4 Clustering results

3.3 Reconnaissance sub-mission planning algorithm

3.3.1 Mathematical derivation

The specific theory of cross entropy and importance sampling methods can be got in [41-44],here the detail derivation process of the discrete combination optimization problem depicted in (10) is given.Let the number of targets assigned to UAViisNTi,andni=NTi+1 which includes the starting point.Then,the probability density matrix (PDM) is defined as follows:

where ?j,k=1,2,···,ni,p(j|j)=0 deals with the reconnaissance times constraint,that is,every target is not detected repeatedly.

According to the PDMMRi,the probability density function is defined.

The basic idea of cross entropy is to estimate the parameters of the probability density function based on minimizing the Kullback-Leibler distance.Consequently,the following optimization problem can be designed,which is used to estimate the PDMMRiby minimizing the cross entropy ofHsamples,here the sample denotes the decision vector.

whereNsis the number of sampling,and we can compute the voyage distance cost function of each sample and sort them in ascending order,andHdenotes theHsamples among theNssamples whose voyage distance cost is less than theNs-Hsamples.Here we setH=βNs」,β ∈(0,1) is quantile,and·」 is rounding down symbol.

Consequently,the following minimal optimization problem can be summarized

where (26) is used to avoid the repetitive reconnaissance.According to the Lagrange multiplier method and Karush-Kuhn-Tucker (KKT) conditions,the solution to the minimization problem (30) can be denoted as

3.3.2 Algorithm design

The importance sampling method is originated from the MC method,and its basic idea is to find a proper probability density function which allows to reduce the number of sampling and increase the accuracy and reduce the variance.Rubinstein [41] used the idea of cross entropy to describe the probability estimation problem of rare probability event,and the importance sampling method was applied to reduce the number of samplings.

In this paper,the relevant sampling strategy is adopted to avoid repeatable reconnaissance which is useful to deal with the reconnaissance times constraintC4.Consequently,the reconnaissance mission sampling (RMS)algorithm is designed in Algorithm 4,given the iteration timest,PDM,and number of nodesni.LetxRi,1=1,which denotes the UAVistarts from the UAVS base.Let thexRi,jcolumn in the PDMbe 0 and normalize the PDM,generate the next node indexxRi,j+1according to thexRi,jrow in the PDM.The stopping condition is that all nodes have been visited.

Based on the RMS algorithm,the reconnaissance mission planning algorithm based on importance sampling and cross entropy (RMP-ISCE) is designed in Algorithm 5.The initial value of PDMcan be computed according to (26).We can generatedecision vectors according to the Algorithm 4 and compute the corresponding voyage distance cost according to Step 3-Step 6.Then we can sort theNSvoyage distance cost in ascending order and sort the corresponding decision vectors.The firstHdecision vectors are selected,furthermore,(31) is utilized to update the PDMMRi,and the stopping condition of the RMPACEIS algorithm is that all elements in PDMMRibelong to set {0,1}.In this case,the decision vector is deterministic.

In fact,it is worth noting that the acquired sample based on Algorithm 4 is the decision vector.Thejth position in decision vector denotes the (j-1)th reconnaissance target.For example,XRi=[1,3,4,5,2]Tmeans that there are four targets,andxRi,1=1 denotes the UAVistarts from the UAVS base,the reconnaissance sequence given byXRiis “UAVS base →Target 2 →Target 3 →Target 4 → T arget 1 → UAVS base”,in this case,the position of UAVS base is considered,which allows UAV to start from different locations.

3.3.3 Complexity analysis

LetNSdenotes the sample size,Tdenotes the iteration number of the RMP-ISCE algorithm,niis the number of nodes visited by UAVi.The computational cost of the RMP-ISCE algorithm includes four parts,the initialization (Oini),sampling (Osample),sorting (Osort) and updating (Oupdate),and the computational complexity of the RMP-ISCE algorithm can be denoted asO=Oini+Osample+Oso]rt+Oupdate.To be specific,O=ni+T[niNS+NS+niβNS,therefore,the time complexity of the RMPISCE algorithm can be denoted asO(TniNS).Let Num denote the population size of OPSO,IDACO,and GADO;letDdenote the iteration number of OPSO,IDACO,and GADO.Then we can get the computational complexity for solving the sub-mission of the three methods isO(Num·Dni).

It is easy to get that the time complexity of theKsubmissions based on RMP-ISCE,OPSO,IDACO,and GADO algorithms can be separatel(ydenoted as follows):O(KTniNS),O(K·Num ·Dni),OK·Num ·Dni·lg(ni)andO(K·Num ·Dni).

3.4 Reconnaissance mission re-planning algorithm

3.4.1 Mission re-planning

According to the sensor constraintC2and voyage distance constraintC3,the look-up table method is utilized to assign the proper UAV to carry out each reconnaissance sub-mission.In this paper,the UAV is regarded as the Dubins car,the reconnaissance sequence of UAV is planned based on the RMP-ISCE algorithm and the flight path of UAV is smoothed based on Dubins curve.During the reconnaissance mission process,it is meaningful to take the healthy state of UAV into consideration,UAV may be damaged or fail to work which is a probability event as depicted in (5).Assuming that UAVkis damaged at time τ,that is,h(k;τ)=0 .There areundetected targets,a simple and effective measure the UAVS base can adopt is to re-assign the remaining targets to these healthy UAVs.In this case,it is of great necessity to re-plan the reconnaissance sequence of those healthy UAVs.Here how to assign the remaining targets to these healthy UAVs is depicted as follows.

The essential assignment rules include two points:(i) The UAVS base has especial fondness for assigning the remained targets to those healthy UAVs in mission rather than re-dispatching a new UAV from UAVS base,which can avoid loss due to the crash of UAV.(ii) The allocated UAVs must satisfy with sensor constraintC2and voyage distance constraintC3,the following formulas are designed.

The reconnaissance mission re-planning (RMRP) algorithm is designed in Algorithm 6.It is an integrated algorithm which includes target assignment and path planning.The target assignment part is depicted in Step 1 to Step 14.It is worth noting that there is a special situation:some targets remained by UAVkare not assigned to any UAV due to the sensor constraintC2and voyage distance constraintC3.Consequently,we construct the setJto save these targets which should be detected by a new UAV from the UAVS base.Then,the RMS algorithm and RMP-ISCE algorithm should be utilized to re-plan the reconnaissance sequence for the minimum voyage distance cost.

3.4.2 Complexity analysis The computational complexity of the RMRP algorithm includes two parts,target assignment part can be denoted asO1=and mission re-planning can be denoted asO2=(K-1)TNS,whereis the sum of the number of targets not detected by UAViand the number of targets allocated to UAVi.

3.5 Reconnaissance mission planning and re-planning flow-chart

Based on the above five modules,intelligence analysis,sub-mission area division,mission sequence planning,path smoothing,and online re-planning are designed.The flow-chart of reconnaissance mission planning and re-planning is depicted in Fig.5.Intelligence analysis module gives the relevant hypothesis,definition,and constraint description of the reconnaissance scenario,and constructs the discrete combinational optimization problem.In the sub-mission area division module,an IKMC algorithm is proposed to divide the mission into several sub-missions,where the IKVS algorithm is designed to compute the initialKvalue,and the ICCS algorithm is designed to choose the initial clustering center.In the reconnaissance sub-mission sequence planning module,relevant mathematical formulas are deduced to solve the optimization problem,the RMS algorithm is designed for sampling and the RMP-ISCE algorithm is designed for iteration.The path smoothing module gives the smoothed flight path based on Dubins curve.In online re-planning module,the healthy state of UAV is considered,if an UAV is damaged at any time,the remained targets will be assigned to other healthy UAVs,and then the RMRP algorithm is designed for re-planning the reconnaissance scheme.

4.Experimental results and analysis

4.1 Experiment design

Experiment is conducted to prove the performance of the reconnaissance mission planning and re-planning algorithm proposed in this paper.Here the experimental scenario is described and relevant algorithm parameters are given.Suppose that there are 48 targets scattered in the mission area which covers an area of 30 km2,the coordinate of each target is randomly selected and the specific mission scenario is depicted in Fig.6.The blue solid graphics (hexagonal star,diamond,square,triangle,star)represent targets and the red solid circle represents the UAVS base.

Different shapes denote different target types,the specific description is depicted in Table 2,for example,the solid square represents the target which belongs to Type a.To be specific,Target 31 depicted in Fig.6 belongs to Type a,the UAV loaded with a-type sensor can be used to detect this target.The parameters of UAVs are depicted in Table 3,which includes UAV serial number,loaded sensors,maximum voyage distance,flight velocity,and minimum turning radius.According to Table 2 and Table 3,it is easy to find that UAV 1 can be used to detect Target 31.However,UAV 2 cannot be utilized to detect Target 31.

Table 2 Target type and shape

Table 3 Parameters of UAVs

Fig.6 Targets distribution information map

In order to analyze the effectiveness of the proposed RMP-ISCE algorithm,IDACO [21],OPSO [25],GADO[26],and MC algorithms are implemented for comparison.The relevant algorithm parameters are given in Table 4.The sampling size (NS) of the RMP-ISCE algorithm is equal to the population size of IDACO,OPSO,and GADO algorithms (Num),and the maximum iteration times of all algorithms are 500.In addition,the quantile of the RMP-ISCE algorithm is set to 0.4 which means that there are 80 samples to be utilized to update the PDM during the iteration process.It is well-known that there are many control parameters of IDACO,OPSO,and GADO algorithms,for instance,cognitive coefficient in the OPSO algorithm,crossover probability in the GADO algorithm,pheromone coefficient in the IDACO algorithm,etc.However,it is remarkable that there are only two control parameters of the RMP-ISCE algorithm,which is quite easy to operate.In this paper,the other parameters of OPSO,GADO,and IDACO algorithms not listed in Table 4 are determined by cross validation.The MC number (NMC) is set to 106.Furthermore,in order to avoid the randomness and improve the credibility,30 simulation is carried out and the statistical average value is computed,which is used to verify the stability performance of the proposed algorithm.All algorithms are implemented in an Intel Core i5 @ 3.06 GHz processor with 8 GB RAM.

Table 4 Parameters setting of proposed algorithm and benchmark algorithms

4.2 Results and analysis

4.2.1 Reconnaissance mission planning

For the mission scenario depicted in Fig.6,the initialKvalue can be computed based on Algorithm 1,that is,K=3.The weight factors of density and dispersion are 0.5,and the initial clustering centers (the green solid graphics,Target 10,Target 21,and Target 39) depicted in Fig.7 can be determined based on the ICCS algorithm.The submission division result is depicted in Fig.8,where three colors (blue,green,and black) are used to represent three sub-missions.There are 18,15,and 15 targets scattered respectively in these three sub-mission areas respecitively.Then,the look-up table method is applied to assign UAVs to carry out these sub-missions,the assignment results are given in Table 5.UAV 1 is responsible for detecting 18 targets in sub-mission area 1.UAV 2 is responsible for detecting 15 targets in sub-mission area 2.UAV 6 is responsible for detecting 15 targets in sub-mission area 3.

Table 5 Assignment results

Fig.7 Initial clustering centers

Fig.8 Submission division based on IKMC algorithm

The iteration process of several algorithms (RMPISCE,OPSO,GADO,IDACO) are depicted in Fig.9,thex-axis represents the iteration times and they-axis represents the fitness value,the fitness value represents the voyage distance cost.According to Fig.9,it is obvious that using the RMP-ISCE algorithm to get the stable solution only needs less iteration,which implies that the convergence rate of the RMP-ISCE algorithm is better than OPSO and GADO algorithms.In addition,the fitness value acquired by the RMP-ISCE algorithm is the least,which allows us to make a conclusion that the voyage distances cost planned by the RMP-ISCE algorithm is the optimal.For one thing,the iteration process of the RMPISCE algorithm depends on probabilistic sampling,which ensures that each iteration always goes in the determined direction.While there are a lot of randomness in the iteration processes of OPSO,GADO,and IDACO algorithms,which slows down the convergence rate.For another,the evolutionary strategies of OPSO,GADO,and IDACO algorithms are easy to make the algorithms premature.However,the proposed RMS algorithm has great searching ability.As a conclusion,the RMP-ISCE algorithm has great advantages over OPSO,GADO,IDACO algorithms about convergence rate and optimality.

Fig.9 Fitness curve corresponding to three sub-missions

Thirty duplications have been done for the reconnaissance sequence planning of UAV 1,UAV 2,and UAV 6,and the statistical average values of voyage distance cost and computation time are presented in Fig.10 and Fig.11.From the perspective of voyage distance cost,compared with OPSO,GADO,IDACO,and MC algorithms,the voyage distance cost computed by the proposed RMP-ISCE algorithm is the shortest,which means that the acquired reconnaissance sequence solution based on the RMP-ISCE algorithm is better than OPSO,GADO,IDACO,and MC algorithms.From the view of computation time,although the computational complexity of RMP-ISCE,OPSO,GADO,and IDACO algorithms are almost identical,the computation time consumed by the proposed RMP-ISCE algorithm is less than OPSO,GADO,IDACO,and MC algorithms.The conclusions gotten in Fig.10 and Fig.11 are the same as those acquired from Fig.9.In addition,it is obvious that the stability of the proposed RMP-ISCE algorithm is better.

Fig.10 Average voyage distance cost

Fig.11 Average computation time

In order to make the planned results realizable in real mission scenarios,the Dubins curve is applied to smooth the planned reconnaissance sequence,the path smoothing results are depicted in Fig.12.The red solid line stands for the flight path of UAV 1,the blue solid line stands for the flight path of UAV 2,and the black solid line stands for the flight path of UAV 6.It is obvious that the Dubins path based on the RMP-ISCE algorithm is more attractive and simpler.Combined with Fig.9,Fig.10,and Fig.12,we can find that the reconnaissance sequence planned by the RMP-ISCE algorithm is the shortest,for one thing,it saves fuel and decreases cost,for another,it also saves reconnaissance time which makes the next decision scheme leisurely

Fig.12 Path smoothing results based on Dubins curve

4.2.2 RMRP

The UAV on mission may be damaged due to bad weather,interference,and interception measures.Supposing that the UAV breaks down is a rare event during the mission process,the damaged UAV cannot continue to perform the reconnaissance mission,then it is of great necessity to re-plan for these unperformed targets.How the UAV is damaged is not the focus of this paper.Instead,we pay close attention to the matter that the UAV crash occurs on a certain moment.The mission re-planning algorithm has been given in Section 3.Here,relevant simulation is done to prove the effectiveness of the proposed algorithm.The relevant information about UAVs is depicted in Table 6,the UAV 2 is damaged at 354 s and cannot go on working,and the unperformed targets of UAV 2 include target 18 and target 19,which should be re-planned.According to the assignment rules given in Section 3 the UAVS base assigns target 18 to UAV 1,and assigns target 19 to UAV 6.In this case,the reconnaissance sequences of UAV 1 and UAV 6 should be re-planned to get the optimal reconnaissance path to reduce voyage distance cost.Similarly,30 times simulations are carried out to get the statistical results.

Table 6 UAVs state information

The voyage cost distance planned by the RMRP algorithm is depicted in Table 7,where “Before” means the flight distance before the UAV 2 breaks down,“After”means the flight distance after the UAV 2 breaks down,it is obvious that the total voyage distance cost of each UAV meets the voyage distance constraint according to Table 7.The average voyage distance cost and average computation time are depicted in Fig.13 and Fig.14.In Fig.13,the voyage distance costs of UAV 1 re-planned by OPSO,GADO,and IDACO algorithms are almost equal,which are more than the result re-planned by the MC algorithm which is equal to the exhaustive search algorithm.It is obvious that the voyage distance cost of UAV 1 re-planned by the RMRP algorithm is almost equal to that re-planned by the MC algorithm,that is,the reconnaissance sequence generated by the RMRP algorithm is the best.In addition,the voyage distance cost of UAV 6 re-planned by RMRP,OPSO,IDACO and MC algorithms are same,which means that the optimal solution can be solved based on RMRP,OPSO,IDACO algorithms when the number of targets is not large.In terms of computation time,it is obvious that the proposed RMRP algorithm is better than OPSO,GADO,IDACO,and MC algorithms according to Fig.14.

Table 7 Voyage distance cost planned by RMRP algorithm

Fig.13 Average voyage distance cost

Fig.14 Average computation time

The smoothing path of re-planning results based on Dubins curve is depicted in Fig.15.The black solid symbol “x” represents the location of damaged UAV,the black solid symbol “+” represents the start location of re-planning,the red solid line stands for the re-planned flight path of UAV 1,and the black solid line stands for re-planned the flight path of UAV 6.To be specific,when UAV 2 breaks down,UAV 1 and UAV 6 continue to carry out the reconnaissance mission,when they receive re-planned order which is sent from the UAVS base,then UAV 1 and UAV 6 will carry out the re-planned reconnaissance order.As depicted in Fig.15,the flight path of UAV 1 based on the RMRP algorithm is shorter and more fascinating than those planned by OPSO,GADO,IDACO,and MC algorithms.The flight path of UAV 6 based on the RMRP,OPSO,IDACO,and MC algorithms are same,which means that when the target size is not large,RMRP,OPSO,IDACO,and MC algorithms can get the optimal reconnaissance sequence.It is worth noting that the key kernel of RMRP algorithm is the RMP-ISCE algorithm.Consequently,it further shows that the proposed RMP-ISCE algorithm is better than those swarm optimization algorithms in convergence rate and solution quality.

Fig.15 Path re-planning results based on Dubins curve

5.Conclusions

In this paper,aiming at the reconnaissance mission planning problem in real-word scenarios,an effective reconnaissance mission planning and re-planning scheme is proposed.Firstly,we propose an IKMC algorithm to deal with the problem that a single UAV cannot cover all targets scattered in the mission area.Compared with the standardK-means clustering algorithm,the IKMC algorithm can determines the initial clustering centers based on target density and dispersion.In this case,it can stably and effectively divide the mission area into multiple sub-mission areas.Secondly,the look-up table method is utilized to handle the voyage distance and sensor type constraints,which assure that each UAV can carry out the reconnaissance sub-mission,the mission assignment scheme is acquired.Thirdly,the reconnaissance sequence planning problem of each sub-mission is formulated at the cost of voyage distance,which is an extended traveling salesman problem with complex constraints.Based on the idea of cross entropy and importance sampling,the RMP-ISCE algorithm is designed to solve the reconnaissance sequence planning problem,the detailed deduction process of the proposed RMP-ISCE algorithm is given.Then,after getting the optimal solution of the reconnaissance sequence planning problem,the flight path of UAV is planned based on the Dubins curve,which makes the path available.Finally,the healthy state of UAV during the reconnaissance process is considered,if a UAV is out of working,the remained targets should be detected by other UAVs.The RMRP algorithm based on the look-up table method and the RMP-ISCE algorithm is proposed to deal with the re-planning problem.

The reconnaissance mission planning and re-planning framework consists of intelligence analysis,sub-mission area division,mission sequence planning,path smoothing,and online re-planning,which can work effectively.The proposed framework provides an extended orientation for the reconnaissance and search problem.Various clustering algorithms and assignment algorithms could be involved in this framework to realize the mission planning.The proposed planning and re-planning algorithms whose kernel ideas are cross-entropy and importance sampling have excellent performance in terms of convergence rate,computation consumption,and stability.The detailed derivation process of the optimization problem based on cross-entropy and importance sampling is given,which allows interested author to apply the idea to other optimization problems in different fields.

For future research,we will focus on the promotion of cross entropy and importance sampling methods in its efficiency and time consumption by sample selection and appropriate parameter settings.