Page 55 - Innovations in Intelligent Machines

44 P.B. Sujit et al.
the sensor radius. It is assumed that UAVs know the position of both the
targets and other UAVs precisely but the strength of the targets are known
with certain probability which is a function of the distance between the UAV
and the target.
Let us assume that at time t s ,UAV i can see m i number of targets and
n i number of UAVs within its sensor range. It senses the value of the targets
with probability p(d ij ),j =1, ··· ,m i where d ij is the distance between the
i th UAV and the j th target. Based on these information, the i th UAV decides
its action, which can be attacking any one of the j targets or opting for search.
The decision taken by the i th UAV is given as x i =[x i1 ,x i2 ,...,x im i ,x i(m i +1) ]
where x ij ∈{0, 1} denotes whether the i th UAV will perform the task j or
not. Here, the task j = m i + 1 is the search task.
Let the benefit of performing the task x ij by the i th UAV be C ij .In
general, C ij is a function of the states of the environment, i.e. the current
position of the UAVs, the current position of the targets and the value of the
targets. We will model C ij in the next section. The payoff of the whole team
is then given as
n i m i +1

ω = C ij x ij (6)
i=1 j=1
The objective of the team is to maximise ω with respect to the action, x ij
taken by the UAVs at time t s . We assume that the overall mission of the UAVs
will be optimal if the decision taken at each time step is optimal. However,
there may be some constraints on the combined decision taken by the team
x =[x 1 ,x 2 , ··· ,x n ] due to practical limitations. At any given time, an UAV
can perform only one task, so
m i

(7)
x ij =1,i =1, 2, ··· ,n i
j=1
For the mission to be effective, it is necessary that only one UAV be assigned
to one target at a given time. However the number of targets present may be
more than the number of UAVs and so it may not be possible to assign UAVs
to all the targets. Thus, we have

n i

x ij ≤ 1,j =1, 2, ··· ,m i (8)
i=1
Hence, the optimization problem can be posed as maximize ω in (6) with
respect to x subjected to the constraints in (7)-(8) and x ij ∈{0, 1}, ∀i, j.
Here, both the objective function as well as the constraints are linear. Thus,
it can be solved using linear programming. However, linear programming give
solution in x ij ∈ [0, 1]. For this class of problem, it is easy to see that for