Kohonen-guided Parallel Bidirectional Voronoi-assisted Heuristic Search

Abstract

Multi-process bidirectional heuristic search algorithms (such as PBA*) that utilize island nodes have been shown to have the potential for exponential speedup over their plain counterparts that do not utilize island nodes. PBA* (Parallel Bidirectional A*) is a primary algorithm in this area and, to the best of our knowledge, unique in its usage of island nodes for reducing the size of the traversed search space and in its usage of multidimensional heuristics for reducing interprocess communication cost. Both, island nodes use and reference nodes use within the context of multidimensional heuristics have been reported to provide excellent performance, compared to plain heuristic search counterparts. However, both of these two features have also resisted refinements for over two decades. Specifically, the two main issues are: how to identify well-placed (in the state space) island nodes, and how to generate well-placed reference nodes. The work presented in this paper is an initial step toward this end. We present two methods, one employing Voronoi diagrams for the purpose of identifying well-placed island nodes, and one employing Kohonen Networks for the purpose of identifying well-placed reference nodes. We implement and compare our methods against a plain version of PBA*. Our finding indicate that the cost of incorporating the proposed improvements into PBA* is negligible; and when PBA* is equipped with the island identification method, or with the reference node identification method, it outperforms its random island nodes counterpart and its random reference nodes counterpart, respectively, for the vast majority of test cases.