Paper Overview
Field: ML Authors: Minh Vu Duc, Trung Le Huu, Hà Minh Hoàng Published: 2026-09-11 arXiv: 2509.05828
Summary
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.
The paper introduces 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).
Experiments and Findings
- PFS is compared against FS on N-Puzzle, Pancake Sorting, and the Traveling Salesman Problem (TSP), with an anytime variant evaluated on generalized covering TSP (GCTSP) using multiple values of \(w\) and \(p\).
- Benefits are largest when long plateaus in \(f_{\min}\) delay effective FOCAL admission: the probabilistic factor reduces node expansions by approximately 90% or more (e.g., N-Puzzle and TSP).
- For the anytime algorithm family, Anytime PFS (APFS) outperforms all tested algorithms on GCTSP.
- Gains are smaller when deterministic search already progresses 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 dependent on the domain and bound.
*Auto-collected on 2026-09-12*