Voronoi-assisted Parallel Bidirectional Heuristic Search - Advances in Computational Science and Engineering - page 76

Fig. 4. Algorithm PBA* in a general case

In the case of search space management, the difficulty arises from the fact that
when N searches are concurrently in progress, it is very time consuming to have each
process test if one of its generated nodes is identical to some node generated by any
other process (note, in the 2-processor case, checking for common nodes is fairly
inexpensive, since there are only two searches in progress). As an attempt to ease this
task, multi-dimensional heuristics (MDH) were developed by [11, 12]. As part of the
MDH approach, additional nodes, called reference nodes, are designated into the
search space, in order to “guide” the search. Based on the reference nodes use in
MDH, several intersection detection algorithms have been devised [11, 10, and 12].
The algorithms' task is to prevent node exchange between any two processes, unless
there is a high probability that the search spaces of these processes intersect. Simula-
tion results have shown that in the worst case, unnecessary node exchange is cut down
in half, whereas in the best case it is cut down almost completely (only 1% of the
nodes are exchanged between two non-intersecting subspaces). Later in this paper we
outline some of the intersection detection algorithms since we use them in the imple-
mentation of our proposed method here.

2 Our Proposal

We present our method of how to select X-nodes which are located appropriately in
the state space. Algorithm A, below, describes the proposed method.

Algorithm A .
Step A.1 : generate a set

{ }

Xx x =

1 ,..., M

of candidate X-nodes.

{ }

P = ππ

1 ,...,

π

Step A.2 : convert set X into set such that is the projection of

M i

x onto a 2-dim space.
Step A.3 : Form D-graph, the Delaunay graph for set P.
Step A.4 : Calculate the shortest path SP = [S-X1-X2- …-Xk-G] connecting S and
G in the D-graph of step A.3.
Step A.5 : Select as X-nodes the nodes corresponding to points X1, X2, …, Xk and
execute algorithm PBA* between S and G.