# Cooperative Task Allocation Method of MCAV/UCAV Formation

Authors: Yun Zhong; Peiyang Yao; Yu Sun; Juan Yang
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

Unmanned Combat Aerial Vehicle (UCAV) cooperative task allocation under Manned Combat Aerial Vehicle’s (MCAV) limited control is one of the important problems in UCAV research field. Hereto, we analyze the key technical and tactical indices influence task allocation problem and build an appropriate model to maximize the objective function values as well as reflecting various constraints. A novel improved multigroup ant colony algorithm (IMGACA) is proposed to solve the model; the algorithm mainly includes random sequence-based UCAV selection strategy, constraint-based candidate task generation strategy, objective function value-based state transition strategy, and crossover operator-based local search strategy. Simulation results show that the built model is reasonable and the proposed algorithm performs well in feasibility, timeliness, and stability.


---

## Body

## 1. Introduction

UCAVs being equipped with communication system have been widely used in battlefield under the fierce battlefield countermeasure and complex battlefield environment [1]. By means of forming task coalition, MCAVs cooperate with UCAVs to execute combat tasks, and in this way they can exert respective advantages [2]. By taking advantages of strong maneuver, outstanding stealth, and low cost, UCAVs get deep into the battlefield front with harsh battlefield environment, carrying out various combat tasks such as battlefield detection, interference, attack, and assessment, while MCAVs mainly provide command and control (C2) outside the combat zone and give full play to MCAV commanders’ comprehensive judgment and rational decision-making ability.MCAV/UCAV cooperative task allocation problem is one of the key technologies in MCAV/UCAV cooperative engagement, and it is a NP-hard problem [3]. Firstly, it takes task types, values, and locations into account and then establishes the allocation model which maximizes allocation efficiency function and meets all technical and tactical constraints, and finally it applies the appropriate algorithm to solve the model. Currently, the research on the problem focuses primarily on model building [4–6] and algorithm solving [7, 8].In terms of task allocation models, researchers usually abstracted the task allocation problem into existing mature models such as multiple travelling salesman problem (MTSP), mixed integer linear programming (MILP), and vehicle routing problem (VRP). Besides, Air Force Research Laboratory (AFRL) raised a model called capacitated vehicle routing problem with time window (CVRPTW) and applied it to reconnaissance mission planning of Global Hawks and Predators [9].As far as task allocation algorithms are concerned, they mainly include centralized algorithms and distributed algorithms. The former ones include integer programming algorithm, swarm intelligence heuristic algorithm and evolutionary algorithm, and the latter ones include contract net protocol and auction algorithm, which are based on market mechanism and realize dynamic task allocation through negotiation. In [10], a novel task allocation method based on genetic algorithm (GA) was proposed; it realized quick and effective allocation within a relatively short time, while, in [11], the balance of UCAVs’ task load was considered, and the adaptive inertia weight improved particle swarm algorithm was introduced to solve the allocation model; in the end, the business contract mechanism was adopted to realize task coordination. Choi et al. [12] put forward two decentralized algorithms to coordinate a fleet of autonomous vehicles: consensus-based auction algorithm (CBAA) and its generalization to the multiallocation problem, that is, consensus-based bundle algorithm (CBBA), both of which produced conflict-free feasible solutions that were robust to inconsistencies in the situational awareness and communication topology changes via the synchronous interaction of information status. Furthermore, to solve the information transmission chaos problem in asynchronous communication system in [12], an asynchronous consensus-based bundle algorithm (ACBBA) was proposed in [13]; however, it still could not realize cooperation between UCAVs.Ant colony algorithm (ACA) was first presented by Italian scholar Dorigo and Gambardella [14] to solve travelling salesman problem (TSP), and it has been applied to solve various kinds of combinatorial optimization problems afterwards [15–17]. The principle of ACA is to simulate the real ant colony foraging mechanism in nature and introduce heuristic information into pheromone release/volatile mechanism, which will speed up the convergence rate of ACA.The remainder of this paper is organized as follows. A task allocation optimization model of MCAV/UCAV formation, which overall considers various constraints, is built in Section2, and in this section, mathematical complexity of the model is also analyzed. Based on ACA, we propose a novel improved multigroup ant colony algorithm (IMGACA) in Section 3, and the algorithm includes random sequence-based UCAV selection strategy, constraint-based candidate task generation strategy, objective function value-based state transition strategy, and crossover operator-based local search strategy. By adopting these strategies, the ability of algorithm to eliminate conflicts and escape from local optimum is enhanced. Three simulation cases are designed to verify that the algorithm is feasible, time-effective, and stable in Section 4. At last, in Section 5, a summarization is given, and the future work is prospected.


## 2. Model Building

Basic elements in MCAV/UCAV cooperative task allocation problem include MCAVs, UCAVs, and tasks. Under the centralized-distributed command and control structure of MCAV, UCAVs formation attacks enemy targets cooperatively. The set of UCAVs is U
=
{
U
1
,
U
2
,
…
,
U
N
v
}, where N
v is the number of UCAVs in the set, and the attribute values of U
i
(
i
=
1,2
,
…
,
N
v
) mainly include location, value, task load, and velocity, which are represented as L
U
i, V
U
i, T
L
i, and V
e
l
i, respectively. The set of tasks is T
=
T
1
,
T
2
,
…
,
T
N
t, where N
t is the number of tasks in the set, and the attribute values of T
j
j
=
1,2
,
…
,
N
t mainly include location and value, which are represented as L
T
j and V
T
j, respectively. There are no no-fly zones and unexpected obstacles.Figure1 shows a typical task execution process of MCAV/UCAV task coalition. Tasks are mainly executed by UCAVs; only when asked for cooperation request, MCAV provides cooperative guidance support.Figure 1
Typical task execution process.


### 2.1. Assumptions

To simplify the problem, three assumptions are given.Assumption 1.
For MCAV/UCAV cooperative engagement system, all platforms are not limited to flight range.Assumption 2.
All platforms move in a straight line; that is, there are no platform kinematical constraints.Assumption 3.
The number of tasksN
t is less than the sum of task loads of all UCAVs: ∑
i
=
1
N
v
T
L
i
=
N
l; that is, all tasks can be executed.


### 2.2. Definition of Decision Variables and Constraint Conditions

To build the mathematical model for the MCAV/UCAV cooperative task allocation, at first, we define the related decision variables.(i)
Allocation variablex
i
j, which represents the element in task allocation matrix X
=
x
i
j
N
v
×
N
t, x
i
j
=
1, denotes the idea that U
i executes T
j, while x
i
j
=
0 on behalf of the opposite meaning.
(ii)
Transfer variabley
n
j
i, which represents the transfer status between tasks, y
n
j
i
=
1, denotes the idea that U
i is assigned to T
j after executing T
n, while y
n
j
i
=
0 on behalf the opposite meaning. In particular, if n
=
j is true, then y
n
j
i
=
0.ToU
i and T
j, if x
i
j
=
1, then it contains two cases. The first case is that U
i is assigned to T
j after executing T
n, which means y
n
j
i
=
1. The second case is that U
i is assigned tasks for the first time; that is, T
n has no leading tasks, which means y
n
j
i
=
0. Assuming that there is a virtual task, T
0 should be assigned to all UCAVs at first, so the constraint relationship between x
i
j and y
n
j
i can be expressed as(1)
∑
n
=
0
N
t
y
n
j
i
-
x
i
j
=
0
,
i
=
1,2
,
…
,
N
v
;
j
=
1,2
,
…
,
N
t
.Meanwhile, after executingT
n, U
i can be assigned only one task; namely,(2)
∑
j
=
1
N
t
y
n
j
i
≤
1
,
i
=
1,2
,
…
,
N
v
;
n
=
0,1
,
…
,
N
t
.In addition, in consideration of task load constraint, task number constraint, and so on, we give task allocation constraints as follows:(3)
∑
j
=
1
N
t
x
i
j
≤
T
L
i
,
i
=
1,2
,
…
,
N
v
(4)
∑
i
=
1
N
v
x
i
j
=
1
,
j
=
1,2
,
…
,
N
t
(5)
∑
i
=
1
N
v
∑
j
=
1
N
t
x
i
j
≤
N
d
=
min
⁡
N
t
,
N
l
=
N
t
,where formula (3) represents the task load constraint, formula (4) denotes the idea that a task only can be executed by UCAV for once, and formula (5) represents the task number constraint.


### 2.3. MCAV Trust Degree

Due to the heterogeneous characteristics of UCAV, it is bound to have differences in performance and result when different UCAVs execute the same task. Hence, when decomposing a mission into several tasks, the MCAV commander has his subjective preference, which is defined as trust degree. The value of trust degree depends on task executed qualityT
E
Q of UCAVs, drawing on the experience of [18]; T
E
Q
i
j is defined as(6)
T
E
Q
i
j
=
1
1
+
exp
⁡
6
1
-
2
A
T
i
j
,where A
T
i
j
i
=
1,2
,
…
,
N
v
;
j
=
1,2
,
…
,
N
t is U
i’s kill probability to T
j.


### 2.4. Attack Benefit Function

The definition of attack benefit is the benefit value gained during the execution of tasks, and it is related to the MCAV trust degree. This paper defines attack benefit function as(7)
G
=
∑
i
=
1
N
v
∑
j
=
1
N
t
T
E
Q
i
j
·
x
i
j
.


### 2.5. Attack Cost Function

WhenU
i executes combat tasks, it has got to pay the corresponding costs such as threat cost, flight range cost, and ammunition cost; we will define the concept of these three costs in the following text.IfT
j’s damage probability to U
i is D
A
i
j, the value of U
i is V
U
i, then the threat cost of T
j to U
i can be expressed as C
1, and the calculating formula is (8)
C
1
=
∑
i
=
1
N
v
∑
j
=
1
N
t
D
A
i
j
·
x
i
j
·
V
U
i
.In addition, to make the flight range of all UCAVs in MCAV/UCAV cooperative engagement system as short as possible is also an important optimization objective; we define the flight range cost as(9)
C
2
=
∑
i
=
1
N
v
∑
j
=
1
N
t
D
i
j
D
m
a
x
·
x
i
j
,where D
i
j represents the distance from U
i to T
j, and D
m
a
x is the maximum value within D
i
j.And lastly, if the different types of ammunition loaded on UCAVs have the similar attack effect to the same task, then it should be possible to choose the ammunition that has lower cost. Suppose the cost of ammunitionA
m
i loaded on U
i is V
A
i; the ammunition cost in task allocation is (10)
C
3
=
∑
i
=
1
N
v
∑
j
=
1
N
t
V
A
i
·
1
-
A
T
i
j
·
x
i
j
.So the total cost is(11)
C
=
C
1
+
C
2
+
C
3
.


### 2.6. Allocation Model

MCAV commanders always want task completion time to be as short as possible, in MCAV/UCAV cooperative engagement system; it is necessary to introduce the influence of task completion time into the model. Suppose the expected task completion time of MCAV commanders ist
e
x
p; then the definition of task completion time as well as aging factor is expressed as(12)
t
c
p
l
=
max
j
∈
1,2
,
…
,
N
t
⁡
t
j
A
F
t
i
m
e
=
λ
t
c
p
l
/
t
e
x
p
,where t
j is the completion time of task T
j, and λ is regulatory parameter and satisfied with 0
<
λ
<
1.From the above analysis, it can be seen that the MCAV/UCAV cooperative task allocation is not a single-objective optimization problem but a multiobjective optimization problem. We adopt linear weight sum method to translate it to a single-objective optimization one; therefore, the objective function is defined as(13)
max
⁡
f
=
ω
1
G
-
ω
2
C
·
A
F
t
i
m
e
,where ω
1 and ω
2 are weighting coefficient of G and C, respectively; we usually take them to be 1.The task allocation model can be expressed as(14)
m
a
x
f
∑
n
=
0
N
t
y
n
j
i
-
x
i
j
=
0
∑
j
=
1
N
t
y
n
j
i
≤
1
∑
j
=
1
N
t
x
i
j
≤
T
L
i
∑
i
=
1
N
v
x
i
j
=
1
∑
i
=
1
N
v
∑
j
=
1
N
t
x
i
j
≤
N
d
=
min
⁡
N
t
,
N
l
=
N
t
x
i
j
,
y
n
j
i
∈
0,1
i
=
1,2
,
…
,
N
v
;
n
=
0,1
,
…
,
N
t
;
j
=
1,2
,
…
,
N
t
.


### 2.7. Mathematical Complexity of the Model

Analyzing the problem size, the number of feasible solutions is provided below.Lemma 4.
IfN
=
N
1
+
N
2
⋯
+
N
n (N
,
N
1
,
N
2
,
…
,
N
n are all positive integers), then N
!
≥
N
1
!
×
N
2
!
×
⋯
×
N
n
! is always to be true.Proof.
Firstly, take a simple case; ifN
=
N
1
+
N
2, then N
1
!
×
N
2
!
=
N
1
!
×
(
N
-
N
1
)
! = 1
×
2
×
⋯
×
N
1
×
1
×
2
×
⋯
×
(
N
-
N
1
)
≤
1
×
2
×
⋯
×
N
1
×
(
N
1
+
1
)
×
(
N
1
+
2
)
×
⋯
×
N
=
N
! is always to be true. Then, the conclusion just drawn above can be extended to general case; that is, if N
=
N
1
+
N
2
+
⋯
+
N
n, then N
1
!
×
N
2
!
×
⋯
×
N
n
!
≤
N
12
!
×
N
3
!
×
N
4
!
×
⋯
×
N
n
!
≤
N
123
!
×
N
4
!
×
N
5
!
⋯
×
N
n
!
≤
⋯
≤
N
123
⋯
n
!
=
N
!, where N
12
=
N
1
+
N
2
,
N
123
=
N
1
+
N
2
+
N
3
,
N
123
⋯
n
=
N
1
+
N
2
+
⋯
+
N
n.Theorem 5.
When task loads of UCAVs are unlimited, the upper bound of feasible solution number isN
s
=
2
P
N
l
,
N
t.Proof.
According to Assumption3, N
t
≤
N
l, so it can be seen that N
t tasks are allocated to N
l task loads independently, and the permutation of allocation plan is C
N
l
,
N
t. So if N
t tasks are allocated among N
v UCAVs, there are two cases: (i) the most extreme case is that all tasks are allocated to one UCAV, and, in this case, the permutation of N
t tasks is N
t
!; (ii) tasks are allocated to more than two UCAVs; based on Lemma 4, in this case, the permutation of N
t tasks is less than N
!. So the total feasible solution number is less than C
N
l
,
N
t
×
(
N
!
+
N
!
)
=
2
C
N
l
,
N
t
×
N
!
=
2
P
(
N
l
,
N
t
).


## 2.1. Assumptions

To simplify the problem, three assumptions are given.Assumption 1.
For MCAV/UCAV cooperative engagement system, all platforms are not limited to flight range.Assumption 2.
All platforms move in a straight line; that is, there are no platform kinematical constraints.Assumption 3.
The number of tasksN
t is less than the sum of task loads of all UCAVs: ∑
i
=
1
N
v
T
L
i
=
N
l; that is, all tasks can be executed.


## 2.2. Definition of Decision Variables and Constraint Conditions

To build the mathematical model for the MCAV/UCAV cooperative task allocation, at first, we define the related decision variables.(i)
Allocation variablex
i
j, which represents the element in task allocation matrix X
=
x
i
j
N
v
×
N
t, x
i
j
=
1, denotes the idea that U
i executes T
j, while x
i
j
=
0 on behalf of the opposite meaning.
(ii)
Transfer variabley
n
j
i, which represents the transfer status between tasks, y
n
j
i
=
1, denotes the idea that U
i is assigned to T
j after executing T
n, while y
n
j
i
=
0 on behalf the opposite meaning. In particular, if n
=
j is true, then y
n
j
i
=
0.ToU
i and T
j, if x
i
j
=
1, then it contains two cases. The first case is that U
i is assigned to T
j after executing T
n, which means y
n
j
i
=
1. The second case is that U
i is assigned tasks for the first time; that is, T
n has no leading tasks, which means y
n
j
i
=
0. Assuming that there is a virtual task, T
0 should be assigned to all UCAVs at first, so the constraint relationship between x
i
j and y
n
j
i can be expressed as(1)
∑
n
=
0
N
t
y
n
j
i
-
x
i
j
=
0
,
i
=
1,2
,
…
,
N
v
;
j
=
1,2
,
…
,
N
t
.Meanwhile, after executingT
n, U
i can be assigned only one task; namely,(2)
∑
j
=
1
N
t
y
n
j
i
≤
1
,
i
=
1,2
,
…
,
N
v
;
n
=
0,1
,
…
,
N
t
.In addition, in consideration of task load constraint, task number constraint, and so on, we give task allocation constraints as follows:(3)
∑
j
=
1
N
t
x
i
j
≤
T
L
i
,
i
=
1,2
,
…
,
N
v
(4)
∑
i
=
1
N
v
x
i
j
=
1
,
j
=
1,2
,
…
,
N
t
(5)
∑
i
=
1
N
v
∑
j
=
1
N
t
x
i
j
≤
N
d
=
min
⁡
N
t
,
N
l
=
N
t
,where formula (3) represents the task load constraint, formula (4) denotes the idea that a task only can be executed by UCAV for once, and formula (5) represents the task number constraint.


## 2.3. MCAV Trust Degree

Due to the heterogeneous characteristics of UCAV, it is bound to have differences in performance and result when different UCAVs execute the same task. Hence, when decomposing a mission into several tasks, the MCAV commander has his subjective preference, which is defined as trust degree. The value of trust degree depends on task executed qualityT
E
Q of UCAVs, drawing on the experience of [18]; T
E
Q
i
j is defined as(6)
T
E
Q
i
j
=
1
1
+
exp
⁡
6
1
-
2
A
T
i
j
,where A
T
i
j
i
=
1,2
,
…
,
N
v
;
j
=
1,2
,
…
,
N
t is U
i’s kill probability to T
j.


## 2.4. Attack Benefit Function

The definition of attack benefit is the benefit value gained during the execution of tasks, and it is related to the MCAV trust degree. This paper defines attack benefit function as(7)
G
=
∑
i
=
1
N
v
∑
j
=
1
N
t
T
E
Q
i
j
·
x
i
j
.


## 2.5. Attack Cost Function

WhenU
i executes combat tasks, it has got to pay the corresponding costs such as threat cost, flight range cost, and ammunition cost; we will define the concept of these three costs in the following text.IfT
j’s damage probability to U
i is D
A
i
j, the value of U
i is V
U
i, then the threat cost of T
j to U
i can be expressed as C
1, and the calculating formula is (8)
C
1
=
∑
i
=
1
N
v
∑
j
=
1
N
t
D
A
i
j
·
x
i
j
·
V
U
i
.In addition, to make the flight range of all UCAVs in MCAV/UCAV cooperative engagement system as short as possible is also an important optimization objective; we define the flight range cost as(9)
C
2
=
∑
i
=
1
N
v
∑
j
=
1
N
t
D
i
j
D
m
a
x
·
x
i
j
,where D
i
j represents the distance from U
i to T
j, and D
m
a
x is the maximum value within D
i
j.And lastly, if the different types of ammunition loaded on UCAVs have the similar attack effect to the same task, then it should be possible to choose the ammunition that has lower cost. Suppose the cost of ammunitionA
m
i loaded on U
i is V
A
i; the ammunition cost in task allocation is (10)
C
3
=
∑
i
=
1
N
v
∑
j
=
1
N
t
V
A
i
·
1
-
A
T
i
j
·
x
i
j
.So the total cost is(11)
C
=
C
1
+
C
2
+
C
3
.


## 2.6. Allocation Model

MCAV commanders always want task completion time to be as short as possible, in MCAV/UCAV cooperative engagement system; it is necessary to introduce the influence of task completion time into the model. Suppose the expected task completion time of MCAV commanders ist
e
x
p; then the definition of task completion time as well as aging factor is expressed as(12)
t
c
p
l
=
max
j
∈
1,2
,
…
,
N
t
⁡
t
j
A
F
t
i
m
e
=
λ
t
c
p
l
/
t
e
x
p
,where t
j is the completion time of task T
j, and λ is regulatory parameter and satisfied with 0
<
λ
<
1.From the above analysis, it can be seen that the MCAV/UCAV cooperative task allocation is not a single-objective optimization problem but a multiobjective optimization problem. We adopt linear weight sum method to translate it to a single-objective optimization one; therefore, the objective function is defined as(13)
max
⁡
f
=
ω
1
G
-
ω
2
C
·
A
F
t
i
m
e
,where ω
1 and ω
2 are weighting coefficient of G and C, respectively; we usually take them to be 1.The task allocation model can be expressed as(14)
m
a
x
f
∑
n
=
0
N
t
y
n
j
i
-
x
i
j
=
0
∑
j
=
1
N
t
y
n
j
i
≤
1
∑
j
=
1
N
t
x
i
j
≤
T
L
i
∑
i
=
1
N
v
x
i
j
=
1
∑
i
=
1
N
v
∑
j
=
1
N
t
x
i
j
≤
N
d
=
min
⁡
N
t
,
N
l
=
N
t
x
i
j
,
y
n
j
i
∈
0,1
i
=
1,2
,
…
,
N
v
;
n
=
0,1
,
…
,
N
t
;
j
=
1,2
,
…
,
N
t
.


## 2.7. Mathematical Complexity of the Model

Analyzing the problem size, the number of feasible solutions is provided below.Lemma 4.
IfN
=
N
1
+
N
2
⋯
+
N
n (N
,
N
1
,
N
2
,
…
,
N
n are all positive integers), then N
!
≥
N
1
!
×
N
2
!
×
⋯
×
N
n
! is always to be true.Proof.
Firstly, take a simple case; ifN
=
N
1
+
N
2, then N
1
!
×
N
2
!
=
N
1
!
×
(
N
-
N
1
)
! = 1
×
2
×
⋯
×
N
1
×
1
×
2
×
⋯
×
(
N
-
N
1
)
≤
1
×
2
×
⋯
×
N
1
×
(
N
1
+
1
)
×
(
N
1
+
2
)
×
⋯
×
N
=
N
! is always to be true. Then, the conclusion just drawn above can be extended to general case; that is, if N
=
N
1
+
N
2
+
⋯
+
N
n, then N
1
!
×
N
2
!
×
⋯
×
N
n
!
≤
N
12
!
×
N
3
!
×
N
4
!
×
⋯
×
N
n
!
≤
N
123
!
×
N
4
!
×
N
5
!
⋯
×
N
n
!
≤
⋯
≤
N
123
⋯
n
!
=
N
!, where N
12
=
N
1
+
N
2
,
N
123
=
N
1
+
N
2
+
N
3
,
N
123
⋯
n
=
N
1
+
N
2
+
⋯
+
N
n.Theorem 5.
When task loads of UCAVs are unlimited, the upper bound of feasible solution number isN
s
=
2
P
N
l
,
N
t.Proof.
According to Assumption3, N
t
≤
N
l, so it can be seen that N
t tasks are allocated to N
l task loads independently, and the permutation of allocation plan is C
N
l
,
N
t. So if N
t tasks are allocated among N
v UCAVs, there are two cases: (i) the most extreme case is that all tasks are allocated to one UCAV, and, in this case, the permutation of N
t tasks is N
t
!; (ii) tasks are allocated to more than two UCAVs; based on Lemma 4, in this case, the permutation of N
t tasks is less than N
!. So the total feasible solution number is less than C
N
l
,
N
t
×
(
N
!
+
N
!
)
=
2
C
N
l
,
N
t
×
N
!
=
2
P
(
N
l
,
N
t
).


## 3. IMGACA

### 3.1. Establishment of Job-Division Ant Colony

There are obvious differences between cooperative task allocation problem and TSP, and the latter one can be solved effectively by traditional ACA. The main differences are listed as follows.(i)
Task execution has parallel characteristic; that is, tasks are likely to be executed by UCAVs simultaneously, and it is difficult for traditional ACA to reflect the influence of such parallel characteristic.
(ii)
Platform has collaborative characteristic, and there exists task and resource collaboration among different UCAVs; traditional ACA is difficult to handle this kind of collaborative relationship with mutual coupling.
(iii)
Task execution has aftereffect characteristic; that is, due to the presence of various constraints, current task execution order will affect the subsequent task, and traditional ACA is difficult to solve this kind of aftereffect characteristic.So, based on the analysis to MCAV/UCAV cooperative task allocation, UCAVs are mapped to ant subgroups in ant colony, ants belonging to different subgroups with the same serial number make up ant subclusters, and each cluster realizes implicit communication via pheromone interaction to generate the allocation plan.Suppose the number of subgroup of artificial ant colony isN
S
G
=
N
v; for U
i, the number of ants in subgroup is m. The set of U
i’s ant subgroup is S
G
i
=
a
n
t
i
j
,
j
=
1,2
,
…
,
m; all ant subgroups form ant colony system G
=
{
S
G
i
,
i
=
1,2
,
…
,
N
S
G
}. Note that a
n
t
i
j and a
n
t
k
j belonging to different ant subgroups S
G
i and S
G
k, respectively, will influence each other while generating their own task allocation plan; to avoid this situation, we establish m local tabu table T
a
b
u
=
t
a
b
u
1
,
t
a
b
u
2
,
…
,
t
a
b
u
m, and each tabu table is written in the task index that has been executed by other ants and in this way can solve the repeated execution problem for tasks.Above all, job-division ant colony can be shown as ant matrix in Figure 2, the matrix row represents all ant subgroups, and the matrix column represents all ant subclusters S
G
j
=
a
n
t
i
j
,
i
=
1,2
,
…
,
N
v.Figure 2
Ant colony based on the job-division mechanism.


### 3.2. Random Sequence-Based UCAV Selection Strategy

When selecting specific UCAV to execute task, deterministic selection sequence will lead the search algorithm to trap in local optimum, so, to guarantee the solution diversity in the algorithm solving process, random sequence is adopted to select UCAV. Moreover, to avoid conflict, it is necessary to exclude that the UCAV has reached maximum task load.


### 3.3. Constraint-Based Candidate Task Generation Strategy

By formulas (3), (4), and (5), in the MCAV/UCAV cooperative task allocation problem, constraints mainly include load constraint of UCAVs and number constraint of tasks. To avoid the generation of infeasible solutions brought by blindness or randomness of search algorithm and further result in performance degrading of algorithm, when a
n
t
i
j chooses candidate task in the set a
l
l
o
w
_
T
a
n
t
i
j, it should screen out those tasks that do not meet constraints; only in this way can computational scale and complexity be reduced.Based on the above analysis, a candidate task set generating algorithm (CTSGA) is proposed; the details are shown in Algorithm1.Algorithm 1:CTSGA for a
n
t
i
j based on constraint condition. Where ⋅ denotes the cardinality of the vector, T
A
a
n
t
i
j and T
A
(
a
n
t
i
-
j
) denote the task set whose task element has been executed by a
n
t
i
j and other ants in S
C
j except for a
n
t
i
j, respectively.
Input:T
A
(
a
n
t
i
-
j
), a
l
l
o
w
_
T
a
n
t
i
j
=
ø, T, T
L
i; Output: a
l
l
o
w
_
T
a
n
t
i
j
(1)procedure Select a
n
t
i
j and task set T
(2)if  T
A
a
n
t
i
j
<
T
L
i
then
(3)if  T
j
∉
T
A
a
n
t
i
-
j
then
(4)a
l
l
o
w
_
T
a
n
t
i
j
=
a
l
l
o
w
_
T
a
n
t
i
j
∪
T
j
,
∀
j
∈
1
,
N
t
(5)end if
(6)end if
(7)end procedure


### 3.4. Objective Function Value-Based State Transition Strategy

Whena
n
t
i
j selects a task in a
l
l
o
w
_
T
a
n
t
i
j, which one to be selected and how to be selected are significant issues. In this paper, pseudo-random proportional rule is considered to be a reasonable method and it can be expressed as(15)
y
=
arg
⁡
max
s
∈
allow
_
T
ant
ij
⁡
τ
r
s
k
α
·
η
r
s
k
β
if
q
≤
q
0
Y
else,where τ
r
s
k is pheromone value from r to s in kth iteration and η
r
s
k is heuristic information value from r to s in kth iteration, while α and β represent pheromone factor and heuristic information factor, respectively, reflecting the relative importance of pheromones and heuristic information in solving process to get feasible solutions. And q
0 is a constant value that lies between 0 and 1, while q is a random number that obeys uniform distribution in 0,1.In other words, ants will select the optimal path for state transition with probabilityq
0 and will explore a new path in the roulette way with probability 1
-
q
0. Y in formula (15) is a selected task in random proportional rule shown as follows:(16)
p
k
r
,
s
=
τ
r
s
k
α
·
η
r
s
k
β
∑
u
τ
r
u
k
α
·
η
r
u
k
β
,
u
∈
a
l
l
o
w
_
T
a
n
t
i
j
0
,
u
∉
a
l
l
o
w
_
T
a
n
t
i
j
.ACA has the positive feedback, self-organization and distributed characteristics; the positive feedback mechanism especially will lead search algorithm to trap in local optimum in later iterations [19]. Aiming at this problem, an adaptive adjustment strategy for task selection is proposed: at the earlier stage of iteration, to improve the computational convergence, we set smaller candidate tasks size, while at the later stage of iteration, to ensure the diversity of solutions, we set larger candidate tasks size.The concept of task selection window, which can be utilized to shift between intensification and diversification [20], is applied to set the size of candidate tasks dynamically. When a
n
t
i
j selects a specific path at a certain probability, it does not mean that all candidate tasks in a
l
l
o
w
_
T
a
n
t
i
j will have the chance to be selected as the next executed task; specific steps are as follows.Step 1.
Sort all tasks ina
l
l
o
w
_
T
a
n
t
i
j on the basis of aggregation operator of pheromone and heuristic information value.Step 2.
Judge if current number of iteration has reached half of the total number of iterations; if so, setσ
1
=
0.5; otherwise, set σ
2
=
0.9.Step 3.
On the basis of formula (17), it generates updated size of candidate task set, where σ is filtration factor, the value of σ is assigned σ
1 or σ
2 depending on the iterative process, and · is rounded-up operation. Note that if a
l
l
o
w
_
T
a
n
t
i
j contains only one task, then it will be selected immediately.(17)
a
l
l
o
w
_
T
a
n
t
i
j
⟵
σ
·
a
l
l
o
w
_
T
a
n
t
i
j
.


### 3.5. Crossover Operator-Based Local Search Strategy

ACA has strong global search ability, but search efficiency is low; therefore, local optimizer is introduced to raise its solution precision and convergence rate.After all ant subclusters finish a round of searching, the feasible solution spaceΘ
k
k
=
1,2
,
…
,
K is formed, and we utilize neighborhood heuristic knowledge to direct its local search; the steps are as follows.Step 1.
Sort all objective function values inU
-
T allocation matrix where x
i
j
=
1, and seek out the U
i
-
T
j pair which has the minimum objective function value.Step 2.
Find out UCAVs whose remaining task load is greater than 0 inU except for U
i, then put these UCAVs into the set F
Y, and, at last, calculate and record the element number f
y of F
Y.Step 3.
AllocateT
j to UCAV in F
Y randomly; if it satisfies the idea that the variation of objective function value Δ
s
w
a
p
U
i
,
U
i
-
,
T
j
>
0, then change T
j’s execution platform from U
i to U
i
-; otherwise, stay the same.Step 4.
UpdateF
Y, and repeat Steps 1–3 for N times; N is a positive integer, and its usual value is set to be 3.


### 3.6. Pheromone Update Strategy

In multigroup ant colony search system, only iteration-best ant can update global pheromone; the goal is to make the search process more targeted and guide ants to search near the optimal solution in the current iteration. So when IMGACA updates global pheromone, it mainly adopts ant-density system update strategy, and the updating formula is defined as (18)
τ
r
,
s
=
1
-
ρ
g
l
o
·
τ
r
,
s
+
ρ
g
l
o
·
Q
,where Q is a constant value and ρ
g
l
o is a global update factor, and it is satisfied with 0
<
ρ
g
l
o
<
1.When updating local pheromone, in order to guide ants to search near the solution where task completion time is shorter, it mainly adopts ant-quantity system update strategy, and the principle is to release more pheromone in such search path.(19)
τ
r
,
s
=
1
-
ρ
l
o
c
·
τ
r
,
s
+
ρ
l
o
c
·
Q
E
t
E
t
=
t
S
C
k
min
⁡
t
S
C
k
,where ρ
l
o
c is a local update factor, and it is satisfied with 0
<
ρ
l
o
c
<
1, and t
S
C
k is task completion time of the kth ant subcluster S
C
k.


## 3.1. Establishment of Job-Division Ant Colony

There are obvious differences between cooperative task allocation problem and TSP, and the latter one can be solved effectively by traditional ACA. The main differences are listed as follows.(i)
Task execution has parallel characteristic; that is, tasks are likely to be executed by UCAVs simultaneously, and it is difficult for traditional ACA to reflect the influence of such parallel characteristic.
(ii)
Platform has collaborative characteristic, and there exists task and resource collaboration among different UCAVs; traditional ACA is difficult to handle this kind of collaborative relationship with mutual coupling.
(iii)
Task execution has aftereffect characteristic; that is, due to the presence of various constraints, current task execution order will affect the subsequent task, and traditional ACA is difficult to solve this kind of aftereffect characteristic.So, based on the analysis to MCAV/UCAV cooperative task allocation, UCAVs are mapped to ant subgroups in ant colony, ants belonging to different subgroups with the same serial number make up ant subclusters, and each cluster realizes implicit communication via pheromone interaction to generate the allocation plan.Suppose the number of subgroup of artificial ant colony isN
S
G
=
N
v; for U
i, the number of ants in subgroup is m. The set of U
i’s ant subgroup is S
G
i
=
a
n
t
i
j
,
j
=
1,2
,
…
,
m; all ant subgroups form ant colony system G
=
{
S
G
i
,
i
=
1,2
,
…
,
N
S
G
}. Note that a
n
t
i
j and a
n
t
k
j belonging to different ant subgroups S
G
i and S
G
k, respectively, will influence each other while generating their own task allocation plan; to avoid this situation, we establish m local tabu table T
a
b
u
=
t
a
b
u
1
,
t
a
b
u
2
,
…
,
t
a
b
u
m, and each tabu table is written in the task index that has been executed by other ants and in this way can solve the repeated execution problem for tasks.Above all, job-division ant colony can be shown as ant matrix in Figure 2, the matrix row represents all ant subgroups, and the matrix column represents all ant subclusters S
G
j
=
a
n
t
i
j
,
i
=
1,2
,
…
,
N
v.Figure 2
Ant colony based on the job-division mechanism.


## 3.2. Random Sequence-Based UCAV Selection Strategy

When selecting specific UCAV to execute task, deterministic selection sequence will lead the search algorithm to trap in local optimum, so, to guarantee the solution diversity in the algorithm solving process, random sequence is adopted to select UCAV. Moreover, to avoid conflict, it is necessary to exclude that the UCAV has reached maximum task load.


## 3.3. Constraint-Based Candidate Task Generation Strategy

By formulas (3), (4), and (5), in the MCAV/UCAV cooperative task allocation problem, constraints mainly include load constraint of UCAVs and number constraint of tasks. To avoid the generation of infeasible solutions brought by blindness or randomness of search algorithm and further result in performance degrading of algorithm, when a
n
t
i
j chooses candidate task in the set a
l
l
o
w
_
T
a
n
t
i
j, it should screen out those tasks that do not meet constraints; only in this way can computational scale and complexity be reduced.Based on the above analysis, a candidate task set generating algorithm (CTSGA) is proposed; the details are shown in Algorithm1.Algorithm 1:CTSGA for a
n
t
i
j based on constraint condition. Where ⋅ denotes the cardinality of the vector, T
A
a
n
t
i
j and T
A
(
a
n
t
i
-
j
) denote the task set whose task element has been executed by a
n
t
i
j and other ants in S
C
j except for a
n
t
i
j, respectively.
Input:T
A
(
a
n
t
i
-
j
), a
l
l
o
w
_
T
a
n
t
i
j
=
ø, T, T
L
i; Output: a
l
l
o
w
_
T
a
n
t
i
j
(1)procedure Select a
n
t
i
j and task set T
(2)if  T
A
a
n
t
i
j
<
T
L
i
then
(3)if  T
j
∉
T
A
a
n
t
i
-
j
then
(4)a
l
l
o
w
_
T
a
n
t
i
j
=
a
l
l
o
w
_
T
a
n
t
i
j
∪
T
j
,
∀
j
∈
1
,
N
t
(5)end if
(6)end if
(7)end procedure


## 3.4. Objective Function Value-Based State Transition Strategy

Whena
n
t
i
j selects a task in a
l
l
o
w
_
T
a
n
t
i
j, which one to be selected and how to be selected are significant issues. In this paper, pseudo-random proportional rule is considered to be a reasonable method and it can be expressed as(15)
y
=
arg
⁡
max
s
∈
allow
_
T
ant
ij
⁡
τ
r
s
k
α
·
η
r
s
k
β
if
q
≤
q
0
Y
else,where τ
r
s
k is pheromone value from r to s in kth iteration and η
r
s
k is heuristic information value from r to s in kth iteration, while α and β represent pheromone factor and heuristic information factor, respectively, reflecting the relative importance of pheromones and heuristic information in solving process to get feasible solutions. And q
0 is a constant value that lies between 0 and 1, while q is a random number that obeys uniform distribution in 0,1.In other words, ants will select the optimal path for state transition with probabilityq
0 and will explore a new path in the roulette way with probability 1
-
q
0. Y in formula (15) is a selected task in random proportional rule shown as follows:(16)
p
k
r
,
s
=
τ
r
s
k
α
·
η
r
s
k
β
∑
u
τ
r
u
k
α
·
η
r
u
k
β
,
u
∈
a
l
l
o
w
_
T
a
n
t
i
j
0
,
u
∉
a
l
l
o
w
_
T
a
n
t
i
j
.ACA has the positive feedback, self-organization and distributed characteristics; the positive feedback mechanism especially will lead search algorithm to trap in local optimum in later iterations [19]. Aiming at this problem, an adaptive adjustment strategy for task selection is proposed: at the earlier stage of iteration, to improve the computational convergence, we set smaller candidate tasks size, while at the later stage of iteration, to ensure the diversity of solutions, we set larger candidate tasks size.The concept of task selection window, which can be utilized to shift between intensification and diversification [20], is applied to set the size of candidate tasks dynamically. When a
n
t
i
j selects a specific path at a certain probability, it does not mean that all candidate tasks in a
l
l
o
w
_
T
a
n
t
i
j will have the chance to be selected as the next executed task; specific steps are as follows.Step 1.
Sort all tasks ina
l
l
o
w
_
T
a
n
t
i
j on the basis of aggregation operator of pheromone and heuristic information value.Step 2.
Judge if current number of iteration has reached half of the total number of iterations; if so, setσ
1
=
0.5; otherwise, set σ
2
=
0.9.Step 3.
On the basis of formula (17), it generates updated size of candidate task set, where σ is filtration factor, the value of σ is assigned σ
1 or σ
2 depending on the iterative process, and · is rounded-up operation. Note that if a
l
l
o
w
_
T
a
n
t
i
j contains only one task, then it will be selected immediately.(17)
a
l
l
o
w
_
T
a
n
t
i
j
⟵
σ
·
a
l
l
o
w
_
T
a
n
t
i
j
.


## 3.5. Crossover Operator-Based Local Search Strategy

ACA has strong global search ability, but search efficiency is low; therefore, local optimizer is introduced to raise its solution precision and convergence rate.After all ant subclusters finish a round of searching, the feasible solution spaceΘ
k
k
=
1,2
,
…
,
K is formed, and we utilize neighborhood heuristic knowledge to direct its local search; the steps are as follows.Step 1.
Sort all objective function values inU
-
T allocation matrix where x
i
j
=
1, and seek out the U
i
-
T
j pair which has the minimum objective function value.Step 2.
Find out UCAVs whose remaining task load is greater than 0 inU except for U
i, then put these UCAVs into the set F
Y, and, at last, calculate and record the element number f
y of F
Y.Step 3.
AllocateT
j to UCAV in F
Y randomly; if it satisfies the idea that the variation of objective function value Δ
s
w
a
p
U
i
,
U
i
-
,
T
j
>
0, then change T
j’s execution platform from U
i to U
i
-; otherwise, stay the same.Step 4.
UpdateF
Y, and repeat Steps 1–3 for N times; N is a positive integer, and its usual value is set to be 3.


## 3.6. Pheromone Update Strategy

In multigroup ant colony search system, only iteration-best ant can update global pheromone; the goal is to make the search process more targeted and guide ants to search near the optimal solution in the current iteration. So when IMGACA updates global pheromone, it mainly adopts ant-density system update strategy, and the updating formula is defined as (18)
τ
r
,
s
=
1
-
ρ
g
l
o
·
τ
r
,
s
+
ρ
g
l
o
·
Q
,where Q is a constant value and ρ
g
l
o is a global update factor, and it is satisfied with 0
<
ρ
g
l
o
<
1.When updating local pheromone, in order to guide ants to search near the solution where task completion time is shorter, it mainly adopts ant-quantity system update strategy, and the principle is to release more pheromone in such search path.(19)
τ
r
,
s
=
1
-
ρ
l
o
c
·
τ
r
,
s
+
ρ
l
o
c
·
Q
E
t
E
t
=
t
S
C
k
min
⁡
t
S
C
k
,where ρ
l
o
c is a local update factor, and it is satisfied with 0
<
ρ
l
o
c
<
1, and t
S
C
k is task completion time of the kth ant subcluster S
C
k.


## 4. Simulation Experiment

### 4.1. Parameter Setting

For purpose of verifying the superiority of the model and IMGACA, we run the IMGACA on a PC with Pentium (R) Dual-Core CPU E6600 3.06 GHz, and it is based on MATLAB R2010a software environment. Parameter setting in the IMGACA is listed as follows: t
e
x
p
=
10, α
=
3, β
=
8, λ
=
0.85, m
=
50, q
0
=
0.75, Q
=
3, ρ
g
l
o
=
0.05, and ρ
l
o
c
=
0.02.Table1 lists the task information including location and value.Table 1
Task information.
Task
L
T
V
T
T
1
(568, 508)
22.3
T
2
(259, 113)
32.6
T
3
(307, 365)
54.2
T
4
(467, 621)
34.6
T
5
(134, 311)
35.4
T
6
(514, 236)
33.1
T
7
(384, 469)
32.6
T
8
(156, 543)
43.4
T
9
(469, 182)
31.9
T
10
(281, 503)
44.1
T
11
(456, 247)
62.5
T
12
(89, 254)
33.6
T
13
(313, 256)
32.9
T
14
(617, 92)
23.2
T
15
(418, 507)
44.3
T
16
(383, 116)
23.0
T
17
(164, 229)
67.4
T
18
(605, 539)
33.4Table2 lists the UCAV information including location, value, velocity, and value of ammunition loaded on UCAVs.Table 2
UCAV information.
UCAV
L
U
V
U
V
e
l
V
A
U
1
(156, 443)
4.5
200
1.4
U
2
(195, 487)
6.0
150
2.3
U
3
(312, 584)
5.5
250
1.6
U
4
(237, 285)
3.0
250
1.6
U
5
(565, 591)
3.5
200
2.5
U
6
(652, 368)
5.0
300
2.3


### 4.2. Feasibility Analysis

Set the number of UCAVs as 6 and that of tasks as 18; besides, the matrices representing the kill probability of UCAVs to tasks and the damage probability of tasks to UCAVs areA
T and D
A; they are, respectively, set to be as follows.We make a comparative simulation between simulation scenarios with limited (task load vector isT
L
=
2,2
,
2,2
,
2,8) or unlimited task load for all UCAVs; the iteration number is 600, and, as shown in Table 3, is the simulation results in the two cases.Table 3
Task allocation plan with limited or unlimited task load.
UCAV
Flight range
Attack benefit
Attack cost
Allocation plan
Limited
U
1
380.47
61.10
3.96
T
10
→
T
5
U
2
573.81
64.85
3.61
T
18
→
T
4
U
3
182.01
65.78
5.64
T
15
→
T
7
U
4
498.24
68.71
3.99
T
9
→
T
3
U
5
504.14
78.20
5.33
T
11
→
T
13
U
6
2433.92
246.59
21.56
T
17
→
T
12
→
T
8
→
T
6
→
T
16
→
T
2
→
T
14
→
T
1
Unlimited
U
1
927.81
82.11
7.96
T
5
→
T
16
→
T
18
U
2
755.31
93.52
4.95
T
17
→
T
4
U
3
500.71
62.54
5.42
T
7
→
T
12
U
4
839.52
132.23
7.74
T
3
→
T
8
→
T
13
→
T
9
U
5
1020.19
144.63
9.13
T
10
→
T
11
→
T
15
→
T
1
U
6
726.63
78.54
6.70
T
6
→
T
14
→
T
2It is observed that when task load of UCAVs is limited, the task allocation solution is not an optimal one, and when task load of UCAVs is unlimited, the task allocation solution is more balanced and better feasible one.(20)
A
T
=
0.4
0.1
0.7
0.5
0.6
0.8
0.1
0.3
0.9
0.4
0.9
0.7
0.8
0.1
0.7
0.5
0.8
0.3
0.3
0.2
0.5
0.5
0.8
0.4
0.4
0.1
0.8
0.6
0.2
0.2
0.8
0.6
0.9
0.3
0.1
0.5
0.1
0.1
0.9
0.2
0.7
0.6
0.5
0.6
0.3
0.8
0.2
0.6
D
A
=
0.3
0.1
0.5
0.4
0.4
0.5
0.1
0.4
0.2
0.2
0.5
0.3
0.3
0.5
0.2
0.4
0.1
0.3
0.3
0.2
0.4
0.5
0.4
0.3
0.3
0.2
0.1
0.4
0.1
0.5
0.1
0.5
0.3
0.3
0.1
0.2
0.2
0.1
0.4
0.4
0.5
0.1
0.3
0.4
0.2
0.5
0.1
0.3
.Figures3–5 give, respectively, comparison results of the objective function value, task completion time, and flight range of all UCAVs between the two cases. It can be seen from Figure 3 that when task load of UCAVs is unlimited, the final objective function value is superior to that of another one; it is because the feasible solution space of the former case is larger, and it is more likely to find out a better feasible solution, while the convergence rate is slower. From Figures 4 and 5, we can draw the conclusion that the task completion time of the case with unlimited task load is much shorter, while the flight range is longer. This is because, with limited task load, the task allocation is unbalanced, tasks are mainly executed by U
6, and the task completion time is relatively long.Figure 3
Comparison figure on objective function value.Figure 4
Comparison figure on task completion time.Figure 5
Comparison figure on flight range of all UCAVs.


### 4.3. Timeliness Analysis

Select the general situation that task load is limited (task load vector isT
L
=
[
4,5
,
4,3
,
4,3
]), set the simulation time to be 50 s, and take an average for the data to compare IMGACA with GA by running 10 times, respectively.From Table4, we can see that when simulation time is 50 s, IMGACA can iterate for 230.2 times on average, while GA is 842.3 times; this is due to GA’s algorithm design which is simple, so it can iterate for more times in unit time, because IMGACA adopts better strategy to carry out state transition, while GA adopts random generation method, so the initial value of IMGACA is superior to that of GA. When it comes to the final objective function value, IMGACA can reach 492.61 and GA is 426.28, so, at the same time constraint, IMGACA outperforms GA with better find-best ability and efficiency.Table 4
Comparison result between IMGACA and GA in 50 s.
Iterations
Initial value
Final value
IMGACA
230.2
445.42
492.61
GA
842.3
317.58
426.28


### 4.4. Stability Analysis

According to Theorem5, mathematical complexity of the model is high, so IMGACA and GA are difficult to converge to the global optimal solution. To prove the stability of IMGACA, we design two cases to illustrate: (i) in small problem scale, IMGACA can converge rapidly to a fixed value (it is very likely to be global optimal solution); (ii) in large problem scale, the variance of all final objective function values of IMGACA is small.As shown in Figure6, the convergence process is in small problem scale for 10 times. From Figure 6, it can be seen that in small problem scale, for example, 3 UCAVs, 8 tasks (select U
1
–
U
3, T
1
–
T
8 in Tables 1 and 2), IMGACA can always converge to 188.74, and we can draw a conclusion that IMGACA has excellent convergence ability.Figure 6
Convergence process in small problem scale.However, in large problem scale, we use the simulation scenario in Section4.3 (6 UCAVs, 18 tasks). After calculation, the variance of 10 final objective function values of IMGACA is 17.56, and that of GA is 135.40. Hence, compared to GA, IMGACA exhibits more stability in convergence.


## 4.1. Parameter Setting

For purpose of verifying the superiority of the model and IMGACA, we run the IMGACA on a PC with Pentium (R) Dual-Core CPU E6600 3.06 GHz, and it is based on MATLAB R2010a software environment. Parameter setting in the IMGACA is listed as follows: t
e
x
p
=
10, α
=
3, β
=
8, λ
=
0.85, m
=
50, q
0
=
0.75, Q
=
3, ρ
g
l
o
=
0.05, and ρ
l
o
c
=
0.02.Table1 lists the task information including location and value.Table 1
Task information.
Task
L
T
V
T
T
1
(568, 508)
22.3
T
2
(259, 113)
32.6
T
3
(307, 365)
54.2
T
4
(467, 621)
34.6
T
5
(134, 311)
35.4
T
6
(514, 236)
33.1
T
7
(384, 469)
32.6
T
8
(156, 543)
43.4
T
9
(469, 182)
31.9
T
10
(281, 503)
44.1
T
11
(456, 247)
62.5
T
12
(89, 254)
33.6
T
13
(313, 256)
32.9
T
14
(617, 92)
23.2
T
15
(418, 507)
44.3
T
16
(383, 116)
23.0
T
17
(164, 229)
67.4
T
18
(605, 539)
33.4Table2 lists the UCAV information including location, value, velocity, and value of ammunition loaded on UCAVs.Table 2
UCAV information.
UCAV
L
U
V
U
V
e
l
V
A
U
1
(156, 443)
4.5
200
1.4
U
2
(195, 487)
6.0
150
2.3
U
3
(312, 584)
5.5
250
1.6
U
4
(237, 285)
3.0
250
1.6
U
5
(565, 591)
3.5
200
2.5
U
6
(652, 368)
5.0
300
2.3


## 4.2. Feasibility Analysis

Set the number of UCAVs as 6 and that of tasks as 18; besides, the matrices representing the kill probability of UCAVs to tasks and the damage probability of tasks to UCAVs areA
T and D
A; they are, respectively, set to be as follows.We make a comparative simulation between simulation scenarios with limited (task load vector isT
L
=
2,2
,
2,2
,
2,8) or unlimited task load for all UCAVs; the iteration number is 600, and, as shown in Table 3, is the simulation results in the two cases.Table 3
Task allocation plan with limited or unlimited task load.
UCAV
Flight range
Attack benefit
Attack cost
Allocation plan
Limited
U
1
380.47
61.10
3.96
T
10
→
T
5
U
2
573.81
64.85
3.61
T
18
→
T
4
U
3
182.01
65.78
5.64
T
15
→
T
7
U
4
498.24
68.71
3.99
T
9
→
T
3
U
5
504.14
78.20
5.33
T
11
→
T
13
U
6
2433.92
246.59
21.56
T
17
→
T
12
→
T
8
→
T
6
→
T
16
→
T
2
→
T
14
→
T
1
Unlimited
U
1
927.81
82.11
7.96
T
5
→
T
16
→
T
18
U
2
755.31
93.52
4.95
T
17
→
T
4
U
3
500.71
62.54
5.42
T
7
→
T
12
U
4
839.52
132.23
7.74
T
3
→
T
8
→
T
13
→
T
9
U
5
1020.19
144.63
9.13
T
10
→
T
11
→
T
15
→
T
1
U
6
726.63
78.54
6.70
T
6
→
T
14
→
T
2It is observed that when task load of UCAVs is limited, the task allocation solution is not an optimal one, and when task load of UCAVs is unlimited, the task allocation solution is more balanced and better feasible one.(20)
A
T
=
0.4
0.1
0.7
0.5
0.6
0.8
0.1
0.3
0.9
0.4
0.9
0.7
0.8
0.1
0.7
0.5
0.8
0.3
0.3
0.2
0.5
0.5
0.8
0.4
0.4
0.1
0.8
0.6
0.2
0.2
0.8
0.6
0.9
0.3
0.1
0.5
0.1
0.1
0.9
0.2
0.7
0.6
0.5
0.6
0.3
0.8
0.2
0.6
D
A
=
0.3
0.1
0.5
0.4
0.4
0.5
0.1
0.4
0.2
0.2
0.5
0.3
0.3
0.5
0.2
0.4
0.1
0.3
0.3
0.2
0.4
0.5
0.4
0.3
0.3
0.2
0.1
0.4
0.1
0.5
0.1
0.5
0.3
0.3
0.1
0.2
0.2
0.1
0.4
0.4
0.5
0.1
0.3
0.4
0.2
0.5
0.1
0.3
.Figures3–5 give, respectively, comparison results of the objective function value, task completion time, and flight range of all UCAVs between the two cases. It can be seen from Figure 3 that when task load of UCAVs is unlimited, the final objective function value is superior to that of another one; it is because the feasible solution space of the former case is larger, and it is more likely to find out a better feasible solution, while the convergence rate is slower. From Figures 4 and 5, we can draw the conclusion that the task completion time of the case with unlimited task load is much shorter, while the flight range is longer. This is because, with limited task load, the task allocation is unbalanced, tasks are mainly executed by U
6, and the task completion time is relatively long.Figure 3
Comparison figure on objective function value.Figure 4
Comparison figure on task completion time.Figure 5
Comparison figure on flight range of all UCAVs.


## 4.3. Timeliness Analysis

Select the general situation that task load is limited (task load vector isT
L
=
[
4,5
,
4,3
,
4,3
]), set the simulation time to be 50 s, and take an average for the data to compare IMGACA with GA by running 10 times, respectively.From Table4, we can see that when simulation time is 50 s, IMGACA can iterate for 230.2 times on average, while GA is 842.3 times; this is due to GA’s algorithm design which is simple, so it can iterate for more times in unit time, because IMGACA adopts better strategy to carry out state transition, while GA adopts random generation method, so the initial value of IMGACA is superior to that of GA. When it comes to the final objective function value, IMGACA can reach 492.61 and GA is 426.28, so, at the same time constraint, IMGACA outperforms GA with better find-best ability and efficiency.Table 4
Comparison result between IMGACA and GA in 50 s.
Iterations
Initial value
Final value
IMGACA
230.2
445.42
492.61
GA
842.3
317.58
426.28


## 4.4. Stability Analysis

According to Theorem5, mathematical complexity of the model is high, so IMGACA and GA are difficult to converge to the global optimal solution. To prove the stability of IMGACA, we design two cases to illustrate: (i) in small problem scale, IMGACA can converge rapidly to a fixed value (it is very likely to be global optimal solution); (ii) in large problem scale, the variance of all final objective function values of IMGACA is small.As shown in Figure6, the convergence process is in small problem scale for 10 times. From Figure 6, it can be seen that in small problem scale, for example, 3 UCAVs, 8 tasks (select U
1
–
U
3, T
1
–
T
8 in Tables 1 and 2), IMGACA can always converge to 188.74, and we can draw a conclusion that IMGACA has excellent convergence ability.Figure 6
Convergence process in small problem scale.However, in large problem scale, we use the simulation scenario in Section4.3 (6 UCAVs, 18 tasks). After calculation, the variance of 10 final objective function values of IMGACA is 17.56, and that of GA is 135.40. Hence, compared to GA, IMGACA exhibits more stability in convergence.


## 5. Conclusions

Aiming at the UCAV cooperative task allocation problem under MCAV’s limited control, we establish the task allocation model considering attack benefit, attack cost, and task completion time comprehensively and propose a novel algorithm called IMGACA to solve the model. The simulations reveal that IMGACA performs quite well in some aspects such as feasibility, timeliness, and stability.The future work is to study the dynamic adjustment problem of task allocation plan existing parameter and event uncertainties.



---

*Source: 6051046-2016-12-28.xml*