Probabilistic Focal Search: Accelerating Bounded-Suboptimal Search via Randomized Node Expansion

Forum topic · 小凯 · 2026-09-13

Summary

Probabilistic Focal Search (PFS) is a new bounded-suboptimal search algorithm that addresses a key inefficiency in classic Focal Search (FS): FS's deterministic node selection policy can leave the lower bound f_min unchanged for many expansions, delaying admission of useful nodes into the FOCAL set. PFS follows the FS guided choice with probability p and expands a minimum-f OPEN node with probability 1-p, which advances the lower bound, enlarges FOCAL, and admits nodes that may lead to feasible solutions. Benchmarks on N-Puzzle, Pancake Sorting, and TSP show that when long f_min plateaus delay FOCAL admission, the probabilistic factor reduces node expansions by roughly 90% or more. The same scheduler transfers to Dynamic Potential Search (PDPS), and the anytime variant APFS outperforms all tested anytime algorithms on the Generalized Covering TSP (GCTSP). Gains are smaller when deterministic search already advances efficiently, indicating the mechanism is most useful when FOCAL admission is the bottleneck.

Paper Overview

Field: cs.AI
Authors: Minh Vu Duc, Trung Le Huu, Hà Minh Hoàng, Trung Thanh Nguyen, Phuong Khanh Nguyen, Huynh Thi Thanh Binh
Published: 2026-09-13
arXiv: 2609.10584

Abstract (Original)

Bounded-suboptimal search seeks a solution within a factor $$w$$ of optimal while reducing search effort. Focal Search (FS) uses heuristic guidance within FOCAL, the frontier nodes eligible under the threshold $w f_{\min}$ , but its deterministic policy may leave $f_{\min}$ unchanged for many expansions. We introduce Probabilistic Focal Search (PFS), which follows the FS guided choice with probability $$p$$ and expands a minimum- $$f$$ OPEN node with probability $$1-p$$ . The latter branch encourages the lower bound to advance, enlarging FOCAL and admitting nodes that may lead to feasible solutions. By balancing guidance and lower-bound advancement, this mechanism can reduce time to a bounded solution when progress is limited by delayed FOCAL admission.

As a secondary transfer experiment, the same scheduler is applied to Dynamic Potential Search, yielding Probabilistic Dynamic Potential Search (PDPS). PFS is benchmarked against FS on N-Puzzle, Pancake Sorting, and the Traveling Salesperson Problem (TSP), and its anytime extension is evaluated on the Generalized Covering TSP (GCTSP) using multiple $$w$$ and $$p$$ values.

Key Findings

The largest gains occur when long $f_{\min}$ plateaus delay useful FOCAL admissions; in such settings the probabilistic factor may reduce node expansions by about 90% or more (e.g., on N-Puzzle and TSP).
For the anytime algorithm family, Anytime Probabilistic Focal Search (APFS) outperforms all tested algorithms in evaluating anytime methods on GCTSP.
The benefit is smaller when the deterministic search already advances efficiently (e.g., Pancake Sorting), indicating the probabilistic factor is most useful when FOCAL admission is a search bottleneck.
The PDPS transfer shows the mechanism also works with potential guidance, though its common-success effects remain domain- and bound-dependent.