Toward State Space Island Identification in Multi-process Bidirectional Heuristic Search

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. However, the performance of the former can dramatically degrade if the island nodes are not appropriately placed in the state space prior to the beginning of such algorithms. The problem of how to generate appropriately located island nodes has resisted any general purpose solution to date. This work is an initial proposal toward this end. We implement 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 by over 80% of the time.