# Task Assignment for Multi-UAV under Severe Uncertainty by Using Stochastic Multicriteria Acceptability Analysis

Authors: Xiaoxuan Hu; Jing Cheng; He Luo
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

This paper considers a task assignment problem for multiple unmanned aerial vehicles (UAVs). The UAVs are set to perform attack tasks on a collection of ground targets in a severe uncertain environment. The UAVs have different attack capabilities and are located at different positions. Each UAV should be assigned an attack task before the mission starts. Due to uncertain information, many criteria values essential to task assignment were random or fuzzy, and the weights of criteria were not precisely known. In this study, a novel task assignment approach based on stochastic Multicriteria acceptability analysis (SMAA) method was proposed to address this problem. The uncertainties in the criteria were analyzed, and a task assignment procedure was designed. The results of simulation experiments show that the proposed approach is useful for finding a satisfactory assignment under severe uncertain circumstances.


---

## Body

## 1. Introduction

Unmanned aerial vehicles (UAVs) are playing increasingly important roles in military and civilian applications. Over the last decade, UAVs were employed as intelligent units in various missions in dangerous and complex environments. When executing multiple missions, UAVs form teams and are able to work cooperatively. In this context, the multi-UAV cooperative control and decision mechanisms, including task assignment, path planning, and tactical decision making, have received a great deal of attention.The purpose of multi-UAV task assignment is to allocate necessary tasks to UAVs, so as to maximize the overall performance. Here, tasks involve reconnaissance, search, attack, and verification. In applications wherein a group of UAVs executed complex missions, the result of task assignment directly determined how well the missions were performed. This problem has generated many research interests and a variety of approaches have been developed for different scenarios. Methods like linear programming [1, 2], dynamic programming (DP) [3], and Markov decision processes (MDP) [4] were employed. For solving techniques, the genetic algorithm [5, 6] and tabu search algorithm [7] were used.Researchers have also considered task assignment under uncertain circumstances. Choi et al. [8] addressed single and multiple assignment problems by presenting 2 decentralized algorithms: the consensus-based auction algorithm (CBAA) and the consensus-based bundle algorithm (CBBA). These 2 algorithms were independent of inconsistencies in situational awareness and could, respectively, produce conflict-free solutions to the assignment problem. Bertuccelli et al. [9] extended the CBBA to resolve the heterogeneous UAVs real-time task assignment problem in uncertain environments. The first extension accounts for obstacle regions in order to generate collision-free paths for UAVs. The second extension reduces sensitivity to sensor noise and minimizes the churning behavior in flight paths. Alighanbari and How [10] presented a robust filter-embedded task assignment (RFETA) algorithm to achieve the target assignment for UAVs in uncertain dynamic environments. The algorithm used two techniques; one is proactive in order to hedge against the uncertainty, while the other is reactive in order to limit churning behavior by the vehicles. Alighanbari et al. [11] formulated a modification of the classical task assignment under noisy conditions. They developed a noise rejection algorithm that reduced the effects of high frequency noise on the planner. This algorithm could be used to mitigate the effect of noise in situational awareness on the solution.In this study, we considered a task assignment problem for multi-UAV that performed attack tasks on a collection of ground targets in a severe, uncertain environment. Each target had to be allocated to a UAV before the mission began. The severe and uncertain environment refers to battlefield conditions in which much information vital to an assignment is random, fuzzy, or unknown. For example, the location of a target is vague within the task area. Though the predetected location provides a reference, it may be not in accordance with the real target location because of a sensor error or target movement; the threat of a target’s defense system to the UAVs is unclear; the value of the target is fuzzy. These conditions are often encountered in real-world UAV applications. Under these conditions, the common methods for task assignment cannot be used and new methods that can deal with severe uncertainty are needed.To address this problem, we propose a novel task assignment method based on the stochastic multicriteria acceptability analysis (SMAA). SMAA is a method used for stochastic multicriteria decision problems. It ranks alternatives based on multiple criteria values that are random variables and can also address problems without weight information. Lahdelma et al. [12] gave the first version of the SMAA method, and later studies presented a series of extended versions, including SMAA-2 [13], SMAA-3 [14], SMAA-O [15], SMAA-A [16], SMAA-TRI [17], and SMAA-P [18]. Here we have employed SMAA-2 to handle battlefield uncertainty. The aim of this study is to offer a suitable and reliable method for task assignment under severe uncertain circumstances.The rest of this paper is organized as follows. Section2 defines the problem. Section 3 analyses the criteria essential to task assignment. Section 4 provides the task assignment procedure. In Section 5, the results of simulation experiments are given and analyzed. Finally, the conclusion is presented in Section 6.


## 2. Problem Description

The problem is to assign the attack tasks ofNT geographically dispersed ground targets to NU UAVs. Each UAV is equipped with an air-to-ground missile and can attack one target during one flight. Each UAV is assigned only one target, and each target should only be allocated to a UAV (i.e., NU=NT). The task assignment problem needs to be solved before the mission starts. The objective of task assignment is to maximize the total reward; one example of an assignment is shown in Figure 1. In this example, 3 targets were assigned to 3 UAVs, one target for each UAV.Figure 1
Example of a task assignment: 3 UAVs and 3 targets.The major symbols used for the problem are listed in Symbols.To make an assignment, we consider 3 criteria:RA, CF, and CL. Their values are computed through the following 6 subcriteria: (1) the value of the target; (2) the value of the UAV; (3) the distance between the UAV and the target; (4) the flying cost per unit distance of UAV; (5) the probability of UAV loss; and (6) the probability of killing target. The 3 criteria are given by the following expressions:(1)RA=∑i=1NU∑j=1NTxijpijtvjt,CF=∑i=1NU∑j=1NTxijdijciu,CL=∑i=1NU∑j=1NTxijpijuviu.The common model for task assignment is given as follows:(2)max⁡ω1RA-ω2CF-ω3CL=max∑i=1NU∑j=1NTxijω1pijtvjt-ω2dijciu-ω3pijuviu,(3)s.t.∑i=1NUxij=1,(4)∑j=1NTxij=1,(5)∑k=13ωk=1,(6)xij=0,1i=1,2,…,NU,j=1,2,…,NT,(7)ωk∈0,1k=1,2,3.Objective function (2) aims to maximize the total task reward, which is the difference between the expected attack reward and the cost. ωk(k=1,2,3) are weights, given by military commanders or experts. Constraints (3) and (4) ensure that there is a one-to-one relationship between the UAV and the target. Constraint (5) ensures that the weights are normalized. Constraints (6) and (7) give the range of the variables.The task assignment problem can be settled by solving the above model when all values of the parameters are given. However, in complex battlefield scenarios, much information is severely uncertain. Uncertainty increases many difficulties for task assignment. In these conditions, we need new methods to handle uncertainty.


## 3. Criteria Analysis

In this section, we will provide an analysis of the criteria and give methods to quantitatively describe the involved uncertainties.


### 3.1. The Value of the Target

The value of a target, evaluated by military commanders or experts, determines whether the target is worth attacking. For ease of calculation in this paper, the lower and upper bounds of the value of target have been set to be 0 and 100. A higher number indicates a higher value. However, it is difficult for the commanders or experts to provide a precise value. They typically prefer to use linguistic variables, such as “very high” and “fairly low.” These linguistic variables are fuzzy descriptors that cannot be used in task assignment models. To solve this problem, we have defined a fuzzy linguistic setS based on the work in [19, 20]:(8)S=s0,s1,s2,s3,s4,s5,s6,s7,s8=extremely  high,  very  high,  high,  fairly  high,  medium,  fairly  low,  low,  very  low,  extremely  low.Each linguistic variable inS matches a value interval: extremelyhigh=[90,100], veryhigh=[80,90], high=[70,80], fairlyhigh=[55,70], medium=[45,55], fairlylow=[30,45], low=[20,30], verylow=[10,20], and extremelylow=[0,10]. Using the fuzzy set, the commanders or experts can use a linguistic variable to describe the value of a target, and then the variable is transformed to a numerical interval.


### 3.2. The Value of the UAV

When a UAV attacks a target, the UAV may also be at risk of being attacked. Therefore, the UAV’s value is an important factor that we need to consider. By contrasting it with the value of target, the value of UAV can be accurately obtained and can be represented by a precise number.


### 3.3. The Distance between the UAV and the Target

The distance between the UAV and the target is an important criterion for task assignment. To minimize the flying costs, a UAV tends to select the nearest target when other variables are equal.The distance between the UAVui and target tj is calculated by using the Euclidean distance, as shown in (9)dij=xiu-xjt2+yiu-yjt2.In battlefield circumstances, the coordinate(xjt,yjt) of target tj is not a certain value. The information we have is the detected position (xjt′,yjt′) of tj. However, there is usually a deviation between a target’s detected position and its real position.Normally, the real position(xjt,yjt) follows a two-dimensional Gaussian distribution whose expectation is (xjt′,yjt′), as shown in (10)fxjt,yjt=12πσ1σ21-ρ2·e-1/21-ρ2xjt-xjt′2/σ12-2ρxjt-xjt′/σ1yjt-yjt′2/σ2+yjt-yjt′2/σ22.Becausexjt and yjt are independent, we let ρ=0 and we assume σ1=σ2=1. Then (10) can be simplified as(11)fxjt,yjt=12πe-1/2xjt-xjt′2+yjt-yjt′2.In (11), the probability distribution of a target’s real position within the task area is shown in Figure 2. The probability is 0.159 that a target’s real position is in accordance with the detected position.Figure 2
Probability distribution of target position.The position can be accurately detected only when the UAV approaches the target. However, at the time the task assignment is made, the UAV only has uncertain information.


### 3.4. The Flying Cost per Unit Distance of UAV

This criterion, as well as the distance between the UAV and the target, determines the flying cost of a mission. For a UAV, the value of this criterion is fixed.


### 3.5. The Probability of UAV Loss

A high value target is usually protected by a defense system that is equipped with surface-to-air missiles. When performing the attack task, the UAV also faces the possibility of being destroyed. Washburn and Kress [21] provided the probability of ui loss when attacking target tj as(12)piju=exp⁡-R-R022b2,rjmin≤R≤rjmax0,R>rjmaxorR<rjmin,where R denotes the real-time distance between tj and ui and R0 and b are parameters calculated using (13)R0=rjmin+rjmax2,b=2rjmax-rjmin.Equation (12) indicates that the probability of ui loss is 0 when being out of the range of a surface-to-air missile; within the range of the missile, the probability approximates a Gaussian distribution.To calculatepiju, we reasonably assume the following: (1) the defense system will attack a UAV at the same time the UAV attacks the target; (2) a UAV always attacks a target at the UAV’s best striking distance, which depends on the UAV’s onboard weapon. Different weapons have their own best strike distances.Based on the above assumptions, we substituteR in (12) with distr. distr typically is an interval, such as [20km,25km]. Consequently, piju is also an interval, like [0.50,0.65] and so forth.


### 3.6. The Probability of Killing Target

As mentioned above, the UAV always attacks the target at the UAV’s best striking distance. Washburn and Kress [21] presented the probability pijt of UAV ui killing target tj as (14)pijt=1-0.5ridam2/cepidam2,where cep represents the circular error probability, the definition of which is the following. If the probability that the weapon’s two-dimensional shooting error falls within the circle is 0.5, the radius of circle will be called the circular error probability.


## 3.1. The Value of the Target

The value of a target, evaluated by military commanders or experts, determines whether the target is worth attacking. For ease of calculation in this paper, the lower and upper bounds of the value of target have been set to be 0 and 100. A higher number indicates a higher value. However, it is difficult for the commanders or experts to provide a precise value. They typically prefer to use linguistic variables, such as “very high” and “fairly low.” These linguistic variables are fuzzy descriptors that cannot be used in task assignment models. To solve this problem, we have defined a fuzzy linguistic setS based on the work in [19, 20]:(8)S=s0,s1,s2,s3,s4,s5,s6,s7,s8=extremely  high,  very  high,  high,  fairly  high,  medium,  fairly  low,  low,  very  low,  extremely  low.Each linguistic variable inS matches a value interval: extremelyhigh=[90,100], veryhigh=[80,90], high=[70,80], fairlyhigh=[55,70], medium=[45,55], fairlylow=[30,45], low=[20,30], verylow=[10,20], and extremelylow=[0,10]. Using the fuzzy set, the commanders or experts can use a linguistic variable to describe the value of a target, and then the variable is transformed to a numerical interval.


## 3.2. The Value of the UAV

When a UAV attacks a target, the UAV may also be at risk of being attacked. Therefore, the UAV’s value is an important factor that we need to consider. By contrasting it with the value of target, the value of UAV can be accurately obtained and can be represented by a precise number.


## 3.3. The Distance between the UAV and the Target

The distance between the UAV and the target is an important criterion for task assignment. To minimize the flying costs, a UAV tends to select the nearest target when other variables are equal.The distance between the UAVui and target tj is calculated by using the Euclidean distance, as shown in (9)dij=xiu-xjt2+yiu-yjt2.In battlefield circumstances, the coordinate(xjt,yjt) of target tj is not a certain value. The information we have is the detected position (xjt′,yjt′) of tj. However, there is usually a deviation between a target’s detected position and its real position.Normally, the real position(xjt,yjt) follows a two-dimensional Gaussian distribution whose expectation is (xjt′,yjt′), as shown in (10)fxjt,yjt=12πσ1σ21-ρ2·e-1/21-ρ2xjt-xjt′2/σ12-2ρxjt-xjt′/σ1yjt-yjt′2/σ2+yjt-yjt′2/σ22.Becausexjt and yjt are independent, we let ρ=0 and we assume σ1=σ2=1. Then (10) can be simplified as(11)fxjt,yjt=12πe-1/2xjt-xjt′2+yjt-yjt′2.In (11), the probability distribution of a target’s real position within the task area is shown in Figure 2. The probability is 0.159 that a target’s real position is in accordance with the detected position.Figure 2
Probability distribution of target position.The position can be accurately detected only when the UAV approaches the target. However, at the time the task assignment is made, the UAV only has uncertain information.


## 3.4. The Flying Cost per Unit Distance of UAV

This criterion, as well as the distance between the UAV and the target, determines the flying cost of a mission. For a UAV, the value of this criterion is fixed.


## 3.5. The Probability of UAV Loss

A high value target is usually protected by a defense system that is equipped with surface-to-air missiles. When performing the attack task, the UAV also faces the possibility of being destroyed. Washburn and Kress [21] provided the probability of ui loss when attacking target tj as(12)piju=exp⁡-R-R022b2,rjmin≤R≤rjmax0,R>rjmaxorR<rjmin,where R denotes the real-time distance between tj and ui and R0 and b are parameters calculated using (13)R0=rjmin+rjmax2,b=2rjmax-rjmin.Equation (12) indicates that the probability of ui loss is 0 when being out of the range of a surface-to-air missile; within the range of the missile, the probability approximates a Gaussian distribution.To calculatepiju, we reasonably assume the following: (1) the defense system will attack a UAV at the same time the UAV attacks the target; (2) a UAV always attacks a target at the UAV’s best striking distance, which depends on the UAV’s onboard weapon. Different weapons have their own best strike distances.Based on the above assumptions, we substituteR in (12) with distr. distr typically is an interval, such as [20km,25km]. Consequently, piju is also an interval, like [0.50,0.65] and so forth.


## 3.6. The Probability of Killing Target

As mentioned above, the UAV always attacks the target at the UAV’s best striking distance. Washburn and Kress [21] presented the probability pijt of UAV ui killing target tj as (14)pijt=1-0.5ridam2/cepidam2,where cep represents the circular error probability, the definition of which is the following. If the probability that the weapon’s two-dimensional shooting error falls within the circle is 0.5, the radius of circle will be called the circular error probability.


## 4. Assignment Model

The SMAA-2 method was employed to solve the task assignment problem. The SMAA-2 method can handle multiattribute decision making problems in which uncertain criteria values ​​and uncertain weights exist simultaneously. The SMAA-2 method has been applied in many aspects of the real world. Kangas et al. [22] used the SMAA-2 method for strategic forest planning. Hokkanen et al. [23] used the SMAA-2 method in a technology competition for cleaning polluted soil in Helsinki. Menou et al. [24] gave a decision support for centralizing cargo at a Moroccan airport hub using the SMAA-2 method. Rahman et al. [25] used the SMAA-2 method to evaluate the choices for sustainable rural electrification in developing countries. Pesola et al. [26] applied the method on alternatives for remote monitoring systems of municipal buildings.


### 4.1. The SMAA-2 Method

Consideringm alternatives A={x1,x2,…,xm} and n evaluation criteria, ω is a weight vector for the decision maker (DM) to express his subjective preference. ωk represents the weight of criterion k, satisfying ∑k=1nωk=1. A weight distribution with density function fω is used to represent the DM’s partially known or unknown preference. The weight distribution is in the set of feasible weights W defined as W=ω∈Rn:ω≥0and∑k=1nωk=1.  ξik represents the uncertain or imprecise value of criterion k for alternative xi. Similarly, a joint probability distribution with density function fξ in the space X is used to represent the uncertain or imprecise criteria values. The utility of alternative xi is defined as (15)Ui=Uξi,ω=∑k=1nωkUkξik,where Ukξik is the utility function of criterion k.The SMAA-2 method defines a ranking functionrankξi,ω which is given by the following to represent the rank of alternative xi: (16)rankξi,ω=1+∑h=1mρUξh,ω>Uξi,ω,where ρUξh,ω>Uξi,ω is a judgment function. If Uξh,ω>Uξi,ω, then ρUξh,ω>Uξi,ω=1; otherwise ρUξh,ω>Uξi,ω=0.The SMAA-2 method is based on analyzing the sets of favorable rank weightsWirξ. Alternative xi always obtains rank r for arbitrary weight ω∈Wirξ. Wirξ is defined as (17)Wirξ=ω∈W:rankξi,ω=r.The SMAA-2 method presents 3 important analysis indices. All the indices are based on properties of these stochastic sets. The first index is the rank acceptability indexbir, defined as the expected volume of Wirξ: (18)bir=∫Xfξ∫Wirξfωdωdξ.It is computed as a multidimensional integral over the criteria distributions and the favorable rank weights, representing the acceptability or the probability of alternativexi rank r.The rank acceptability index is a real number in[0,1] and is generally expressed as a percent. Normally, the more acceptable alternatives should have higher acceptabilities for the best ranks.The second index is the central weight vectorωic, the best single weight vector representation of a hypothetical DM supporting alternative xi to rank first. It is computed as a double integral over the criteria distributions and the favorable first rank weights Wi1ξ:(19)ωic=∫Xfξ∫Wi1ξfωωdωdξbi1.The central weight vectorωic is the expected center of gravity of the favorable first rank weights Wi1ξ. It can help the DM understand what preferences support the different alternatives. Moreover, the central weight vectors are used to compute the confidence factor.The third index is the confidence factorpic, representing the probability for the alternative xi ranking first if the central weight vector is chosen. It is computed as an integral over the criteria distributions:(20)pic=∫ξ:rankξi,ωic=1fξdξ.The confidence factor can also be used to judge whether the criteria value is accurate enough to distinguish the alternatives when the central weight vector is used. Providing any weight vector can also calculate the corresponding confidence factor in a similar way.Comparing the alternatives according to their rank acceptabilities can be seen as a “second-order” multicriteria decision problem [13]. The SMAA-2 method additionally defines the holistic acceptability index to provide a measure of the overall acceptability of each alternative. It is represented as a weighted sum of the rank acceptabilities:(21)aih=∑r=1mαrbir,where αr are referred to as metaweights (or rank weights). A complete priority order between the metaweights should be well defined. Lahdelma and Salminen [13] gave three possible choices: linear weights αr=m-r/m-1, inverse weights αr=1/r, and centroid weights αr=∑i=rm1/i/∑i=1m1/i. After comparison, they preferred using centroid weights.In practice, accurately calculating these indices requires complex computation processes. In order to reduce the computational complexity, Tervonen and Lahdelma [27] gave an approximate computation method by using the Monte Carlo technique. Even when dealing with large-scale problems, this method can quickly solve them. Furthermore Tervonen [28] presentedJSMAA: open source software for SMAA computations.


### 4.2. The Decision Model

To solve the problem of assigning the attack tasks onNT targets to NU UAVs, we decompose the problem into NT parts based on the number of targets. For target tj(j=1,2,…,NT), let the NU UAVs be alternatives and use bijr, aijh, ωijc, and pijc to, respectively, represent the rank acceptability index, holistic acceptability index, central weight vector, and confidence factor of alternative ui. These indices are calculated by using the SMAA-2 method. On the basis of the indices, the DMs make the assignment decisions.In this study, the DMs have weight intervals of the criteria and the widths of the intervals are small. The main consideration of the DMs is the overall acceptability. So the holistic acceptability index is the most suitable index for making decisions. Then the task assignment model in Section2 is modified as(22)max∑i=1NU∑j=1NTxijaijh(23)s.t.∑i=1NUxij=1,∑j=1NTxij=1,xij=0,1i=1,2,…,NU,j=1,2,…,NT.In this model, objective function (22) aims to maximize the holistic acceptability of the assignment schemes. To calculate the holistic acceptability, the DMs select centroid weights αr=∑i=rm1/i/∑i=1m1/i.The steps of task assignment for multiple UAVs under severe uncertainty are given in Figure3.Figure 3
The steps of task assignment.In step 1, linear utility functions are used. Letξikk=1,2,3, respectively, represent the values of criteria RA, CF, and CL for alternative ui. Their values can be calculated using (1). RA is an income-type criterion. CF and CL are cost-type criteria. Their utility functions can, respectively, be defined as(24)Ukξik=ξik-ξikminξikmax-ξikmink=1,Ukξik=-ξik-ξikminξikmax-ξikmink=2,3,where ξikmin=min1≤i≤m⁡ξik and ξikmax=max1≤i≤m⁡ξik. The effects of the utility functions are to normalize the criteria values.Based on the work of [27], the detailed procedure of Step 4 is given in Algorithm 1.Algorithm 1:Calculating the indices for target tj.
(1)     Initialize the data;
(2)    Forl = 1 to IB do// IB  is the number of iterations
(3)  Randomly generate a weight vectorω=(ω1,ω2,ω3) based on the prior weight information;
(4)  Randomly generate a set of sub-criteria values (pijt, piju, viu, vjt, dij, ciu);
(5)  Calculateξik (k = 1, 2, 3) for each ui, using  (1);
(6)  CalculateUk(ξik) (k = 1, 2, 3) for each ui, using (24);
(7)  CalculateUi for each ui using (15);
(8)  Sortui according to the size of Ui; getting hijl; // hijl  represents the sorting of  ui  in iteration  l.
(9)  Ifui rank the first, then ωijc=ωijc+ω;
(10)  End for
(11)   Fori = 1 to NU do
(12)  Forr = 1 to NU do
(13)hijr=∑l=1IB(hijl=r?1:0); // hijr  is the total number of times that  ui  obtains rank  r;
(14)bijr=hijr/IB;
(15)  End for
(16)  Calculateaijh according to  (21);
(17)  End for
(18)   Fori = 1 to NU do
(19)ωijc=ωijc/hij1;
(20) End for
(21)  Forl = 1 to IP do   // IP  is the number of iterations
(22) Randomly generate a set of sub-criteria values (pijt, piju, viu, vjt, dij, ciu);
(23) Calculate ξik (k = 1, 2, 3) for each ui, using  (1);
(24) Calculate Uk(ξik) (k = 1, 2, 3) for each ui, using (24);
(25)      Fori = 1 to NU do
(26)ω=ωijc;
(27)       CalculateUi for each ui using  (15);
(28)       Sortui according to the size of Ui;
(29)       Ifui rank the first, then pijc=pijc+1;
(30)      End for
(31)  End for
(32) Fori = 1 to NU do
(33)pijc=pijc/IP;
(34) End for


## 4.1. The SMAA-2 Method

Consideringm alternatives A={x1,x2,…,xm} and n evaluation criteria, ω is a weight vector for the decision maker (DM) to express his subjective preference. ωk represents the weight of criterion k, satisfying ∑k=1nωk=1. A weight distribution with density function fω is used to represent the DM’s partially known or unknown preference. The weight distribution is in the set of feasible weights W defined as W=ω∈Rn:ω≥0and∑k=1nωk=1.  ξik represents the uncertain or imprecise value of criterion k for alternative xi. Similarly, a joint probability distribution with density function fξ in the space X is used to represent the uncertain or imprecise criteria values. The utility of alternative xi is defined as (15)Ui=Uξi,ω=∑k=1nωkUkξik,where Ukξik is the utility function of criterion k.The SMAA-2 method defines a ranking functionrankξi,ω which is given by the following to represent the rank of alternative xi: (16)rankξi,ω=1+∑h=1mρUξh,ω>Uξi,ω,where ρUξh,ω>Uξi,ω is a judgment function. If Uξh,ω>Uξi,ω, then ρUξh,ω>Uξi,ω=1; otherwise ρUξh,ω>Uξi,ω=0.The SMAA-2 method is based on analyzing the sets of favorable rank weightsWirξ. Alternative xi always obtains rank r for arbitrary weight ω∈Wirξ. Wirξ is defined as (17)Wirξ=ω∈W:rankξi,ω=r.The SMAA-2 method presents 3 important analysis indices. All the indices are based on properties of these stochastic sets. The first index is the rank acceptability indexbir, defined as the expected volume of Wirξ: (18)bir=∫Xfξ∫Wirξfωdωdξ.It is computed as a multidimensional integral over the criteria distributions and the favorable rank weights, representing the acceptability or the probability of alternativexi rank r.The rank acceptability index is a real number in[0,1] and is generally expressed as a percent. Normally, the more acceptable alternatives should have higher acceptabilities for the best ranks.The second index is the central weight vectorωic, the best single weight vector representation of a hypothetical DM supporting alternative xi to rank first. It is computed as a double integral over the criteria distributions and the favorable first rank weights Wi1ξ:(19)ωic=∫Xfξ∫Wi1ξfωωdωdξbi1.The central weight vectorωic is the expected center of gravity of the favorable first rank weights Wi1ξ. It can help the DM understand what preferences support the different alternatives. Moreover, the central weight vectors are used to compute the confidence factor.The third index is the confidence factorpic, representing the probability for the alternative xi ranking first if the central weight vector is chosen. It is computed as an integral over the criteria distributions:(20)pic=∫ξ:rankξi,ωic=1fξdξ.The confidence factor can also be used to judge whether the criteria value is accurate enough to distinguish the alternatives when the central weight vector is used. Providing any weight vector can also calculate the corresponding confidence factor in a similar way.Comparing the alternatives according to their rank acceptabilities can be seen as a “second-order” multicriteria decision problem [13]. The SMAA-2 method additionally defines the holistic acceptability index to provide a measure of the overall acceptability of each alternative. It is represented as a weighted sum of the rank acceptabilities:(21)aih=∑r=1mαrbir,where αr are referred to as metaweights (or rank weights). A complete priority order between the metaweights should be well defined. Lahdelma and Salminen [13] gave three possible choices: linear weights αr=m-r/m-1, inverse weights αr=1/r, and centroid weights αr=∑i=rm1/i/∑i=1m1/i. After comparison, they preferred using centroid weights.In practice, accurately calculating these indices requires complex computation processes. In order to reduce the computational complexity, Tervonen and Lahdelma [27] gave an approximate computation method by using the Monte Carlo technique. Even when dealing with large-scale problems, this method can quickly solve them. Furthermore Tervonen [28] presentedJSMAA: open source software for SMAA computations.


## 4.2. The Decision Model

To solve the problem of assigning the attack tasks onNT targets to NU UAVs, we decompose the problem into NT parts based on the number of targets. For target tj(j=1,2,…,NT), let the NU UAVs be alternatives and use bijr, aijh, ωijc, and pijc to, respectively, represent the rank acceptability index, holistic acceptability index, central weight vector, and confidence factor of alternative ui. These indices are calculated by using the SMAA-2 method. On the basis of the indices, the DMs make the assignment decisions.In this study, the DMs have weight intervals of the criteria and the widths of the intervals are small. The main consideration of the DMs is the overall acceptability. So the holistic acceptability index is the most suitable index for making decisions. Then the task assignment model in Section2 is modified as(22)max∑i=1NU∑j=1NTxijaijh(23)s.t.∑i=1NUxij=1,∑j=1NTxij=1,xij=0,1i=1,2,…,NU,j=1,2,…,NT.In this model, objective function (22) aims to maximize the holistic acceptability of the assignment schemes. To calculate the holistic acceptability, the DMs select centroid weights αr=∑i=rm1/i/∑i=1m1/i.The steps of task assignment for multiple UAVs under severe uncertainty are given in Figure3.Figure 3
The steps of task assignment.In step 1, linear utility functions are used. Letξikk=1,2,3, respectively, represent the values of criteria RA, CF, and CL for alternative ui. Their values can be calculated using (1). RA is an income-type criterion. CF and CL are cost-type criteria. Their utility functions can, respectively, be defined as(24)Ukξik=ξik-ξikminξikmax-ξikmink=1,Ukξik=-ξik-ξikminξikmax-ξikmink=2,3,where ξikmin=min1≤i≤m⁡ξik and ξikmax=max1≤i≤m⁡ξik. The effects of the utility functions are to normalize the criteria values.Based on the work of [27], the detailed procedure of Step 4 is given in Algorithm 1.Algorithm 1:Calculating the indices for target tj.
(1)     Initialize the data;
(2)    Forl = 1 to IB do// IB  is the number of iterations
(3)  Randomly generate a weight vectorω=(ω1,ω2,ω3) based on the prior weight information;
(4)  Randomly generate a set of sub-criteria values (pijt, piju, viu, vjt, dij, ciu);
(5)  Calculateξik (k = 1, 2, 3) for each ui, using  (1);
(6)  CalculateUk(ξik) (k = 1, 2, 3) for each ui, using (24);
(7)  CalculateUi for each ui using (15);
(8)  Sortui according to the size of Ui; getting hijl; // hijl  represents the sorting of  ui  in iteration  l.
(9)  Ifui rank the first, then ωijc=ωijc+ω;
(10)  End for
(11)   Fori = 1 to NU do
(12)  Forr = 1 to NU do
(13)hijr=∑l=1IB(hijl=r?1:0); // hijr  is the total number of times that  ui  obtains rank  r;
(14)bijr=hijr/IB;
(15)  End for
(16)  Calculateaijh according to  (21);
(17)  End for
(18)   Fori = 1 to NU do
(19)ωijc=ωijc/hij1;
(20) End for
(21)  Forl = 1 to IP do   // IP  is the number of iterations
(22) Randomly generate a set of sub-criteria values (pijt, piju, viu, vjt, dij, ciu);
(23) Calculate ξik (k = 1, 2, 3) for each ui, using  (1);
(24) Calculate Uk(ξik) (k = 1, 2, 3) for each ui, using (24);
(25)      Fori = 1 to NU do
(26)ω=ωijc;
(27)       CalculateUi for each ui using  (15);
(28)       Sortui according to the size of Ui;
(29)       Ifui rank the first, then pijc=pijc+1;
(30)      End for
(31)  End for
(32) Fori = 1 to NU do
(33)pijc=pijc/IP;
(34) End for


## 5. Simulation Experiments

The proposed task assignment method was tested by simulation experiments. In the experiments, the task area was represented by1000∗1000 grid, which was populated by 4 UAVs and 4 targets, as seen in Figure 4. The experiments were run on a computer with an Intel Core 2 Duo E7500 2.93 GHz processor and 2 GB RAM.Figure 4
Task area.The parameters used for the simulations are summarized in Tables1 and 2.Table 1
Attribute values of the UAVs.
UAV
(
x
i
u
,
y
i
u
)
r
i
dam
ce
p
i
dam
v
i
u
d
i
str
c
i
u
u
1
(755, 760)
20
12
80
[
500,600
]
14
u
2
(750, 720)
15
8
75
[
505,530
]
15
u
3
(785, 775)
15
10
90
[
500,550
]
13
u
4
(770, 740)
13
8
85
[
520,540
]
14Table 2
Attribute values of the targets.
Target
(
x
j
t
′
,
y
j
t
′
)
v
j
t
r
j
max
⁡
r
j
min
⁡
t
1
(80,  95)
(90,  100)
600
300
t
2
(70,  64)
(80,  90)
800
350
t
3
(52,  80)
(90,  100)
600
400
t
4
(58,  68)
(90,  100)
700
400In these simulations, the DM’s preference has been divided into 2 categories as follows.(
1
) The primary purpose of the mission is to kill all the targets. The DM considers criterion RA to be the most important, CL to be the second most important, and CF to be the third most important. The weight intervals are given in Table 3.Table 3
The weight intervals.
Attribute
R
A
C
F
C
L
ω
min
⁡
0.4
0.1
0.25
ω
max
⁡
0.55
0.2
0.4Using the Monte Carlo technique, the results are shown in Table4. The rank acceptability indices are presented in Figures 5–8.Table 4
Rank acceptability indices and holistic acceptability indices.
Target
UAV
b
i
j
1
b
i
j
2
b
i
j
3
b
i
j
4
ω
i
j
c
p
i
j
c
a
i
j
h
t
1
u
1
0.1320
0.8678
0.0001
0.0001
0.4959
0.1556
0.3485
0.0455
0.5265
u
2
0.4395
0.0685
0.3161
0.1759
0.5237
0.1631
0.3132
1
0.5281
u
3
0.4284
0.0636
0.3432
0.1648
0.4684
0.1544
0.3772
0
0.5197
u
4
0.0001
0.0001
0.3406
0.6592
0.5215
0.1137
0.3648
0
0.0621
t
2
u
1
0.0504
0.9493
0.0002
0.0001
0.5050
0.1587
0.3362
0
0.4819
u
2
0.3616
0.0263
0.3145
0.2976
0.5258
0.1663
0.3079
1
0.4307
u
3
0.5879
0.0242
0.2904
0.0975
0.4767
0.1532
0.3701
0
0.6517
u
4
0.0001
0.0002
0.3949
0.6048
0.5172
0.1592
0.3236
0
0.0720
t
3
u
1
0.1631
0.8366
0.0002
0.0001
0.5011
0.1539
0.3450
0.0894
0.5434
u
2
0.3790
0.0849
0.3293
0.2068
0.5259
0.1651
0.3090
1
0.4775
u
3
0.4578
0.0784
0.3271
0.1367
0.4690
0.1547
0.3763
0
0.5529
u
4
0.0001
0.0001
0.3434
0.6564
0.5205
0.1969
0.2826
0
0.0626
t
4
u
1
0.0841
0.9156
0.0001
0.0002
0.4959
0.1568
0.3473
0
0.5003
u
2
0.4516
0.0439
0.3288
0.1757
0.5226
0.1627
0.3147
1
0.5313
u
3
0.4642
0.0404
0.3503
0.1451
0.4696
0.1547
0.3757
0
0.5463
u
4
0.0001
0.0001
0.3208
0.6790
0.5491
0.1521
0.2988
0
0.0585Figure 5
Rank acceptability indicesb1–b4 for target t1.Figure 6
Rank acceptability indicesb1–b4 for target t2.Figure 7
Rank acceptability indicesb1–b4 for target t3.Figure 8
Rank acceptability indicesb1–b4 for target t4.Using (22)-(23), the final results of task assignment are listed in Table 5, where 1 indicates that the target was assigned to the UAV and 0 otherwise.Table 5
The final result of assignment.
UAV
Target
t
1
t
2
t
3
t
4
u
1
0
0
1
0
u
2
0
0
0
1
u
3
0
1
0
0
u
4
1
0
0
0(
2
) The primary purpose of the mission was to kill all the targets in the case of ensuring that the UAVs underwent zero damage, as far as possible. The DM considers criterion CL to be the most important, RA to be the second most important, and CF to be the third most important. The weight intervals are given in Table 6. The results are shown in Table 7.Table 6
The weight intervals.
Attribute
R
A
C
F
C
L
ω
min
⁡
0.25
0.1
0.45
ω
max
⁡
0.35
0.2
0.55Table 7
Rank acceptability indices and holistic acceptability indices.
Target
UAV
b
i
j
1
b
i
j
2
b
i
j
3
b
i
j
4
ω
i
j
c
p
i
j
c
a
i
j
h
t
1
u
1
0
0.9997
0.0002
0.0001
0
0
0
0
0.4544
u
2
0
0
0.0001
0.9999
0
0
0
0
0.0000
u
3
0.9999
0.0001
0
0
0.3163
0.1668
0.5169
0.9976
0.9999
u
4
0.0001
0.0002
0.9997
0
0.3149
0.1847
0.5004
0
0.1820
t
2
u
1
0.9997
0.0002
0.0001
0
0.3165
0.1666
0.5168
1
0.9998
u
2
0
0.0001
0.9999
0
0
0
0
0
0.1818
u
3
0
0
0
1.0000
0
0
0
0
0.0000
u
4
0.0003
0.9997
0
0
0.3093
0.1687
0.5220
0
0.4547
t
3
u
1
0
0.9997
0.0003
0
0
0
0
0
0.4545
u
2
1.0000
0
0
0
0.3164
0.1667
0.5169
1
1.0000
u
3
0
0
0
1.0000
0
0
0
0
0.0000
u
4
0
0.0003
0.9997
0
0
0
0
1
0.1819
t
4
u
1
0
0.9997
0.0003
0
0
0
0
0
0.4545
u
2
0
0
0
1.0000
0
0
0
0
0
u
3
1.0000
0
0
0
0.3163
0.1672
0.5165
1
1.0000
u
4
0
0.0003
0.9997
0
0
0
0
1
0.1819The final results of task assignment are listed in Table8.Table 8
The final result of assignment.
UAV
Target
t
1
t
2
t
3
t
4
u
1
0
1
0
0
u
2
0
0
1
0
u
3
0
0
0
1
u
4
1
0
0
0


## 6. Conclusion

This paper presented a task assignment method for multiple UAVs under severe uncertainty conditions, in which the values of the criteria essential to task assignment were random, fuzzy, or unknown. Taking advantage of the SMAA-2 method, this paper established the solving model and the solution process.In the simulations, we selected different weight information for 2 simulation experiments. In the experiments, there was little difference in the central weight vector for each assignment, so we only needed to select alternatives on the basis of the holistic acceptability index. However, if the central weight vectors vary widely, the selection should instead be based on the holistic acceptability index, the central weight vector, and the confidence factor.Another advantage to the SMAA-2 method is that it allows using any preference models commonly accepted by DMs in practical problems. This paper uses the linear utility function, because it is reasonably easy to handle, both theoretically and computationally; also, DMs understood it easily.The proposed method provides a new method to apply to task assignment. It can provide an acceptable task allocation scheme before a mission, when a great deal of information is uncertain.



---

*Source: 249825-2015-08-16.xml*