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

Voronoi-assisted Parallel Bidirectional Heuristic Search
Anestis A. Toptsis and Rahul A. Chaturvedi
Dept. of Computer Science and Engineering,
York University, Toronto, Ontario, Canada
{anestis,rahul}@cse.yorku.ca
Abstract. We propose a method for identifying well-placed island nodes for the
purpose of performing a bidirectional parallel heuristic search algorithm. Multi-
process bidirectional heuristic search algorithms that utilize island nodes (such
as PBA*) have been shown to have the potential for exponential speedup over
their plain counterparts that do not utilize island nodes. The problem of how to
generate appropriately located island nodes has resisted any general purpose so-
lution to date. The proposed method is an initial step toward this end. We im-
plement our method and evaluate its performance within PBA* for a variety of
sliding-tiles puzzles. Our findings reveal that the overhead cost of using our
method is negligible, while at the same time, when PBA* is equipped with the
proposed method, it outperforms its random-island-nodes counterpart for the
vast majority of test cases.
1 Introduction
Heuristic search is one of the foundational areas of artificial intelligence (AI).
Recently, it has many applications in several diverse and practical areas such as Soft-
ware Engineering and the Web (e.g., [1, 2, and 3]). Heuristic search is essentially a
graph traversal with the characteristic that the number of nodes in the graph is huge
and thus the graph nodes are generated on the fly (as opposed to being already
known), as we traverse the graph. This sort of traversal is called heuristic search,
because we always search for some “goal” node G, in the graph, and we always use
heuristics (guesses and estimates that indicate the best way to proceed in the course of
the graph traversal). Heuristic search algorithms can be classified into two types,
unidirectional and bidirectional . In the unidirectional category (e.g., [4]) there is only
one-direction type of process, emanating from the source node S and seeking the goal
node G. The bidirectional category (e.g., [5, 6, 7, and 8]) incorporates two types of
processes - one forward type search process, from S to G, and one reverse type search
process, from G to S. Each of the processes can be executed using a typical unidirec-
tional algorithm such as A* [4]. In some bidirectional search algorithms, special kind
of nodes, called X-nodes (or islands), are used to aid the search. The concept of intro-
ducing X-nodes to speed up the search was introduced in [9] and there have since
been developed several algorithms that utilize X-nodes. Notable examples are PBA*,
WS_PBA*, and SSC_PBA*, described in [7, 8].
Bidirectional multiprocessor heuristic search has been introduced by Nelson [13], first
for 2 processors as a parallelization of Pohl's algorithm [5], and it was later generalized