Page 63 - Innovations in Intelligent Machines

52 P.B. Sujit et al.
on auctions [20]. But in the application under consideration since the system
of UAVs is decentralized, each agent would become an auctioneer and hence
both the agents would auction the same target.
Consider Case B in Figure 3, where A 1 has T 1 and T 2 in its sensor range
while A 2 has only T 2 . The auction mechanism requires broadcast of all the
target and their associated costs. Resolving conflicts using auctions is a diffi-
cult task. In Case C, we can see that A 1 sees T 1 while A 3 is already on its way
to attack T 1 .So, A 1 wastes some resource in moving towards a target that is
already assigned, Since the communication is limited it does not have access
to the assignment of other agents. Instead of T 1 it could have attacked T 2 .
Here too greedy and auction algorithm would not yield good performance. In
Case D, agent A 3 gets the auction information from A 1 and A 2 about T 1 ,now
A 3 does not know to which agent it has to send the bid. A modification to the
standard auction algorithm may eliminate some of the difficult issues, how-
ever this would complicate the decision-making rules for multiple agents using
auction mechanism locally. These complications in using auctions for limited
communication cases motivate us to use negotiation as a tool to handle these
situations efficiently. In Case A, A 1 and A 2 can negotiate on which agent
would be assigned to target T 1 . While in Case B, A 1 and A 2 can negotiate
such that one agent attacks T 1 and the other moves towards T 2 . In Case C,
A 2 can detect a conflict between A 1 and A 3 and send decisions such that A 1
or A 3 move towards T 1 . However, in Case D, A 3 actually negotiates between
A 1 and A 2 , which are not neighbours, and detects possible conflict and hence
provides an efficient task allocation decision.
However, the implementation of negotiation scheme involves designing of
negotiation rules over which the decision-making process takes place. In the
next section we describe the negotiation scheme employed for decision-making.
At every time step each agent has to perform a task. The task can be
(i) searching for a target or (ii) attacking a target. Each agent senses its
environment consisting of other agents and targets. An agents’ assignment for
a task depends on four different situations. These situations are dependent
on the availability of neighbouring agents and targets. The four situations, in
which agent A i has to perform a task and play a role in the decision making
process are:

1. No targets and no neighbours
Task: Search
Decision role: Continue to move in the same direction
2. No targets but has neighbours
Task: Perform search or attack. The target information may be provided
by the neighbouring agents.
Decision role: Acts as a negotiator for neighbouring agents
3. Targets are present but no neighbours
Task: Attack
Decision role: Select a target that yields maximum value