Page 53 - Innovations in Intelligent Machines

42 P.B. Sujit et al.
unexplored tasks to group of mobile robots. The paper also provides some
theoretical bounds on the computational complexity of the proposed algo-
rithm. Sariel and Balch [24] present an auction scheme with various objectives.
The various objectives are based on traveling salesman problems.
In reality, the UAVs are subjected to limited communication constraint
which most of the researchers have not addressed. Hence, the algorithm devel-
oped either cannot adhere to the limitation imposed by UAVs, or they cannot
be easily extended. Hence, there is necessity to develop task allocation algo-
rithms that are distributed and can perform efficiently. In this chapter we pro-
pose team theory, game theory, and negotiation based task allocation schemes
that consider the communication constraint of the UAVs into account and
show that they perform better than various other strategies.

3 Task Allocation Using Team Theory

3.1 Basics of Team Theory

A team (as defined in [25]) is a group of individuals each of whom takes deci-
sion about something different but who receive a common reward as a joint
result of all those decisions. The individuals get information about the external
situation (state of the environment) through observations and communication
and so the information available to different individuals are different. They
take decision based on their respective information. The state of the environ-
ment is a random variable, the probability distribution of which is known a
priori to the individuals. Based on the state of the environment and the deci-
sion taken, the team incurs a common payoff. Team theory deals with finding
the best communication and the best decision rules, given the payoff function,
the probability distribution of the environment and the communication cost.
Let T = {1, 2,... ,N} denote a team of N individuals or decision makers
and S denote the set of alternative states of the environment. We consider
the set S to be discrete and finite, i.e., the possible configuration/state of the
environment is finite. The probability mass function defined on the set S is
given by γ(s).
When the state of the environment is s ∈ S, each decision maker receives
the signal y i (s) as information through the process of observation. Let Y i =
{y i } denote the set of alternative signals that the decision maker i can receive
as information. The function η i : S → Y i is called the information function of
the i th decision maker and so

y i = η i (s) (1)

The set of all information function η = {η 1 ,η 2 ,...,η N } is called the informa-
tion structure of the team.
Based on the information y i received by the i th team member, it takes
the decision x i .Let X i = {x i } be the set of alternative decisions that the i th