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

As shown in Table 2, there are two types of overhead in incorporating Algorithm A
of section 2 into algorithm PBA*: the GRN overhead , and the D/D overhead . The
GRN overhead is the cost of executing essentially steps A.1 and A.2 of Algorithm A
(generate candidate X-nodes and project them onto a 2-dim space). The D/D overhead
is the cost of executing steps A.3 and A.4 of Algorithm A (form the D-graph and
calculate shortest path with Dijkstra's algorithm). As we see in Table 2, the total
overhead (GRN + D/D) is 25 seconds, which is 0.41% (25/6103) of the time required
to execute algorithm PBA*-VD. We also note that the total time to execute PBA*-VD
(i.e. the time for the actual PBA*-VD plus the total overhead time) does not exceed
the time to execute PBA*-R. Therefore, assuming that the incorporation of the Vo-
ronoi-Dijkstra technique into algorithm PBA* does not, in any way, harm the overall
quality of the heuristic search process, the overhead for employing the Voronoi-
Dijkstra method for finding useful X-nodes is not only negligible, but it also posi-
tively contributes (as evidenced by the results shown in Table 1), to the overall quality
of PBA*.
Result 3 : The Voronoi-Dijkstra “anomaly” . Our experiments uncover an unfortunate
scenario, illustrated in Figure 8.
Fig. 8. The Voronoi-Dijkstra “anomaly”
Figure 8 shows the D-graph formed by a specific arrangement of randomly gener-
ated candidate X-nodes. The path S, X1, X2, X3, G is the shortest path connecting S
and G and, therefore, X1, X2, and X3 are chosen as the X-nodes for the execution of
algorithm PBA*-VD. Note, however, although these nodes are the ones that form a