Bounded‑suboptimal search aims to find a solution whose cost is at most a factor $w$ of the optimal one while minimizing search effort. Focal Search (FS) restricts expansion to the frontier nodes whose $f$‑value lies within the threshold $w f_{\min}$ (the FOCAL set) and uses heuristic guidance inside this set. However, its deterministic policy often leaves the lower bound $f_{\min}$ unchanged for many expansions, preventing FOCAL from admitting new promising nodes.
We introduce Probabilistic Focal Search (PFS): with probability $p$ it follows the FS‑guided choice, and with probability $1-p$ it expands the minimum‑$f$ node from OPEN. The latter branch pushes the lower bound forward, enlarges FOCAL, and allows nodes that may lead to feasible solutions to enter the focal set. By balancing guidance and lower‑bound advancement, PFS can cut the time to a bounded solution when progress is limited by delayed FOCAL admission.
As a secondary transfer experiment, we apply the same scheduler to Dynamic Potential Search, yielding Probabilistic Dynamic Potential Search (PDPS). We benchmark PFS against FS on N‑Puzzle, Pancake Sorting, and the Traveling Salesperson Problem (TSP), and evaluate its anytime extension on the Generalized Covering TSP (GCTSP) using multiple $w$ and $p$ values.
The results show that the largest gains occur when long $f_{\min}$ plateaus delay useful FOCAL admissions; in such settings the probabilistic factor can 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 methods on GCTSP. Conversely, when the deterministic search already advances the lower bound efficiently (e.g., Pancake Sorting), the benefit of the probabilistic factor is modest, indicating that it is most useful when FOCAL admission is the search bottleneck. The PDPS transfer demonstrates that the mechanism also works with potential‑based guidance, although its success remains domain‑ and bound‑dependent.
Review: Probabilistic Focal Search injects a simple random scheduler between deterministic guidance and lower‑bound progression, effectively alleviating FOCAL admission bottlenecks. It achieves substantial reductions in search effort across diverse benchmarks, especially in problems where $f_{\min}$ tends to plateau, making it a valuable addition to the bounded‑suboptimal search toolkit.