Information Technology Reference
In-Depth Information
any node
v
to the homebase
r
. For such a stored path
P
,Start(
P
) refers to the node
v
. For any path
P
=(
u
0
,
u
1
,...
u
t
)
in the tree
T
, the label sequence of path
P
is
Λ
(
. Other than the tree
T
, the algorithm also main-
tains the cross-edges which together with
T
, give the complete map of
G
.
P
)=(
δ
(
u
0
,
u
1
)
,...
δ
(
u
k
−
1
,
u
t
))
Algorithm 3:
BFS-Tree-Construction
Map
:=
T
:=
{
r
}
;
Add
r
to Queue;
ROOT_PATHS :=
;
while
Queue is not empty
do
Get next node
v
from Queue and go to
v
using
Map
;
while
node v has unexplored edges
do
Traverse the next unexplored edge
e
{
φ
}
=(
v
,
u
)
;
for
each path P
ROOT_PATHS
do
Apply sequence
∈
at node
u
;
if
successfully reached a marked node
then
Add to
Map
a cross-edge from
v
to Start(
P
);
Update the number of explored edges at the node Start(
P
);
Return to node
v
using
T
and exit Loop;
Λ
(
P
)
else
Backtrack to node
u
;
if
All path sequences failed to reach a marked node
then
Add a new node
u
to
T
and
Map
;
Add edge
to
T
and
Map
;
Insert
u
to Queue ;
ROOT_PATHS := ROOT_PATHS
(
v
,
u
)
∪
Path
T
(
u
,
r
)
;
Backtrack to node
v
;
When two identical agents execute the Algorithm
3
from marked homebases, it
is clear that the agents will not have a map of the complete graph. However, the
following properties are satisfied.
Lemma 2 ([
8
]).
During algorithm BFS-Tree-Construction: (i) The graph T con-
structed by each agent will be an acyclic connected subgraph of G, and (ii) if the
maps constructed by the two agents are identical then the views from the two home-
bases are identical.
The tree constructed by an agent in the above algorithm, is similar to the terri-
tory of an agent as in Sect.
12.6
. Due to the above properties, we know that when
the maps obtained by the two agents are identical, then rendezvous is not solvable
deterministically. So, we only need to consider the case when the maps are distinct.
In this case if we could compare the maps of the agents, we can elect one of the
agents and the agents could rendezvous at the homebase of the elected agent. This
algorithm (called Algorithm RDVwithToken) was presented in [
8
] and we have the
following result.
Search WWH ::
Custom Search