Paper Overview
Field: Machine Learning Authors: Minh Vu Duc, Trung Le Huu, Hà Minh Hoàng Published: 2026-09-11 arXiv: 2509.05828
Abstract
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).
Key Findings
- PFS is compared against FS on N-Puzzle, Pancake Sorting, and the Traveling Salesman Problem (TSP); an anytime extension (Anytime PFS, APFS) is evaluated on Generalized Covering TSP (GCTSP) using multiple values of \(w\) and \(p\).
- Gains are largest when \(f_{\min}\) plateaus for long periods and delay effective FOCAL admission: the probabilistic factor reduces node expansions by roughly 90% or more (e.g., N-Puzzle and TSP).
- For the anytime family, APFS outperforms all tested algorithms on GCTSP.
- Gains are smaller when deterministic search already advances efficiently (e.g., Pancake Sorting), indicating the probabilistic factor is most useful when FOCAL admission is the search bottleneck.
- The PDPS transfer shows the mechanism also applies to potential-based guidance, but its success remains domain- and bound-dependent.