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

for N processors, N > 2 [11, 12]. The N-processor algorithm, PBA*, uses intermediate
nodes of the search space, called islands or X-nodes . The terms islands and X-nodes are
equivalent for the purposes of this paper. Historically, the term island nodes first ap-
peared in [9] to denote intermediate nodes in the search space, with the property that an
optimal path passes through at least one of them. The term X-nodes was introduced in
[11] to denote intermediate node in the search space but not requiring that an optimal
path passes through at least one of them. Also, since the algorithm described in [11]
requires two search processes (one forward and one reverse) to emanate from each node,
the term X-node was coined as a reminder of the bidirectionalism in the search (see
figure 1) in order to divide the search space into smaller subspaces.
Fig. 1. X-node
In this paper, the terms islands and X-nodes are used interchangeably, and mean in-
termediate nodes of the search space, some of which may participate in a path (not
necessarily optimal) connecting the source and goal nodes. Note, some of these in-
termediate nodes may not participate in a solution (actually this is especially true in
[9] where only one of the island nodes participates in the solution). As illustrated in
Figure 2, in addition to the parallel searches conducted from the source node S and
the goal node G, two parallel searches are conducted from each X-node; a forward
search towards the goal node G, and a reverse search towards the source node S. A
solution is found as soon as a set of search spaces intersect in such a way that a path
can be traced from S to G. The complexity of PBA* was analyzed in [11, 12]. In the
Fig. 2. Parallel bidirectional search with islands