Parallel bidirectional search using multidimensional heuristics

Artificial Intelligence search techniques make use of heuristics to search problem graphs in a best-first manner. The research described in this dissertation has focused on developing heuristic search techniques suitable for distributed computer architectures. A bidirectional searching scheme which uses n processors to conduct simultaneous heuristic searches from the initial, goal and (island) "X" nodes is presented. These X-nodes are nodes which are estimated to lie in between the initial and goal nodes. Solutions found by using this search method involve the participation of multiple searches conducted on different processors. Expected performance increases result from the use of parallelism combined with the search radius reduction associated with bidirectional methods. One problem with this scheme is generating X-nodes which lie in between the initial and goal nodes. X-node generation is explored for three different cases with the conclusion that such nodes can be successfully for some problem domains. Another problem with this search method is the task of search management. This problem consists of detecting intersections between the different distributed search spaces while minimizing the amount of node exchanging among the various processors. A solution for this problem is presented. This solution uses a set of reference nodes in the search space to set up an N-space which is used to approximate the positions of the search spaces. This approximation is used to decide when two search processes should start exchanging nodes. Test results are given in support of this method which is referred to as multi-dimensional heuristics. Additionally it is shown that this idea of multi-dimensional heuristic can also be used as a general heuristic improvement procedure as well. Test results show that this method can improve both the tile reversal and Manhatten heuristics for the 15-puzzle.