Research map / Learning theory and algorithms / Combinatorial and search optimization

Parallel Greedy Best-First Search with a Bound on Expansions Relative to Sequential Search

AAAI 2025 · Learning theory and algorithms › Combinatorial and search optimization · approach: Heuristic and local search algorithms · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes OBAT, a BTS-constrained parallel greedy best-first search with a shared Open list whose expansions are provably bounded by sequential GBFS plus k|p|, and shows with SGE (OBAT_S) it is competitive in coverage on IPC-based planning benchmarks.

Problem

Parallel greedy best-first search with shared Open/Closed lists can deviate drastically from sequential GBFS, and prior BTS-constrained methods like PUHF have no bound on the number of expansions relative to sequential GBFS.

Approach

OBAT defers potential progress states (b-states) into a Deferred queue so that only one bench is explored at a time, which yields a provable bound on expansions relative to sequential GBFS with some tie-breaking policy; OBAT_S adds separate generation and evaluation (SGE) to raise evaluation rates.

Key results

• OBAT_S reaches 532 coverage at 16 threads, matching KPGBFS_S (532) and exceeding PUHF3_S (510) out of 1260 instances.
• OBAT expands significantly fewer states than KPGBFS but has a significantly lower state evaluation rate, giving 496 coverage at 16 threads versus 529 for KPGBFS.
• The paper shows PUHF is pathological relative to sequential GBFS, so its expansions are not bounded by a constant multiple of GBFS expansions.

Measured effects reported in the paper

Surprising findings

• PUHF with k>=2 threads can be pathological relative to sequential GBFS even though it is BTS-constrained.
• OBAT without SGE has much lower evaluation rates than unconstrained KPGBFS, so the expansion bound comes at a practical cost unless SGE is used.

Limitations

• OBAT without SGE has significantly lower state evaluation rates than KPGBFS and PUHF3, reducing coverage.
• Evaluated only up to 16 threads; scalability to more threads is unresolved.
• Replaced gripper and miconic instances with harder generated instances, a non-standard benchmark modification.

Experimental setup

Datasets: Autoscale-21.11 satisficing benchmark set

Benchmarks: Autoscale-21.11 IPC-based planning benchmarks (1260 instances)

Metrics: coverage number of states expanded state evaluation rate

Baselines: GBFS KPGBFS KPGBFS_S PUHF3 PUHF3_S

Builds on: PUHF KPGBFS Bench Transition System SGE

Closest papers by meaning

• PEA*+IDA*: An Improved Hybrid Memory-Restricted Algorithm (AAAI 2022 · similarity 0.86)
• Breadth-First Search vs. Restarting Random Walks for Escaping Uninformed Heuristic Regions (AAAI 2026 · similarity 0.85)
• Tiebreaking Strategies for A* Search: How to Explore the Final Frontier (AAAI 2016 · similarity 0.85)
• Don't Waste Population: Post-Anneal Refinement for Combinatorial Optimization (NeurIPS 2026 · similarity 0.84)
• On the Completeness of Best-First Search Variants That Use Random Exploration (AAAI 2016 · similarity 0.84)
• Sample Complexity of Learning Heuristic Functions for Greedy-Best-First and A* Search (NeurIPS 2022 · similarity 0.84)