Information Technology Reference
In-Depth Information
In
step A.1
, we randomly generate a fairly large number of nodes. These are
candi-
date
X-nodes and the intention is that after the processing done in steps A.2, A.3, and
A.4, a small number of those nodes is selected for being used in algorithm PBA*. In
step A.2
, we map the nodes
x
generated in step A.1 onto points
π
of an N-dim
space. In our case, we use N=2. (This is because a 2-dim space is more convenient to
use for step A.3. In the future we plan to extend our work for N > 2). To project a
node
i
x
onto a point
π
r
and
in 2-dim space we use two randomly generated nodes
i
r
(other than the ones of set X of step A.1). Then
π
is calculated as
i
(
)
(
)
(
)
π
=
md
x
,
r
,
md
x
,
r
i
i
1
i
2
(
)
md x r
is the Manhattan distance between
x
and
r
(j=1, 2). In
step A.3
,
we form the D-graph of the set P calculated in step A.2. This graph is the Delaunay
triangulation DT(P) for the set of points P. The main property of DT(P) is that no
point in P is inside the circumcircle of any triangle of DT(P). Also, the DT(P) corre-
sponds to the dual graph of the Voronoi diagram for P. This latter property is our
main motive in calculating the DT(P). Without loss of generality, we assume that the
vertices of DT(P) correspond to the centers/generators of the Voronoi cells in the
Voronoi diagram that corresponds to DT(P). The property of interest from any Vo-
ronoi diagram is that all the points within a Voronoi cell are closer to the center of
that cell than to the center of any other cell, including the neighboring cells. There-
fore, by considering the Voronoi diagram of the DT(P) graph, we somewhat avoid
choosing as X-nodes nodes that are too close to each other. (Note, such X-nodes
would correspond to search spaces that possibly duplicate each other and thus waste
resources by exploring the same part of the global search space). Consequently, we
designate
as our X-nodes the generator nodes of the Voronoi cells that form a
shortest
path between S and G. In
step A.4
, we apply Dijkstra's shortest path algorithm on
graph DT(P) and calculate SP = [S-X1-X2- …-Xk-G], the shortest path connecting S
and G. Note, S and G of path SP of step A.4 are not the actual source and goal
nodes
but they are the 2-dim
points
(as calculated in step A.2) corresponding to the actual
source and goal nodes. Also, X1, …, Xk of step A.4 are 2-dim points corresponding
to certain candidate X-nodes generated during step A.1. For simplicity in notation we
use the same symbols to refer to the corresponding actual nodes S and G and the cor-
responding X-nodes of the 2-dim points X1, …, Xk. In
step A.5
, we designate as our
X-nodes the nodes that correspond to the points X1, …, Xk, and using those nodes we
execute algorithm PBA* between S and G.
,
where
i
j
3 Performance Evaluation
We implement A*, the traditional heuristic search algorithm, and two versions of
PBA*, PBA*-R and PBA*-VD. PBA*-R is PBA* with randomly generated X-nodes;
PBA*-VD is PBA* with Voronoi-Dijkstra designated X-nodes, per Algorithm A of
Section 2. We use the sliding tiles puzzle problem for our tests and run A*, PBA*-R,
and PBA*-VD for 17 puzzles (3 of the puzzles are 6x6, i.e., 35-puzzles, 4 are 5x5,
and 10 are 4x4 puzzles). We use the Manhattan distance as our heuristic function.
Algorithms PBA*-R and PBA*-VD complete their execution and find solutions for
Search WWH ::
Custom Search