Information Technology Reference
In-Depth Information
with the corresponding winning agent. This process is repeated with the objective
of eventually forming a single tree spanning the graph
G
so that all the agents gather
at the root of this spanning tree. We show that this is always possible whenever the
condition of Theorem
2
is satisfied.
Procedure DDFS:
An agent
A
starts from its homebase a depth-first search traver-
sal marking the nodes that it visits (unless they are already marked) and labeling
them with numbers 1
,
,
,...
etc. Each node marked by the agent and the edge used
to reach it are added to its tree. If the agent reaches an already marked node, it back-
tracks to the previous node and tries the other edges incident to the node. The agent
stops when there are no unexplored edges incident to the nodes of its tree. This tree
is the territory
T
A
of the agent.
Partial-view (PV):
Based on the territory of an agent, we define the
Partial-View
PV
A
of an agent
A
having territory
2
3
T
A
, as the finite rooted tree (see Fig.
12.2
), such
that: (i) The root corresponds to the homebase
v
0
of agent
A
. (ii) For every other
node
v
i
in
T
A
, there is a vertex
x
i
in
PV
A
. (iii) For each edge
(
v
i
,
v
j
)
in
T
A
,thereis
an edge
(
x
i
,
x
j
)
in
PV
A
. (iv) For each outgoing edge
e
=(
v
i
,
u
i
)
such that
v
i
∈ T
A
but
e
∈ T
A
,
PV
A
contains an extra vertex
y
i
(called an external vertex) and an edge
e
that joins
x
i
to it. (v) Each edge in
PV
A
is marked with two labels, which
are same as those of the corresponding edge in
G
. (vi) Each vertex
x
i
in
PV
A
is
labeled with
=(
x
i
,
y
i
)
,where
v
i
is the node in
G
corresponding to
x
i
. (vii)
Each vertex is also labeled with the numeric identifier assigned to the corresponding
node during procedure DDFS.
λ
(
v
i
)
and
χ
p
(
v
i
)
2
3
2
3
1
0
1
4
1
2
1
3
3
3
2
2
2
4
3
1
1
2
4
4
3
1
2
3
2
2
2
1
1
1
3
2
3
4
3
3
2
1
2
1
1
3
4
2
2
3
23
4
3
3
2
2
2
1
2
3
3
1
1
0
10
0
2
Fig. 12.2
Territories and Partial-Views: (
a
)Agraph
G
with ten nodes and two agents
A
and
B
(whose territories are marked by
bold
edges). (
b
)The
Partial-View PV
A
for agent
A
The algorithm proceeds by comparing the partial-views of neighboring agents
(we use a fixed ordering on the partial-views). We say that an agent
A
is a neighbor
to agent
B
, if there exists an edge
T
B
.
By this definition, an agent may be its own neighbor. The communication between
neighbors works as follows. To send any information
w
, the agent writes
w
on each
(
u
,
v
)
such that
u
∈
T
A
,
(
u
,
v
)
∈
T
A
and
v
∈
Search WWH ::
Custom Search