A Survey of Parallel A

Alex Fukunaga, Adi Botea, Yuu Jinnai, Akihiro Kishimoto

Abstract: A is a best-first search algorithm for finding optimal-cost paths in graphs. A benefits significantly from parallelism because in many applications, A is limited by memory usage, so distributed memory implementations of A that use all of the aggregate memory on the cluster enable problems that can not be solved by serial, single-machine implementations to be solved. We survey approaches to parallel A, focusing on decentralized approaches to A which partition the state space among processors. We also survey approaches to parallel, limited-memory variants of A such as parallel IDA.

The A algorithm is the gold standard for finding optimal paths in domains ranging from robot path planning to computational biology. However, it faces a significant "memory wall." To guarantee an optimal solution, A must maintain a list of every visited state (the CLOSED list) to prevent redundant work. For complex problems, this list quickly exhausts a computer's RAM. Parallelizing A is not merely about speed; it is about leveraging aggregate memory*. By distributing the search across a cluster, researchers can pool memory resources to solve massive problems unreachable by single machines.

Architectural Approaches to Parallel A*

Parallel A* implementations are generally categorized by how they manage work distribution and list management.

Taxonomy of parallel A* search algorithms, categorizing approaches by list management, work distribution, and communication methods.
  • Centralized Parallel A (SPA): Multiple threads share a single "OPEN" list. While simple to implement, this approach fails to scale due to lock contention as threads compete for access to shared data.
  • Hash-Based Decentralized A (HDA): This state-of-the-art approach assigns every possible state to a specific "owner" processor using a hash function (typically Zobrist hashing). When a processor generates a new state, it sends it to the owner, naturally facilitating load balancing and duplicate detection without a central bottleneck.
  • Abstract Zobrist Hashing (AZH): A hybrid method that groups related states on the same processor using abstractions. This significantly lowers communication overhead by reducing the frequency of inter-processor messages.
  • Parallel IDA*: For extremely memory-constrained environments, iterative deepening variants trade computation time for memory, often employing "work stealing" to maintain high processor utilization.

Evaluation Benchmarks

The survey evaluates these methods using several classic AI benchmarks that test different aspects of search efficiency and state-space complexity.

The 15-puzzle, a classic sliding-tile benchmark used to measure the efficiency of parallel search algorithms.

Key datasets include:

  • Sliding-Tile Puzzles (15 and 24-Puzzle): Standard benchmarks for measuring search efficiency.
  • Multiple Sequence Alignment (MSA): A critical problem in bioinformatics for comparing DNA or protein sequences.
  • Domain-Independent AI Planning: Using PDDL to solve generalized logic problems.
  • Grid Maps: 2D pathfinding for robotics and game development.

Key Insights and Results

Parallel search introduces unique challenges, most notably Search Overhead. Parallel threads may expand more nodes than a serial search because they might continue exploring "good" paths while a serial search would have already terminated upon finding the optimal one. Minimizing this wasted work is a primary goal of parallel design.

Experimental results indicate that Hash-Based Decentralized A (HDA) is the most robust scaling approach. Advanced techniques like *AZHDA (Abstract Zobrist HDA*) have been shown to achieve nearly linear speedup on multi-core systems. Furthermore, AZH can reduce communication overhead by over 90% in specific domains compared to standard Zobrist hashing, without significantly increasing search overhead.

Limitations and Future Work

Despite these advancements, several challenges remain. Running A* on GPUs is difficult because the CLOSED list quickly exceeds the limited VRAM available per core. Additionally, some work distribution methods, like Hyperplane distribution, are currently limited to "levelized" graphs where paths only move forward in time. Future research is needed to adapt these methods to general, loopy graphs and to develop "anytime" parallel algorithms that can provide rapid, suboptimal solutions that improve over time.

Summary updated

Abstract

A* is a best-first search algorithm for finding optimal-cost paths in graphs. A* benefits significantly from parallelism because in many applications, A* is limited by memory usage, so distributed memory implementations of A* that use all of the aggregate memory on the cluster enable problems that can not be solved by serial, single-machine implementations to be solved. We survey approaches to parallel A*, focusing on decentralized approaches to A* which partition the state space among processors. We also survey approaches to parallel, limited-memory variants of A* such as parallel IDA*.
BibTeX
@inproceedings{fukunaga2018survey,
  author = {Alex Fukunaga and Adi Botea and Yuu Jinnai and Akihiro Kishimoto},
  title = {{A Survey of Parallel A}},
  booktitle = {Handbook of Parallel Constraint Reasoning},
  year = {2018},
  url = {https://openreview.net/forum?id=0jIhgUhyMX},
}
Figure