Information Technology Reference
In-Depth Information
Fig. 2.
Medium total number of iterations of the algorithms with exchange of all of the informa-
tion vs. partial exchange of information , target only, and greedy for 60 agents
performance than the latter one. Moreover, it is visible from Figure 1 that the dynam-
ics of the assignment solution when the communication graph is connected with high
probability is better within the all and partial information exchange than the greedy
approach with no communication.
On the other hand, surprisingly, as the communication graph gets more and more
disconnected and the communication range decreases, the assignment solution of the
greedy policy approach becomes superior than the other information exchange policies
and the target-only policy has the worst assignment dynamics in respect to decreasing
communication range. This is explained through the fact that outdated past information
regarding the global assignment solution in dynamic and unpredictable environments is
not sufficient to compose locally a satisfactory assignment as is the case in the assign-
ment problem in [12] where agents move towards static targets and their assignment
information converges faster to feasible sub-optimal solutions with limited bounds in
respect to optimal solutions. However, in all of these cases, the solution in average de-
grades gracefully with the decrease of the communication range
ρ
and the maximum
step size
d
max
.
For the case of initial zero prices, the total number of iterations of one auction run
(one step) in which each target agent receives a bid from the agents of the opposite
group is no more than max
(
a,θ
)
|c
aθ
|/
. Once all objects receive at least one bid, one
auction step terminates and agents move one step towards their targets. In the worst
case, if all the agents of one group form a single connected component and if each
iteration of a single run involves one bid by a single person, the total number of itera-
tions is no more than
n ·
max
(
a,θ
)
|c
aθ
|/
and since each bid requires
O
(
n
) operations,
the running time of each algorithm step (moving one step towards assigned targets) is
O
(
n
2
max
i,j
|a
ij
|/
. The total running time of the allocation is
s · n ·
max
(
a,θ
)
|c
aθ
|/
,
where
s
is a number of steps from agents' initial to final target positions. For further
information regarding the general auction algorithm complexity, see, e.g., [2].
