Page 52 - Innovations in Intelligent Machines

Team, Game, and Negotiation based UAV Task Allocation 41
It is shown that negotiation based task allocation can efficiently allocate tasks
and targets to UAVs, and detect and resolve conflicts between neighbour-
ing UAVs. The decision-making mechanism has very low computational over-
heads, and is shown to be scalable to large number of UAVs and targets.
One of the major tasks that need to be carried out in such wide area oper-
ations is that of search and it has enough facets of its own to merit a separate
treatment. The search task is carried out to detect targets in an unknown
region. The problem associated with search is to develop coordination algo-
rithms for multiple UAVs to minimize search route duplication and maximize
the information collected during the operation. We show that intelligent distri-
buted algorithms, based on game theory, can be developed to perform such
search tasks.

2 Existing Literature

Task allocation of UAVs is an active research area for the past few years. When
a UAV detects a target, it broadcasts the information to all the other UAVs in
the search space. Since, the information is common to all the UAVs, each UAV
independently solves a task allocation algorithm and determines its task. The
various task allocation schemes developed by researchers are based on network
flow model [9] [10], mixed integer linear programming (MILP) [11], dynamic
programming [12] or genetic algorithm [13]. The task allocation can also have
additional objectives like minimize path lengths [14], or timing constraints
[10]. Turra et al. [15] present a task allocation algorithm for multiple UAVs
performing search, identification, attack, and verification tasks in an unknown
region for targets that move in real time. These authors also address the
problem of obstacle avoidance. Jin et al. [16] propose a probabilistic task
allocation scheme for the scenario presented in [9, 1].
Recently, market based approaches have shown a considerable increase in
performance for task allocation strategies to multiple agent applications. Dias
and Stenz [17, 18] introduce a novel approach for coordinating robots based on
the free market architecture in economics. The approach defines revenues and
cost functions across the possible plans for executing a specified task. The task
is accomplished by decomposing it into sub-tasks and allowing the robots to
bid and negotiate to carry out these sub-tasks. Gerkey and Mataric [19] use
an auction mechanism for multi-robot coordination while they analyze the
communication and computational complexity involved in multi-robot task
allocation in [20]. The authors categorize the task allocation methods based
on the capability of the robots and the kind of tasks involved. Mataric et al.
[21] develop various task allocation strategies and study their performance on
a multi robot application with sensor noise. Their simulation study is com-
pared with results obtained using experiments. Gurfil [22] also uses an auction
mechanism for task allocation among multiple UAVs performing search and
destroy mission. Lagoudakis et al. [23] use auction algorithm for assigning