This survey paper, "A Survey of Parallel A*," provides a comprehensive look at how researchers have scaled one of the most fundamental algorithms in Artificial Intelligence to work across multiple processors, large-scale clusters, and even GPUs.
TL;DR
While the A* search algorithm is the gold standard for finding optimal paths, it is notoriously memory-hungry, often crashing single machines. This paper surveys how parallelization—specifically decentralized, hash-based work distribution—allows researchers to pool the memory of entire clusters to solve massive problems that were previously unreachable.
What Problem Does This Paper Address?
The A algorithm is a "best-first" search used in everything from robot path planning to computational biology. However, it faces a "memory wall." To guarantee an optimal solution, A must keep every "visited" state in a list (the CLOSED list) to avoid redundant work. For complex problems, this list grows so large it exhausts a computer's RAM long before a solution is found.
Parallelizing A isn't just about making it faster; it’s about aggregate memory*. By spreading the search across 100 machines, you gain 100 times the RAM. The challenge lies in doing this efficiently. If processors spend all their time talking to each other (communication overhead) or waiting for access to a shared list (synchronization overhead), the parallel version might actually be slower than a single-threaded one.
Methods
The authors categorize parallel A* into several distinct architectural approaches:
- Centralized Parallel A (SPA): Multiple threads share a single "OPEN" list of states to explore. This is easy to implement but fails to scale because threads constantly fight for "locks" on the shared data.
- Decentralized Parallel A (HDA): This is the current state-of-the-art. Each processor has its own local lists. A hash function (specifically Zobrist hashing) is used to assign every possible state to a specific "owner" processor. When a processor generates a new state, it sends it to the owner. This naturally handles both load balancing and duplicate detection without needing a central bottleneck.
- Abstract Zobrist Hashing (AZH): A hybrid approach that groups related states together on the same processor using "abstractions." This reduces the need for processors to send messages back and forth, significantly lowering communication overhead.
- Parallel IDA*: For problems where even a cluster's memory isn't enough, the paper explores "Iterative Deepening" variants that trade time for memory, using techniques like "work stealing" to keep all processors busy.
Datasets
The paper evaluates these methods using several classic AI benchmarks:
- The 15-Puzzle and 24-Puzzle: Standard sliding-tile puzzles used to measure search efficiency.
- Multiple Sequence Alignment (MSA): A critical problem in computational biology for comparing DNA/protein sequences.
- Domain-Independent AI Planning: Using standard languages like PDDL (Planning Domain Definition Language) to solve generalized logic problems.
- Grid Maps: Pathfinding for robots or game characters in 2D environments.
Key Insights and Ideas
- The "Search Overhead" Trap: Parallel search often expands more nodes than serial search. This is because a parallel thread might find a "good" solution and keep searching, while a serial search would have stopped immediately upon finding the "best" one. Minimizing this "wasted" work is a primary goal of parallel design.
- Zobrist Hashing is the Secret Sauce: The choice of hash function is critical. Zobrist hashing—which uses XOR operations on bit strings—provides a near-perfect uniform distribution of work across processors, which is why it outperforms simpler methods.
- The Cloud Economics of Search: In cloud environments (like AWS), the authors suggest a "doubling strategy" for resource allocation. Since you don't know how much memory a problem needs, it is mathematically optimal to double your hardware allocation each time a search fails due to memory exhaustion.
Key Results
The survey highlights that Hash-Based Decentralized A (HDA) is the most robust approach for scaling.
- Speedup: In experimental comparisons (Figure 6), AZHDA (Abstract Zobrist HDA) achieved the highest speedup, nearly linear up to 16 cores, while the centralized "SharedOpen" approach actually saw performance decrease as more threads were added due to lock contention.
- Efficiency: Advanced hashing techniques like AZH were shown to reduce communication overhead by over 90% in some domains compared to standard Zobrist hashing, without significantly increasing the search overhead.
Limitations and Future Work
- GPU Bottlenecks: While GPUs have thousands of cores, their memory per core is tiny. The paper notes that running full A* on a GPU is still difficult because the "CLOSED" list quickly exceeds the GPU's VRAM.
- Non-Levelized Graphs: Some advanced work distribution methods (like Hyperplane distribution) only work on "levelized" graphs (where paths only move forward in time). Adapting these to more general, loopy graphs remains an open challenge.
- Real-Time Constraints: Most parallel A* research focuses on solving a problem once. Future work is needed on "anytime" parallel algorithms that can provide a "good enough" answer quickly and improve it over time.
Summary updated