Exploiting Algebraic Structure in Parallel State Space Search

Jonathan Bright, Simon Kasif, Lewis StillerAAAI 1994

Abstract

This paper presents a parallel algorithm for searching massive state spaces by exploiting the underlying algebraic structure of problems like the knapsack problem and Rubik's Cube. By parallelizing the classic Schroeppel and Shamir algorithm, the authors achieve a time complexity of $O(N^{1/4}/P)$ and a space complexity of $O(N^{1/4})$, effectively allowing researchers to double the searchable depth of complex problems on massively parallel machines.

Introduction

State-space search is a cornerstone of Artificial Intelligence, used for everything from planning to game playing. However, most methods (like IDA*) rely heavily on heuristics to prune the search tree. When good heuristics are unavailable or the state space is astronomical, these methods fail.

While parallel computing offers a way out, simply throwing more processors at the problem often leads to a "space bottleneck." If an algorithm requires $O(N^{1/2})$ space to achieve a significant speedup, it quickly outstrips the memory available on even the largest supercomputers. The authors seek to bridge this gap by creating an algorithm that is both time-efficient and space-efficient, specifically targeting "monotonic and decomposable" problems.

Methodology

The authors build upon the Schroeppel and Shamir algorithm, a sequential technique that solves the knapsack problem by partitioning the input into four lists ($A, B, C, D$) and looking for intersections of sums (e.g., $A+B$ vs. $C+D$).

Parallel Generation and Data Structures

Instead of generating sums one by one using a priority queue (which is inherently sequential), the authors propose a method to generate $2^{n/4}$ elements in parallel. They use an array called TEMP to track candidate elements and iteratively "filter" them to find the smallest set of candidates.

In the knapsack problem, addition is monotonic ($b < b' \implies a+b < a+b'$). However, in permutation groups (like Rubik's Cube), this doesn't hold. The authors introduce a Trie-based data structure where interior nodes are reordered based on the specific permutation being applied. This allows them to maintain a lexicographical order even when the operators are complex.

Figure 1: A Trie structure representing the initial state space elements before reordering.
Figure 2: The Trie structure reordered to maintain lexicographical consistency after a permutation operation.

Computational Model

The algorithm is described using the CREW PRAM (Concurrent Read Exclusive Write Parallel Random Access Machine) model, which simplifies the description by hiding communication costs, though the authors acknowledge the practical challenges of this assumption.

Benchmarks and Key Insights

As a theoretical algorithmic paper, it evaluates the approach against canonical computational benchmarks including the Knapsack Problem and Permutation Groups (specifically the Shortest Word Problem, which generalizes puzzles like Rubik’s Cube).

  • The Power of Four: By splitting a problem into four parts rather than two (the standard "meet-in-the-middle" approach), the space requirement drops from $O(N^{1/2})$ to $O(N^{1/4})$. This is the difference between a problem being impossible to fit in RAM and being trivial.
  • Algebraic Leverage: The paper argues that we shouldn't just rely on "blind" search or heuristics. If a problem has an algebraic structure (like being a group or a groupoid), that structure can be used to mathematically decompose the search.
  • Parallelizing the Priority Queue: The "aha moment" in the parallel implementation is replacing the sequential priority queue with a parallel filtering process in the TEMP array, allowing multiple processors to contribute to the generation of the next batch of states simultaneously.

Results and Future Work

The algorithm achieves a time complexity of $O(N^{1/4}/P)$ using $O(N^{1/4})$ space, where $N$ is the size of the state space and $P$ is the number of processors. The authors claim this approach can effectively double the depth of the search that current technology can perform for this class of problems.

While theoretically sound, the authors admit the CREW PRAM model is unrealistic for actual hardware because it ignores the high cost of communication. Future directions include applying compression techniques, such as Binary Decision Diagrams (BDDs), to further reduce the memory footprint and refining implementation-dependent parameters to improve performance on actual hardware like the CM-5.

Summary updated

BibTeX
@inproceedings{bright1994exploiting,
  author = {Jonathan Bright and Simon Kasif and Lewis Stiller},
  title = {{Exploiting Algebraic Structure in Parallel State Space Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure