Exploiting Algebraic Structure in Parallel State-Space Seach (Extended Abstract)

Innovative Applications of Massive Parallelism

Volume

Papers from the 1993 AAAI Spring Symposium

Contents

In this paper we present an approach for performing very large state-space search on parallel machines. While the majority of searching methods in ArtificiM Intelligence rely on heuristics, the paralld 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 algorithms have applications to many important problems in Artificial Intelligence and Combinatorial Optimization such as planning problems and scheduling problems.