Information Technology Reference
In-Depth Information
, there are vertices
u
and
v
∈
u
)=
•
For every faulty edge
e
=(
u
,
v
)
V
2
with
μ
H
(
v
)=
−
u
)
,
(
u
,
v
)
v
,
μ
H
(
1 and arcs
(
u
,
u
)
,
(
v
,
and
(
v
)
∈A
with labels
(
δ
e
(
u
)
,
0
)
,
(
0
,
δ
e
(
u
))
,
(
δ
e
(
v
)
,
0
)
,and
(
0
,
δ
e
(
u
))
respectively;
Fig. 12.3
The extended-map of an environment containing faulty edges (marked in
dashed lines
)
and black-holes (colored
black
)
The
extended-map
can be thought of as a canonical representation of the envi-
ronment (see Fig.
12.3
). It can be shown that any execution of a deterministic algo-
rithm on the environment
(
G
,
λ
,Q,
p
,
δ
,
η
)
can be simulated on the extended-map
(
H
,
μ
H
)
. Based on this we have the following result from [
9
].
Theorem 10.
It is not possible to rendezvous k
−
τ
agents in an environment whose
extended-map is not symmetric-covering minimal.
In the following we will briefly discuss an algorithm that solves the rendezvous of
k
−
τ
agents in an environment that satisfies the conditions above. We present below
a lower bound on the moves complexity of any algorithm solving rendezvous of
k
−
τ
agents (see [
9
] for a proof).
Theorem 11.
For solving rendezvous of (k
−
τ
) agents in an environment
(
G
,
λ
,Q,
p
,
δ
,
η
)
without any knowledge other than the size of G, the agents need to make at
least
Ω
(
m
(
m
+
k
))
moves in total.
We can ensure that no more than one agent dies while traversing the same link,
using the
cautious walk
technique as in [
17
]. At each node, all the incident edges are
considered to be unexplored in the beginning. Whenever an agent
A
at a node
u
has
to traverse an unexplored edge
e
as “Being
Explored” and if it is able to reach the other end
v
successfully, it immediately
returns to node
u
and re-marks the link
=(
u
,
v
)
, agent
A
first marks link
δ
u
(
e
)
as “safe”. During the algorithm we
follow the rule that no agent ever traverses a link that is marked “Being Explored”.
This ensures no more than
δ
u
(
e
)
agents may die during the algorithm.
The algorithm is based on similar ideas as in Algorithm
2
. Recall that the algo-
rithm proceeded with each agent exploring a part of the graph and marking its terri-
tory, followed by comparison between the territories of agents over multiple rounds.
In the present algorithm, several improvisations are required to account for the fact
that some agents may die during the execution of the algorithm. First of all, rounds
τ
Search WWH ::
Custom Search