Page 58 - Innovations in Intelligent Machines

Team, Game, and Negotiation based UAV Task Allocation 47
The objective is to maximize the expected payoff E(ω) with the constraints
defined in Section 3.1, thus each UAV solves the following linear programming
problem:

max E( c ij x ij ) (15)
x
ij
i =1,...,n i ; j =1,...,m i ,m i +1, (m i +1)+1,..., (m i +1)+(n i − 1)

subject to

i
ˆ
x ij =1, ∀i; x ij ≤ 1∀j; x ˆ =0, ∀i, and j ∈ T ; x ij ∈ [0, 1], ∀i, j
i,j v
j i
where j = m i + 1 is a search task, j =(m i +1)+1,..., (m i +1)+(n i − 1)
represent the virtual targets.

3.4 Simulation Results

We demonstrate the effectiveness of using team theory for a multi-UAV task
allocation problem using a simulation environment. Consider a geographical
search space of 100×100 with 20 targets present in the geographical region, as
shown in Figure 2(a). The search and attack operation is carried out for 200
time steps, which also represents the flight time of the UAVs. The sensor range
of each UAV is 20. The location of the targets are not known a priori to the
UAVs. All the targets in the search space have the same target value for these
set of simulations, however, in general, the target may have different target
values depending on their threat levels. The targets are located randomly in
the search space. We use 7 UAVs for the mission. The UAVs perform search,
attack and speculative tasks on the target. We compare the results when UAVs
use team theory based decision making with other types of task allocations,
namely, greedy allocation, and limited sensor range with full communication.

Greedy Allocation

In this allocation scheme, each UAV decides to move to a target that would
give maximum benefit. Since the value of the targets are random variables, we
consider the expected value of the target to calculate the benefit C ij . Hence,
the i th UAV’s decision is given by:

max C ij = max[E(V j )w r − S ij ] (16)
j j