Exploiting Algebraic Structure in Parallel State Space Search

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.