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

S and S overlap, but

SS ∩=∅

Fig. 7.

a b

If the central control process uses an overlap table to decide when to turn on com-
munication between two searches, it can be assured that some existing intersection
will not be overlooked. Unfortunately, the existence of these overlaps does not insure
that the two search spaces contain a common node. The condition is not sufficient for
several reasons, one of which is that the heuristics only estimate distances to the ref-
erence nodes. However, even if the heuristic makes no errors in estimating distances,
there are still other reasons why this condition is not sufficient. As shown in Figure 7,
it may be that the approximated space of S a intersects with the approximated space of
S b without having any single node in (S b ) S a overlap all the reference node ranges in
(S a ) S b . The result of this is that no nodes lie in the intersection of the approximated
spaces [11]. Three different intersection detection algorithms, which increasingly
progressive degree of refinement, are outlined next.

(1) IDA-1 maintains a [min, max] overlap table and when the approximated
spaces of S f and S r intersect, S r will begin sending its nodes to S f .
(2) IDA-2 is based on addressing one of the reasons which keeps the overlap
condition, the basis of IDA-1, from being sufficient to insure that two spaces
intersect. IDA-2 waits until the reference node values of a single node in S r
lie in the approximated space of S f . When this condition occurs, S r will then
begin sending its nodes to S f .
(3) IDA-3 checks for the same condition as IDA-2 except that it does so on a node
by node basis. Both IDA-1 and IDA-2 end up turning on communication per-
manently. It may be that two search spaces only come close to intersecting for
a short period of time resulting to a lot of unnecessary node sending if com-
munication is permanently turned on. Instead, IDA-3 checks as each node is
generated and only sends nodes which lie in the approximated space of S f .
As mentioned earlier, we adopt IDA-3 for our evaluation. Our experiments reveal the
following.