Speculative Parallel Best First Search

Problem

Explore how best-first search algorithms such as A* can use parallel work without changing the expansion order that defines the sequential algorithm.

Next step

Benchmark the implementation against a sequential baseline across search problems and worker counts.

Approach

1. 1 Keep a main thread responsible for selecting and expanding nodes in the same order as a conventional best-first search.
2. 2 Use worker threads to speculatively generate successors for nodes that may be expanded later.
3. 3 Store generated successors so that when the main thread reaches a node, it can reuse work that has already been completed.
4. 4 Preserve the main algorithm's expansion ordering while moving successor generation off the critical path when speculation is correct.

Results

• • Separates order-sensitive best-first expansion from parallel successor generation.
• • Provides a C++ research codebase for investigating speculative parallelism in best-first search algorithms.