Information Technology Reference
shortest path between S and G, nodes C1, …, C5 seem to be a better alternative for
X-nodes to use for PBA*-VD! This leads us to speculate that the shortest path (as
calculated by the Dijkstra algorithm) may not be the best choice for X-nodes and,
instead, the straightest path between S and G might be a better alternative ! Investiga-
tion of the ramifications of this “anomaly” is in our immediate research plans.
We present a method to generate appropriately located island nodes within a search
space. The motive for doing so is that such generated nodes will help in establishing a
solution path faster, if used by a multi-process bidirectional heuristic search algo-
rithm, such as PBA*. To the best of our knowledge this problem has resisted any type
of general purpose solution for more than two decades. We implement our method
and test it using PBA*, a bidirectional multi-process heuristic search algorithm de-
signed to utilize island nodes. Our findings indicate that PBA*-VD (the version of
PBA* that uses the island nodes generated by our method) outperforms PBA*-R (the
version of PBA* that uses randomly generated island nodes), more than 80% of the
time. Also, the overhead of incorporating our method into PBA* is negligible (less
than 0.5% of the cost of executing the PBA* algorithm itself). Interestingly, we also
uncover an “anomaly” (Result 3, in Section 3), whose remedying points to a method
of generating even more appropriately located island nodes.
Our future research plans include investigating the ramifications of the found
“anomaly” and also extending our method to N-dimensional spaces, when N > 2.
Also, we are interested in investigating the impact of the placement of reference
nodes (the use of reference nodes is at the heart of the MDH methodology described
in section 2). Specifically, besides the placement of X-nodes, the placement of refer-
ence nodes possibly impacts the performance of PBA*. In our current implementation
of PBA*-R and PBA*-VD we use randomly generated reference nodes - which is the
approach followed by all previous works in this area. Earlier findings (e.g., )
suggest that increasing the number of reference nodes beyond a certain threshold
(about five reference nodes) provides little or no improvement on the performance of
PBA*. However, the impact of the location of reference nodes is, as yet, unknown.
We are currently working toward investigating this problem.
1. Antoniol, G., Di Penta, M., Harman, M.: Search-Based Techniques Applied to Optimiza-
tion of Project Planning for a Massive Maintenance Project. In: Proceedings of IEEE In-
ternational Conference on Software Maintenance, pp. 240-249 (2005)
2. Yu, F., Ip, H.S., Leung, C.H.: A Heuristic Search for Relevant Images on the Web. In:
Leow, W.-K., Lew, M., Chua, T.-S., Ma, W.-Y., Chaisorn, L., Bakker, E.M. (eds.)
CIVR 2005. LNCS, vol. 3568, pp. 599-608. Springer, Heidelberg (2005)
3. Bekkerman, R., Zilberstein, S., Allan, J.: Web Page Clustering using Heuristic Search in
the Web Graph. In: Proceedings of IJCAI 2007, the 20th International Joint Conference on
Artificial Intelligence (2007)