Information Technology Reference
In-Depth Information
one agent, its assignment is canceled making it unassigned and eligible for bidding
in the ongoing round unless if it has already come to its target position
q
θ
a
;inthat
case, the agent on the target position remains assigned to the target while other
agents within the connected component update the value of the target
θ
a
and cancel
the assignment to the same.
•
All the agents scan the environment for closer targets than their assigned ones;
if one is found, they break the assignment with their assigned target and become
eligible for biding in the ongoing round.
•
If agent
a
is unassigned, it finds its best target, calculates the bid value and bids for
that target using the following bidding and assignment procedure.
4.1
Bidding
To submit a bid, each agent
a
unassigned in its partial assignment
S
a
(
t, h
):
•
finds target
θ
a
which offers the best possible value
θ
a
=argmin
θ
∈
Θ
{c
aθ
(
t
)
−
v
θa
(
t, h
)
}
, and calculates bid for target
θ
a
as follows:
b
aθ
a
(
t, h
)=
v
θ
a
a
(
t, h
)+
u
a
(
t, h
)
−w
a
(
t, h
)+
=
c
aθ
a
(
t
)
−w
a
(
t, h
)+
,where
u
a
(
t, h
)=min
θ
∈
Θ
{c
aθ
(
t
)
−
v
θa
(
t, h
)
}
and
w
a
(
t, h
)=min
k
=
θ
a
∈
Θ
{c
ak
(
t
)
−v
ka
(
t, h
)
}
is the second best utility
that is, the best value over targets other than
θ
a
.
raises the value of its preferred target by the bidding increment
γ
a
so that it is indif-
ferent between
θ
a
and the second best target, that is, it sets
v
θa
(
t, h
) to
v
θa
(
t, h
)+
γ
a
(
t, h
),where
γ
a
(
t, h
)=
u
θa
(
t, h
)
− w
a
(
t, h
)+
.
The bidding phase is over when all the unassigned agents calculate their bid.
•
4.2
Assignment
Let
P
(
θ
a
)(
t, h
)
⊆ C
a
(
t
) be the set of agents with bids pending for target
θ
a
.Only
one agent
a
coord
∈ P
(
θ
a
)(
t, h
) is responsible for the assignment of target
θ
a
and if
there is more than one agent in
P
(
θ
a
)(
t, h
), the first one in the lexicographic ordering
coordinates the auction for that target.
Each agent
a
=
a
coord
∈ P
(
θ
a
)(
t, h
), broadcasts its bid
b
aθ
a
(
t, h
). Agent
a
coord
receives the bids
b
kθ
a
(
t, h
) of all other agents
k ∈ P
(
θ
a
)(
t, h
),
k
=
a
coord
, regarding
θ
a
. Following steps are performed to resolve the assignment:
•
Agent
a
coord
selects agent
a
θ
a
=argmax
a
∈
P
(
θ
a
)(
t,h
)
b
aθ
a
with the highest bid
b
aθ
a
max
=max
a
∈
P
(
θ
)(
t,h
)
b
aθ
a
.
•
If
b
aθ
a
max
≥ v
θ
a
a
(
t, h
)+
then
v
θ
a
a
(
t, h
):=
b
aθ
a
max
, the updated assignment
information is broadcasted to all the agents
k
=
a
coord
∈ C
a
(
t
) which update their
sets of assignments
S
a
(
t
) by replacing the current agent assigned to it (if any), with
agent
a
θ
a
.
•
If
b
aθ
a
max
<v
θ
a
a
(
t, h
)+
then all bids for target
θ
a
are cleared, no reassignment
or target value change is made.
If there are any unassigned agents left within
C
a
(
t
), the assignment algorithm starts
again from the bidding phase within iteration
h
+1. This process terminates when each
agent
a ∈ A
has a target assignment.
