Page 62 - Innovations in Intelligent Machines

Team, Game, and Negotiation based UAV Task Allocation 51
possible. The task allocation problem can be solved by using either a central-
ized controller or a decentralized controller. In the former case each agent
communicates the information it has to the central controller that solves a
task allocation algorithm and assigns each agent to a particular task. How-
ever, implementing this task allocation strategy in real-time requires large
communication overheads and will not be scalable to large number of agents
and targets. Also, these strategies are not robust to failures. Hence, a decen-
tralized task allocation strategy, which avoids many of these problems, may be
more advantageous if implemented on a multi-agent system. One way of imple-
menting a decentralized task allocation strategy would be by making each
agent broadcast its information to all the other agents so that each agent has
the required information to solve the task allocation problem independently
and assign a task for itself. The implementation of this task allocation strat-
egy also requires large amount of communication among the agents. To reduce
this demand one can define a neighbourhood concept for each agent so that
an agent communicates its information only to those agents that are in its
neighbourhood. The neighbourhood can be range dependent, in which case it
is dynamic or pre-defined, in which case it is static or randomly selected. In
this work, we will assume only range dependent neighbourhood for agents.
The implementation of decentralized task allocation with finite communi-
cation range poses several challenging problems. For instance, consider Case
A in Figure 3 where agent A 1 and A 2 have target T 1 in their sensor range and
an allocation has to take place as to which agent should be assigned to the
target. The task allocation can be done using a greedy strategy, in which case
both the agents would move towards the same target which is not desirable.
Another task allocation mechanism used in multi-robot literature is based

T
1
T A 3
2 T
1
A
2
A A
1 2
A
1
Case A Case C

A 2
A 1
T 2
A 2
A
1
T A 3
1
Case B Case D
Fig. 3. Some scenarios for decision-making