Front-to-Attractors: Modifying the Front-to-Front Heuristic in Bidirectional Search

# Front-to-Attractors: Modifying the Front-to-Front Heuristic in Bidirectional Search
Source: [https://arxiv.org/html/2606.07047](https://arxiv.org/html/2606.07047)
###### Abstract

Heuristics play a central role in the performance of bidirectional search algorithms, which commonly rely on two main classes\.Front\-to\-end\(F2E\) heuristics estimate the distance from a statessto the target of the search \(the𝑔𝑜𝑎𝑙\\mathit\{goal\}for forward search or the𝑠𝑡𝑎𝑟𝑡\\mathit\{start\}for backward search\)\. In contrast,front\-to\-front\(F2F\) heuristics estimate the distance fromssto the opposite search frontier using a pairwise functionh​\(s,s′\)h\(s,s^\{\\prime\}\), wheres′s^\{\\prime\}ranges over frontier states\. Although F2F heuristics are typically more informative and therefore reduce the number of node expansions, their reliance on extensive pairwise evaluations incurs substantial computational overhead\. To address this limitation, we introduce a new heuristic class,front\-to\-attractors\(F2A\), that preserves much of the informativeness of F2F while dramatically reducing its computational cost\. Rather than evaluating distances to all states on the opposite frontier, F2A estimates the distance fromssto a small, dynamically maintained set ofattractorsin the opposite search direction\. These attractors serve as a surrogate for the full frontier, enabling rich heuristic guidance at a fraction of the computational expense while maintaining the optimality guarantees offered by F2F\. We evaluate F2A across multiple domains and show that it reduces the number of pairwise evaluations by up to11\.2×11\.2\\timescompared to F2F, while achieving4\.8×4\.8\\timesfewer node expansions than F2E on average\.

## Introduction

Bidirectional heuristic search \(Bi\-HS\) aims to find the least\-cost path between two states by running a forward and backward search simultaneously, reducing effective search depth as the two frontiers meet\. A central design choice in Bi\-HS is the heuristic used to guide these searches\. Most existing algorithms usefront\-to\-end\(F2E\) heuristics, which estimate the cost from a state to the target of the current search direction \(goalfor forward search orstartfor backward search\)\. Although inexpensive, F2E heuristics offer weak guidance because they treat the two searches independently and ignore the progress of the opposite frontier \(i\.e\., Open list\)\. In contrast,front\-to\-front\(F2F\) heuristics estimate the distance from a state to the opposite frontier using a pairwise functionh​\(s,s′\)h\(s,s^\{\\prime\}\), wheres′s^\{\\prime\}ranges over the states in the opposite frontier\. F2F heuristics are more informative\(Siaget al\.[2023](https://arxiv.org/html/2606.07047#bib.bib19)\)and typically require fewer state expansions to find a solution\. Their drawback is computational cost: evaluating the heuristic of a state in one direction requires pairwise evaluations between the state and all states in the opposite frontier\.

Due to this overhead leading to long planning times, most work on improving Bi\-HS focuses on F2E methods, proposing enhanced expansion rules, stronger termination conditions, and effective pruning strategies\(Sadhukhan[2013](https://arxiv.org/html/2606.07047#bib.bib12); Holteet al\.[2017](https://arxiv.org/html/2606.07047#bib.bib8); Shahamet al\.[2017](https://arxiv.org/html/2606.07047#bib.bib10); Eckerleet al\.[2017](https://arxiv.org/html/2606.07047#bib.bib9); Chenet al\.[2017](https://arxiv.org/html/2606.07047#bib.bib11); Sewell and Jacobson[2021](https://arxiv.org/html/2606.07047#bib.bib13); Shperberget al\.[2019](https://arxiv.org/html/2606.07047#bib.bib14); Wanget al\.[2025](https://arxiv.org/html/2606.07047#bib.bib16)\)\. Only a few approaches attempt to exploit or refine F2F heuristics\(Felneret al\.[2010](https://arxiv.org/html/2606.07047#bib.bib20); Lippiet al\.[2012](https://arxiv.org/html/2606.07047#bib.bib21),[2016](https://arxiv.org/html/2606.07047#bib.bib22); Mayer and Krebsbach[2019](https://arxiv.org/html/2606.07047#bib.bib18); Alcázar[2021](https://arxiv.org/html/2606.07047#bib.bib17)\)\. Although F2F\-based algorithms offer strong potential as their heuristics are more informative and often reduce the number of state expansions, they remain significantly slower in practice because heuristic evaluation scales quadratically with frontier size\(Siaget al\.[2023](https://arxiv.org/html/2606.07047#bib.bib19)\)\. Techniques that try to represent the frontier with a smaller set exist, but give suboptimal solutions\(Lavasaniet al\.[2025](https://arxiv.org/html/2606.07047#bib.bib28)\)\.

To overcome the overhead associated with F2F heuristics, this manuscript introduces a new heuristic class, front\-to\-attractors \(F2A\), that retains much of the informativeness of F2F while greatly reducing its computational cost\. The approach leverages the attractor representation introduced inZouet al\.\([2025](https://arxiv.org/html/2606.07047#bib.bib1)\)\. Instead of comparingssagainst all states on the opposite frontier, F2A evaluates distances to a small, dynamically maintained set ofattractors\. These attractors serve as a compact surrogate for the full frontier, enabling rich heuristic guidance at a fraction of the computational expense while preserving the optimality guarantees of F2F\. We evaluate F2A across multiple domains, including 2D grid pathfinding, Sliding Tiles, and Pancake puzzle, and show that it reduces the number of pairwise heuristic evaluations by up to11\.2×11\.2\\timescompared to F2F, while achieving4\.8×4\.8\\timesfewer node expansions than F2E on average\.

## Background

A Bi\-HS problem instanceI=\(G,s​t​a​r​t,g​o​a​l,hF,hB\)I=\(G,start,goal,h\_\{F\},h\_\{B\}\)consists of a graphG=\(V,E\)G=\(V,E\), as​t​a​r​tstartstate, ag​o​a​lgoalstate, and a forward \(F\) and backward \(B\) heuristichF,hBh\_\{F\},h\_\{B\}\. The cost of the shortest path between statessands′s^\{\\prime\}inGGis denoted byc​\(s,s′\)c\(s,s^\{\\prime\}\)\. The objective is to find a path froms​t​a​r​tstarttog​o​a​lgoalwith optimal costC∗C^\{\*\}\. Bi\-HS algorithms perform two searches simultaneously: a forward search froms​t​a​r​tstartand a backward search fromg​o​a​lgoal\. Each search directionD∈\{F,B\}D\\in\\\{F,B\\\}maintains its own Open list,O​p​e​nDOpen\_\{D\}\. For a statess,gD​\(s\),hD​\(s\),fD​\(s\)g\_\{D\}\(s\),h\_\{D\}\(s\),f\_\{D\}\(s\)denote itsgg\-,hh\-, andff\-values in directionDD\. The opposite direction is denoted byO​DOD\.

front\-to\-end\(F2E\) heuristics use a forward heuristichF:𝒮→ℝ≥0h\_\{F\}:\\mathcal\{S\}\\rightarrow\\mathbb\{R\}\_\{\\geq 0\}that estimates the cost from any state tog​o​a​lgoaland a backward heuristichB:𝒮→ℝ≥0h\_\{B\}:\\mathcal\{S\}\\rightarrow\\mathbb\{R\}\_\{\\geq 0\}that estimates the cost from any state tos​t​a​r​tstart\. Theff\-value is computed asfD​\(s\)=gD​\(s\)\+hD​\(s\)f\_\{D\}\(s\)=g\_\{D\}\(s\)\+h\_\{D\}\(s\)\.front\-to\-front\(F2F\) heuristics\(Sint and de Champeaux[1977](https://arxiv.org/html/2606.07047#bib.bib3)\)use a pairwise heuristich:𝒮×𝒮→ℝ≥0h:\\mathcal\{S\}\\times\\mathcal\{S\}\\rightarrow\\mathbb\{R\}\_\{\\geq 0\}that estimates the cost between any pair of states\. The F2F heuristic of a statessin directionDDis computed by estimating the cost betweenssand the opposite frontier\. Theff\-value isfD​\(s\)=gD​\(s\)\+mins′∈O​p​e​nO​D⁡\(h​\(s,s′\)\+gO​D​\(s′\)\)f\_\{D\}\(s\)=g\_\{D\}\(s\)\+\\min\_\{s^\{\\prime\}\\in Open\_\{OD\}\}\(h\(s,s^\{\\prime\}\)\+g\_\{OD\}\(s^\{\\prime\}\)\)\. We use the same definitions for bi\-admissibility and bi\-consistency as\(Eckerleet al\.[2017](https://arxiv.org/html/2606.07047#bib.bib9)\)\.

![Refer to caption](https://arxiv.org/html/2606.07047v1/attractor_p3.png)Figure 1:Attractors are shown as circles, with associated states in matching colors\. The Open list is shown in lighter shades, and the remaining states are in the Closed list\. Attractors with no associated frontier states are shown in gray\.#### Attractors

Attractors\(Zouet al\.[2025](https://arxiv.org/html/2606.07047#bib.bib1)\)were introduced as a memory\-efficient alternative to storing the full Closed list in best\-first search\. They represent the Closed list sparsely by storing only an intelligently selected small set of states and using them as anchors for solution reconstruction\. During search, every state added to the Open list is assigned to an attractor, and each attractor \(excepts​t​a​r​tstart\) is linked to a parent attractor, forming a tree that serves as a compact surrogate for the full Closed list\. Fig\.[1](https://arxiv.org/html/2606.07047#Sx2.F1)illustrates how attractors decompose the search space\.

Given a distance functionhdist:𝒮×𝒮→ℝ≥0h\_\{\\mathrm\{dist\}\}:\\mathcal\{S\}\\times\\mathcal\{S\}\\rightarrow\\mathbb\{R\}\_\{\\geq 0\}, attractors are chosen so that the path to any statessin the Open list can be reconstructed by*greedy tracing*\. Formally, leta​\(s\)a\(s\)denote the attractor assigned toss\. Greedy tracing proceeds by repeatedly applying the updates←arg⁡mins′∈P​r​e​d​\(s\)⁡hdist​\(s′,a​\(s\)\),s\\leftarrow\\arg\\min\_\{s^\{\\prime\}\\in Pred\(s\)\}h\_\{\\mathrm\{dist\}\}\(s^\{\\prime\},\\,a\(s\)\),until reaching the attractora​\(s\)a\(s\), after which tracing continues recursively through parent attractors untils​t​a​r​tstartis reached\. Each such greedy segment corresponds to a portion of the current best path toss, which allows all non\-attractor states to be safely discarded while still enabling full solution reconstruction\. More details on how attractors are maintained are in the appendix\.

## Method

In F2F heuristics, computing the heuristic value of a state in one search direction requires comparing it against all states in the opposite frontier to obtain a valid underestimate of the optimal path cost\. While this provides highly informative guidance, it also incurs substantial computational overhead\. To reduce this cost, we introducefront\-to\-attractors\(F2A\) heuristics\. Although attractors were originally proposed for sparsifying the Closed list, they also have an important structural property: they form a sparse set of ancestors for the states on the frontier\. F2A leverages this structure by replacing comparisons against the entire opposite frontier with comparisons against a much smaller, dynamically maintained set of active attractors, denotedA​t​t​r​sDAttrs\_\{D\}\.

As illustrated in Fig\. 2, computing the F2F heuristic for a statessrequires pairwise evaluations betweenssand all states in the opposite frontier \(highlighted in yellow\)\. In contrast, the F2A heuristic evaluatesssonly against the active attractors in the opposite direction that have at least one associated frontier state \(highlighted in red\)\. Formally, the F2A heuristic for a statessin directionDDis computed as:hD​\(s\)=mins′∈A​t​t​r​sO​D⁡\(h​\(s,s′\)\+gO​D​\(s′\)\)h\_\{D\}\(s\)=\\min\_\{s^\{\\prime\}\\in Attrs\_\{OD\}\}\\bigl\(h\(s,s^\{\\prime\}\)\+g\_\{OD\}\(s^\{\\prime\}\)\\bigr\)\. Since all least\-cost paths discovered so far must pass through their corresponding attractors, F2A preserves optimality guarantees while reducing the number of pairwise evaluations\.111F2A keeps only the active attractors with associated states in the Open list \(colored in Fig[1](https://arxiv.org/html/2606.07047#Sx2.F1)\), rather than the full attractor tree\.

![Refer to caption](https://arxiv.org/html/2606.07047v1/f2a_f2f_v2.png)Figure 2:F2F heuristics estimate the distance to the opposite frontier \(shown in yellow\)\. F2A heuristics estimate the distance to the opposite attractors \(shown in red\)\.### Algorithm Overview

Bi\-HS with F2A heuristics follows the standard Bi\-HS loop used for F2F heuristics, requiring only minor additional bookkeeping to maintain the set of active attractors\. The pairwise heuristich​\(s,s′\)h\(s,s^\{\\prime\}\)must be bi\-consistent\. The overall procedure consists of the following steps, as outlined in Alg\.[1](https://arxiv.org/html/2606.07047#alg1)\. At each iteration, the search:

1. 1\.Selects a search direction:A common strategy ,which we use, is to select the directionDDwith the smaller Open listO​p​e​nDOpen\_\{D\}\(line[6](https://arxiv.org/html/2606.07047#alg1.l6)\), as noted byHolteet al\.\([2017](https://arxiv.org/html/2606.07047#bib.bib8)\)\.
2. 2\.Expands a state:The statesswith the smallestfDf\_\{D\}\-value \(highergDg\_\{D\}\-value for tiebreaking\) inO​p​e​nDOpen\_\{D\}is selected for expansion \(lines[7](https://arxiv.org/html/2606.07047#alg1.l7)–[8](https://arxiv.org/html/2606.07047#alg1.l8)\)\. Its successors are generated, assignedff\-values, inserted intoO​p​e​nDOpen\_\{D\}, and used to updateUU\(lines[14](https://arxiv.org/html/2606.07047#alg1.l14)–[24](https://arxiv.org/html/2606.07047#alg1.l24)\)\. Each successor’s heuristic is computed once upon generation by comparing the state to attractors in the opposite directionA​t​t​r​sO​DAttrs\_\{OD\}\(line[21](https://arxiv.org/html/2606.07047#alg1.l21)\)\.
3. 3\.Updates attractors:When expandingss, if a better path to a successors′s^\{\\prime\}is found, the attractor ofs′s^\{\\prime\}is updated \(line[17](https://arxiv.org/html/2606.07047#alg1.l17)\)\. The algorithm attempts to assigns′s^\{\\prime\}the same attractor asssto minimize the number of attractors maintained\. This is allowed only if greedy tracing froms′s^\{\\prime\}toward this attractor leads throughss\(line[27](https://arxiv.org/html/2606.07047#alg1.l27)\)\. If this condition holds,s′s^\{\\prime\}inheritsss’s attractor \(lines[29](https://arxiv.org/html/2606.07047#alg1.l29)–[30](https://arxiv.org/html/2606.07047#alg1.l30)\)\. Otherwise,ssbecomes the attractor fors′s^\{\\prime\}and is inserted intoA​t​t​r​sDAttrs\_\{D\}\(line[32](https://arxiv.org/html/2606.07047#alg1.l32)\)\. This update logic follows the same principlesZouet al\.\([2025](https://arxiv.org/html/2606.07047#bib.bib1)\)222We also use the same tiebreaking strategy when paths of the same cost are found\.; details are omitted from the pseudocode for clarity\. By assigning attractors in this manner,A​t​t​r​sDAttrs\_\{D\}forms a sparse set of ancestor states through which all current best paths to the frontier states pass\. This sparsity makes F2A heuristics much cheaper to compute while still providing strong guidance\.
4. 4\.Checks for termination:The search terminates when the current best solution costUUis less than or equal to the lower boundLL\(optimal path has been found\) or if the Open list becomes empty \(no solution exists\) \(line[5](https://arxiv.org/html/2606.07047#alg1.l5)\)\.

Algorithm 1Bi\-HS with F2A Heuristic1:procedureF2A Bi\-HS\(

s​t​a​r​t,g​o​a​lstart,goal\)

2:

A​t​t​r​sF←\{s​t​a​r​t\},A​t​t​r​sB←\{g​o​a​l\}Attrs\_\{F\}\\leftarrow\\\{start\\\},Attrs\_\{B\}\\leftarrow\\\{goal\\\}
3:

O​p​e​nF←\{s​t​a​r​t\},O​p​e​nB←\{g​o​a​l\}Open\_\{F\}\\leftarrow\\\{start\\\},Open\_\{B\}\\leftarrow\\\{goal\\\}
4:

U,L←∞U,L\\leftarrow\\infty
5:whileNotTerminated\(

U,LU,L\)do

6:

D←D\\leftarrowChooseDirection\(\)

7:Pop

sswith smallest

fDf\_\{D\}\-value from

O​p​e​nDOpen\_\{D\}
8:Expand\(

ss,

DD\)

9:

L←L\\leftarrowUpdateLB\(\)

10:Removeall

a∈A​t​t​r​sDa\\in Attrs\_\{D\}that are unassigned

11:

12:procedureExpand\(

ss,

DD\)

13:Move

ssfrom

O​p​e​nDOpen\_\{D\}to

C​l​o​s​e​dDClosed\_\{D\}
14:for

s′∈S​u​c​cD​\(s\)s^\{\\prime\}\\in Succ\_\{D\}\(s\)do

15:if

gD​\(s′\)≥gD​\(s\)\+c​\(s,s′\)g\_\{D\}\(s^\{\\prime\}\)\\geq g\_\{D\}\(s\)\+c\(s,s^\{\\prime\}\)then

16:

gD​\(s′\)=gD​\(s\)\+c​\(s,s′\)g\_\{D\}\(s^\{\\prime\}\)=g\_\{D\}\(s\)\+c\(s,s^\{\\prime\}\)
17:UpdateAttractor\(s,s′,D\)\(s,s^\{\\prime\},D\)

18:if

s′∈O​p​e​nD∪C​l​o​s​e​dDs^\{\\prime\}\\in Open\_\{D\}\\cup Closed\_\{D\}then

19:remove

s′s^\{\\prime\}from

O​p​e​nD∪C​l​o​s​e​dDOpen\_\{D\}\\cup Closed\_\{D\}
20:if

s′∉O​p​e​nDs^\{\\prime\}\\notin Open\_\{D\}then

21:

hD​\(s′\)=mins′′∈A​t​t​r​sO​D⁡\(h​\(s′,s′′\)\+gO​D​\(s′′\)\)h\_\{D\}\(s^\{\\prime\}\)=\\min\_\{s^\{\\prime\\prime\}\\in Attrs\_\{OD\}\}\(h\(s^\{\\prime\},s^\{\\prime\\prime\}\)\+g\_\{OD\}\(s^\{\\prime\\prime\}\)\)⊳\\trianglerightIf not yet computed

22:Insert

s′s^\{\\prime\}in

O​p​e​nDOpen\_\{D\}with

gD​\(s′\)\+hD​\(s′\)g\_\{D\}\(s^\{\\prime\}\)\+h\_\{D\}\(s^\{\\prime\}\)
23:if

s′∈O​p​e​nO​Ds^\{\\prime\}\\in Open\_\{OD\}then

24:

U←min⁡\(U,gF​\(s′\)\+gB​\(s′\)\)U\\leftarrow\\min\(U,g\_\{F\}\(s^\{\\prime\}\)\+g\_\{B\}\(s^\{\\prime\}\)\)
25:

26:procedureUpdateAttractor\(

s,s′,Ds,s^\{\\prime\},D\)

27:

sm​i​n′′←argmins′′∈P​r​e​d​\(s′\)s^\{\{\}^\{\\prime\\prime\}\}\_\{min\}\\leftarrow\\operatorname\*\{argmin\}\_\{s^\{\{\}^\{\\prime\\prime\}\}\\in Pred\(s^\{\\prime\}\)\}𝐡𝐝𝐢𝐬𝐭\(s′′,s\.attractor\)\\mathbf\{h\_\{dist\}\}\(s^\{\{\}^\{\\prime\\prime\}\},s\.attractor\)
28:

s′\.a​t​t​r​a​c​t​o​r←ss^\{\\prime\}\.attractor\\leftarrow s
29:if

sm​i​n′′=ss^\{\{\}^\{\\prime\\prime\}\}\_\{min\}=sthen

30:

s′\.a​t​t​r​a​c​t​o​r←s\.a​t​t​r​a​c​t​o​rs^\{\\prime\}\.attractor\\leftarrow s\.attractor
31:elseif

ssnot in

A​t​t​r​sDAttrs\_\{D\}then

32:Insert

ssin

A​t​t​r​sDAttrs\_\{D\}

### Theoretical Properties

Our proof follows the same structure asHolteet al\.\([2017](https://arxiv.org/html/2606.07047#bib.bib8)\)\. Here we provide a high level sketch\. A more detailed proof can be found in the appendix\.

###### Definition 1\.

For any optimal pathP=s0,s1,…​snP=s\_\{0\},s\_\{1\},\.\.\.s\_\{n\}froms​t​a​r​tstart\(s0\)\(s\_\{0\}\)tog​o​a​lgoal\(sn\)\(s\_\{n\}\), letiibe the largest index such thatsk∈C​l​o​s​e​dFs\_\{k\}\\in Closed\_\{F\}∀k∈\[0,i−1\]\\forall k\\in\[0,i\-1\], and letjjbe the smallest index such thatsk∈C​l​o​s​e​dBs\_\{k\}\\in Closed\_\{B\}∀k∈\[j\+1,n\]\\forall k\\in\[j\+1,n\]\. We sayPP“has not been found” ifi<ji<jandPP“has been found” otherwise\.

###### Theorem 1\.

If, at the beginning of an iteration of Alg\.[1](https://arxiv.org/html/2606.07047#alg1), there exists an optimal pathPPfroms​t​a​r​tstarttog​o​a​lgoalthat has not been found, thenL≤C∗L\\leq C^\{\*\}\.

###### Proof Sketch\.

If there exists an optimal path that has not been found, there will be a node inPP,sis\_\{i\}, inO​p​e​nFOpen\_\{F\}withgF​\(si\)=c​\(s​t​a​r​t,si\)g\_\{F\}\(s\_\{i\}\)=c\(start,s\_\{i\}\)and a node inPP,sjs\_\{j\}, inO​p​e​nBOpen\_\{B\}withgB​\(sj\)=c​\(sj,g​o​a​l\)g\_\{B\}\(s\_\{j\}\)=c\(s\_\{j\},goal\)\. ThenC∗=gF​\(si\)\+c​\(si,sj\)\+gB​\(sj\)≥gF​\(si\)\+h​\(si,sj\)\+gB​\(sj\)C^\{\*\}=g\_\{F\}\(s\_\{i\}\)\+c\(s\_\{i\},s\_\{j\}\)\+g\_\{B\}\(s\_\{j\}\)\\geq g\_\{F\}\(s\_\{i\}\)\+h\(s\_\{i\},s\_\{j\}\)\+g\_\{B\}\(s\_\{j\}\)\(admissibility\)\. With the F2A heuristic,fF​\(s\)=gF​\(s\)\+mina∈A​t​t​rB⁡\(h​\(s,a\)\+gB​\(a\)\)f\_\{F\}\(s\)=g\_\{F\}\(s\)\+\\min\_\{a\\in Attr\_\{B\}\}\\bigl\(h\(s,a\)\+g\_\{B\}\(a\)\\bigr\)\. By construction of attractors, for everys′∈O​P​E​NBs^\{\\prime\}\\in OPEN\_\{B\}there existsa∈A​t​t​rBa\\in Attr\_\{B\}withgB​\(s′\)=c​\(s′,a\)\+gB​\(a\)g\_\{B\}\(s^\{\\prime\}\)=c\(s^\{\\prime\},a\)\+g\_\{B\}\(a\)\. Sinceh​\(s,a\)≤h​\(s,s′\)\+c​\(s′,a\)h\(s,a\)\\leq h\(s,s^\{\\prime\}\)\+c\(s^\{\\prime\},a\)\(consistency\),h​\(s,a\)\+gB​\(a\)≤h​\(s,s′\)\+gB​\(s′\)h\(s,a\)\+g\_\{B\}\(a\)\\leq h\(s,s^\{\\prime\}\)\+g\_\{B\}\(s^\{\\prime\}\)\. Taking minima over attractors yieldsfF​\(s\)≤gF​\(s\)\+mins′∈O​P​E​NB⁡\(h​\(s,s′\)\+gB​\(s′\)\)f\_\{F\}\(s\)\\leq g\_\{F\}\(s\)\+\\min\_\{s^\{\\prime\}\\in OPEN\_\{B\}\}\\bigl\(h\(s,s^\{\\prime\}\)\+g\_\{B\}\(s^\{\\prime\}\)\\bigr\)\. Therefore,L=mins∈O​P​E​NF⁡fF​\(s\)≤mins∈O​P​E​NF,s′∈O​P​E​NB⁡\(gF​\(s\)\+h​\(s,s′\)\+gB​\(s′\)\)≤gF​\(si\)\+h​\(si,sj\)\+gB​\(sj\)≤C∗\.L=\\min\_\{s\\in OPEN\_\{F\}\}f\_\{F\}\(s\)\\leq\\min\_\{s\\in OPEN\_\{F\},\\,s^\{\\prime\}\\in OPEN\_\{B\}\}\\bigl\(g\_\{F\}\(s\)\+h\(s,s^\{\\prime\}\)\+g\_\{B\}\(s^\{\\prime\}\)\\bigr\)\\leq g\_\{F\}\(s\_\{i\}\)\+h\(s\_\{i\},s\_\{j\}\)\+g\_\{B\}\(s\_\{j\}\)\\leq C^\{\*\}\.∎

###### Theorem 2\.

If there exists a path froms​t​a​r​tstarttog​o​a​lgoal, Alg\.[1](https://arxiv.org/html/2606.07047#alg1)will returnU=C∗U=C^\{\*\}\(an optimal path\) upon termination\.

###### Proof Sketch\.

Theorem[1](https://arxiv.org/html/2606.07047#Thmtheorem1)implies thatL≤C∗L\\leq C^\{\*\}until all optimal paths have been found\. And sinceU\>C∗U\>C^\{\*\}until the first optimal path froms​t​a​r​tstarttog​o​a​lgoalis found \(due to the process by whichUUis updated\), at which pointU=C∗U=C^\{\*\}, this means that if a path does exist, when Alg\.[1](https://arxiv.org/html/2606.07047#alg1)terminatesU=C∗U=C^\{\*\}\. ∎

This implies that when Alg\.[1](https://arxiv.org/html/2606.07047#alg1)terminates at least one optimal path has been found, indicating that Bi\-HS with F2A heuristics is both complete and optimal\.

## Practical Considerations

#### Degenerating to F2E

Ifg​o​a​lgoalis included in the backward attractor setA​t​t​r​sBAttrs\_\{B\}, then for any statessin the forward direction we haveh​\(s,g​o​a​l\)≤h​\(s,s′\)\+gB​\(s′\)​∀s′∈A​t​t​r​sBh\(s,goal\)\\leq h\(s,s^\{\\prime\}\)\+g\_\{B\}\(s^\{\\prime\}\)\\,\\,\\forall\\,s^\{\\prime\}\\in Attrs\_\{B\}, provided thathhis consistent\. This implies that the F2A heuristic degenerates to F2E when the goal \(or start\) is an attractor, reducing the informativeness of the heuristic\.

#### Optimizations to preserve heuristic informativeness\.

In general, attractors become less informative as they drift farther from the frontier\. To mitigate this, we introduce two optimizations\. Both rely on a thresholdδ\\deltaapplied to the difference ingg\-values between an attractor and its assigned states\.

1. 1\.New Attractor \(NA\)\.When a successors′s^\{\\prime\}inherits the attractor of its parentss, we check whether the difference betweeng​\(s′\)g\(s^\{\\prime\}\)andg\(s\.attractor\)g\(s\.\\mathrm\{attractor\}\)exceedsδ\\delta\. If so,ssis assigned as the new attractor fors′s^\{\\prime\}\. This ensures the active attractor set is a good approximation of the search frontier by keeping attractors close\.
2. 2\.Associated States \(AS\)\.For each attractor, we maintain the subset of its assigned frontier states whosegg\-values differ from the attractor’s by more thanδ\\delta\. If this set is nonempty, we use the associated states in place of the attractor for heuristic computation\. In effect, when an attractor becomes too far from the frontier to serve as an informative surrogate, we fall back to using its frontier states for heuristic evaluation\.

Table 1:Results for planners across domains\. F2A employ optimizations \(“no opt” means no optimization\) that vary by domain\.![Refer to caption](https://arxiv.org/html/2606.07047v1/planner_time_vs_expansion_delay_tiles_VBi-HS_logscale.png)Figure 3:Sliding Tiles with an added delay per expansion\.

## Experiments

We evaluated F2A on three standard benchmark domains commonly used in Bi\-HS studies\.\(1\) 2D Grid Pathfinding:Evaluated on the DAO “brc” and maze maps with five corridor widths\(Sturtevant[2012](https://arxiv.org/html/2606.07047#bib.bib26)\), using 4\-connected unit\-cost actions and the Manhattan Distance heuristic\.\(2\) 15 Sliding Tiles:20 instances \(fewest nodes\) from\(Korf[1985](https://arxiv.org/html/2606.07047#bib.bib25)\), using the Manhattan Distance heuristic\.\(3\) 14\-Pancake Puzzle:50 random instances using the GAP\-11heuristic \(GAP heuristic\(Helmert[2010](https://arxiv.org/html/2606.07047#bib.bib27)\)but ignoring the smallest pancake\.\)

We compared F2A \(with and without the NA and AS optimizations\) to F2E and F2F using both vanilla Bidirectional Heuristic Search \(VBi\-HS\) and Near\-optimal Bidirectional Search \(NBS\)\(Chenet al\.[2017](https://arxiv.org/html/2606.07047#bib.bib11)\)\. VBi\-HS denotes the framework used to instantiate F2E, F2F, and F2A \(i\.e\., Alg\. 1 with different heuristic formulations\), following the ideas of\(Pohl[1969](https://arxiv.org/html/2606.07047#bib.bib23)\)and\(Sint and de Champeaux[1977](https://arxiv.org/html/2606.07047#bib.bib3)\)\. Since NBS was originally designed for F2E heuristics, we extended it to support F2F and F2A by changing the heuristic used to computeff\-values while keeping the same pairwise lower bound\. BAE\*\(Sadhukhan[2013](https://arxiv.org/html/2606.07047#bib.bib12)\)is a state\-of\-the\-art Bi\-HS algorithm but assumes fixed heuristic values assigned at node generation, making it unclear how to extend it to dynamic heuristics like F2F and F2A that depend on the evolving opposite frontier\. However, we include BAE\* with F2E heuristics and A\*\(Hartet al\.[1968](https://arxiv.org/html/2606.07047#bib.bib2)\)as references\. The same search direction policy is used for the Bi\-HS algorithms\. We report results usingδ=20\\delta=20for both NA and AS on the grid maps, andδ=4\\delta=4for Sliding Tiles and Pancake\. For each planner we report mean runtime \(RT\), number of node expansions \(Exp\), and number of heuristic evaluations \(HE\), presented in Table[1](https://arxiv.org/html/2606.07047#Sx4.T1)\. Our evaluation focuses on how different heuristic classes trade off computation cost against search guidance, rather than on identifying a dominant heuristic\. Additional discussion on the experimental results is included in the appendix\.

#### Grid Maps

With VBi\-HS, both F2A \(no opt\) and F2A \(NA\) achieve the fastest runtimes among all variants\. The improvement is primarily driven by a substantial reduction in heuristic evaluations—10\.3× fewer on DAO and 11\.2× fewer on Maze maps compared to F2F—while still outperforming F2E in terms of expansions \(1\.4× and 2\.0× fewer\)\. Under NBS, the F2A variants also require fewer heuristic evaluations than F2F and produce fewer expansions than F2E\. As expected, F2A reduces heuristic evaluations versus F2F while preserving informativeness, yielding fewer expansions than F2E; this trend holds across domains\.

#### Sliding Tiles

Naive F2A degenerates to F2E in this domain\. However, incorporating the NA optimization makes F2A substantially more informative\. With VBi\-HS, expansions decrease by2\.84×2\.84\\timesrelative to F2E, and by3\.08×3\.08\\timesunder NBS\. Heuristic evaluations decrease by1\.23×1\.23\\timesand2\.32×2\.32\\timescompared to F2F, for VBi\-HS and NBS respectively\. The AS optimization further reduces expansions but incurs a much higher number of heuristic evaluations\.

To better understand when F2A heuristics provide benefits, we conducted an additional experiment in which an artificial delay was added to every state expansion\. The resulting runtime curves, shown in Fig\.[3](https://arxiv.org/html/2606.07047#Sx4.F3), reveal a performance window after0\.60\.6ms where F2A \(AS\) achieves the best runtime across all planners\. This study suggests the existence of domains in which the trade\-off between heuristic computation cost and expansion cost aligns favorably for F2A, enabling it to outperform F2E, F2F, and A\* in total runtime\.

#### Pancake

F2A also degenerates to F2E in the Pancake domain\. The AS optimization substantially increases the informativeness of F2A\. With VBi\-HS, expansions decrease by8\.23×8\.23\\timesrelative to F2E, and by4\.21×4\.21\\timesunder NBS\.

## Conclusion

We introduced front\-to\-attractors \(F2A\), a heuristic for bidirectional search that preserves much of the guidance of front\-to\-front \(F2F\) while significantly reducing computational cost\. By estimating the distance to a set of attractors rather than all frontier states, F2A requires minimal overhead and integrates easily into existing algorithms\. Across multiple domains, it reduced heuristic evaluations by up to11\.2×11\.2\\timesover F2F and achieved4\.8×4\.8\\timesfewer expansions than F2E, while maintaining competitive runtimes, making it a practical approach for scalable bidirectional search\.

## References

- V\. Alcázar \(2021\)The consistent case in bidirectional search and a bucket\-to\-bucket algorithm as a middle ground between front\-to\-end and front\-to\-front\.InProceedings of the International Conference on Automated Planning and Scheduling,Vol\.31,pp\. 7–15\.Cited by:[Introduction](https://arxiv.org/html/2606.07047#Sx1.p2.1)\.
- J\. Chen, R\. C\. Holte, S\. Zilles, and N\. R\. Sturtevant \(2017\)Front\-to\-end bidirectional heuristic search with near\-optimal node expansions\.arXiv preprint arXiv:1703\.03868\.Cited by:[Introduction](https://arxiv.org/html/2606.07047#Sx1.p2.1),[Experiments](https://arxiv.org/html/2606.07047#Sx5.p2.3)\.
- J\. Eckerle, J\. Chen, N\. Sturtevant, S\. Zilles, and R\. Holte \(2017\)Sufficient conditions for node expansion in bidirectional heuristic search\.InProceedings of the International Conference on Automated Planning and Scheduling,Vol\.27,pp\. 79–87\.Cited by:[Introduction](https://arxiv.org/html/2606.07047#Sx1.p2.1),[Background](https://arxiv.org/html/2606.07047#Sx2.p2.12)\.
- A\. Felner, C\. Moldenhauer, N\. Sturtevant, and J\. Schaeffer \(2010\)Single\-frontier bidirectional search\.InProceedings of the AAAI conference on artificial intelligence,Vol\.24,pp\. 59–64\.Cited by:[Introduction](https://arxiv.org/html/2606.07047#Sx1.p2.1)\.
- P\. E\. Hart, N\. J\. Nilsson, and B\. Raphael \(1968\)A formal basis for the heuristic determination of minimum cost paths\.IEEE transactions on Systems Science and Cybernetics4\(2\),pp\. 100–107\.Cited by:[Experiments](https://arxiv.org/html/2606.07047#Sx5.p2.3)\.
- M\. Helmert \(2010\)Landmark heuristics for the pancake problem\.InProceedings of the International Symposium on Combinatorial Search,Vol\.1,pp\. 109–110\.Cited by:[Experiments](https://arxiv.org/html/2606.07047#Sx5.p1.1)\.
- R\. C\. Holte, A\. Felner, G\. Sharon, N\. R\. Sturtevant, and J\. Chen \(2017\)MM: a bidirectional search algorithm that is guaranteed to meet in the middle\.Artificial Intelligence252,pp\. 232–266\.Cited by:[Introduction](https://arxiv.org/html/2606.07047#Sx1.p2.1),[item 1](https://arxiv.org/html/2606.07047#Sx3.I1.i1.p1.2),[Theoretical Properties](https://arxiv.org/html/2606.07047#Sx3.SSx2.p1.1),[Proof of Optimality](https://arxiv.org/html/2606.07047#Sx7.SSx6.p1.1)\.
- R\. E\. Korf \(1985\)Depth\-first iterative\-deepening: an optimal admissible tree search\.Artificial intelligence27\(1\),pp\. 97–109\.Cited by:[Experiments](https://arxiv.org/html/2606.07047#Sx5.p1.1)\.
- S\. Lavasani, L\. Siag, S\. S\. Shperberg, A\. Felner, and N\. R\. Sturtevant \(2025\)Anchor search: a unified framework for suboptimal bidirectional search\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.39,pp\. 27045–27053\.Cited by:[Introduction](https://arxiv.org/html/2606.07047#Sx1.p2.1)\.
- M\. Lippi, M\. Ernandes, and A\. Felner \(2012\)Efficient single frontier bidirectional search\.InProceedings of the International Symposium on Combinatorial Search,Vol\.3,pp\. 105–111\.Cited by:[Introduction](https://arxiv.org/html/2606.07047#Sx1.p2.1)\.
- M\. Lippi, M\. Ernandes, and A\. Felner \(2016\)Optimally solving permutation sorting problems with efficient partial expansion bidirectional heuristic search\.AI Communications29\(4\),pp\. 513–536\.Cited by:[Introduction](https://arxiv.org/html/2606.07047#Sx1.p2.1)\.
- L\. E\. Mayer and K\. D\. Krebsbach \(2019\)Front\-to\-front bidirectional best\-first search reconsidered\.\.InFLAIRS,pp\. 14–19\.Cited by:[Introduction](https://arxiv.org/html/2606.07047#Sx1.p2.1)\.
- I\. Pohl \(1969\)Bi\-directional and heuristic search in path problems\.Ph\.D\. Thesis,Department of Computer Science, Stanford University\.Cited by:[Experiments](https://arxiv.org/html/2606.07047#Sx5.p2.3)\.
- S\. K\. Sadhukhan \(2013\)Bidirectional heuristic search based on error estimate\.CSI Journal of Computing2\(1\-2\),pp\. S1\.Cited by:[Introduction](https://arxiv.org/html/2606.07047#Sx1.p2.1),[Experiments](https://arxiv.org/html/2606.07047#Sx5.p2.3)\.
- E\. C\. Sewell and S\. H\. Jacobson \(2021\)Dynamically improved bounds bidirectional search\.Artificial Intelligence291,pp\. 103405\.Cited by:[Introduction](https://arxiv.org/html/2606.07047#Sx1.p2.1)\.
- E\. Shaham, A\. Felner, J\. Chen, and N\. Sturtevant \(2017\)The minimal set of states that must be expanded in a front\-to\-end bidirectional search\.InProceedings of the International Symposium on Combinatorial Search,Vol\.8,pp\. 82–90\.Cited by:[Introduction](https://arxiv.org/html/2606.07047#Sx1.p2.1)\.
- S\. S\. Shperberg, A\. Felner, N\. R\. Sturtevant, S\. E\. Shimony, and A\. Hayoun \(2019\)Enriching non\-parametric bidirectional search algorithms\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.33,pp\. 2379–2386\.Cited by:[Introduction](https://arxiv.org/html/2606.07047#Sx1.p2.1)\.
- L\. Siag, S\. Shperberg, A\. Felner, and N\. R\. Sturtevant \(2023\)Comparing front\-to\-front and front\-to\-end heuristics in bidirectional search\.InProceedings of the International Symposium on Combinatorial Search,Vol\.16,pp\. 158–162\.Cited by:[Introduction](https://arxiv.org/html/2606.07047#Sx1.p1.2),[Introduction](https://arxiv.org/html/2606.07047#Sx1.p2.1)\.
- L\. Sint and D\. de Champeaux \(1977\)An improved bidirectional heuristic search algorithm\.J\. ACM24\(2\),pp\. 177–191\.External Links:ISSN 0004\-5411,[Link](https://doi.org/10.1145/322003.322004),[Document](https://dx.doi.org/10.1145/322003.322004)Cited by:[Background](https://arxiv.org/html/2606.07047#Sx2.p2.12),[Experiments](https://arxiv.org/html/2606.07047#Sx5.p2.3)\.
- N\. Sturtevant \(2012\)Benchmarks for grid\-based pathfinding\.Transactions on Computational Intelligence and AI in Games4\(2\),pp\. 144 – 148\.External Links:[Link](http://web.cs.du.edu/~sturtevant/papers/benchmarks.pdf)Cited by:[Experiments](https://arxiv.org/html/2606.07047#Sx5.p1.1)\.
- Y\. Wang, E\. Weiss, B\. Mu, and O\. Salzman \(2025\)Bidirectional search while ensuring meet\-in\-the\-middle via effective and efficient\-to\-compute termination conditions\.InProceedings of the Thirty\-Fourth International Joint Conference on Artificial Intelligence,pp\. 8987–8995\.Cited by:[Introduction](https://arxiv.org/html/2606.07047#Sx1.p2.1)\.
- A\. Zou, M\. S\. Saleem, and M\. Likhachev \(2025\)Attractor\-based closed list search: sparsifying the closed list for efficient memory\-constrained planning\.InProceedings of the Thirty\-Fourth International Joint Conference on Artificial Intelligence,pp\. 9031–9038\.Cited by:[Introduction](https://arxiv.org/html/2606.07047#Sx1.p3.3),[Attractors](https://arxiv.org/html/2606.07047#Sx2.SS0.SSS0.Px1.p1.1),[item 3](https://arxiv.org/html/2606.07047#Sx3.I1.i3.p1.12),[Maintaining Attractors](https://arxiv.org/html/2606.07047#Sx7.SSx5.p1.3)\.

## Appendix

### Delta Values

We experimented with a range ofδ\\deltavalues and observed that performance is domain dependent\. In grid pathfinding, delta values in the range of 20–100 produced similar results, whereas in Sliding Tiles and Pancake the choice of delta was more sensitive\. Empirically, choosing delta as a fraction \(typically less than one\-half\) of the solution length yielded good trade\-offs, while larger values often caused degeneration toward F2E\. These strategies are intended to balance heuristic informativeness against heuristic computation cost, and this balance is inherently domain\-specific\. However, the qualitative conclusion remains unchanged across the tested range: smaller delta moves F2A toward F2F\-like behavior with more heuristic evaluations, while larger delta reduces the effect of the optimization, with behavior converging to naive F2A, which is more F2E\-like in the presence of degeneration\. Sliding Tiles and Pancake are more delta\-sensitive than grid pathfinding because they have exponential state\-space growth and short solution lengths\. This is especially pronounced in Pancake due to its higher branching factor\.

### Degenerating to F2E

For the Sliding Tiles and Pancake domains we observed degeneration to F2E\. In permutation domains with exponential state spaces, states close to the start may lie on branches that are never expanded, causing stale attractors near the start/goal to remain and reducing heuristic informativeness\. The NA and AS optimizations are designed to prevent F2A from degenerating to F2E by ensuring that the representatives used in heuristic computation remain close to the frontier\.

NA does not explicitly remove such attractors, but rather re\-associates states to a closer attractor when their parent is expanded\. A stale attractor is removed only after all associated states are expanded \(and their successors re\-associated with closer attractors\)\. As a result, NA is less effective in the Pancake domain, due to its higher branching factor \(14 vs\. 4\), which increases the likelihood of persistent low\-g frontier states that are never expanded\.

AS mitigates this by explicitly disabling attractors far from the frontier and directly using their associated frontier states instead for heuristic calculation, thereby preserving heuristic quality\. However, this increases heuristic evaluations\. The experimental results reflect this trade\-off: in Sliding Tiles, naive F2A matches F2E in expansions, while NA reduces expansions; in Pancake, both naive F2A and NA behave like F2E, suggesting in this domain NA does not prevent degeneration, whereas AS significantly reduces expansions \(8\.2×\\timesin VBi\-HS and 4\.3×\\timesin NBS\) but incurs higher heuristic computation \(278\.9×\\timesin VBi\-HS and 496\.7×\\timesin NBS\)\.

### Additional Results

Below we include the runtime plots for adding an artificial delay to every state expansion in the Sliding Tiles domain\. Fig\.[4](https://arxiv.org/html/2606.07047#Sx7.F4)shows the runtime curves for VBi\-HS while Fig\.[5](https://arxiv.org/html/2606.07047#Sx7.F5)shows the runtime curves for NBS\. As shown in both figures, there is a performance window where an F2A variant has the best runtime across all planners \(approximately after0\.60\.6ms for VBi\-HS \(AS\) and approximately between0\.60\.6and55ms for NBS \(NA\)\)\.

![Refer to caption](https://arxiv.org/html/2606.07047v1/planner_time_vs_expansion_delay_tiles_VBi-HS_logscale.png)Figure 4:Sliding Tiles with an added delay per expansion \(VBi\-HS\)\.![Refer to caption](https://arxiv.org/html/2606.07047v1/planner_time_vs_expansion_delay_tiles_NBS_logscale.png)Figure 5:Sliding Tiles with an added delay per expansion \(NBS\)\.
### Applying F2A Heuristics to Bi\-HS Algorithms

F2A heuristics are dynamic and change based on the opposite search frontier similarly to F2F heuristics\. Because of this, F2A heuristics can be easily adapted to Bi\-HS algorithms that support F2F heuristics\. However, it is difficult to adapt F2A heuristics to Bi\-HS algorithms that do not support F2F heuristics\. One such example is BAE\*\. BAE\* cannot directly support F2F or F2A heuristics because it assumes fixed heuristic values assigned at node generation, whereas F2F/F2A values are dynamic and depend on the evolving opposite frontier\. In BAE\*, both forward and backward heuristic values must be computed when a node is generated and remain fixed thereafter; these values are then used in its error estimates and lower\-bound maintenance\. F2E heuristics satisfy this requirement\. In contrast, for a node generated in one direction, its F2F/F2A value with respect to the opposite direction depends on future changes to the current frontier\. We could not design a BAE\* adaptation that both retains the benefits of F2F/F2A and preserves BAE\*’s optimality assumptions\.

Other Bi\-HS frameworks such as NBS and VBi\-HS do not have the same fixed heuristic value requirement in this form, and so we adapted them to support F2F and F2A heuristics\.

### Maintaining Attractors

In Attractor Based Closed List Search \(ACLS\)\(Zouet al\.[2025](https://arxiv.org/html/2606.07047#bib.bib1)\), attractors are maintained such that at any point during the search the optimal path from the start to any state in the Open list can be reconstructed through a series of greedy traces\. The high level idea is that during every expansion the search determines if the statessthat is being expanded is required to reconstruct the current best path to any of its successorss′s^\{\\prime\}\. If it is,ssis stored as an attractor\.

When expandingss, if a better path to one of its successorss′s^\{\\prime\}is discovered, we must be able to reconstruct this new path tos′s^\{\\prime\}\. To minimize the number of attractors saved, we attempt to assigns′s^\{\\prime\}the same attractor asss\. Fors′s^\{\\prime\}to inheritss’s attractor, it is necessary thats′s^\{\\prime\}’s greedy tracing through this attractor leads toss\. If this condition is met,sscan be deleted without affecting the path reconstruction\. However, in the case of using attractors for the F2A heuristic states are not deleted, as memory is not the constraint and states can be potentially re\-expanded\. If this condition is not met, thenssitself is assigned as the attractor fors′s^\{\\prime\}, in which case it is saved with its parent attractor set tos\.a​t​t​r​a​c​t​o​rs\.attractor\. By assignings′s^\{\\prime\}’s attractor in this way, the best path tos′s^\{\\prime\}is always recoverable\.

Attractor maintenance relies on a data structure calledA​t​t​r​sDAttrs\_\{D\}\. This structure maintains the list of attractors and a counter representing the number of states assigned to each attractor\. Unlike ACLS, the F2A heuristic only relies on the set of attractors that have at least one associated state in the Open list \(i\.e\., the active attractors\)\. As a result, the counter only keeps track of how many states inO​p​e​nDOpen\_\{D\}are assigned to it, but not child attractors\. These counters are updated whenever states are assigned, reassigned, or removed fromO​p​e​nDOpen\_\{D\}\. When an attractor no longer has any frontier states associated with it \(its counter reaches zero\), it is removed fromA​t​t​r​sDAttrs\_\{D\}\.

When multiple paths of the same cost lead to a statess, we tiebreak by selecting the path that assigns an attractor farthest fromss\. Here, “farther away” is quantified as the attractor with a higher𝐡𝐝𝐢𝐬𝐭\\mathbf\{h\_\{dist\}\}value relative toss\. For example, consider two parentss′s^\{\\prime\}ands′′s^\{\\prime\\prime\}, both sharing the same attractortt\. Ifs′s^\{\\prime\}is the greedy predecessor ofssbased ontt\(due to deterministic tiebreaking\), buts′′s^\{\\prime\\prime\}was expanded first,s′′s^\{\\prime\\prime\}might be unnecessarily added to theA​t​t​r​sAttrsstructure and assigned asss’s attractor instead oftt\. To prevent such scenarios, we tiebreak by favoring the path with the attractor that is farther away, such thatttwill be assigned asss’s attractor onces′s^\{\\prime\}is expanded\. Alternatively, it is possible to bypass the tiebreaking routine altogether at the expense of saving more attractors\.

### Proof of Optimality

In this section we will prove the optimality of Alg\. 1\. We will follow the same structure asHolteet al\.\([2017](https://arxiv.org/html/2606.07047#bib.bib8)\), with the notable difference being Theorem[3](https://arxiv.org/html/2606.07047#Thmtheorem3)\. LetC∗=c​\(s​t​a​r​t,g​o​a​l\)C^\{\*\}=c\(start,goal\)be the optimal cost\.

###### Definition 2\.

For any optimal pathP=s0,s1,…​snP=s\_\{0\},s\_\{1\},\.\.\.s\_\{n\}froms​t​a​r​tstart\(s0\)\(s\_\{0\}\)tog​o​a​lgoal\(sn\)\(s\_\{n\}\), letiibe the largest index such thatsk∈C​l​o​s​e​dFs\_\{k\}\\in Closed\_\{F\}∀k∈\[0,i−1\]\\forall k\\in\[0,i\-1\], and letjjbe the smallest index such thatsk∈C​l​o​s​e​dBs\_\{k\}\\in Closed\_\{B\}∀k∈\[j\+1,n\]\\forall k\\in\[j\+1,n\]\. We sayPP“has not been found” ifi<ji<jandPP“has been found” otherwise\.

###### Definition 3\.

Nodennis ”permanently closed” in the forward direction ifn∈C​l​o​s​e​dFn\\in Closed\_\{F\}andgF​\(n\)=c​\(s​t​a​r​t,n\)g\_\{F\}\(n\)=c\(start,n\)\. Likewise,nnis permanently closed in the backward search direction ifn∈C​l​o​s​e​dBn\\in Closed\_\{B\}andgB​\(n\)=c​\(n,g​o​a​l\)g\_\{B\}\(n\)=c\(n,goal\)\.

The name ”permanently closed” is based on the following lemma\.

###### Lemma 1\.

If nodennis permanently closed in a particular search direction at the start of some iteration, it will be permanently closed in that direction at the start of all subsequent iterations\.

###### Proof\.

This proof is for the forward search, the proof for the backward search is analogous\. Alg\. 1 does not changegF​\(n\)g\_\{F\}\(n\)whilen∈C​l​o​s​e​dFn\\in Closed\_\{F\}, sonncan only stop being permanently closed by being removed fromC​l​o​s​e​dFClosed\_\{F\}\. This is possible but only if a strictly cheaper path tonnis found, which is not possible sincegF​\(n\)=c​\(s​t​a​r​t,n\)g\_\{F\}\(n\)=c\(start,n\)for a node permanently closed in the forward direction\. Therefore, oncennis permanently closed in the forward direction it will remain so\. ∎

###### Lemma 2\.

LetP=s0,s1,…​snP=s\_\{0\},s\_\{1\},\.\.\.s\_\{n\}be an optimal path froms​t​a​r​t=s0start=s\_\{0\}to any statesns\_\{n\}\. Ifsns\_\{n\}is not permanently closed in the forward direction and eithern=0n=0orn\>0n\>0andsn−1s\_\{n\-1\}is permanently closed in the forward direction, thensn∈O​p​e​nFs\_\{n\}\\in Open\_\{F\}andgF​\(sn\)=c​\(s​t​a​r​t,sn\)g\_\{F\}\(s\_\{n\}\)=c\(start,s\_\{n\}\)\. Analogously, letP=s0,s1,…​snP=s\_\{0\},s\_\{1\},\.\.\.s\_\{n\}be an optimal path from any states0s\_\{0\}tog​o​a​l=sngoal=s\_\{n\}\. Ifs0s\_\{0\}is not permanently closed in the backward direction and eithern=0n=0orn\>0n\>0ands1s\_\{1\}is permanently closed in the backward direction, thens0∈O​p​e​nBs\_\{0\}\\in Open\_\{B\}andgB​\(s0\)=c​\(s0,g​o​a​l\)g\_\{B\}\(s\_\{0\}\)=c\(s\_\{0\},goal\)\.

###### Proof\.

This proof is for the forward search, the proof for the backward search is analogous\. Ifn=0n=0,s0=s​t​a​r​ts\_\{0\}=starthas not been closed in the forward direction and the lemma is true because line[3](https://arxiv.org/html/2606.07047#alg1.l3)puts​t​a​r​t∈O​p​e​nFstart\\in Open\_\{F\}withgF​\(s​t​a​r​t\)=c​\(s​t​a​r​t,s​t​a​r​t\)=0g\_\{F\}\(start\)=c\(start,start\)=0\. Supposen\>0n\>0\. Whensn−1s\_\{n\-1\}was expanded and permanently closed in the forward directionsns\_\{n\}was generated via an optimal path \(in lines[15](https://arxiv.org/html/2606.07047#alg1.l15)and[16](https://arxiv.org/html/2606.07047#alg1.l16)\),gF​\(sn\)=gF​\(s\)\+c​\(s,s′\)=c​\(s​t​a​r​t,sn−1\)\+c​\(sn−1,sn\)=c​\(s​t​a​r​t,sn\)g\_\{F\}\(s\_\{n\}\)=g\_\{F\}\(s\)\+c\(s,s^\{\\prime\}\)=c\(start,s\_\{n\-1\}\)\+c\(s\_\{n\-1\},s\_\{n\}\)=c\(start,s\_\{n\}\)\.sns\_\{n\}cannot have been permanently closed in the forward direction at that time because if it was, it still would be \(Lemma[1](https://arxiv.org/html/2606.07047#Thmlemma1)\)\. Ifsn∈C​l​o​s​e​dF∪O​p​e​nFs\_\{n\}\\in Closed\_\{F\}\\cup Open\_\{F\}at that time with a suboptimalgg\-value, then it would have been removed fromC​l​o​s​e​dF∪O​p​e​nFClosed\_\{F\}\\cup Open\_\{F\}and added toO​p​e​nFOpen\_\{F\}withgF​\(sn\)=c​\(s​t​a​r​t,sn\)g\_\{F\}\(s\_\{n\}\)=c\(start,s\_\{n\}\)\. Ifsn∉C​l​o​s​e​dF∪O​p​e​nFs\_\{n\}\\notin Closed\_\{F\}\\cup Open\_\{F\}at that time, it would likewise have been added toO​p​e​nFOpen\_\{F\}withgF​\(sn\)=c​\(s​t​a​r​t,sn\)g\_\{F\}\(s\_\{n\}\)=c\(start,s\_\{n\}\)\. Finally, ifsn∈O​p​e​nFs\_\{n\}\\in Open\_\{F\}at that time withgF​\(sn\)=c​\(s​t​a​r​t,sn\)g\_\{F\}\(s\_\{n\}\)=c\(start,s\_\{n\}\), it would have remained so\. Therefore, no matter whatsns\_\{n\}’s status was at the timesn−1s\_\{n\-1\}was expanded to become permanently closed in the forward direction, at the end of that iterationsn∈O​p​e​nFs\_\{n\}\\in Open\_\{F\}andgF​\(sn\)=c​\(s​t​a​r​t,sn\)g\_\{F\}\(s\_\{n\}\)=c\(start,s\_\{n\}\)\. In subsequent iterationsgF​\(sn\)g\_\{F\}\(s\_\{n\}\)cannot have changed, since that only happens if a strictly cheaper path tosns\_\{n\}is found, which is impossible\. It also cannot have been closed, since if that had happened it would now be permanently closed\. ∎

###### Lemma 3\.

LetP=s0,s1,…​snP=s\_\{0\},s\_\{1\},\.\.\.s\_\{n\}be an optimal path froms​t​a​r​tstart\(s0\)\(s\_\{0\}\)to any statesns\_\{n\}\. Ifsns\_\{n\}is not permanently closed in the forward direction then there exists anii\(0≤i≤n\)\(0\\leq i\\leq n\)such thatsi∈O​p​e​nFs\_\{i\}\\in Open\_\{F\}andgF​\(si\)=c​\(s​t​a​r​t,si\)g\_\{F\}\(s\_\{i\}\)=c\(start,s\_\{i\}\)\. Letim​i​ni\_\{min\}be the smallest suchiiand definenFn\_\{F\}\(for pathPP\) to besim​i​ns\_\{i\_\{min\}\}\. Analogously, letP=s0,s1,…​snP=s\_\{0\},s\_\{1\},\.\.\.s\_\{n\}be an optimal path from any states0s\_\{0\}tog​o​a​l=sngoal=s\_\{n\}\. Ifs0s\_\{0\}is not permanently closed in the backward direction then there exists ajj\(0≤j≤n\)\(0\\leq j\\leq n\)such thatsj∈O​p​e​nBs\_\{j\}\\in Open\_\{B\}andgB​\(sj\)=c​\(sj,g​o​a​l\)g\_\{B\}\(s\_\{j\}\)=c\(s\_\{j\},goal\)\. Letjm​a​xj\_\{max\}be the largest suchjjand definenBn\_\{B\}\(for pathPP\) to besjm​a​xs\_\{j\_\{max\}\}\.

###### Proof\.

This proof is for the forward search, the proof for the backward search is analogous\. Ifs​t​a​r​t∉C​l​o​s​e​dFstart\\notin Closed\_\{F\}, theni=0i=0has the required properties\. Supposes​t​a​r​t∈C​l​o​s​e​dFstart\\in Closed\_\{F\}\. Letkk\(0≤k≤n\)\(0\\leq k\\leq n\)be the largest index such thatsks\_\{k\}is permanently closed\. Such akkmust exist becauses​t​a​r​tstart\(k=0\)\(k=0\)is permanently closed\. By Lemma[2](https://arxiv.org/html/2606.07047#Thmlemma2)sk\+1∈O​p​e​nFs\_\{k\+1\}\\in Open\_\{F\}andgF​\(sk\+1\)=c​\(s​t​a​r​t,sk\+1\)g\_\{F\}\(s\_\{k\+1\}\)=c\(start,s\_\{k\+1\}\)\. Thereforei=k\+1i=k\+1has the required properties\. ∎

The following lemma shows that for an optimal pathPPfroms​t​a​r​tstarttog​o​a​lgoal,nFn\_\{F\}andnBn\_\{B\}forPPare exactly the statessis\_\{i\}andsjs\_\{j\}forPPdefined in Definition[2](https://arxiv.org/html/2606.07047#Thmdefinition2)\.

###### Lemma 4\.

LetP=s0,s1,…​snP=s\_\{0\},s\_\{1\},\.\.\.s\_\{n\}be an optimal path froms​t​a​r​tstart\(s0\)\(s\_\{0\}\)tog​o​a​lgoal\(sn\)\(s\_\{n\}\)that has not been found\. ThennFn\_\{F\}andnBn\_\{B\}, as defined in Lemma[3](https://arxiv.org/html/2606.07047#Thmlemma3), both exist forPPandnF=sin\_\{F\}=s\_\{i\}andnB=sjn\_\{B\}=s\_\{j\}, wheresis\_\{i\}andsjs\_\{j\}are as defined in Definition[2](https://arxiv.org/html/2606.07047#Thmdefinition2)\.

###### Proof\.

Letiiandjjbe as in Definition[2](https://arxiv.org/html/2606.07047#Thmdefinition2)\. For the forward search,s0,s1,…​sis\_\{0\},s\_\{1\},\.\.\.s\_\{i\}is an optimal path froms​t​a​r​tstarttosis\_\{i\}andsi∉C​l​o​s​e​dFs\_\{i\}\\notin Closed\_\{F\}and therefore is not permanently closed in the forward direction\. Therefore,s0,s1,…​sis\_\{0\},s\_\{1\},\.\.\.s\_\{i\}satisfies Lemma[3](https://arxiv.org/html/2606.07047#Thmlemma3)for the forward direction andnF=si′n\_\{F\}=s\_\{i^\{\\prime\}\}exists for paths0,s1,…​sis\_\{0\},s\_\{1\},\.\.\.s\_\{i\}\. Becauses0,s1,…​si−1s\_\{0\},s\_\{1\},\.\.\.s\_\{i\-1\}are all inC​l​o​s​e​dFClosed\_\{F\}, it must be thati′=ii^\{\\prime\}=i\. Sincei′i^\{\\prime\}is the smallest index between 0 andiisuch thatsi′∈O​p​e​nFs\_\{i^\{\\prime\}\}\\in Open\_\{F\}andgF​\(si′\)=c​\(s​t​a​r​t,si′\)g\_\{F\}\(s\_\{i^\{\\prime\}\}\)=c\(start,s\_\{i^\{\\prime\}\}\), it is also the smallest index between 0 andnnwith these properties, sosi′s\_\{i^\{\\prime\}\}is alsonFn\_\{F\}for pathPP\. For the backward search the reasoning is analogous\. ∎

###### Theorem 3\.

If, at the beginning of an iteration of Alg\. 1, there exists an optimal pathPPfroms​t​a​r​tstarttog​o​a​lgoalthat has not been found, thenL≤C∗L\\leq C^\{\*\}\.

###### Proof\.

LetnF=sin\_\{F\}=s\_\{i\}andnB=sjn\_\{B\}=s\_\{j\}be as defined in Lemma[3](https://arxiv.org/html/2606.07047#Thmlemma3)\. Lemma[4](https://arxiv.org/html/2606.07047#Thmlemma4)guarantees thatnFn\_\{F\}andnBn\_\{B\}exist forPP\. Becausei<ji<j, with an admissible pairwise heuristicC∗=gF​\(si\)\+c​\(si,sj\)\+gB​\(sj\)≥gF​\(si\)\+h​\(si,sj\)\+gB​\(sj\)C^\{\*\}=g\_\{F\}\(s\_\{i\}\)\+c\(s\_\{i\},s\_\{j\}\)\+g\_\{B\}\(s\_\{j\}\)\\geq g\_\{F\}\(s\_\{i\}\)\+h\(s\_\{i\},s\_\{j\}\)\+g\_\{B\}\(s\_\{j\}\)\. With the F2A heuristic,fF​\(s\)=gF​\(s\)\+mina∈A​t​t​rB⁡\(h​\(s,a\)\+gB​\(a\)\)f\_\{F\}\(s\)=g\_\{F\}\(s\)\+\\min\_\{a\\in Attr\_\{B\}\}\\bigl\(h\(s,a\)\+g\_\{B\}\(a\)\\bigr\)\. By construction of attractors, for everys′∈O​P​E​NBs^\{\\prime\}\\in OPEN\_\{B\}there existsa∈A​t​t​rBa\\in Attr\_\{B\}withgB​\(s′\)=c​\(s′,a\)\+gB​\(a\)g\_\{B\}\(s^\{\\prime\}\)=c\(s^\{\\prime\},a\)\+g\_\{B\}\(a\)\. With a consistent pairwise heuristic,h​\(s,a\)≤h​\(s,s′\)\+c​\(s′,a\)h\(s,a\)\\leq h\(s,s^\{\\prime\}\)\+c\(s^\{\\prime\},a\), which impliesh​\(s,a\)\+gB​\(a\)≤h​\(s,s′\)\+gB​\(s′\)h\(s,a\)\+g\_\{B\}\(a\)\\leq h\(s,s^\{\\prime\}\)\+g\_\{B\}\(s^\{\\prime\}\)\. Taking minima over attractors yieldsfF​\(s\)≤gF​\(s\)\+mins′∈O​P​E​NB⁡\(h​\(s,s′\)\+gB​\(s′\)\)f\_\{F\}\(s\)\\leq g\_\{F\}\(s\)\+\\min\_\{s^\{\\prime\}\\in OPEN\_\{B\}\}\\bigl\(h\(s,s^\{\\prime\}\)\+g\_\{B\}\(s^\{\\prime\}\)\\bigr\)\. Therefore,L=mins∈O​P​E​NF⁡fF​\(s\)≤mins∈O​P​E​NF,s′∈O​P​E​NB⁡\(gF​\(s\)\+h​\(s,s′\)\+gB​\(s′\)\)≤gF​\(si\)\+h​\(si,sj\)\+gB​\(sj\)≤C∗\.L=\\min\_\{s\\in OPEN\_\{F\}\}f\_\{F\}\(s\)\\leq\\min\_\{s\\in OPEN\_\{F\},\\,s^\{\\prime\}\\in OPEN\_\{B\}\}\\bigl\(g\_\{F\}\(s\)\+h\(s,s^\{\\prime\}\)\+g\_\{B\}\(s^\{\\prime\}\)\\bigr\)\\leq g\_\{F\}\(s\_\{i\}\)\+h\(s\_\{i\},s\_\{j\}\)\+g\_\{B\}\(s\_\{j\}\)\\leq C^\{\*\}\.∎

###### Lemma 5\.

If there exists a path froms​t​a​r​tstarttog​o​a​lgoal, Alg\. 1 will not terminate until at least one optimal path froms​t​a​r​tstarttog​o​a​lgoalhas been found\.

###### Proof\.

Lemma[4](https://arxiv.org/html/2606.07047#Thmlemma4)guarantees thatO​p​e​nFOpen\_\{F\}andO​p​e​nBOpen\_\{B\}are both non\-empty as long as there is any optimal path froms​t​a​r​tstarttog​o​a​lgoalthat has not been found, so the termination condition for empty Open lists cannot be satisfied until all optimal paths froms​t​a​r​tstarttog​o​a​lgoalhave been found\. The only other termination condition isU≤LU\\leq L\. Assume for the purpose of contradiction that this termination condition is satisfied before any optimal path froms​t​a​r​tstarttog​o​a​lgoalhas been found\. Theorem[3](https://arxiv.org/html/2606.07047#Thmtheorem3)shows thatL≤C∗L\\leq C^\{\*\}until all optimal paths froms​t​a​r​tstarttog​o​a​lgoalhave been found, so forU≤C∗U\\leq C^\{\*\}to hold if no optimal paths froms​t​a​r​tstarttog​o​a​lgoalhave been found,UUmust be equal toC∗C^\{\*\}\. We will now show thatU=C∗U=C^\{\*\}implies an optimal path froms​t​a​r​tstarttog​o​a​lgoalhas been found, contradicting our assumption, thereby proving the lemma\.UUis set in line[24](https://arxiv.org/html/2606.07047#alg1.l24)\. On the iteration in whichUUwas set toC∗C^\{\*\}, there must have been a child node generated,s′s^\{\\prime\}, that satisfied the conditions of line[23](https://arxiv.org/html/2606.07047#alg1.l23), i\.e\.,s′∈O​p​e​nBs^\{\\prime\}\\in Open\_\{B\}andgF​\(s′\)\+gB​\(s′\)=C∗g\_\{F\}\(s^\{\\prime\}\)\+g\_\{B\}\(s^\{\\prime\}\)=C^\{\*\}\. The latter impliesgF​\(s′\)=c​\(s​t​a​r​t,s′\)g\_\{F\}\(s^\{\\prime\}\)=c\(start,s^\{\\prime\}\)andgB​\(s′\)=c​\(s′,g​o​a​l\)g\_\{B\}\(s^\{\\prime\}\)=c\(s^\{\\prime\},goal\), i\.e\.,s′s^\{\\prime\}is on an optimal path froms​t​a​r​tstarttog​o​a​lgoalwith optimalgg\-values in both directions\. This means that all the nodes on the forward and backward generating paths fors′s^\{\\prime\}are permanently closed\. The concatenation of these two paths, withs′s^\{\\prime\}in between, is an optimal path froms​t​a​r​tstarttog​o​a​lgoalthat was found on the iteration whenUUwas set toC∗C^\{\*\}\. ∎

###### Lemma 6\.

If there exists a path froms​t​a​r​tstarttog​o​a​lgoal, letP=s0,s1,…​snP=s\_\{0\},s\_\{1\},\.\.\.s\_\{n\}be the first optimal path froms​t​a​r​tstart\(s0\)\(s\_\{0\}\)tog​o​a​lgoal\(sn\)\(s\_\{n\}\)that is found during Alg\. 1’s execution, and letnF=sin\_\{F\}=s\_\{i\}andnB=sjn\_\{B\}=s\_\{j\}be as defined in Lemma[3](https://arxiv.org/html/2606.07047#Thmlemma3)at the beginning of the iteration on whichPPis found\. Then during that iterationUUwill be set toC∗C^\{\*\}in line[24](https://arxiv.org/html/2606.07047#alg1.l24)\.

###### Proof\.

Lemma[5](https://arxiv.org/html/2606.07047#Thmlemma5)guarantees thatPPexists, and Lemma[4](https://arxiv.org/html/2606.07047#Thmlemma4)guarantees thatnFn\_\{F\}andnBn\_\{B\}exist forPPat the beginning of the iteration on which it becomes found\. One of them must be expanded on this iteration becausePP’s status will not change from ”not found” to ”found” ifnFn\_\{F\}remains onO​p​e​nFOpen\_\{F\}andnBn\_\{B\}remains onO​p​e​nBOpen\_\{B\}\. We will complete the proof assuming thatnFn\_\{F\}is expanded\. The proof in the case thatnBn\_\{B\}is expanded is analogous\. We will first prove that whennFn\_\{F\}is expanded,nBn\_\{B\}will be generated as one of its children\.

SupposenBn\_\{B\}is not generated as a child ofnFn\_\{F\}when it is expanded in the forward direction\. Then there must exist one or more nodes between them, i\.e\.,P=s​t​a​r​t​…​nF,t1​…​tk,nb​…​g​o​a​lP=start\.\.\.n\_\{F\},t\_\{1\}\.\.\.t\_\{k\},n\_\{b\}\.\.\.goal\(k≥1\)\(k\\geq 1\)\. In order forPPto be ”found” at the end of this iteration, it must be the case thatti∈C​l​o​s​e​dF​∀1≤i≤kt\_\{i\}\\in Closed\_\{F\}\\forall 1\\leq i\\leq k\. Since the paths​t​a​r​t​…​nF,t1start\.\.\.n\_\{F\},t\_\{1\}is an optimal path froms​t​a​r​tstarttot1t\_\{1\},t1∈C​l​o​s​e​dFt\_\{1\}\\in Closed\_\{F\}after being generated bynFn\_\{F\}means that it had previously been generated via a different optimal path, which implies an optimal path had previously been found froms​t​a​r​tstartto all thetit\_\{i\}and tonBn\_\{B\}\. Combining this previously found optimal path froms​t​a​r​tstarttonBn\_\{B\}with the optimal path found by the backwards search fromnBn\_\{B\}tog​o​a​lgoalcreates an optimal path froms​t​a​r​tstarttog​o​a​lgoalthat had been found prior toPP\. This contradicts the premise thatPPis the first optimal path froms​t​a​r​tstarttog​o​a​lgoal\.

BecausenBn\_\{B\}is a child ofnFn\_\{F\},nB∈O​p​e​nBn\_\{B\}\\in Open\_\{B\}andgF​\(nB\)\+gB​\(nB\)=c​\(s​t​a​r​t,nB\)\+c​\(nB,g​o​a​l\)=C∗g\_\{F\}\(n\_\{B\}\)\+g\_\{B\}\(n\_\{B\}\)=c\(start,n\_\{B\}\)\+c\(n\_\{B\},goal\)=C^\{\*\}, soUUwill be set toC∗C^\{\*\}in line[24](https://arxiv.org/html/2606.07047#alg1.l24)\. ∎

###### Theorem 4\.

If there exists a path froms​t​a​r​tstarttog​o​a​lgoal, Alg\. 1 will returnU=C∗U=C^\{\*\}\(an optimal path\) upon termination\.

###### Proof\.

Lemma[5](https://arxiv.org/html/2606.07047#Thmlemma5)has shown that if there is a path froms​t​a​r​tstarttog​o​a​lgoal, Alg\. 1 will not terminate until at least one optimal path froms​t​a​r​tstarttog​o​a​lgoalhas been found\. And by Lemma[6](https://arxiv.org/html/2606.07047#Thmlemma6)when the first optimal path is foundUUwill be set toC∗C^\{\*\}\. Thus, when Alg\. 1 terminatesU≤C∗U\\leq C^\{\*\}\. SinceU≥C∗U\\geq C^\{\*\}by construction, when Alg\. 1 terminatesU=C∗U=C^\{\*\}\. ∎