Information Technology Reference
In-Depth Information
W.l.o.g., and for simplicity, we model the agents as points in plane which move on
a straight line towards their assigned targets. Experiments were performed for up to
60 agents (30 agents in each group) in [0
,
50]
2
⊂
R
2
where the initial robot agent
positions were generated uniformly randomly. The value of communication range
ρ
is set from 0 to 25; furthermore, maximum step size
d
max
varies from 1 to 40 since
above the latter values, the number of exchanged messages, crossed distance, and the
number of algorithm runs remain unchanged due to high probability of communication
graph connectedness.
For each group's number of robots
n
varying from 1 to 30,
Fig. 1.
Medium total distance crossed by
60
agents in
[0
,
50]
2
environment in respect to commu-
nication range
ρ
and maximum step size
d
max
equal for both groups: left, for all, partial, and no
information exchange (greedy), right: for target only vs. greedy no information exchange
we considered 10 different instances. We assume maximum distances crossed in each
time period to be equal for the two groups, that is,
d
[
a
max
=
d
[
θ
max
=
d
max
;thesame
assumption applies to the communication range of the two groups, i.e.,
ρ
a
=
ρ
θ
=
ρ
,
∀a ∈ A
and
∀θ ∈ Θ
. The average assignment solution (over 10 instances) for the
problem with 60, (30 + 30) agents is presented in Figure 1. The latter represents the
dynamics of the total distance crossed by all the agents in respect to varying maximum
step size
d
max
and the communication range
ρ
when the multi-agent system used one
of the four information exchange policies.
Figures 2 and 3 present the medium total number of runs of the algorithms with
the applied policies of the information exchange and a medium number of messages
exchanged during the total running time of the algorithm.
As can be visible from the Figures, the presented auction algorithm with included
mobility is stable, i.e., it always produces a feasible allocation solution. The experi-
ments show that the average total crossed distance for all the 3 cases with informa-
tion exchange give the same optimal solution as Bertsekas' algorithm in the case of
connected communication graph among all the agents. All and partial information ex-
change result in very similar average total distance, the former having slightly superior
