Information Technology Reference
In-Depth Information
4.3
Agent Movement
When all agents are assigned to their respective targets in the final auction iteration, say
h
fin
(
t
), at round
t
of the iterative auction, the agent movement phase takes place:
•
if agent
a ∈ A
is not at its target position
p
θ
a
, it moves one step toward
θ
a
, covering
at most a maximum distance
d
[
a
max
.
•
Once when agent
a
comes to the position of its assigned and available target, it
sets its target value
v
θ
a
a
(
t, h
fin
(
t
)) to
−
inf, and broadcasts the latter to the inter-
ested agents in
C
a
(
t
) based on its information exchange policy; this will disable
(discourage) assigning the rest of interested agents to the same target.
If the initial targets' values
v
θ
(1
,
0) are identically zero, the
-CS condition (see, e.g.,
[2]) will be satisfied because the value of any assigned target is strictly increasing during
the auction process and must be at least
. To assure the convergence of the algorithm
and to exclude the possibility of multiple exchanges of agents on the target positions,
and therefore of infinite loops, the target value is modeled in the way that it decreases
infinitely when an agent arrives on its assigned available target position so that once
arrived, an agent remains on the same. Since there is a limited number of bids for any
target while there still exist targets that have not yet received any bids, the dynamic
auction algorithm will finish when all targets have been given at least one bid and the
last agent comes to its target.
The presented algorithm works also when the number of agents differs from the num-
ber of targets. In fact, if the number of targets is not less than the number of agents, the
assignment process terminates when each agent reaches its assigned target; otherwise,
the assignment process terminates when all the unassigned agents realize that all the
targets are occupied.
5
Simulation Setup and Results
We simulate a Multi-Agent (robot) System with the forward auction algorithm im-
plemented in MatLab. The dynamic modified auction algorithm is experimented with
4 different kinds of information exchange among agents within each
C
a
(
t
)
,
∀a ∈
A
, and, similarly for all
θ ∈ Θ
within their
C
θ
(
t
),for
t ∈{
1
,...,T}
,and
h ∈
{
0
,...,h
fin
(
t
)
}
. In each experiment, both groups of agents
A
and
Θ
apply within
their group one of the following information exchange policies:
•
exchange of all assignment data in
S
a
and target values
v
θ,a
(
t, h
) for targets
θ ∈ Θ
among all agents
a ∈ C
a
(
t
);
•
partial exchange of target values
v
θ
a
,a
(
t, h
) and assignments in
S
a
regarding only
the targets assigned to connected agents
a ∈ C
a
(
t
);
•
exchange only of the target value
v
θ
a
,a
(
t, h
) among the agents assigned to the same
target
θ
a
;
•
no information exchange at all. The result is a greedy algorithm where each agent
behaves in a selfish and greedy way.
