Page 60 - Innovations in Intelligent Machines

Team, Game, and Negotiation based UAV Task Allocation 49
subject to

x ij =1; x ij ≤ 1; x ij ∈ [0, 1], ∀i, j
j i
where i =1,...,N and j =1,...,t a , with t a representing all the targets
detected so far.
Figure 2(b) shows the performance curves for 7 UAVs performing search
and attack tasks on a 100 × 100 search space shown in Figure 2(a). For eval-
uation of the performance by each strategy we use the percentage values of
the target destroyed (T d ). For instance, at time step t i ,if,say, t c targets are
completely destroyed, t h targets are half destroyed, and t n targets are not
attacked, then

T d = t c +0.5t h +0t n (18)

The target value destroyed (T d ) provides an insight into how many targets
are half destroyed or fully destroyed in the search space. We can see that
as time passes the number of targets being destroyed increases and hence the
target value destroyed (T d ) also increases. The performance of greedy strategy
is found to be the worst compared to other two strategies. However, team
theoretic strategy performs the best in spite of there being no communication
between UAVs.
Figure 2(b) show the performance of a particular simulation. To obtain the
average performance of all the strategies, we carry out the simulation for 20
different random target maps for 200 time steps, each with the same UAV posi-
tions. During the search task, it is logical that, after some time, during which
search is carried out and if no targets are found, the UAV has to change its
direction, so that there is a better chance of finding a target. Hence, after every
10 steps of search task, the UAVs change their direction of search by a random
angle. Hence, the performance of the target destroyed sometimes depends on
the random change in search direction. Hence, to average out the randomness
of search we simulate search and attack operation over each target map three
times and consider the average performance. Figure 2(d) shows the average
performance of each strategy for 20 such randomly generated target maps.
From the figure we can see that initially all the strategies perform almost at
the same level but as time progresses, team theoretic strategy outperforms the
other strategies. This is a significant result since the team theoretic strategy
assumes no communication between UAVs and has limited sensor range. In
case of full communication, there is considerable communication cost and the
computational cost are also more, when compared to team theoretic strate-
gies, as the UAV has to consider all the other UAVs information about the
targets. The greedy strategy has a tendency to move in groups and thus not
effectively using the resources of having multiple UAVs for the mission. Team
theory perform better and is scalable to large scale systems as the information
sensing is local and consequently the computational effort is less.