Page 51 - Innovations in Intelligent Machines

40 P.B. Sujit et al.
carry out several tasks in relation to the targets or other entities of interest
present in the region [1, 2]. An efficient task allocation method is necessary
to assign UAVs to targets.
The classical solution for such task allocation problems is a centralized one
that generates the necessary commands for the UAVs. But, centralized task
allocation systems have well known limitations and do not address scalabil-
ity issues too well. Hence, there is a necessity to develop decentralized task
allocation algorithms. These algorithms must be suitable for implementation
in a multiple agent UAV swarm, should be scalable, and also have low com-
putational overheads. An efficient task allocation strategy should have the
ultimate objective to complete the mission in minimum time by cooperating
and coordinating with other UAVs. Cooperation can be achieved by explicit
or implicit communication with neighbouring UAVs.
In this chapter, we will present decentralized and distributed task allo-
cation schemes based on concepts from team theory, game theory, and from
negotiation techniques used in decision-making problems arising in economics,
and apply these to design intelligent decision-making strategies for multiple
UAV systems performing a wide area search and surveillance mission [3]-[8].
In this context, we will explore the role that communication between UAVs
plays during decision-making.
The overall problem of task allocation is modelled as a sequence of tasks
that the UAVs need to carry out on a target. The allocation of tasks will
depend on various factors such as the proximity of the UAV to the target, its
perception of the target status, its capability to carry out the task at hand,
the choice that it may have in carrying out a given task or obtain greater
benefit by performing some other tasks, where the choice can be between
some alternate targets or tasks, and so on. All this needs to be carried out in
a decentralized and distributed manner.
In team theoretical task allocation, each UAV takes decision autonomously.
The UAV senses the status of the target and evaluates the expected benefit of
attacking the target. The UAV also senses the presence of other UAVs within
its sensor radius, and estimates the probability of the neighbouring UAVs
attacking the target. Based on these values (expected benefit of attacking a
target and the probability of the other UAVs attacking the same target), a
linear programming problem is formulated. The UAV decides on a task/target
assignment based on the solution provided by this formulation, which is proven
to be team optimal. An important feature of the decision-making process is
that, there is no explicit communication between UAVs. This formulation
is especially useful in a hostile environment where communication between
UAVs is either minimal or just not possible.
In negotiation based task allocation we restore the communication among
UAVs for decision making. Each UAV broadcasts its intentions to attack a
target, along with its perceived benefit in doing so, to its neighbours. A UAV
evaluates all the proposals that it receives. The evaluation is carried out by
comparing the benefits proposed by other UAVs in attacking the same target.