Page 68 - Innovations in Intelligent Machines

Team, Game, and Negotiation based UAV Task Allocation 57
to all the agents as that will violate Rule 3. There are two possible ways of
resolving deadlock: loss information and token algorithm.
Loss information: In this scheme, agent A i requests for more information from
i
agents in A(T ). This additional information will aid in effective decision-
k
making. The additional information that an agent requests is the value of
possible loss that each proposing agent suffers if it chooses the next best
action instead of the proposed action. Let the new benefit vector for agent A k
ˆ
be B k and the loss λ k be evaluated using (25) as,
ˆ ˆ
B k = {B k \ b i (C S K )}; λ k = max B k − max B k (25)

where, \ denotes set difference. When agent A i requests for loss information,
the loss λ k is sent to agent A i .Let Λ i represent the set of loss information
i
received from all the agents in A(T ). An accept is sent to an agent A j that
k
satisfies the condition in (26) and reject is sent to the remaining agents.
A j = arg max(Λ i ) (26)
i
Suppose there are multiple b i (T j )’s that are at the next highest level, then
the same procedure needs to be repeated. Using the loss information does
not guarantee that the deadlock will be resolved. This situation can arise
when multiple agents have the same loss value. In that case, we use a token
algorithm as given below.
Token Algorithm : Every agent A i carries a unique token number K i . When-
ever the above situation (of the loss being equal) occurs wherein the agent
is unable to decide to whom it has to send acceptance, the agent requests
i
for token number of the agents A k , A k ∈A(T ). Agent A i compares these
k
token numbers and chooses an agent A j with the least token number. The
ˆ
ˆ
token number of A j is increased by a number N, where N is an arbitrary
large number greater than N. This scheme ensures that an agent that has
been selected earlier in this situation, will not be selected again in a similar
situation if there is at least one other agent which has not been selected before.
Some Theoretical Results

Theorem 1. If more than one agent is proposing a target T j , then at least
one of the agents will receive all acceptances from its neighbors.

i
Proof. Let A(T ) be the set of agents proposing target T j as their proposal.
j
Then, by Rule 2, agent A i sends an accept decision to agent A j which has
the maximum b i (T j ). If there are multiple agents with same b i (T j ) then A i
invokes the deadlock resolution mechanism by which one agent would receive
an accept.