Source-linked AI summary
Probabilistic Focal Search: Accelerating Bounded-Suboptimal Search via Lower-Bound Advancement
Minh Vu Duc, Trung Le Huu, Hà Minh Hoàng, Trung Thanh Nguyen, Phuong Khanh Nguyen, Huynh Thi Thanh Binh
TL;DR
Bounded-suboptimal focal search can stall when delayed FOCAL admission leaves the lower bound unchanged. The paper introduces probabilistic scheduling that alternates guided and minimum-f selection, improving search most when lower-bound advancement unlocks useful FOCAL nodes; gains are smaller when FOCAL is already sufficient.
Problem
Focal Search may leave fmin unchanged for many expansions, delaying FOCAL admissions that could provide useful guided choices.
Method
PFS follows the guided FOCAL policy with probability p and selects a minimum-f OPEN node with probability 1 − p, with the scheduler also transferred to DPS as PDPS.
Results
Across domains, PFS improves most when delayed FOCAL admission is a bottleneck, including at least 87.2% fewer penalized expansions and 89.0% lower capped runtime on TSP.
Takeaways & Limitations
Probabilistic lower-bound advancement is most useful when newly eligible FOCAL states improve guided choices, whereas it adds work when the existing FOCAL envelope already suffices.
Takeaways & Limitations
The benefit is smaller when the initial FOCAL is already sufficient, as in Pancake, where PFS adds 30 OPEN-head expansions without improving the envelope.
Abstract
from arXiv · showhide
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, 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. Across these benchmarks, 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. We also observe that the benefit is smaller when the deterministic search already advances efficiently (e.g., Pancake Sorting), indicating that the probabilistic factor is most useful when FOCAL admission is a search bottleneck. The PDPS transfer shows that the mechanism also transfers to potential guidance, although its common-success effects remain domain- and bound-dependent.
Introduction
The paper identifies when probabilistic scheduling improves focal search and reports substantial cross-domain gains, especially where delayed FOCAL admission limits progress.
- PFS raises N-Puzzle success from 44.3% to 83.6% while reducing penalized expansions by 60.7% and capped runtime by 69.8%.
- Across both TSP datasets, PFS reaches at least 96.4% success and reduces penalized expansions and capped runtime by at least 87.2% and 89.0%.
- APFS solves 189/234 medium GCTSP instances versus 82/234 for AFS.
- Minimum-f selections help when they advance the lower bound and admit nodes that guided selection can exploit, but add overhead when FOCAL is already sufficient.
Background and Related Work
The paper situates focal search as bounded-suboptimal search with admissibility controlled by a lower-bound threshold, while relating DPS to focal search through dynamic potential ordering.
- A* expands minimum-f nodes for optimality, whereas Weighted A* orders by g(n) + wh(n) to obtain a w-suboptimal solution more quickly.
- Focal Search: FS maintains fmin as the minimum OPEN f-value and selects guided nodes from FOCAL under a multiplicative eligibility threshold.
- Focal Search: Focal Search separates its admissibility certificate from its secondary priority, which need not be admissible.
- Dynamic Potential Search: DPS is a focal-search special case whose secondary priority is negative dynamic potential, with potential ordering depending on the current fmin.
- Dynamic Potential Search: The DPS endpoint convention assigns +∞ potential to h = 0 nodes only when g(n) ≤ wfmin, preserving a safe goal test.
Probabilistic Focal Search
PFS randomizes between guided FOCAL selection and minimum-f OPEN selection to advance the lower bound, while preserving the bounded-suboptimality certificate and motivating transfer to DPS.
- PFS follows the FS policy with probability p and selects a minimum-f OPEN node with probability 1 − p; p = 1 recovers FS and p = 0 uses A* ordering.
- PDPS applies the same Bernoulli scheduler to DPS, changing only the guided branch to maximum-potential selection while retaining eligible goal acceptance.
- The randomized branch preserves the lower bound and acceptance condition, so every first-solution PFS result remains within wC∗ for all p ∈ [0, 1].
- Minimum-f expansion can clear fmin plateaus, raise wfmin, and admit additional nodes that the guided policy can exploit.
- The same threshold motivation extends to PDPS because its potential-guided policy is tested for exploiting newly eligible nodes.
Experiments
Across benchmark and anytime experiments, probabilistic scheduling most improves search when delayed FOCAL admission limits progress, while gains are smaller or reversed when existing guidance is already sufficient.
- First-solution results: PFS substantially improves N-Puzzle and TSP performance, raising success while reducing penalized expansions and capped runtime.On N-Puzzle, success rises from 44.3% to 83.6%; on TSP-40, from 78.6% to 99.4%, with expansion ratios of 0.393 and 0.058, respectively.
- First-solution results: PDPS also outperforms DPS across domains, with higher success, lower penalized expansion ratios, and lower capped runtime.Success improves from 65.4% to 77.7% on N-Puzzle and from 79.1% to 88.7% on TSP-50; expansion ratios are 0.757 and 0.658.
- Bound dependence: On TSP-50, PFS helps most at tight bounds but adds work once both methods solve every instance.For w ≤ 1.25, PFS solves 77–100 instances versus 25–71 for FS, while at w = 2 paired expansion and runtime ratios exceed 1.
- Mechanism analysis: PFS clears heavy N-Puzzle f_min plateaus earlier, terminating after 43,972 expansions versus 444,774 for FS.Threshold increases admit batches of nodes into FOCAL, allowing secondary guidance to exploit the enlarged eligible set.
- Mechanism analysis: PFS adds overhead on Pancake because the initial FOCAL threshold already admits the solution without advancing f_min.FS uses 147 guided expansions, whereas PFS performs those plus 30 unhelpful OPEN-head expansions.
- Probability sensitivity: Across tested probabilities, PFS consistently reduces expansions on commonly solved N-Puzzle and TSP instances, but no universal p is best.Median setting-level ratios are 0.121–0.151 for N-Puzzle and 0.021–0.029 for TSP, versus 1.222–1.629 on Pancake.
- Anytime evaluation: APFS achieves the highest first-solution coverage and strongest refinement results among the evaluated anytime methods.It finds solutions on 81/81 small and 189/234 medium GCTSP instances, and reaches the refinement target on 81 small and 181 medium instances.
- Anytime evaluation: The transfer to PDPS shows that lower-bound advancement can also help potential ordering when FOCAL admission limits progress.APDPS improves its deterministic parent, especially on medium GCTSP instances, although APFS remains strongest because prize deficit guides residual-quota feasibility.
Discussion and Conclusion
PFS improves focal search most when delayed FOCAL admission limits progress, while its gains shrink when the deterministic search already advances effectively.
- PFS improves search most when delayed FOCAL admission is a bottleneck, while Pancake Sorting shows smaller gains when the initial FOCAL is already sufficient.The mechanism helps when newly eligible states improve guided choices; otherwise, OPEN-head selections add work.
- Figures 7 and 8 compare cumulative incumbent discovery and time to reach costs within 1% of the lowest final value across four GCTSP methods.
- APFS solves 189/234 medium GCTSP instances versus 82/234 for AFS, and APFS leads all evaluated anytime methods.
Exact DPS Eligibility
Exact DPS eligibility follows from the potential bound: a maximum-potential node is guaranteed to lie within FOCAL’s threshold.
- Under the theorem’s assumptions, an exact maximum-potential node satisfies f(n) ≤ wfmin and therefore lies in FOCAL.
- Because FOCAL contains a minimum-f OPEN node whenever OPEN is nonempty and w ≥ 1, exact DPS need only consider FOCAL.
Admissible Quota–Kruskal-Forest Lower Bound
The Quota–Kruskal-Forest heuristic lower-bounds remaining completion cost by selecting a cheapest acyclic edge set sufficient to cover the residual quota.
- QKF computes a lower bound from the residual quota by finding the minimum number of capacity-ranked vertices needed for any feasible completion.
- For positive residual quota, QKF selects the cheapest required acyclic edges in a complete graph over the current vertex, depot, and covering vertices.
- QKF is admissible because every feasible completion contains an acyclic subset no more costly than the selected edge set.