Jonathan Bright, Simon Kasif, Lewis Stiller
In this paper we present an approach for performing very large state-space search on parallel machines. While the majority of searching methods in Artificial Intelligence rely on heuristics, the parallel algorithm we propose exploits the algebraic structure of problems to reduce both the time and space complexity required to solve these problems on massively parallel machines. Our algorithm runs in O(N^1/4/p) time using O(N^1/4) space with P processors where N is the size of the state space and P is the number of processors. The technique we present is applicable to several classes of exhaustive searches. Applications include the knapsack problem and the shortest word problem in permutation groups which is a natural generalization of several common planning benchmarks such as Rubik’s Cube and the n-puzzle.