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

# Probabilistic Focal Search: Accelerating Bounded-Suboptimal Search via Lower-Bound Advancement
Source: [https://arxiv.org/html/2609.10584](https://arxiv.org/html/2609.10584)
Trung Le HuuHà Minh HoàngTrung Thanh NguyenPhuong Khanh NguyenHuynh Thi Thanh Binh

###### Abstract

Bounded\-suboptimal search seeks a solution within a factorwwof optimal while reducing search effort\. Focal Search \(FS\) uses heuristic guidance within FOCAL, the frontier nodes eligible under the thresholdw​fminwf\_\{\\min\}, but its deterministic policy may leavefminf\_\{\\min\}unchanged for many expansions\. We introduce Probabilistic Focal Search \(PFS\), which follows the FS guided choice with probabilityppand expands a minimum\-ffOPEN node with probability1−p1\-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 multiplewwandppvalues\. Across these benchmarks, the largest gains occur when longfminf\_\{\\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\.

1SLSCM Lab, National Economics University

2University of Warwick

3DataOpt Lab, National Economics University

4CADA Lab, National Economics University

5Hanoi University of Science and Technology

## Introduction

Bounded\-suboptimal heuristic search trades optimality for a certificate: given a factorw≥1w\\geq 1, it seeks a solution of cost at mostw​C∗wC^\{\*\}while using far less search than A\*\. Focal Search \(FS\) realizes this idea with an admissible primary heuristic and a secondary priority\. It maintains𝐹𝑂𝐶𝐴𝐿=\{n∈𝑂𝑃𝐸𝑁:f⁡\(n\)≤w​fmin\}\\mathit\{FOCAL\}=\\\{n\\in\\mathit\{OPEN\}:f\(n\)\\leq wf\_\{\\min\}\\\}and repeatedly expands the best eligible node under that secondary priority\([Pearl and Kim 1982](https://arxiv.org/html/2609.10584#bib.bib3)\)\. Dynamic Potential Search \(DPS\) instead ranks OPEN by a potential that changes with the same lower boundfminf\_\{\\min\}\([Gilon et al\. 2016](https://arxiv.org/html/2609.10584#bib.bib4)\)\.

This separation between certification and guidance is powerful, but it creates a feedback loop\. Guided expansions can remain on one minimum\-ffplateau; whilefminf\_\{\\min\}is unchanged, so is the eligibility thresholdw​fminwf\_\{\\min\}\. A good node just outside that threshold cannot benefit from the secondary policy until the lower\-bound frontier advances\. The deterministic policy has no explicit control for making that happen\.

We study a minimal intervention to FS: with probabilitypp, retain its guided FOCAL choice; with probability1−p1\-p, expand a minimum\-ffOPEN node\. This yields Probabilistic Focal Search \(PFS\)\. The intervention does not relax the solution envelope\. Rather, it spends a controlled fraction of selections on the frontier defining that envelope\. The question is empirical as well as theoretical: forced OPEN\-head work may shorten harmful plateaus, but it is overhead when FS already advances effectively\. As a secondary transfer experiment, we apply the same scheduler to DPS, yielding Probabilistic Dynamic Potential Search \(PDPS\)\. This comparison tests whether the mechanism transfers to a different guided policy\.

We evaluate this idea on N\-Puzzle, Pancake Sorting, and the Traveling Salesperson Problem \(TSP\), and evaluate its anytime extension on the metric Generalized Covering TSP \(GCTSP\)\. The results show that probabilistic lower\-bound advancement can improve success and substantially reduce search effort when it admits useful nodes that the guided policy can exploit; APFS also leads the evaluated anytime methods on GCTSP\. We further analyze cases in which the intervention provides little or no benefit, explaining how an already sufficient FOCAL or ineffective guidance over newly admitted nodes can limit the mechanism\. PDPS and APDPS serve as secondary transfer experiments for this dependence on the guided policy\.

This paper contributes:

- •PFS, a tunable Bernoulli scheduler that interleaves guided FOCAL selections with minimum\-ffOPEN selections, together with a bounded\-suboptimality proof;
- •a mechanism analysis identifying when the scheduler helps and when it adds overhead: minimum\-ffselections help when they advance the lower bound and admit nodes that the guided policy can exploit, but not when FOCAL is already sufficient or the new admissions do not improve guided choices; and
- •a cross\-domain evaluation supporting both the scheduler’s effectiveness and the proposed mechanism\. On N\-Puzzle, PFS raises success from 44\.3% to 83\.6%, while reducing penalized mean expansions by 60\.7% and capped mean runtime by 69\.8%\. Across both TSP datasets, it reaches at least 96\.4% success and reduces these metrics by at least 87\.2% and 89\.0%\. Its smaller gains on Pancake, where FOCAL is already sufficient, together with the gains and remaining regressions in the DPS family, are consistent with the identified boundary conditions\. In anytime GCTSP, APFS solves 189/234 medium instances versus 82/234 for AFS\.

## Background and Related Work

Each search nodennrepresents a problem state together with its current path information\. Letg⁡\(n\)g\(n\)be its best known path cost, leth⁡\(n\)h\(n\)be an admissible estimate of the remaining cost, and letf⁡\(n\)=g⁡\(n\)\+h⁡\(n\)f\(n\)=g\(n\)\+h\(n\)\. A\* expands a minimum\-ffnode and returns an optimal solution under standard graph search assumptions\([Hart et al\. 1968](https://arxiv.org/html/2609.10584#bib.bib1)\)\. Weighted A\* \(WA\*\) instead orders byqw​\(n\)=g⁡\(n\)\+w​h​\(n\)q\_\{w\}\(n\)=g\(n\)\+wh\(n\)to obtain aww\-suboptimal solution more quickly\([Pohl 1970](https://arxiv.org/html/2609.10584#bib.bib2)\)\.

#### Focal Search\.

FS maintains the lower boundfmin=minn∈𝑂𝑃𝐸𝑁⁡f⁡\(n\)f\_\{\\min\}=\\min\_\{n\\in\\mathit\{OPEN\}\}f\(n\)and the eligible set

𝐹𝑂𝐶𝐴𝐿=\{n∈𝑂𝑃𝐸𝑁:f⁡\(n\)≤w​fmin\}\.\\mathit\{FOCAL\}=\\\{n\\in\\mathit\{OPEN\}:f\(n\)\\leq wf\_\{\\min\}\\\}\.\(1\)FOCAL can also be defined using an explicit eligibility thresholdCCas𝐹𝑂𝐶𝐴𝐿⁡\(C\)=\{n∈𝑂𝑃𝐸𝑁:f⁡\(n\)≤C\}\\mathit\{FOCAL\}\(C\)=\\\{n\\in\\mathit\{OPEN\}:f\(n\)\\leq C\\\}\. In this paper, we use the multiplicative definition in Equation \([1](https://arxiv.org/html/2609.10584#Sx2.E1)\)\. It selects an eligible node using a secondary priorityd⁡\(n\)d\(n\), which need not itself be admissible\. This decoupling distinguishes focal search from algorithms whose ordering and certificate use the same heuristic\. Anytime Focal Search reuses this structure while tightening the bound after incumbent solutions\([Cohen et al\. 2018](https://arxiv.org/html/2609.10584#bib.bib11)\); our main study concerns the first bounded solution\.

#### Dynamic Potential Search\.

DPS can be viewed as a special case of FS whose secondary priority is the negative dynamic potential,d​\(n\)=−uw​\(n\)d\(n\)=\-u\_\{w\}\(n\)\([Gilon et al\. 2016](https://arxiv.org/html/2609.10584#bib.bib4)\), where

uw​\(n\)=w​fmin−g⁡\(n\)h⁡\(n\)\.u\_\{w\}\(n\)=\\frac\{wf\_\{\\min\}\-g\(n\)\}\{h\(n\)\}\.\(2\)Forh⁡\(n\)\>0h\(n\)\>0,uw​\(n\)≥1u\_\{w\}\(n\)\\geq 1exactly whenf⁡\(n\)≤w​fminf\(n\)\\leq wf\_\{\\min\}\. Under exact potential ordering, a maximum\-potential node in OPEN is therefore in FOCAL, so DPS can maximizeuw​\(n\)u\_\{w\}\(n\)over OPEN without maintaining FOCAL explicitly\. Unlike FS with a fixed secondary priority, however,uw​\(n\)u\_\{w\}\(n\)depends onfminf\_\{\\min\}\. Every change infminf\_\{\\min\}therefore requires the potentials and their ordering to be refreshed before the next selection\. Following the weighted\-graph treatment of DPS\([Gilon et al\. 2017](https://arxiv.org/html/2609.10584#bib.bib5)\), we define anh=0h=0node to have potential\+∞\+\\inftyonly ifg⁡\(n\)≤w​fming\(n\)\\leq wf\_\{\\min\}, and−∞\-\\inftyotherwise\. This endpoint convention is essential for a safe goal test\.

## Probabilistic Focal Search

Algorithm[1](https://arxiv.org/html/2609.10584#alg1)presents PFS\. It retains the OPEN and FOCAL organization of FS but uses a probabilityppto choose between two selection policies\. At iterationtt, it drawsZt∼Bernoulli⁡\(p\)Z\_\{t\}\\sim\\mathrm\{Bernoulli\}\(p\), wherePr⁡\(Zt=1\)=p\\Pr\(Z\_\{t\}=1\)=pandPr⁡\(Zt=0\)=1−p\\Pr\(Z\_\{t\}=0\)=1\-p\. WhenZt=1Z\_\{t\}=1, PFS follows the FS policy and selects the minimum\-ddnode in FOCAL\. WhenZt=0Z\_\{t\}=0, it selects a minimum\-ffnode from OPEN\. Thusp=1p=1recovers FS, whilep=0p=0uses A\*’s primary ordering\.

Algorithm 1Probabilistic Focal Search \(PFS\)1:start node

s0s\_\{0\},

w≥1w\\geq 1, and

p∈\[0,1\]p\\in\[0,1\]
2:

g⁡\(s0\)←0g\(s\_\{0\}\)\\leftarrow 0;

O​P​E​N←\{s0\}OPEN\\leftarrow\\\{s\_\{0\}\\\};

C​L​O​S​E​D←∅CLOSED\\leftarrow\\emptyset
3:

fmin←f⁡\(s0\)f\_\{\\min\}\\leftarrow f\(s\_\{0\}\);

F​O​C​A​L←\{s0\}FOCAL\\leftarrow\\\{s\_\{0\}\\\}
4:while

O​P​E​N≠∅OPEN\\neq\\emptysetdo

5:draw

Z∼Bernoulli⁡\(p\)Z\\sim\\mathrm\{Bernoulli\}\(p\)
6:if

Z=1Z=1then

7:

n←arg⁡minu∈F​O​C​A​L⁡d⁡\(u\)n\\leftarrow\\arg\\min\_\{u\\in FOCAL\}d\(u\)
8:else

9:

n←arg⁡minu∈O​P​E​N⁡f⁡\(u\)n\\leftarrow\\arg\\min\_\{u\\in OPEN\}f\(u\)
10:endif

11:if

G​o​a​l​\(n\)Goal\(n\)then

12:return

nn
13:endif

14:remove

nnfrom OPEN and FOCAL; add

nnto CLOSED

15:relax successors; insert/reopen improved successors in OPEN and in FOCAL when currently eligible

16:if

O​P​E​N≠∅OPEN\\neq\\emptysetthen

17:

fmin′←minu∈O​P​E​N⁡f⁡\(u\)f^\{\\prime\}\_\{\\min\}\\leftarrow\\min\_\{u\\in OPEN\}f\(u\)
18:if

fmin′\>fminf^\{\\prime\}\_\{\\min\}\>f\_\{\\min\}then

19:add newly eligible nodes to FOCAL

20:elseif

fmin′<fminf^\{\\prime\}\_\{\\min\}<f\_\{\\min\}then

21:rebuild FOCAL using threshold

w​fmin′wf^\{\\prime\}\_\{\\min\}
22:endif

23:

fmin←fmin′f\_\{\\min\}\\leftarrow f^\{\\prime\}\_\{\\min\}
24:endif

25:endwhile

26:returnfailure

The initialization places the start node in OPEN and FOCAL and setsfmin=f⁡\(s0\)f\_\{\\min\}=f\(s\_\{0\}\)\. At a non\-goal expansion, the selected node is removed from both frontier structures and its successors are generated\. Standard duplicate relaxation and reopening are abbreviated: every inserted or improved successor is placed in FOCAL exactly when it satisfies the current threshold\. The algorithm then recomputesfminf\_\{\\min\}\. If it increases, the enlarged threshold admits the newly eligible OPEN nodes; if it decreases after reopening, FOCAL is rebuilt to remove nodes outside the reduced threshold\. Both selection branches choose an eligible node, since the OPEN head hasf=fminf=f\_\{\\min\}, so a selected goal satisfies the samew​fminwf\_\{\\min\}envelope as in FS\.

#### Secondary transfer to DPS\.

To test whether the scheduler transfers beyond FS, we also instantiate it in DPS as PDPS\. PDPS uses the same Bernoulli choice and minimum\-ffOPEN branch\. It changes only the guided branch: whenZ=1Z=1, it selectsn=arg⁡maxu∈F​O​C​A​L​uw​\(u\)n=\\arg\\max\_\{u\\in FOCAL\}u\_\{w\}\(u\)under Equation[2](https://arxiv.org/html/2609.10584#Sx2.E2)\. Under exact potential ordering, the maximum over OPEN lies in FOCAL, so this restriction preserves the DPS choice while keeping only eligible potential groups active\. Thusp=1p=1recovers DPS andp=0p=0again uses A\*’s primary ordering\. Regardless of queue ordering, PDPS accepts a selected goal only after the exact checkg⁡\(n\)≤w​fming\(n\)\\leq wf\_\{\\min\}; otherwise the goal remains in OPEN\.

###### Assumption 1\.

Edge costs are nonnegative, and the primary heuristichhis admissible and nonnegative\. Standard duplicate detection and reopening maintain the frontier invariantfmin≤C∗f\_\{\\min\}\\leq C^\{\*\}until a goal is accepted, whereC∗C^\{\*\}is the optimal solution cost\.

###### Theorem 1\(Certificate preservation\)\.

Any goal returned by first\-solution PFS has cost at mostw​C∗wC^\{\*\}\.

###### Proof\.

Letngn\_\{g\}be the returned goal\. The acceptance condition and frontier invariant give

C=g⁡\(ng\)=f⁡\(ng\)≤w​fmin≤w​C∗\.C=g\(n\_\{g\}\)=f\(n\_\{g\}\)\\leq wf\_\{\\min\}\\leq wC^\{\*\}\.\(3\)The randomized branch changes which node is considered, but neither the lower bound nor the acceptance condition\. The result therefore holds for everyp∈\[0,1\]p\\in\[0,1\]\. ∎

The same certificate transfers to PDPS because it uses the same lower bound and exact goal\-acceptance condition\. Appendix[A](https://arxiv.org/html/2609.10584#A1.SSx1)verifies that its guided DPS choice is also eligible under exact potential ordering\.

###### Lemma 1\.

PFS and FS cannot return a goal whilefmin<C∗/wf\_\{\\min\}<C^\{\*\}/w\.

###### Proof\.

Iffmin<C∗/wf\_\{\\min\}<C^\{\*\}/w, every acceptable goal would haveg⁡\(n\)≤w​fmin<C∗g\(n\)\\leq wf\_\{\\min\}<C^\{\*\}\. This contradicts the definition ofC∗C^\{\*\}\. ∎

This necessary threshold motivates the OPEN\-head branch of PFS\. By expanding a current minimum\-ffnode with probability1−p1\-p, PFS attempts to clear the minimum\-ffplateau and raisefminf\_\{\\min\}towardC∗/wC^\{\*\}/w, thereby raising the threshold and potentially admitting additional guided nodes\. Oncefmin≥C∗/wf\_\{\\min\}\\geq C^\{\*\}/w, any optimal goal node that has already been generated and remains in OPEN satisfiesf⁡\(n\)=C∗≤w​fminf\(n\)=C^\{\*\}\\leq wf\_\{\\min\}and is therefore in FOCAL\.

PDPS inherits the same threshold motivation; the transfer experiments test whether its potential\-based guided policy can exploit newly eligible nodes as effectively as PFS\.

## Experiments

We evaluate PFS and PDPS through four questions: whether they improve their deterministic parents, FS and DPS \(RQ1\); how lower\-bound advancement changes FOCAL and explains their behavior \(RQ2\); how performance varies withpp\(RQ3\); and whether the scheduler benefits their anytime variants, APFS and APDPS \(RQ4\)\. PFS is the primary method, while PDPS tests whether the mechanism transfers to potential\-based guidance\.

Table 1:First\-solution performance over the seven tested bounds atp=0\.70p=0\.70\. P/D denotes probabilistic/deterministic; K and M denote thousands and millions\. Mean expansions use all runs\. Within each setting, an unsuccessful run is assigned the largest expansion count observed across the two compared algorithms, and Exp\. ratio is the ratio of the resulting P/D means\. Unsuccessful runs contribute the time limit to Time P/D\.Figure 1:Probabilistic/deterministic node\-expansion ratios atw=1\.25w=1\.25,p=0\.70p=0\.70\. Labels report deterministic→\\rightarrowprobabilistic solved counts\. The DPS\-family rows use the Envelope FOCAL implementation\. The vertical line denotes equal effort: points to its left favor the probabilistic method, whereas points to its right favor the deterministic counterpart\.### Experimental Setup

![Refer to caption](https://arxiv.org/html/2609.10584v1/figures/npuzzle_regular_success_p070.png)

\(a\) Regular costs

![Refer to caption](https://arxiv.org/html/2609.10584v1/figures/npuzzle_heavy_success_p070.png)

\(b\) Heavy costs

![Refer to caption](https://arxiv.org/html/2609.10584v1/figures/npuzzle_inverse_success_p070.png)

\(c\) Inverse costs

Figure 2:Success rate on Korf’s 100 N\-Puzzle instances across suboptimality bounds\. PFS and PDPS usep=0\.70p=0\.70; the DPS\-family curves use Envelope FOCAL\. Deterministic baselines use the same weight grid where applicable\.![Refer to caption](https://arxiv.org/html/2609.10584v1/figures/npuzzle_regular_expanded_all_p070.png)

\(a\) Regular costs

![Refer to caption](https://arxiv.org/html/2609.10584v1/figures/npuzzle_heavy_expanded_all_p070.png)

\(b\) Heavy costs

![Refer to caption](https://arxiv.org/html/2609.10584v1/figures/npuzzle_inverse_expanded_all_p070.png)

\(c\) Inverse costs

Figure 3:Mean node expansions over all Korf N\-Puzzle runs, including unsuccessful executions\.![Refer to caption](https://arxiv.org/html/2609.10584v1/figures/npuzzle_regular_runtime_p070.png)

\(a\) Regular costs

![Refer to caption](https://arxiv.org/html/2609.10584v1/figures/npuzzle_heavy_runtime_p070.png)

\(b\) Heavy costs

![Refer to caption](https://arxiv.org/html/2609.10584v1/figures/npuzzle_inverse_runtime_p070.png)

\(c\) Inverse costs

Figure 4:Mean running time over all Korf N\-Puzzle runs, with unsuccessful executions assigned the time limit\.Figure 5:Lower\-bound and FOCAL\-size trajectories for heavy N\-Puzzlenpuzzle\_0039,w=1\.25w=1\.25,p=0\.70p=0\.70, seed 42\. PFS terminates at 43,972 expansions and FS at 444,774\.![Refer to caption](https://arxiv.org/html/2609.10584v1/figures/pancake_101_trajectory.png)Figure 6:Lower\-bound and FOCAL trajectories for Pancake\-101pancake\_0071\(w=1\.25w=1\.25,p=0\.80p=0\.80\)\. FS expands 147 nodes and PFS expands 177\.

The benchmarks cover Korf’s 100 15\-Puzzle instances\([Korf 1985](https://arxiv.org/html/2609.10584#bib.bib6)\)with unit, tile\-value, and inverse\-tile costs\([Gilon et al\. 2017](https://arxiv.org/html/2609.10584#bib.bib5)\); 100\-instance Pancake sets of sizes 40, 60, 80, and 101; and two Euclidean TSP datasets, each has 100 instances, containing 40 and 50 cities, respectively\. The anytime study uses 81 small and 234 medium metric instances of the Generalized Covering Traveling Salesperson Problem \(GCTSP\), generated from TSPLIB instances\([Reinelt 1991](https://arxiv.org/html/2609.10584#bib.bib9)\)\. In GCTSP, a tour visits facilities until they collectively cover a required customer quota and then returns to the depot\([Shaelaie et al\. 2014](https://arxiv.org/html/2609.10584#bib.bib10);[Cohen et al\. 2018](https://arxiv.org/html/2609.10584#bib.bib11)\)\.

For both heuristics, N\-Puzzle uses cost\-adjusted Manhattan distance plus linear conflict\([Hansson et al\. 1992](https://arxiv.org/html/2609.10584#bib.bib8)\), while Pancake uses GAP\([Helmert 2010](https://arxiv.org/html/2609.10584#bib.bib7)\)\. For TSP, the primary heuristic combines a minimum spanning tree \(MST\) over the unvisited cities with connections from the current city and back to the depot\. The MST therefore lower\-bounds the cost required to connect the cities that remain in an unfinished tour\. FS and PFS use depth or nearest\-neighbor secondary guidance on TSP\-40 and nearest\-neighbor guidance on TSP\-50\. DPS and PDPS use the same primary heuristic as their FS and PFS counterparts; their node ordering does not use the secondary heuristic\. DPS and PDPS use the same FOCAL implementation, called Envelope FOCAL\. It orders OPEN byffand selects the maximum\-potential group among FOCAL\-eligible states\.

We testw∈\{1\.05,1\.10,1\.15,1\.20,1\.25,1\.50,2\.00\}w\\in\\\{1\.05,1\.10,1\.15,1\.20,1\.25,1\.50,2\.00\\\}andp∈\{0\.60,0\.70,0\.80\}p\\in\\\{0\.60,0\.70,0\.80\\\}\. We usep=0\.70p=0\.70as the main setting for all domains and reportp=0\.60p=0\.60andp=0\.80p=0\.80in the sensitivity analysis; the seven\-bound first\-solution results contain 50,400 runs\. Generated\-node limits are five million for N\-Puzzle and Pancake, and twenty million for TSP and anytime GCTSP\. The datasets and source code are provided in the supplementary material\.

#### Computing environment\.

Algorithms are implemented in C\+\+17 \(g\+\+ \-O3\) and evaluated under Linux on Intel i5\-13500 and AMD Ryzen Threadripper PRO 5975WX workstations\. Each run uses a single dedicated CPU thread with a 300\-second wall\-clock limit and memory monitoring\.

### RQ1: Does PFS Improve Success and Search Effort?

Table[1](https://arxiv.org/html/2609.10584#Sx4.T1)reports success, expansions, and capped running time over all seven tested bounds\. Each row of Figure[1](https://arxiv.org/html/2609.10584#Sx4.F1)places the probabilistic/deterministic expansion ratio beside the corresponding solved counts, so efficiency can be read together with the ability to find a solution\. PFS gives clear improvements on N\-Puzzle and TSP\. On N\-Puzzle, it raises success from 44\.3% to 83\.6%, reduces mean penalized expansions from 1\.902M to 748\.0K \(ratio 0\.393\), and reduces capped mean time from 169\.25 to 51\.11 seconds\. On TSP\-40, success rises from 78\.6% to 99\.4%, the expansion ratio is 0\.058, and mean time falls from 82\.98 to 3\.56 seconds\. TSP\-50 shows the same pattern: 96\.4% versus 58\.3% success, a 0\.128 expansion ratio, and 14\.93 versus 135\.36 seconds\. On Pancake, the two methods have similar success \(72\.0% versus 70\.2%\)\. Under Table[1](https://arxiv.org/html/2609.10584#Sx4.T1)’s all\-run penalty, PFS has a lower expansion ratio \(0\.874\) and capped mean time \(84\.51 versus 90\.04 seconds\)\. RQ2 explains why this aggregate result does not imply lower effort on the Pancake instances solved by both methods\.

The all\-run comparison also favors PDPS over DPS\. PDPS/DPS success is 77\.7%/65\.4% on N\-Puzzle, 95\.8%/94\.0% on Pancake, 96\.0%/89\.3% on TSP\-40, and 88\.7%/79\.1% on TSP\-50\. The corresponding penalized expansion ratios are 0\.757, 0\.793, 0\.586, and 0\.658, while capped mean time is also lower in every domain\. Runtime for both methods is sensitive to the FOCAL implementation because each change infminf\_\{\\min\}changes the potential ordering\.

Using TSP\-50 as an example, Table[2](https://arxiv.org/html/2609.10584#Sx4.T2)illustrates both the benefit of PFS and when probabilistic DPS helps or adds work\. Forw≤1\.25w\\leq 1\.25, PFS solves 77–100 instances versus 25–71 for FS, with mean paired expansion ratios of 0\.061–0\.285 and runtime ratios of 0\.039–0\.332 on commonly solved instances\. Atw=2w=2, both methods solve every instance, but the expansion and runtime ratios rise above 1\. PDPS similarly improves DPS at the tight bounds: forw≤1\.15w\\leq 1\.15, it solves 40–99 instances versus 12–95, and both paired ratios remain below 1\. Once both solve all instances \(w≥1\.20w\\geq 1\.20\), however, the OPEN\-head branch adds work and the paired ratios exceed 1\. Its greater tight\-bound success nevertheless produces the favorable all\-run TSP\-50 values in Table[1](https://arxiv.org/html/2609.10584#Sx4.T1)\.

Figure[1](https://arxiv.org/html/2609.10584#Sx4.F1)fixesw=1\.25w=1\.25to show how the expansion effect varies by configuration rather than suggesting that the probabilistic scheduler is uniformly beneficial\. PFS lies well to the left of equal effort on N\-Puzzle and TSP but slightly to the right on Pancake\. Atw=1\.25w=1\.25, PDPS lies to the left on N\-Puzzle but to the right on Pancake and TSP, where both DPS variants solve every instance\. Advancingfminf\_\{\\min\}helps only when the guided policy can exploit newly eligible states; otherwise, OPEN\-head selections add work\. Figures[6](https://arxiv.org/html/2609.10584#Sx4.F6)–[6](https://arxiv.org/html/2609.10584#Sx4.F6)conclude RQ1 by comparing N\-Puzzle success, node expansions, and runtime across algorithms and bounds\.

Table 2:TSP\-50 results\. Expansion and runtime entries are mean paired probabilistic/deterministic ratios on commonly solved instances; values below 1 favor the probabilistic method\.
### RQ2: How Does Lower\-Bound Advancement Change FOCAL?

The OPEN\-head branch helps only when clearing a minimum\-ffplateau raisesfminf\_\{\\min\}, enlarges the thresholdw​fminwf\_\{\\min\}, and admits nodes that the guided FOCAL policy can exploit\. Otherwise, an OPEN\-head selection merely replaces a guided expansion\. Figures[6](https://arxiv.org/html/2609.10584#Sx4.F6)and[6](https://arxiv.org/html/2609.10584#Sx4.F6)illustrate these two cases\.

On heavy N\-Puzzle \(Figure[6](https://arxiv.org/html/2609.10584#Sx4.F6)\), PFS clearsfminf\_\{\\min\}plateaus earlier\. Each threshold increase can admit a batch of nodes into FOCAL, after which the secondary heuristic guides the search through the enlarged eligible set\. PFS terminates after 43,972 expansions, compared with 444,774 for FS\. This is the intended mechanism: lower\-bound advancement gives the guided policy earlier access to useful nodes\.

On Pancake \(Figure[6](https://arxiv.org/html/2609.10584#Sx4.F6)\), integer path costs and GAP values place many states at the sameff\. Herefmin=98f\_\{\\min\}=98throughout, and the initial thresholdw​fmin=122\.5wf\_\{\\min\}=122\.5already exceeds the returned solution cost 117\. Although the goal is generated later, it is immediately eligible without any increase infminf\_\{\\min\}\. PFS therefore performs the same 147 guided expansions as FS plus 30 OPEN\-head expansions, without creating a more useful FOCAL envelope\. Thus raising the lower bound is not sufficient by itself: PFS benefits only when the resulting FOCAL admissions improve the choices available to the guided policy\.

### RQ3: How Sensitive Is PFS to the Probabilitypp?

Acrossp∈\{0\.60,0\.70,0\.80\}p\\in\\\{0\.60,0\.70,0\.80\\\}and the seven tested bounds, PFS consistently reduces expansions on commonly solved N\-Puzzle and TSP instances, with median setting\-level ratios of 0\.121–0\.151 and 0\.021–0\.029\. On Pancake, the ratios are 1\.222–1\.629 and decrease asppincreases, because fewer selections use the unhelpful OPEN\-head branch\. These paired ratios exclude failures; atp=0\.70p=0\.70, the paired Pancake ratio is 1\.354, whereas the slightly higher PFS success rate yields the all\-run penalized ratio 0\.874 in Table[1](https://arxiv.org/html/2609.10584#Sx4.T1)\. Thus, the conclusions of RQ1 are stable across the tested probabilities, but no universalppemerges\. A suitable value appears to depend on the domain–heuristic pair and its observedfminf\_\{\\min\}\-plateau structure: smallerppfavors lower\-bound advancement when FOCAL admission is delayed, whereas largerppfavors already effective guided selection\.

### RQ4: Does Probabilistic Scheduling Improve Anytime Search?

We compare AFS, APFS, ADPS, and APDPS on 81 small and 234 medium metric GCTSP instances\. All four use the admissible quota\-Kruskal\-forest \(QKF\) lower bound; AFS and APFS use prize deficit as their secondary FOCAL key, whereas ADPS and APDPS use potential ordering with Envelope FOCAL\. The anytime schedule starts atw0=3w\_\{0\}=3, updatesw←Cbest/fmin−0\.10w\\leftarrow C\_\{\\mathrm\{best\}\}/f\_\{\\min\}\-0\.10, and stops atw≤1\.05w\\leq 1\.05\.

Figure[8](https://arxiv.org/html/2609.10584#Sx4.F8)shows that APFS finds at least one solution for 81/81 small and 189/234 medium instances, compared with 76/81 and 82/234 for AFS\. Envelope FOCAL APDPS solves 80/81 small and 74/234 medium instances, versus 78/81 and 25/234 for ADPS\. Thus APDPS improves its deterministic parent, especially on the medium set, while APFS retains the highest first\-solution coverage among all four methods\.

Figure 7:Cumulative number of matched GCTSP instances for which AFS, APFS, ADPS, or APDPS has found an incumbent by timett\.Figure 8:Time to reach a cost within 1% of the lowest final value found by AFS, APFS, ADPS, or APDPS on each matched GCTSP instance\.Figure[8](https://arxiv.org/html/2609.10584#Sx4.F8)evaluates subsequent solution refinement\. For each instance, the target is within 1% of the lowest final cost returned by any of the four evaluated methods\. APFS reaches this target on 81 small and 181 medium instances, compared with 61 and 34 for AFS\. ADPS/APDPS reach it on 76/73 small and 21/42 medium instances\. APDPS therefore doubles the medium target count of ADPS, although ADPS is slightly better on the small set\. On their common successes, APDPS/ADPS median expansion ratios are 0\.950 and 0\.944, and runtime ratios are 0\.513 and 0\.735, for small and medium instances, respectively\.

The DPS\-family result shows that probabilistic lower\-bound advancement also transfers to potential ordering when FOCAL admission limits progress\. APFS remains strongest because prize deficit explicitly directs newly eligible states toward satisfying the residual quota, whereas dynamic potential does not encode this feasibility signal\.

## Discussion and Conclusion

PFS improves bounded\-suboptimal focal search by following the guided FOCAL policy with probabilityppand expanding a minimum\-ffOPEN node with probability1−p1\-p\. The latter branch can clear minimum\-ffplateaus and raisefminf\_\{\\min\}, so the larger thresholdw​fminwf\_\{\\min\}admits additional nodes for guided selection while preserving theww\-suboptimality guarantee\.

Experiments on N\-Puzzle, Pancake Sorting, and two TSP datasets show that this mechanism improves search most clearly when delayed FOCAL admission is a bottleneck\. PFS substantially increases success and reduces expansions and running time on N\-Puzzle and TSP, while Pancake demonstrates the smaller gain when the initial FOCAL is already sufficient\. Envelope FOCAL PDPS improves the all\-run measures over DPS, although common\-success results on Pancake and looser TSP bounds show that OPEN\-head selections add work when potential guidance already succeeds\. On anytime GCTSP, APFS solves 189/234 medium instances versus 82/234 for AFS, while Envelope FOCAL APDPS solves 74/234 versus 25/234 for ADPS\. APFS still leads all evaluated methods\. Overall, activefminf\_\{\\min\}advancement improves focal search when FOCAL admission limits progress and the guided policy can use the newly eligible states\.

## Appendix AAppendix

### Exact DPS Eligibility

Under the main theorem’s assumptions, an exact maximum\-potential node lies inf⁡\(n\)≤w​fminf\(n\)\\leq wf\_\{\\min\}\. Letmmminimizeffin OPEN\. Forh⁡\(m\)\>0h\(m\)\>0,uw​\(m\)=\[w⁡\(g⁡\(m\)\+h⁡\(m\)\)−g⁡\(m\)\]/h⁡\(m\)=w\+\(w−1\)​g​\(m\)/h⁡\(m\)≥1u\_\{w\}\(m\)=\[w\(g\(m\)\+h\(m\)\)\-g\(m\)\]/h\(m\)=w\+\(w\-1\)g\(m\)/h\(m\)\\geq 1\. Thus a maximum\-potentialnnsatisfiesuw​\(n\)≥1u\_\{w\}\(n\)\\geq 1, equivalentlyf⁡\(n\)≤w​fminf\(n\)\\leq wf\_\{\\min\}\. Exact DPS therefore need only consider FOCAL, which contains a minimum\-ffnode whenever OPEN is nonempty andw≥1w\\geq 1\.

### Admissible Quota–Kruskal\-Forest Lower Bound

For statenn, letxxbe its current vertex,ddthe depot,U⁡\(n\)U\(n\)its covered customers, andR⁡\(n\)=max⁡\{0,Q−\|U⁡\(n\)\|\}R\(n\)=\\max\\\{0,Q\-\|U\(n\)\|\\\}the residual quota\. LetCv​\(n\)C\_\{v\}\(n\)be the uncovered customers covered byv∉\{x,d\}v\\notin\\\{x,d\\\}and sort the positive capacities asC\(1\)≥⋯≥C\(m\)C\_\{\(1\)\}\\geq\\cdots\\geq C\_\{\(m\)\}\. Setk⁡\(n\)=min⁡\{j:∑i=1jC\(i\)​\(n\)≥R⁡\(n\)\}k\(n\)=\\min\\\{j:\\sum\_\{i=1\}^\{j\}C\_\{\(i\)\}\(n\)\\geq R\(n\)\\\}; every feasible completion must visit at leastk⁡\(n\)k\(n\)such vertices\. ForR⁡\(n\)\>0R\(n\)\>0, form the complete undirected graph on\{x,d\}∪\{v:Cv​\(n\)\>0\}\\\{x,d\\\}\\cup\\\{v:C\_\{v\}\(n\)\>0\\\}; QKF is the cost of its cheapeste\(n\)=k\(n\)\+𝟏\[x≠d\]e\(n\)=k\(n\)\+\\mathbf\{1\}\[x\\neq d\]acyclic edges, selected by Kruskal\([Kruskal 1956](https://arxiv.org/html/2609.10584#bib.bib12)\)\. IfR⁡\(n\)=0R\(n\)=0, it is00atddandc⁡\(x,d\)c\(x,d\)otherwise\. Every feasible completion contains such an acyclic subset no more costly than itself; hencehQKF​\(n\)≤h∗​\(n\)h\_\{\\mathrm\{QKF\}\}\(n\)\\leq h^\{\*\}\(n\)and QKF is admissible\.

## References

- Cohenet al\.\(2018\)L\. Cohen, M\. Greco, H\. Ma, C\. Hernández, A\. Felner, T\. K\. S\. Kumar, and S\. KoenigAnytime focal search with applications\.InProceedings of the Twenty\-Seventh International Joint Conference on Artificial Intelligence,pp\. 1434–1441\.External Links:[Document](https://dx.doi.org/10.24963/ijcai.2018/199)Cited by:[Focal Search\.](https://arxiv.org/html/2609.10584#Sx2.SS0.SSS0.Px1.p1.2),[Experimental Setup](https://arxiv.org/html/2609.10584#Sx4.SSx1.p1.1)\.
- Gilonet al\.\(2016\)D\. Gilon, A\. Felner, and R\. SternDynamic potential search—a new bounded suboptimal search\.InProceedings of the Ninth Annual Symposium on Combinatorial Search,Vol\.7,pp\. 36–44\.External Links:[Document](https://dx.doi.org/10.1609/socs.v7i1.18392)Cited by:[Introduction](https://arxiv.org/html/2609.10584#Sx1.p1.1),[Dynamic Potential Search\.](https://arxiv.org/html/2609.10584#Sx2.SS0.SSS0.Px2.p1.1)\.
- Gilonet al\.\(2017\)D\. Gilon, A\. Felner, and R\. SternDynamic potential search on weighted graphs\.InProceedings of the Tenth Annual Symposium on Combinatorial Search,Vol\.8,pp\. 119–123\.External Links:[Document](https://dx.doi.org/10.1609/socs.v8i1.18436)Cited by:[Dynamic Potential Search\.](https://arxiv.org/html/2609.10584#Sx2.SS0.SSS0.Px2.p1.2),[Experimental Setup](https://arxiv.org/html/2609.10584#Sx4.SSx1.p1.1)\.
- Hanssonet al\.\(1992\)O\. Hansson, A\. Mayer, and M\. YungCriticizing solutions to relaxed models yields powerful admissible heuristics\.Information Sciences63\(3\),pp\. 207–227\.External Links:[Document](https://dx.doi.org/10.1016/0020-0255%2892%2990070-O)Cited by:[Experimental Setup](https://arxiv.org/html/2609.10584#Sx4.SSx1.p2.1)\.
- Hartet al\.\(1968\)P\. E\. Hart, N\. J\. Nilsson, and B\. RaphaelA formal basis for the heuristic determination of minimum cost paths\.IEEE Transactions on Systems Science and Cybernetics4\(2\),pp\. 100–107\.External Links:[Document](https://dx.doi.org/10.1109/TSSC.1968.300136)Cited by:[Background and Related Work](https://arxiv.org/html/2609.10584#Sx2.p1.1)\.
- Helmert \(2010\)M\. HelmertLandmark heuristics for the pancake problem\.InProceedings of the Third Annual Symposium on Combinatorial Search,Vol\.1,pp\. 109–110\.External Links:[Document](https://dx.doi.org/10.1609/socs.v1i1.18176)Cited by:[Experimental Setup](https://arxiv.org/html/2609.10584#Sx4.SSx1.p2.1)\.
- Korf \(1985\)R\. E\. KorfDepth\-first iterative\-deepening: an optimal admissible tree search\.Artificial Intelligence27\(1\),pp\. 97–109\.External Links:[Document](https://dx.doi.org/10.1016/0004-3702%2885%2990084-0)Cited by:[Experimental Setup](https://arxiv.org/html/2609.10584#Sx4.SSx1.p1.1)\.
- Kruskal \(1956\)J\. B\. KruskalOn the shortest spanning subtree of a graph and the traveling salesman problem\.Proceedings of the American Mathematical Society7\(1\),pp\. 48–50\.External Links:[Document](https://dx.doi.org/10.1090/S0002-9939-1956-0078686-7)Cited by:[Appendix A](https://arxiv.org/html/2609.10584#A1.SSx2.p1.1)\.
- Pearl and Kim \(1982\)J\. Pearl and J\. H\. KimStudies in semi\-admissible heuristics\.IEEE Transactions on Pattern Analysis and Machine IntelligencePAMI\-4\(4\),pp\. 392–399\.External Links:[Document](https://dx.doi.org/10.1109/TPAMI.1982.4767270)Cited by:[Introduction](https://arxiv.org/html/2609.10584#Sx1.p1.1)\.
- Pohl \(1970\)I\. PohlHeuristic search viewed as path finding in a graph\.Artificial Intelligence1\(3–4\),pp\. 193–204\.External Links:[Document](https://dx.doi.org/10.1016/0004-3702%2870%2990007-X)Cited by:[Background and Related Work](https://arxiv.org/html/2609.10584#Sx2.p1.1)\.
- Reinelt \(1991\)G\. ReineltTSPLIB—a traveling salesman problem library\.ORSA Journal on Computing3\(4\),pp\. 376–384\.External Links:[Document](https://dx.doi.org/10.1287/ijoc.3.4.376)Cited by:[Experimental Setup](https://arxiv.org/html/2609.10584#Sx4.SSx1.p1.1)\.
- Shaelaieet al\.\(2014\)M\. H\. Shaelaie, M\. Salari, and Z\. Naji\-AzimiThe generalized covering traveling salesman problem\.Applied Soft Computing24,pp\. 867–878\.External Links:[Document](https://dx.doi.org/10.1016/j.asoc.2014.08.057)Cited by:[Experimental Setup](https://arxiv.org/html/2609.10584#Sx4.SSx1.p1.1)\.