Page 67 - Innovations in Intelligent Machines

56 P.B. Sujit et al.
agent A k which has the highest b i (T j )and reject decisions to the remaining
agents. An agent A i can receive a mix of accept and reject decisions from
its neighbors. If we allow the agent to attack a target T k , since it has got
acceptance from some of the agents, this assignment would cause ineffective
performance as multiple agents will get assigned to the same target. Hence,
Rule 4 guards against agents getting multiple assignment. Rules 1-4 are the
key to the negotiation scheme. While implementing Rule 3, we may encounter
situations where more than one agent has the same b i (T j ), in which case we
use a deadlock resolution scheme that resolves such deadlocks.
Computing route decision (NC4): Agent A i decides whether to implement or
discard its proposed task based on the accept or reject decisions received from
its neighbors. The agent implements its proposal if it receives accept decisions
from all its neighbors and discards it if the agent receives a reject from even
one of its neighbors. An agent that received a reject for its proposal from at
least one neighbor will go on to the next negotiation cycle and this process
will continue till it receives all accept decisions. An agent that has arrived at a
decision (after receiving accept from all its neighbors) will not send any more
proposals during subsequent negotiation cycles. The sequence of negotiation
cycles will terminate automatically when all the agents have converged to a
decision. Later we will prove that only a finite number of negotiation cycles
are necessary. When an agent A i receives reject for all its proposals, it adopts
the search task.

Additional Target Information Exchange
An agent that has received acceptance to its proposal may have other tar-
gets within its sensor range. An agent A i can send this information to its
neighbouring agents who can use it. The information that an agents sends is
the target location and its value as perceived by A i . This information will be
more useful for those agents that may not have decided any targets but are
neighbours of A i . The target information broadcast by A i can also be useful
if all the proposals of agent A j ∈N(A i ) are rejected.
Once an agent receives the available targets from agent A i , it can make
assignment to any of the targets based on random number generation, greedy
strategy, or start a negotiation with its neighbouring agents for obtaining an
assignment. Here, we use greedy strategy for simplicity.

Deadlock Resolution Mechanism

We define a deadlock, when an agent A i is unable to decide to whom it has
to send an acceptance. This situation can happen when more than one agent,
with the same b i (T j ) value, seeks target T j to attack. Since the b i (T j ) values
are same, use of Rule 2 is not possible and agent A i cannot send acceptance