COMPARED to unmanned combat aerial vehicles (UCAVs) that perform solo missions,greater efficiency and operational capability can be realized from teams of UCAVs operating in a coordinated fashion^{[1, 2, 3, 4, 5]}. Designing UCAVs with intelligent and coordinated action capabilities to achieve an overall objective is a major part of multiple UCAVs control in a complicated and uncertain environment^{[6, 7, 8, 9, 10]}. Actually,a military air operation involving multiple UCAVs is a complex dynamic system with many interacting decision-making units which have even conflicting objectives. Modeling and control of such a system is an extremely challenging task,whose purpose is to seek a feasible and optimal scheme to assign the limited combat resource to specific units of the adversary while taking into account the adversary$'$s possible defense strategies^{[8, 11]}. The difficulty lies not only in that it is often very difficult to mathematically describe the underlying processes and objectives of the decision maker but also in that the fitness of one decision maker depends on both its own control input and the opponent$'$s strategies as well.

Dynamic game theory has received increasingly intensive attention as a promising technique for formulating action strategies for agents in such a complex situation,which involves competition against an adversary. The priority of game theory in solving control and decision-making problems with an adversary opponent has been shown in many studies^{[12, 13, 14, 15]}. A game theory approach was proposed for target tracking problems in sensor networks in ^[14],where the target is assumed to be an intelligent agent who is able to maximize filtering errors by escaping behavior. The pursuit-evasion game formulations were employed in ^[16] for the development of improved interceptor guidance laws. Cooperative game theory was used to ensure team cooperation by Semsar-Kazerooni et al.^[13],where a team of agents aimed to accomplish consensus over a common value for their output.

Although finding the Nash equilibrium in a two-player game may be easy since the zero-sum version can be solved in polynomial time by linear programming,this problem has been proved to be indeed PPAD-complete^{[17, 18]}. So the problem of computing Nash equilibria in games is computationally extremely difficult,if not impossible. Based on the analogy of the swarm of birds and the school of fish,Kennedy and Eberhart developed a powerful optimization method,particle swarm optimization (PSO)^{[19, 20]},addressing the social interaction,rather than purely individual cognitive abilities. As one of the most representative method aiming at producing computational intelligence by simulating the collective behavior in nature,PSO has been seen as an attractive optimization tool for the advantages of simple implementation procedure,good performance and fast convergence speed. However,it has been shown that this method is easily trapped into local optima when coping with complicated problems,and various tweaks and adjustments have been made to the basic algorithm over the past decade^{[20, 21, 22]}. To overcome the aforementioned problems,a hybrid predator-prey PSO (PP-PSO) was firstly proposed in ^[21] by introducing the predator-prey mechanism in the biological world to the optimization process.

Recently,bio-inspired computation in UCAVs have attracted much attention^{[23, 24, 25]}. However,the game theory and solutions to the problem of task assignment have been studied independently. The main contribution of this paper is the development of a game theoretic approach to dynamic UCAV air combat in a military operation based on the PP-PSO algorithm. The dynamic task assignment problem is handled from a game theoretic perspective,where the assignment scheme is obtained by solving the mixed Nash equilibrium using PP-PSO at each decision step.

The remainder of the paper is organized as follows: Section II describes the formulation of the problem,including the attrition model of a military air operation and its game theoretic representation. Subsequently,we propose a predator-prey PSO for the mixed Nash equilibrium computing of two-player,non-cooperative game in Section III. An example of an adversary scenario of UCAV combat involving two opposing sides is presented in Section IV to illustrate the effectiveness and adaption of the proposed methodology. Concluding remarks are offered in the last section.

There are two combat sides in the UCAV air combat model. Specifically,the attacking side is labeled as $Red$ and the defending force as $Blue$. Each side consists of different combat units,which are made up of different numbers of combat platforms armed with weapons. Each unit is fully described by its location, number of platforms and the average number of weapons per platform. Thus,the state of each unit at time k is defined as $\xi _{i}^{X}\left( k \right)=\left[x_{i}^{X}\left( k \right),y_{i}^{X}\left( k \right),p_{i}^{X}\left( k \right)w_{i}^{X}\left( k \right) \right]$,where $X$ denotes the $Red$ force or $Blue$ force,$\left[x_{i}^{X}\left( k \right),y_{i}^{X}\left( k \right) \right]$ represents the unit location,$p_{i}^{X}\left( k \right)$ corresponds to the number of platforms of the $i\text{th}$ unit at time $k$,and $w_{i}^{X}\left( k \right)$ to the number of weapons on each platform in the $i\text{th}$ unit of $X$. The number of platforms for the moving units changes according to the following attrition equations

The term in (1) represents the percentage of platforms in the $i\text{th}$ unit of $X$ force,which survive the transition from time $k$ to $k+1$. For each unit in force $X$,this percentage is dependent on the identities of the attacking and the attacked units determined by the choice of target control,and is expressed as

It is assumed in (2) that ${{N}_{d}}$ units of $Y$ fire at the $i\text{th}$ unit of $X$. The engagement factor $Q_{ij}^{XY}\left( k \right)$ of the $j\text{th}$ unit of $Y$ attacking the $i\text{th}$ unit of $X$ at time $k$ is computed from

where $\beta _{ij}^{XY}$ represents the probability that the $j\text{th}$ unit of $Y$ acquires the $i\text{th}$ unit of $X$ as a target,and is calculated by

The attrition factor $P_{ij}^{XY}\left( k \right)$ in (2) represents the probability of the platforms in the $i\text{th}$ unit of $X$ being destroyed by the salvo of $s_{j}^{Y}\left( k \right)$ fired from the $j\text{th}$ unit of $Y$ at time $k$,and is computed as follows

where the term $0\le {{\beta }_{w}}\le 1$ represents the weather impact which reduces the kill probability according to the weather condition,i.e.,1 corresponds to ideal weather condition while 0 corresponds to the worst weather condition. $PK_{ij}^{XY}$ is the probability of $i\text{th}$ unit of $X$ being completely destroyed by the $j\text{th}$ unit of $Y$ under ideal weather and terrain conditions.

In the equation mentioned above $s_{i}^{Y}$ is the average effective kill factor when the $j\text{th}$ unit of $X$ attacks the $i\text{th}$ unit of $Y$ with salvo $c_{i}^{Y}\left( k \right)$,and is calculated from

where $c_{i}^{Y}$ is the salvo size of $j\text{th}$ combat unit of $Y$ and $c$ is a constant referred to as Wes coefficient.

The control vector for each unit for both sides is chosen as

where $V_{{{x}_{i}}}^{X}\left( k \right)$ and $V_{{{y}_{i}}}^{X}\left( k \right)$ are respectively the relocating control corresponding to the $x$-coordinate and $y$-coordinate,$d_{{{x}_{i}}}^{X}\left( k \right)$ is the number of units that fire at $i\text{th}$ unit of $X$,and $c_{{{x}_{i}}}^{X}\left( k \right)$ is the salvo size control variable that decides how many weapons should fire. The number of weapons is updated according to

The state equations of each unit engaged in an air combat are defined as

The problem of dynamic task assignment in the air combat is modeled from a game theoretic perspective in this paper. Suppose $Red$ consists of ${NR}$ units (UCAVs) and it fires $CR$ missiles during each attack or defense. There are ${NB}$ units in the $Blue$ force,whose salvo size is also a constant $CB$. At each decision making step $k$,both sides decide on which units of its own side should be chosen to attack and which units of the opponent should be chosen as targets,with the purpose of maximizing its own objective function. Each combination of attacking and attacked units is seen as a pure strategy in the game. For each side,the number of pure strategies is calculated as

The payoff matrix for both sides is an ${{N}_{RS}}\times

Each entry $J_{i,j}^{R}\left( k \right)$ in $MR$ corresponds to the payoff of $Red$ when it takes the $i\text{th}$ pure strategy against the $j\text{th}$ pure strategy of $Blue$. For the attacking force of $Red$,the objective function $J_{i,j}^{R}\left( k \right)$ is calculated as

where $\varepsilon $ and $\tau $ are weight coefficients. The objection function for the defense of $Blue$ is calculated,by the same token,as

From a game theoretic point of view,the cooperative UCAV task assignment problem is for the tagged side,$Red$,to maximize its own payoff at each decision step,by calculating a mixed Nash equilibrium for the ${{N}_{RS}}\times {{N}_{BS}}$ matrix game.

In the $gbest$-model of PSO,each particle has information of its current position and velocity in the solution space^[21]. And it has the best solution found so far of itself as $pbest$ and the best solution of a whole swarm as $gbest$. The $gbest$-model can be expressed as

where ${{v}_{ij}}(k)$ and ${{x}_{ij}}(k)$ respectively denote the velocity and position of the $i\text{th}$ particle in the $j\text{th}$ dimension at step $k$,and ${{c}_{1}}$ and ${{c}_{2}}$ are weight coefficients,${{r}_{1}}$ and ${{r}_{2}}$ are random numbers between 0 and 1 to reflect the stochastic algorithm nature. The personal best position ${{p}_{i}}$ corresponds to the position in the search space where particle $i$ has the minimum fitness value. The global best position denoted by ${{g}_{i}}$ represents the position yielding the best fitness value among all the particles.

Unfortunately,the basic PSO algorithm is easy to fall into local optima. In this condition,the concept of predator-prey behavior is introduced into the basic PSO to improve the optima finding performance^{[26, 27, 28]}. This adjustment takes a cue from the behavior of schools of sardines and pods of killer whales. In this model,particles are divided into two categories,predator and prey. Predators show the behavior of chasing the center of preys$'$ swarm; they look like chasing preys. And preys escape from predators in the multidimensional solution space. After taking a tradeoff between predation risk and their energy, escaping particles would take different escaping behaviors. The velocities of the predator and the prey in the PP-PSO can be defined by

where $d$ and $r$ denote the predator and prey,respectively, ${{p}_{di}}$ is the best position of predators,${{p}_{ri}}$ is the best position of preys,$g$ is the best position which all the particles have ever found. And ${{\omega }_{d}}$ and ${{\omega }_{r}}$ are defined as

where ${{\omega }_{d}}$ and ${{\omega }_{r}}$ are the inertia weights of predators and preys,which regulate the trade-off between the global (wide-ranging) and local (nearby) exploration abilities of the swarm and are considered critical for the convergence behavior of PSO. $iteratio{{n}_{\max }}$ represents the maximum number of iterations and ${{\omega }_{\max }}$ and ${{\omega }_{\min }}$ denote the maximum and minimum value of ${{\omega }_{r}}$,respectively. And the definition of $I$ is given by the following expression

Then $I$ denotes the number of the $i\text{th}$ prey's nearest predator. In (18),$P$ is used to decide if the prey escapes or not ($P=0$ or $P=1$),and $a$ and $b$ are the parameters that determines the difficulty of the preys escaping from the predators. The closer the prey and the predator,the harder the prey escapes from the predator. Moreover,$a$ and $b$ are shown as

where ${{x}_{span}}$ is the span of the variable.

As a competitive (non-cooperative) strategy of multi-objective multi-criterion system first proposed by Nash^[29],Nash equilibrium is basically a local optimum: a strategy profile (${{s}_{1}},{{s}_{2}},\cdots ,{{s}_{n}}$) such that no player can benefit from switching to a different strategy if nobody else switches,$\forall i,\forall {{s}'_{i}}\in {{S}_{j}}$

where ${{U}_{{{P}_{j}}}}$ denotes the expected payment of person $j$,${{s}_{j}}$ and ${{S}_{j}}$ respectively denote the $i\text{th}$ strategy of player $j$ and the set of strategies. Note that every dominant strategy equilibrium is a Nash equilibrium,but not vice versa. Every game has one Nash equilibrium at least. In this paper,the expected payment is substituted by the objective function which is used to calculate the payoff matrixes denoted by $M{{A}_{m\times n}}$ and $M{{B}_{m\times n}}$. We define the vector of mixed strategies for both sides as ${{X}_{i}}=\left( {{x}_{i1}},\cdots,{{x}_{im}},{{y}_{i1}},\cdots,{{y}_{in}} \right)$,such that ${{x}_{ik}}\ge 0$,${{y}_{ik}}\ge 0$, $\sum\nolimits_{k=1}^{m}{{{x}_{ik}}}=1$, $\sum\nolimits_{k=1}^{n}{{{y}_{ik}}}=1$,where $m={{N}_{RS}}$ and $n={{N}_{BS}}$. So,for each mixed strategy ${{X}_{i}}$,the Nash equilibrium solution $\left( {{X}^{*}},{{Y}^{*}} \right)$ must satisfy the given conditions

For utilizing the proposed algorithm to compute Nash equilibrium here,we give the fitness functions as

In the last two expressions,${{X}_{di,1:m}}(k)$ means the mixed strategies which are produced by the $i\text{th}$ predator for the $A$ force and the $B$ force,respectively. Similarly, ${{X}_{ri,1:m}}(k)$ and ${{X}_{ri,m+1:m+n}}(k)$ denote the mixed strategies which are produced by the $i\text{th}$ prey for the $A$ and $B$ forces. Note that the proposed variables must satisfy the following conditions:

Importantly,the mixed Nash equilibrium corresponds to the minimum of the fitness function and the optimal or the sub-optimal solution will be the closest to zero. The detailed procedure of PP-PSO for the mixed Nash equilibrium computing is demonstrated in Fig. 1.

Fig. 1

	Download: JPG larger image
Fig.1. Procedure of Nash equilibrium computing based on the PP-PSO.

To validate the effectiveness of the proposed method,here we illustrated the Nash equilibrium computing both for zero-sum game and non-zero-sum game using two simple examples. For a fair comparison among these two method,they use the same maximum iteration number ${{N}_{\max }}=100$,the same population size $m=30$,and the same up and lower bounds for inertia weights ${{\omega }_{\max }}=0.9$,${{\omega }_{\min }}=0.2$. Besides,in our proposed PP-PSO,the numbers of predators and preys are set ${{m}_{d}}=10$,${{m}_{r}}=20$, respectively.

Example 1. Consider two-person,zero-sum game and non-zero-sum game illustrated by Tables I and II^[30].

Table I

Table I PAY-OFF MATRIX OF $A$ AND $B$ IN A TWO PLAYER, ZERO-SUM GAME I II III (I) (8,-8) (9,-9) (3,-3) (II) (2,-2) (5,-5) (6,-6) (III) (4,-4) (1,-1) (7,-7)

Table I PAY-OFF MATRIX OF $A$ AND $B$ IN A TWO PLAYER, ZERO-SUM GAME

Table II

Table II PAY-OFF MATRIX OF $A$ AND $B$ IN A TWO PLAYER, NON-ZERO-SUM GAME I II III IV I (1,1) (235,0) (0,235) (0.1,1.1) II (0,235) (1,1) (235,0) (0.1,1.1) III (235,0) (0,235) (1,1) (0.1,1.1) IV (1.1,0.1) (1.1,0.1) (1.1,0.1) (0,0)

Table II PAY-OFF MATRIX OF $A$ AND $B$ IN A TWO PLAYER, NON-ZERO-SUM GAME

As we can see from the above two tables,the first column and the first row represents the strategies of player $A$ and $B$, respectively. For example,in the zero-sum game,each player has three strategies,which are specified by the number of rows and the number of columns. The payoffs are provided in the interior. The first number is the payoff received by the column player; the second is the payoff for the row player. To reduce statistical errors,each algorithm is tested 100 times independently for these two games. Evolution curves for the two-player,zero sum game are depicted in Figs.2$\sim$4. Besides,the simulation results are illustrated from the perspective of average fitness value, best fitness value ever found (Tables III and IV),the minimum error and times that the results satisfied that $error\le 0.01$, where $error$ is defined as the following expressions:

Fig. 2

	Download: JPG larger image
Fig.2. Comparison results of average fitness values for the two player, zero-sum game.

Fig. 3

	Download: JPG larger image
Fig.3. Comparison results of average errors for the two player, zero-sum game.

Fig. 4

	Download: JPG larger image
Fig.4. Comparison results of global best solutions for the two player, zero-sum game.

Table III

Table III COMPARISON RESULTS FOR THE TWO PLAYER, ZERO-SUM GAME Average fitness Best fitness Minimum error Successful hits PP-PSO 0.2439 5.92E-4 0.0091 79 Basic PSO 0.3153 0.0074 0.0145 2

Table III COMPARISON RESULTS FOR THE TWO PLAYER, ZERO-SUM GAME

Table IV

Table IV COMPARISON RESULTS FOR THE TWO PLAYER, NON-ZERO-SUM GAME Average fitness Best fitness Minimum error Successful hits PP-PSO 0.1352 3.836E-13 0.0069 91 Basic PSO 0.6358 0.2897 0.0085 14

Table IV COMPARISON RESULTS FOR THE TWO PLAYER, NON-ZERO-SUM GAME

where ${{e}_{h}}(k)$ and ${{e}_{b}}(k)$ denote the error of the basic PSO and our proposed PP-PSO,$E\_S$ represents the mixed Nash equilibrium solution of the game that the players participate in. Note that for the zero-sum game shown in Table I,$E\_S=\left[ \frac{21}{52},\frac{12}{52},\frac{19}{52},\frac{2}{13},\frac{3}{13},\frac{8}{13} \right]$. And for the non-zero-sum game shown in Table II, $E\_S=\left[ \frac{1}{3},\frac{1}{3},\frac{1}{3},0,\frac{1}{3},\frac{1}{3},\frac{1}{3},0 \right]$.

It is reasonable to conclude from the simple example demonstrated above that the proposed PP-PSO outperforms the basic PSO in terms of solution accuracy,convergence speed,and reliability for Nash equilibrium computing. So it is appropriate to use this method to solve the problem of multiple UCAV air combat modeled by dynamic game theory in the following section.

To validate the effectiveness of the dynamic game theoretic formulation for UCAV air combat,a computational example is performed based on Matlab 2009b using our proposed PP-PSO. Consider an adversary scenario involving two opposing forces here. The attacking force is labeled as $Red$ team,while the defending force is labeled as $Blue$ team. The mission of the $Blue$ force is transporting military supplements from its base to the battlefront while the task of the $Red$ force is attacking and destroying the aerotransports of the $Blue$ force at least 80\,$\%$ and then returning to their air base.

As shown in Fig. 5,the $Blue$ force consists of one transportation unit,which is represented by the solid square,and two combat units. They are on the way back to the base after accomplishing a military mission. The $Red$ force consists of three combat units and aims to destroy the $Blue$ transportation unit. The $Red$ force is also programmed to return the base after the mission. For simplification of the problem,each unit of both sides is assumed to consist of the same type of UCAVs,and each UCAV is equipped with a certain number of air-to-air missiles. Assume that the speed of $Red$ force is nearly 0.25 km/s while the speed of $Blue$ force is nearly 0.2 km/s,and the state variables will be updated every 2 minutes. So the positions of the $Red$ force and the $Blue$ force will change 30 km and 24 km,respectively at each step. The configuration parameters used in the simulation for the $Red$ force and the $Blue$ force are listed in Table V and Table VI, respectively.

Fig. 5

	Download: JPG larger image
Fig.5. Scenario of cooperative UCAV task assignment.

Table V

Table V INITIAL CONFIGURATION OF $Red$ FORCE $\left( x_{i}^{A}(0),y_{i}^{A}(0) \right)$ $p_{i}^{A}(0)$ $w_{i}^{A}(0)$ $P{{K}_{a-bi}}$ ${{r}_{mA}}$ $UA{{V}_{1}}$ $\left( 200,300 \right)$ 10 4 0.6 $UA{{V}_{2}}$ $\left( 201,299 \right)$ 10 4 0.4 20km $UA{{V}_{3}}$ $\left( 202,298 \right)$ 10 4 0.4

Table V INITIAL CONFIGURATION OF $Red$ FORCE

Table VI

Table VI INITIAL CONFIGURATION OF $Blue$ FORCE $\left( x_{i}^{B}(0),y_{i}^{B}(0) \right)$ $p_{i}^{B}(0)$ $w_{i}^{B}(0)$ $P{{K}_{b-ai}}$ ${{r}_{mB}}$ $UA{{V}_{1}}$ (2,2)km 10 0 0 $UA{{V}_{2}}$ (3,2)km 7 3 0.7 20km $UA{{V}_{3}}$ (4,2)km 7 3 0.7

Table VI INITIAL CONFIGURATION OF $Blue$ FORCE

In the simulation,the objective functions of the two forces are chosen as

Fig. 6 presents the flying trajectories for both sides in the air military operations,which result from the proposed game theoretic formulation of task assignment in a dynamic combat environment and the PP-PSO based solution methodology. The $Red$ force starts from near its base and launches attacks to eliminate the $Blue$ transportation force,which is on the way returning to its base after a military mission. The task assignment scheme for both sides are calculated based on the proposed approach described above.

Fig. 6

	Download: JPG larger image
Fig.6. Resulting trajectories of both sides from the proposed approach.

The detailed evolution and convergence behavior with time of platform numbers in combating units are shown in Fig. 7. The combating units of both sides start to fight at the 9th time step. After 3 time steps of engagement,this air military operation ends up at the 11th time step, with $Red$ defeating the $Blue$ force and the surviving forces of both sides returning to their own bases. At the end of the combat,the $Red$ force manages to inflict more than 90%of the platforms in $Blue'$s transportation unit, 78% of platforms in B2,and 70% of platforms in B3. Meanwhile, the $Red$ team pays a price for the victory. The first unit R1 and the third one R3 suffer a slight damage and 30% platforms are destroyed in the attack. However, the second unit R2 of the $Red$ force suffer a serious damage,with more than 60% of the platforms being destroyed in the engagement with the $Blue$ force. The result can be explained from Fig. 8,where snapshots of the dynamic task assignment results at Steps 9,10,and 11 are given. It illustrates that the engagement of both sides has a different pattern at each time step and proves the task assignment process to be a dynamic process with time. At the 9th and 10th time steps,the second unit R2 of the $Red$ force takes actions in accordance with the resulting mixed Nash equilibrium and chooses the first and second units of $Blue$ force as targets, respectively. However,the $Blue$ force insists on attacking R2 by the first unit B1, which is the most powerful unit of its 10 combat platforms. Consequently,R2 suffers the most serious damage in the three units of $Red$.

Fig. 7

	Download: JPG larger image
Fig.7. Number of platforms.

Fig. 8

	Download: JPG larger image
Fig.8. Snapshots of dynamic task assignment results.

It is important to note that both the attacking side and the defense side take advantage of the proposed approach to acquire the assignment scheme over the engagement duration. Therefore,the engagement outcome mainly depends on the initial configuration of each force. The $Red$ force has an advantage in performances and numbers of weapons,which implies the possible result of $Blue'$s defeat. The experimental results are coincident with the theoretical analysis and verify the effectiveness and feasibility of the proposed approach.

This paper developed a game theoretic method for UCAV combat, which is based on the PP-PSO model. By considering both the adversary side and the attacking side as rational game participants,we represented the task allocation scheme as an optional policy set of both sides,and the cooperative task allocation results of both sides were achieved by solving the mixed Nash equilibrium using PP-PSO. An example of military operation involving an attacking side $Red$ and a defense side $Blue$ was presented to verify the effectiveness and adaptive ability of the proposed method. Simulation results show that the combination of game theoretic representation of the task assignment and the application of PP-PSO for the mixed Nash solutions can effectively solve the UCAV dynamic task assignment problem involving an adversary opponent.