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

all 17 puzzles. Due to memory space limitations, algorithm A* is not able to find a
solution for any of the 6x6 puzzles, and for 2 of the 5x5 puzzles. Although algorithms
PBA*-R and PBA*-VD are not admissible, they find near-optimal solutions. (In fact,
the average solution path length found by both versions of PBA* is near-equal to the
optimal path length, 45, as found by A*, which is an admissible algorithm.). For ei-
ther version of PBA*, an intersection detection algorithm , IDA-3, is used to control
search process communication. IDA-3 is originally described in [10] and it has been
used in several of our previous works (e.g., [7, 8, 14, 15, 16]). The main characteristic
of IDA-3 is that it instructs two opposite-direction search processes to exchange
nodes (and, henceforth, compare those nodes) if such nodes are deemed to be “similar
enough” so that they are possibly identical. Since algorithm IDA-3 is central in our
evaluation due to its communication cost, we describe IDA-3 here.

Intersection Detection Algorithm IDA-3.
Every search space is represented as a N-dimensional polyhedron with 2 N corners.
Each corner has coordinates

( )

R , RR ,...,

1 i 2 i i

R is either the minimum or the maximum distance of the X-node correspond-
ing to that search space, from the reference node R , j = 1, ..., N. Two search spaces
S and S may contain a common node when there is an overlap of their corre-
sponding polyhedra. A common node between two search spaces is not possible to
exist, until such an overlap occurs.
Two search spaces S and S might contain an intersection when there is an over-
lap for each of their reference node ranges. Pictorially this is represented by an inter-
section of the approximated spaces in the N-space. In Figure 5 this occurs for

where

ji

S and

S (for 2 reference nodes).

Fig. 5. N-space intersection in PBA* (N = 2)