Parallel bidirectional island search in distributed memory multiprocessors

摘要

Fast heuristic search techniques are crucial in almost all artificial intelligence (AI) systems. They have significant impact on many real life applications, including expert systems, next generation database management systems, robotics, game playing, and automated reasoning. Bidirectional heuristic island search is a state-of-the-art approach which combines forward chaining, backward chaining, use of island states, and multi-dimensional heuristics, in order to achieve high real time performance. This dissertation demonstrates that this approach makes an excellent blend with distributed memory parallel computers. Implementation and extensive testing of algorithm PBA* on both a uniprocessor and a multiprocessor computer (iPSC/2) show that bidirectionalism is a promising approach in heuristic search. Superlinear speedups are uniformly achieved, thus making algorithm PBA* quite attractive for practical usage. These speedups also demonstrate that parallelism in its own right is a promising approach in heuristic search. Addition of wave-shaping features, makes algorithm PBA* even more effective. The resulting algorithm, WS PBA*, provides wave-shaping power to PBA*, by redirecting the concurrent search processes toward fast convergence. Simulation of WS PBA* on a uniprocessor machine, as well as its implementation on an Intel iPSC/2 hypercube demonstrate that WS PBA* performs well without requiring knowledge of the shape of the search space for positioning of the X-nodes and the reference nodes. It also makes good use of the presence of large numbers of reference nodes, thus utilizing the multi-dimensional heuristic concept, originally introduced for algorithm PBA*. The wave-shaping technique introduced by algorithm WS PBA* is generalized with algorithm SSC PBA*. The generalized method partitions every local search space into subspaces (clusters). The local searches aim toward clusters belonging to local searches of opposing direction. Nodes which belong to opposing clusters that are close to each other, are given priority for expansion. The well known uniprocessor bidirectional heuristic search algorithms of DeChampeaux and Politowski-Pohl turn out to be special cases of a 2-process uniprocessor version of algorithm SSC PBA*. Both algorithms, WS PBA* and SSC PBA* are highly scalable, in the sense that they can take advantage of any number of available processors on a multiprocessor machine.