Probabilistic Focal Search: Accelerating Bounded-Suboptimal Search via Lower-Bound Advancement

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.

摘要： 有界次优搜索（Bounded-suboptimal search）旨在寻找一个在最优解 $w$ 倍因子范围内的解，同时减少搜索工作量。焦点搜索（Focal Search, FS）在 FOCAL（即在阈值 $w f_{\min}$ 下符合条件的边界节点集合）内使用启发式引导，但其确定性策略可能导致 $f_{\min}$ 在多次扩展后仍保持不变。

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.

我们引入了概率焦点搜索（Probabilistic Focal Search, PFS），它以概率 $p$ 遵循 FS 的引导选择，并以概率 $1-p$ 扩展一个最小 $f$ 值的 OPEN 节点。后一种分支鼓励下界推进，从而扩大 FOCAL 并接纳可能导向可行解的节点。通过平衡引导与下界推进，当搜索进度受限于 FOCAL 接纳延迟时，该机制可以缩短获得有界解的时间。

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.

作为一项次要的迁移实验，我们将相同的调度器应用于动态势搜索（Dynamic Potential Search），从而产生了概率动态势搜索（PDPS）。我们在 N-Puzzle、煎饼排序（Pancake Sorting）和旅行商问题（TSP）上对 PFS 与 FS 进行了基准测试，并使用多个 $w$ 和 $p$ 值，在广义覆盖旅行商问题（GCTSP）上评估了其随时（anytime）扩展版本。

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.

在这些基准测试中，最大的性能提升出现在长期的 $f_{\min}$ 平台期延迟了有效的 FOCAL 接纳时；在这种情况下，概率因子可以将节点扩展量减少约 90% 或更多（例如在 N-Puzzle 和 TSP 上）。对于随时算法系列，随时概率焦点搜索（APFS）在 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.

我们还观察到，当确定性搜索已经能够高效推进时（例如煎饼排序），该方法的收益较小，这表明概率因子在 FOCAL 接纳成为搜索瓶颈时最为有用。PDPS 的迁移实验表明，该机制同样适用于势引导（potential guidance），尽管其共同成功效应仍取决于具体领域和边界条件。