Page 64 - Innovations in Intelligent Machines

Team, Game, and Negotiation based UAV Task Allocation 53
4. Target as well as neighbours are present
Task: Search or attack
Decision role: Negotiate with neighbours
Once an agent A i is present within a distance d from the target, we assume
that the agent can destroy the target effectively. An agent has to negotiate
with its neighbouring agents for an efficient task allocation. The agents are not
subjected to any turn radius constraints and hence can move in any direction.
The agents have to maximize the number of targets destroyed in the search
space by coordinating with its neighbouring agents through negotiation.

4.2 Decision-making

Negotiation as a Tool to Handle Uncertainty in Agent Actions

In general, negotiation refers to the communication process that facilitates
coordination and cooperation among a group of agents [27]. In multi-agent
systems, its aim is to resolve problems related to resource allocation and task
assignments between various agents in a decentralized setting.
Our approach is somewhat similar to Rubinstein’s model of strategic nego-
tiation [28] where agents make proposals that are either accepted or rejected
by other agents; and whether an agent implements its proposal or not depends
on what other agents do. However, our approach is different from Rubinstein’s
model on many counts due to the nature of the task allocation problem. Unlike
most negotiation models we do not have a situation where each proposal is
vetted by all the other agents. In fact, due to the connectivity restrictions, we
have a network of agents where an agent is not necessarily directly connected
to all other agents. So, each agents decision is based on the response of only
those agents that are connected to it. Moreover, unlike in Rubinstein’s model,
agents make simultaneous offers at pre-defined decision epochs and the actions
are accordingly distributed between agents. Another way in which our model
differs from Rubinstein’s model is that in a task allocation problem the need
for negotiation arises mainly because of lack of information about the action
of other agents. So, the whole process of negotiation is geared towards deter-
mining the action of an agent in a coordinated autonomous fashion without
assuming any kind of hierarchy or priority among agents.
A coordinated decision by an agent would be one that is not in conflict with
the decision of its neighbors. There is no conflict except that which arises due
to uncertainty of agent actions. For example, it occurs when more than one
agent is planning to attack the same target, thus decreasing the effectiveness
of the mission. Resolution of such conflicts can be effected either by

(i) Direct communication/negotiation as in the case when an Agent A i and
another agent A j are within communication range.
(ii) Indirect negotiation when an Agent A i and another agent A j ,A j ∈N(A i )
want to attack the same target T, and A i and A j are connected through