Front-to-Attractors: 改进双向搜索中的前向-前向启发式

# Front-to-Attractors: Modifying the Front-to-Front Heuristic in Bidirectional Search Source: https://arxiv.org/html/2606.07047 ###### 摘要 启发式在双向搜索算法的性能中扮演核心角色，双向搜索通常依赖两个主要类别。前向-终点 (Front-to-End, F2E) 启发式估计从状态 \(s\) 到搜索目标（前向搜索的目标 \(\mathit{goal}\) 或后向搜索的起点 \(\mathit{start}\)）的距离。相比之下，前向-前向 (Front-to-Front, F2F) 启发式使用成对函数 \(h(s, s')\) 估计从 \(s\) 到对向搜索前沿的距离，其中 \(s'\) 遍历前沿状态。虽然 F2F 启发式通常信息量更大，因此减少了节点扩展次数，但它们对大量成对评估的依赖造成了巨大的计算开销。为了解决这一限制，我们引入了一种新的启发式类别——前向-吸引子 (Front-to-Attractors, F2A)，它在保留 F2F 大部分信息量的同时，大幅降低了计算成本。F2A 不是评估到对向前沿所有状态的距离，而是估计从 \(s\) 到对向搜索方向中一个动态维护的小型吸引子集合的距离。这些吸引子作为完整前沿的替代，以极低的计算代价提供丰富的启发式指导，同时保持 F2F 提供的最优性保证。我们在多个领域评估了 F2A，结果表明，与 F2F 相比，它将成对评估次数减少了最多 \(11.2\times\)，同时平均比 F2E 少扩展 \(4.8\times\) 的节点。

## 引言 双向启发式搜索 (Bi-HS) 旨在通过同时运行前向和后向搜索来找到两个状态之间的最小代价路径，随着两个前沿的相遇，有效搜索深度得以降低。Bi-HS 中的一个核心设计选择是用于引导这些搜索的启发式。大多数现有算法使用前向-终点 (F2E) 启发式，它估计从状态到当前搜索方向的目标（前向搜索的目标 \(\mathit{goal}\) 或后向搜索的起点 \(\mathit{start}\)）的代价。虽然 F2E 启发式计算成本低廉，但它们的引导性较弱，因为它们是独立处理两个搜索，忽略了对方前沿（即 Open 列表）的进展。相比之下，前向-前向 (F2F) 启发式使用成对函数 \(h(s, s')\) 估计从状态到对向前沿的距离，其中 \(s'\) 遍历对向前沿中的状态。F2F 启发式信息量更大 (Siag et al. 2023 (https://arxiv.org/html/2606.07047#bib.bib19))，通常需要更少的状态扩展就能找到解。它们的缺点在于计算成本：评估一个方向上的状态的启发式需要对该状态与对向前沿中所有状态进行成对评估。由于这种开销导致规划时间较长，大多数改进 Bi-HS 的工作都集中在 F2E 方法上，提出了增强的扩展规则、更强的终止条件和有效的剪枝策略 (Sadhukhan 2013 (https://arxiv.org/html/2606.07047#bib.bib12); Holte et al. 2017 (https://arxiv.org/html/2606.07047#bib.bib8); Shaham et al. 2017 (https://arxiv.org/html/2606.07047#bib.bib10); Eckerle et al. 2017 (https://arxiv.org/html/2606.07047#bib.bib9); Chen et al. 2017 (https://arxiv.org/html/2606.07047#bib.bib11); Sewell and Jacobson 2021 (https://arxiv.org/html/2606.07047#bib.bib13); Shperberg et al. 2019 (https://arxiv.org/html/2606.07047#bib.bib14); Wang et al. 2025 (https://arxiv.org/html/2606.07047#bib.bib16))。只有少数方法试图利用或改进 F2F 启发式 (Felner et al. 2010 (https://arxiv.org/html/2606.07047#bib.bib20); Lippi et 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))。尽管基于 F2F 的算法潜力巨大，因为它们的启发式信息更丰富，通常能减少状态扩展次数，但由于启发式评估与前沿大小成二次方关系，它们在实际中仍然明显更慢 (Siag et al. 2023 (https://arxiv.org/html/2606.07047#bib.bib19))。存在一些试图用更小集合表示前沿的技术，但会产生次优解 (Lavasani et al. 2025 (https://arxiv.org/html/2606.07047#bib.bib28))。为了克服 F2F 启发式带来的开销，本文引入了一种新的启发式类别——前向-吸引子 (F2A)，它在大幅降低计算成本的同时保留了 F2F 的大部分信息量。该方法利用了 Zou et al. (2025 (https://arxiv.org/html/2606.07047#bib.bib1)) 中引入的吸引子表示。F2A 不是将 \(s\) 与对向前沿中的所有状态进行比较，而是评估到动态维护的小型吸引子集合的距离。这些吸引子作为完整前沿的紧凑替代，以极低的计算代价提供丰富的启发式指导，同时保持 F2F 的最优性保证。我们在多个领域评估了 F2A，包括二维网格路径规划、滑动拼图和煎饼谜题，结果表明，与 F2F 相比，它将成对启发式评估次数减少了最多 \(11.2\times\)，同时平均比 F2E 少扩展 \(4.8\times\) 的节点。

## 背景 一个 Bi-HS 问题实例 \(I = (G, start, goal, h_F, h_B)\) 由一个图 \(G = (V, E)\)、一个 \(\mathit{start}\) 状态、一个 \(\mathit{goal}\) 状态以及前向 (F) 和后向 (B) 启发式 \(h_F, h_B\) 组成。\(G\) 中状态 \(s\) 和 \(s'\) 之间的最短路径代价记为 \(c(s, s')\)。目标是找到一条从 \(\mathit{start}\) 到 \(\mathit{goal}\) 的路径，其最优代价为 \(C^*\)。Bi-HS 算法同时执行两个搜索：从 \(\mathit{start}\) 出发的前向搜索和从 \(\mathit{goal}\) 出发的后向搜索。每个搜索方向 \(D \in \{F, B\}\) 维护自己的 Open 列表 \(\mathit{Open}_D\)。对于状态 \(s\)，\(g_D(s), h_D(s), f_D(s)\) 分别表示其在方向 \(D\) 上的 \(g\) 值、\(h\) 值和 \(f\) 值。对向方向记为 \(\mathit{OD}\)。

前向-终点 (F2E) 启发式使用前向启发式 \(h_F: \mathcal{S} \rightarrow \mathbb{R}_{\geq 0}\) 来估计从任何状态到 \(\mathit{goal}\) 的代价，以及后向启发式 \(h_B: \mathcal{S} \rightarrow \mathbb{R}_{\geq 0}\) 来估计从任何状态到 \(\mathit{start}\) 的代价。\(f\) 值计算为 \(f_D(s) = g_D(s) + h_D(s)\)。

前向-前向 (F2F) 启发式 (Sint and de Champeaux 1977 (https://arxiv.org/html/2606.07047#bib.bib3)) 使用成对启发式 \(h: \mathcal{S} \times \mathcal{S} \rightarrow \mathbb{R}_{\geq 0}\) 来估计任意两个状态之间的代价。方向 \(D\) 中状态 \(s\) 的 F2F 启发式通过估计 \(s\) 与对向前沿之间的代价来计算。\(f\) 值为 \(f_D(s) = g_D(s) + \min_{s' \in \mathit{Open}_{\mathit{OD}}} (h(s, s') + g_{\mathit{OD}}(s'))\)。我们使用与 (Eckerle et al. 2017 (https://arxiv.org/html/2606.07047#bib.bib9)) 相同的双可采纳性和双一致性定义。

![图 1：吸引子显示为圆圈，关联的状态以匹配颜色显示。Open 列表以较浅色调显示，其余状态在 Closed 列表中。没有关联前沿状态的吸引子显示为灰色。](placeholder)

#### 吸引子 吸引子 (Zou et al. 2025 (https://arxiv.org/html/2606.07047#bib.bib1)) 最初被引入作为在最佳优先搜索中存储完整 Closed 列表的一种内存高效替代方案。它们通过仅存储精心选择的少量状态来稀疏地表示 Closed 列表，并将这些状态用作解重构的锚点。在搜索过程中，添加到 Open 列表的每个状态都被分配到一个吸引子，并且每个吸引子（除了 \(\mathit{start}\)）都链接到一个父吸引子，形成一个树结构，作为完整 Closed 列表的紧凑替代。图 1 (https://arxiv.org/html/2606.07047#Sx2.F1) 说明了吸引子如何分解搜索空间。给定一个距离函数 \(h_{\mathrm{dist}}: \mathcal{S} \times \mathcal{S} \rightarrow \mathbb{R}_{\geq 0}\)，吸引子的选择使得可以通过**贪婪追踪**来重构通往 Open 列表中任何状态 \(s\) 的路径。形式化地，设 \(a(s)\) 表示分配给 \(s\) 的吸引子。贪婪追踪通过重复应用更新 \(s \leftarrow \arg\min_{s' \in \mathrm{Pred}(s)} h_{\mathrm{dist}}(s', a(s))\) 来进行，直到到达吸引子 \(a(s)\)，之后通过父吸引子递归地继续追踪，直到到达 \(\mathit{start}\)。每个这样的贪婪段对应于当前通往 \(s\) 的最佳路径的一部分，这允许安全地丢弃所有非吸引子状态，同时仍然能够完整地重构解。关于如何维护吸引子的更多细节见附录。

## 方法 在 F2F 启发式中，计算一个搜索方向中某个状态的启发式值需要将其与对向前沿中的所有状态进行比较，以获得最优路径代价的有效低估。虽然这提供了极具信息量的指导，但也带来了大量的计算开销。为了降低这种成本，我们引入了前向-吸引子 (F2A) 启发式。尽管吸引子最初是为了稀疏化 Closed 列表而提出的，但它们还有一个重要的结构特性：它们形成了前沿状态的祖先状态的稀疏集合。F2A 利用这一结构，将对整个对向前沿的比较替换为对一个小得多的、动态维护的活跃吸引子集合（记为 \(\mathit{Attrs}_D\)）的比较。如图 2 所示，计算某个状态 \(s\) 的 F2F 启发式需要对 \(s\) 与对向前沿中的所有状态（黄色高亮）进行成对评估。相比之下，F2A 启发式只针对对向方向中那些至少有一个关联前沿状态的活跃吸引子（红色高亮）来评估 \(s\)。形式化地，方向 \(D\) 中状态 \(s\) 的 F2A 启发式计算如下：
\[
h_D(s) = \min_{s' \in \mathit{Attrs}_{\mathit{OD}}} \bigl( h(s, s') + g_{\mathit{OD}}(s') \bigr).
\]
由于迄今为止发现的所有最小代价路径都必须经过其对应的吸引子，F2A 在保持最优性保证的同时，减少了成对评估的次数。¹¹1 F2A 仅保留那些在 Open 列表中有关联状态的活跃吸引子（如图 1 中的彩色部分），而不是完整的吸引子树。

![图 2：F2F 启发式估计到对向前沿的距离（黄色所示）。F2A 启发式估计到对向吸引子的距离（红色所示）。](placeholder)

### 算法概述 使用 F2A 启发式的 Bi-HS 遵循用于 F2F 启发式的标准 Bi-HS 循环，只需要增加少量簿记工作来维护活跃吸引子集合。成对启发式 \(h(s, s')\) 必须是双一致的。整体过程包括以下步骤，如算法 1 所示。在每次迭代中，搜索：

1. **选择搜索方向**：一种常用策略（我们采用的）是选择 Open 列表 \(\mathit{Open}_D\) 较小的方向 \(D\)（算法 1 第 6 行），如 Holte et al. (2017 (https://arxiv.org/html/2606.07047#bib.bib8)) 所述。
2. **扩展一个状态**：选择 \(\mathit{Open}_D\) 中具有最小 \(f_D\) 值（平局时选择更大 \(g_D\) 值）的状态 \(s\) 进行扩展（算法 1 第 7–8 行）。生成其后继状态，分配 \(f\) 值，插入到 \(\mathit{Open}_D\) 中，并用于更新 \(U\)（算法 1 第 14–24 行）。每个后继状态的启发式在生成时通过将该状态与对向方向的吸引子 \(\mathit{Attrs}_{\mathit{OD}}\) 进行比较来计算（算法 1 第 21 行）。
3. **更新吸引子**：扩展 \(s\) 时，如果找到通往某个后继状态 \(s'\) 的更优路径，则更新 \(s'\) 的吸引子（算法 1 第 17 行）。算法尝试为 \(s'\) 分配与 \(s\) 相同的吸引子，以最小化维护的吸引子数量。只有当从 \(s'\) 向该吸引子进行贪婪追踪会经过 \(s\) 时，才允许这样做（算法 1 第 27 行）。如果条件成立，\(s'\) 继承 \(s\) 的吸引子（算法 1 第 29–30 行）。否则，\(s\) 成为 \(s'\) 的吸引子，并插入到 \(\mathit{Attrs}_D\) 中（算法 1 第 32 行）。此更新逻辑遵循 Zou et al. (2025 (https://arxiv.org/html/2606.07047#bib.bib1)) 的相同原则²²2我们在发现相同代价的路径时也采用相同的平局处理策略。；伪代码中省略了细节以保持清晰。通过这种方式分配吸引子，\(\mathit{Attrs}_D\) 形成了一个稀疏的祖先状态集合，当前通往前沿状态的所有最佳路径都必须经过这些祖先。这种稀疏性使得 F2A 启发式的计算成本大大降低，同时仍然提供强大的引导。
4. **检查终止**：当当前最佳解代价 \(U\) 小于或等于下界 \(L\)（已找到最优路径）或 Open 列表为空（无解）时，搜索终止（算法 1 第 5 行）。

**算法 1** 使用 F2A 启发式的双向搜索

```
1: procedure F2A 双向搜索(start, goal)
2:   Attrs_F ← {start}, Attrs_B ← {goal}
3:   Open_F ← {start}, Open_B ← {goal}
4:   U, L ← ∞
5:   while 未终止(U, L) do
6:     D ← 选择方向()
7:     从 Open_D 中弹出具有最小 f_D 值的状态 s
8:     扩展(s, D)
9:     L ← 更新下界()
10:    从 Attrs_D 中移除所有未分配的吸引子 a
11:
12: procedure 扩展(s, D)
13:   将 s 从 Open_D 移入 Closed_D
14:   for s' ∈ Succ_D(s) do
15:     if g_D(s') ≥ g_D(s) + c(s, s') then
16:       g_D(s') = g_D(s) + c(s, s')
17:       更新吸引子(s, s', D)
18:       if s' ∈ Open_D ∪ Closed_D then
19:         将 s' 从 Open_D ∪ Closed_D 中移除
20:       if s' ∉ Open_D then
21:         h_D(s') = min_{s'' ∈ Attrs_OD} (h(s', s'') + g_OD(s''))  ▷ 如果尚未计算
22:         将 s' 以 g_D(s') + h_D(s') 插入 Open_D
23:       if s' ∈ Open_OD then
24:         U ← min(U, g_F(s') + g_B(s'))
25:
26: procedure 更新吸引子(s, s', D)
27:   如果贪婪追踪从 s' 到 a(s) 经过 s 则
28:     a(s') ← a(s)
29:   否则
30:     a(s') ← s
31:     将 s 插入 Attrs_D
32:   结束如果
33: 结束 procedure
```