Q*搜索：基于深度Q网络的启发式搜索

https://prl-theworkshop.github.io/prl2024-icaps/papers/9.pdf

Q* Search: Heuristic Search with Deep Q-Networks

Q*搜索：基于深度Q网络的启发式搜索

摘要

几十年来，高效解决具有大动作空间的问题一直是人工智能社区的重要课题。这是因为A*搜索的计算和内存需求随着动作空间的大小线性增长。当A*搜索使用由计算成本高昂的函数逼近器（如深度神经网络）学习的启发式函数时，这种负担变得更加明显。为了解决这个问题，我们提出了Q*搜索，这是一种利用深度Q网络引导搜索的算法，以利用一个事实：通过一次前向传播深度Q网络，可以计算一个节点的子节点的转移成本和启发式值的总和，而无需显式生成这些子节点。这显著减少了计算时间，并且每次迭代只需生成一个节点。我们在不同领域和动作空间中使用Q*搜索，结果表明，随着动作大小的增加，Q*搜索仅受到较小的运行时开销影响。此外，我们的实证结果表明，Q*搜索比A*搜索快129倍，生成的节点数少1288倍。最后，尽管从深度神经网络中获取可接受的启发式函数是一个持续的研究领域，但我们证明了在启发式函数不低估状态的转移成本和“成本到目标”总和的情况下，Q*搜索保证能找到最短路径。

引言

A*搜索（Hart, Nilsson, and Raphael 1968）是一种搜索算法，用于寻找从给定起始状态到给定目标状态的路径，其中目标是一组目标状态。通过维护一个由表示状态的节点和表示状态之间转移的边组成的搜索树，A*搜索根据给定成本优先扩展节点来执行搜索。节点扩展和计算其子节点成本是A*搜索中最耗时的部分之一。节点扩展通过对给定节点关联的状态应用每个可能的动作来生成子节点。节点的成本通过将其路径成本加上启发式值来计算，其中路径成本是从起始节点到给定节点的转移成本总和，启发式值由启发式函数计算，该函数估计从节点关联状态到最近目标状态的“成本到目标”。由于A*搜索的每次迭代包括从优先队列中移除一个节点、扩展该节点、计算其子节点的成本并将其子节点推入优先队列，因此每次迭代生成的新节点数量、启发式函数的应用次数以及推入优先队列的节点数量随动作空间的大小线性增加。这种不断增长的计算负载可能非常巨大，特别是考虑到启发式函数的评估可能是计算密集型的。此外，在许多领域中，生成状态的过程也可能非常耗时，尤其是在运动规划和化学合成中。然而，值得注意的是，这种计算努力中的大部分可能是冗余的，因为A*搜索通常不会扩展它生成的每个节点。

随着深度神经网络（DNNs）（Schmidhuber 2015）作为启发式函数的更频繁使用，减少这种线性增长的计算成本的需求变得更加相关。虽然DNN是通用函数逼近器（Hornik, Stinchcombe, and White 1989），但与基于领域知识、人类直觉和模式数据库的启发式函数相比，它们的计算成本较高（Culberson and Schaeffer 1998）。尽管如此，DNN能够学习启发式函数来解决从谜题（Chen and Wei 2011; Arfaee, Zilles, and Holte 2011; McAleer et al. 2019; Agostinelli et al. 2019）到量子计算（Zhang et al. 2020）再到化学合成（Chen et al. 2020）的问题，同时对问题的结构做出很少的假设。由于其灵活性和泛化能力，DNN提供了以领域无关的方式学习启发式函数的潜力。消除计算成本随动作空间大小的线性增长将使DNN在具有大动作空间的应用中变得实用，例如多序列对齐、定理证明、程序合成和化学合成。

在本文中，我们介绍了Q*搜索，这是一种由深度Q网络（DQN）（Mnih等，2015）引导的搜索算法，每次迭代只需生成一个节点。DQN是一种深度神经网络，它将单个状态映射到其每个后继状态的转移成本与启发式值的总和。这使得我们每次迭代只需生成一个节点，因为我们可以将节点和动作的元组存储在优先队列中，其优先级由DQN决定。当从队列中移除一个节点和动作的元组时，我们可以通过将动作应用于与该节点关联的状态来生成一个新节点。此外，启发式函数的应用次数相对于动作空间的大小是恒定的，而不是线性的。因此，Q*搜索唯一依赖于动作空间的方面是将节点及其可应用的所有可能动作推入优先队列。这比显式生成所有子节点更节省内存，因为在我们实现中，每个动作仅是一个整数。我们的理论结果表明，在启发式函数既不低估最短路径成本也不低估转移成本的情况下，Q*搜索保证能找到最短路径。我们在魔方、Lights Out和35-Pancake拼图上的实验结果表明，Q*搜索比A*搜索快几个数量级，并且生成的节点数少几个数量级。虽然这些环境的动作空间是固定的，但Q*搜索算法对动作空间是固定还是动态的并不敏感。在讨论部分，我们讨论了未来工作的方向，即使用结构化预测创建适用于可变动作空间的DQN。

相关工作

部分扩展A*搜索（PEA*）（Yoshizumi, Miura, and Ishida 2000）是为具有大动作空间的问题提出的。PEA*首先通过生成所有子节点来扩展一个节点，但它只保留成本低于某个阈值的子节点。然后，它添加一个簿记结构来记住被丢弃节点的最高成本。PEA*的目的是节省内存，然而，计算需求并未减少，因为从优先队列中移除的每个节点都必须扩展，并且启发式函数必须应用于其所有子节点。值得注意的是，PEA*与Q*正交，可以与其结合使用以进一步减少内存消耗。

增强部分扩展A*搜索（EPEA*）（Felner等，2012）使用领域相关的操作选择函数，仅基于成本生成子节点的子集。然而，当使用函数逼近（如神经网络）作为启发式函数时，由于动作应用导致的启发式值变化不是预先确定的，EPEA*变得不适用。

延迟启发式评估（Helmert 2006）已被用于在A*搜索中每次迭代仅生成一个节点。这是通过为每个子节点分配与其父节点相同的启发式值，并延迟评估子节点直到它们从优先队列中移除来实现的。然而，这会带来不准确性的代价，特别是当子节点的“成本到目标”与其父节点显著不同时。我们在实验中比较了Q*与这种方法，并表明在绝大多数情况下，Q*搜索找到成本更低的解决方案，并且比延迟启发式评估快得多。此外，在我们的实验中，延迟启发式评估有时会因无法优先选择一个子节点而耗尽内存。

预备知识

一个搜索问题实例，记为I = (G, c, start, goal, h)，由图G = (V, E)组成，其中V中的状态（顶点）和E中的边（转移）以及成本函数c：E → R+，为图的边分配成本。实例指定了一个起始状态（start）和一个目标状态（goal）或一个谓词P：V → {0, 1}，指示状态是否满足目标条件。h是一个启发式函数，它为每个状态s分配从s到最近目标状态的最短路径成本的估计值，通常称为“成本到目标”。主要目标是在图G中发现连接start到goal的路径。派生路径的质量是其组成边的累积成本，由成本函数确定。我们用d(s, s')表示G中s和s'之间的最短（最便宜）路径，用d(start, goal)表示C*。

请注意，图通常是隐式给出的，其中仅给出初始状态以及一组转移函数A。这些函数表示各种转移，例如不同机器人配置、拼图排列或领域无关规划问题中的STRIPS类状态之间的转移。在这项工作中，我们遵循这一假设，这意味着我们提供了一个动作空间A，并且我们假设边集E对应于从每个状态s应用每个动作a ∈ A。我们用A(s, a)表示从状态s应用动作a得到的状态，并用c_a(s)表示相应的转移成本。

深度近似值迭代

值迭代（Puterman and Shin 1978）是一种动态规划算法，是解决马尔可夫决策过程（MDP）和强化学习问题（Bellman 1957; Bertsekas and Tsitsiklis 1996; Sutton and Barto 1998）的核心。它迭代地计算每个状态的期望值，最初假设所有状态的值为零，并通过应用贝尔曼更新逐步改进这些估计。值迭代通常用于具有随机动作效果和潜在无限规划范围的最大化问题。然而，在启发式搜索领域，它可以重新定义为解决最小化问题，特别是旨在最小化成本的问题，具有确定性效果和有限规划范围。这种重新定义由以下方程表示：

在这种情况下，V表示“成本到目标”函数，估计从给定状态通过最短路径到达最近目标状态的成本。这个“成本到目标”函数可以无缝地作为A*搜索的启发式函数。

然而，对于具有大状态空间的问题，将V表示为查找表的内存消耗过大。例如，魔方有4.3 × 10^19个可能的状态。因此，我们转向近似值迭代（Bertsekas and Tsitsiklis 1996），其中V被表示为一个参数化函数vθ，参数为θ。我们选择将vθ表示为深度神经网络（DNN）。通过使用随机梯度下降最小化以下损失函数来学习参数θ：

其中θ'是用于计算更新后的“成本到目标”的“目标”DNN的参数。使用目标DNN已被证明可以使训练过程更加稳定（Mnih等，2015）。在训练期间，参数θ'会定期更新为θ。虽然我们无法保证收敛到v*，但近似值迭代已被证明可以近似v*（Bertsekas and Tsitsiklis 1996）。对于本文研究的谜题，用于训练vθ的状态是通过随机打乱目标状态0到K次生成的。这使得学习能够从目标状态传播到训练集中的所有其他状态。这种深度神经网络和近似值迭代的结合被称为深度近似值迭代（DAVI）。

批量加权A*搜索

A*搜索（Hart, Nilsson, and Raphael 1968）被公认为最广泛认可和最具影响力的搜索算法之一。A*搜索维护一个优先队列OPEN，从中迭代移除并扩展成本最低的节点，以及一个字典CLOSED，用于映射已生成的状态及其路径成本。每个节点的成本为f(n) = g(n) + h(n.s)，其中g(n)是路径成本，即从起始节点到n的路径上的转移成本总和，h(n.s)是启发式值，即从与n关联的状态到最近目标状态的估计“成本到目标”。扩展节点后，其子节点的状态如果尚未在CLOSED中，则将其状态添加到CLOSED中，然后推入OPEN。如果子节点n的状态已在CLOSED中，但n的路径成本比CLOSED中记录的路径成本更低，则更新CLOSED中与n关联的状态的路径成本，并将n添加到OPEN中。算法开始时，OPEN中仅包含与起始状态对应的节点nstart，并在从OPEN中移除与目标状态关联的节点时终止。

当使用学习到的启发式函数（例如使用DNN）执行A*搜索时，计算启发式值可能会使A*搜索变得计算成本高昂。为了缓解这个问题，可以利用图形处理单元（GPU）提供的并行性，通过扩展B个最低成本的节点并并行计算它们的启发式值。此外，即使使用计算成本低且信息量大的启发式函数，A*搜索也可能既耗时又耗内存。为了解决这个问题，可以使用一种称为加权A*搜索（Pohl 1970）的A*搜索变体，以潜在更高的解决方案成本换取潜在更快的运行时间和更少的内存使用。加权A*搜索计算每个节点的成本为f(n) = λg(n) + h(n.s)，其中λ ∈ [0, 1]是一个标量权重。这种每次迭代扩展B个节点并通过λ加权路径成本的组合被称为批量加权A*搜索（BWAS）。BWAS是A*搜索的推广，因为通过将λ设置为1和B设置为1可以恢复A*搜索。如果启发式函数是可接受的（Hart, Nilsson, and Raphael 1968），A*搜索保证能找到最短路径，而加权A*搜索在启发式函数可接受的情况下保证能找到有界次优路径。可接受的启发式函数是一个从不低估最短路径成本的函数。此外，已经证明，在给定可接受的启发式函数的情况下，BWAS保证能找到有界次优路径（Agostinelli等，2021）。虽然DNN不能保证是可接受的，但使用DNN获得可接受的启发式函数是一个正在进行的研究领域（Ernandes and Gori 2004; Agostinelli等，2021）。BWAS算法的伪代码在算法1中给出。

Q学习

与DAVI类似，目标DNN的参数ϕ'在训练期间会定期更新为ϕ。

与值迭代类似，Q学习在表格情况下已被证明可以收敛到最优Q因子q*（Watkins and Dayan 1992）。在近似情况下，Q学习比DAVI具有计算优势，因为虽然DQN的参数数量随动作空间的大小增长，但每次更新计算损失函数所需的前向传播次数保持不变。我们将在结果中展示，在大动作空间中，Q学习的训练时间比DAVI快127倍。

方法 Q*搜索

理论分析

实验评估

在本节中，我们详细介绍了对Q*的实证评估。

设置、基线方法和网络架构

我们在多个领域中评估Q*，包括魔方（12个动作）、7x7 Lights Out谜题（Agostinelli等，2019）（49个动作）和35-Pancake谜题（49个动作）。

我们将Q*与A*搜索以及A*搜索的延迟版本（Helmert 2006）进行比较，后者我们称为Ad*，其中每个子节点的启发式值设置为与父节点的启发式值相同。所有算法每次迭代扩展一批节点N，而不是单个节点，并使用权重λ（即我们评估了每个算法的批量加权版本）。A*和Ad*都使用通过DVAI训练的状态“成本到目标”函数模型，而Q*使用通过Q学习训练的状态-动作“成本到目标”估计。

我们使用ADAM优化器（Kingma and Ba 2014）以批量大小为10,000训练每个模型，进行120万次迭代。我们按照DeepCubeA源代码（Agostinelli等，2020）中定义的相同计划更新目标网络。我们用于训练和搜索的机器配备了48个2.4 GHz Intel Xeon中央处理器（CPU）、192 GB随机存取内存和两个32GB NVIDIA V100 GPU。

先前使用深度强化学习和A*搜索解决魔方的工作在BWAS中使用了λ = 0.6和N = 10000（Agostinelli等，2019）。然而，由于这些搜索参数在速度、内存使用和路径成本之间进行了权衡，我们还研究了不同参数设置下的性能，以了解A*搜索和Q*搜索在这些维度上的比较。因此，我们尝试了λ ∈ {0.0, 0.2, 0.4, 0.6, 0.8, 1.0}和N ∈ {100, 1000, 10000}的所有组合。对于每种方法和每个动作空间，我们修剪了导致机器内存不足或需要超过24小时完成的所有组合。我们使用了与Agostinelli等（2019）先前工作中相同的1,000个魔方测试状态和500个Lights Out测试状态。我们生成了500个35-Pancake谜题的测试状态。每个测试状态是通过将谜题打乱1,000到10,000次获得的。

结果

结果如图1和图2所示。这些图展示了平均路径成本与找到解决方案的平均时间或生成的平均节点数之间的关系。两图的y轴均采用对数刻度，每个数据点代表特定的搜索参数设置。虚线表示识别到的最低平均路径成本，而实线表示最快的解决方案时间或最少的节点生成数，具体取决于上下文，这是由假设的可接受平均路径成本阈值决定的。

图中显示，对于几乎任何可能的路径成本阈值，Q* 都比 A* 和 Ad* 显著更快且生成的节点数显著更少。Ad* 总体上比 A* 有所改进，因为它在每次迭代中只生成一个节点。然而，由于它为节点的所有子节点分配相同的 f 值，它无法优先考虑一个子节点，从而引入了低效性。

所有算法实现的最低平均路径成本仍然相当，最大差异仅为 0.1%，在 RC 领域中观察到。总体而言，在 RC 中，A* 在最佳情况下找到最短路径的概率为 59%，而 Q* 为 56.4%。在 Lights Out 中，A* 和 Q* 在最佳情况下找到最短路径的概率均为 100%。

消融研究：变化动作数量

为了研究 Q* 在动作数量增加时的性能，我们进行了一项消融研究，重点关注魔方领域。标准的 RC 动作空间包括 12 个不同的动作：每个面可以顺时针或逆时针旋转。我们将此动作空间表示为 RC(12)。在消融研究中，我们向 RC 动作空间添加元动作，创建了 RC(156) 和 RC(1884)。RC(156) 包含 RC(12) 中的所有动作以及大小为 2 的所有动作组合 RC(144)。RC(1884) 包含 RC(156) 中的所有动作以及大小为 3 的所有动作组合（1728）。为了确保这些额外的元动作没有冗余，所有元动作的成本也设置为 1。

在之前报告的实验中，我们对模型进行了 120 万次迭代的训练。然而，随着动作空间规模的增加，DAVI 的训练变得不可行。表 1 显示，DAVI 在 RC(156) 上训练需要超过一个月，而在 RC(1884) 上训练需要近一年。因此，我们根据动作空间大小与 RC(12) 的差异按比例减少批量大小。由于 RC(156) 的动作数量是 RC(12) 的 13 倍，我们使用 769 的批量大小训练 DAVI；由于 RC(1884) 的动作数量是 RC(12) 的 157 倍，我们使用 63 的批量大小训练 DAVI。此外，鉴于 A* 搜索中动作空间扩展导致的求解时间增加，我们使用 100 个状态用于 RC(156)，20 个状态用于 RC(1884)，而不是 RC(12) 中使用的完整 500 个状态。

当比较A*和Q*在不同动作空间中的表现时，表3显示，尽管RC(1884)的动作数量是RC(12)的157倍，但Q*找到解决方案的时间仅增加了3.7倍，生成的节点数仅增加了2.3倍。而在相同情况下，A*的求解时间增加了37倍，生成的节点数增加了62.7倍。总体而言，Q*在这两个指标上的表现都更好。对于RC(156)，由于添加了元动作，Q*找到解决方案的时间甚至比RC(12)更短。

训练期间的性能‍‍

为了监控训练期间的性能，我们跟踪了通过简单地根据成本函数贪婪行为解决的状态的百分比。这些状态的生成方式与训练状态的生成方式相同。图5展示了该指标随训练时间的变化情况。结果显示，在RC(12)中，DAVI略优于Q-learning。在RC(156)和RC(1884)中，尽管DAVI的批量较小，但其性能与Q-learning相当。这可能是由于DAVI仅学习单个状态的成本函数，而Q-learning必须学习所有可能下一个状态的转移成本和成本函数的总和。

讨论‍‍‍‍

随着动作空间规模的增加，Q* 在求解时间和生成节点数方面比 A* 显著更有效。在最大的动作空间中，Q* 比 A* 快几个数量级，生成的节点数少几个数量级，同时找到的解决方案具有相同的平均路径成本。对于较小的动作空间，虽然 Q* 几乎总是更快且内存效率更高，但 A* 能够找到比 Q* 成本略低的解决方案。这可能是由于 vθ 和 qϕ 计算内容的差异。由于 DQN 执行的前向传播 qϕ 与使用 vθ 进行一步前瞻相同，这可能使得学习 qϕ 比学习 vθ 更困难。这也解释了为什么在 Lights Out 中，Ad* 在某些情况下比 Q* 更快且生成的节点更少。然而，随着路径成本阈值的降低，Q* 的表现更好。由于 Q-learning 和 Q* 的训练和搜索速度显著更快，通过更长的训练时间和使用更大的 λ 或 N 值进行搜索，这一差距可能会缩小。

尽管本研究中使用的 DQN 是针对固定动作空间的，但 Q* 搜索可以轻松应用于动态动作空间，前提是 DQN 能够计算此类动作空间的 Q 因子。因此，通过选择使用结构化预测的 DQN 架构，可以使用 Q* 解决具有动态动作空间的问题。例如，可以修改图卷积策略网络（You et al. 2018，用于分子优化）以估计与动作空间对应的图结构问题的 Q 因子。在涉及序列的问题中，可以使用长短期记忆网络（Hochreiter and Schmidhuber 1997）或 Transformer 架构（Vaswani et al. 2017）来计算 Q 因子。这将直接应用于具有大但可变动作空间的问题，如化学合成、定理证明、程序合成和网络导航。

结论‍‍‍

高效解决具有大动作空间的搜索问题几十年来一直是人工智能社区的重要课题（Russell 1992; Korf 1993; Yoshizumi, Miura, and Ishida 2000）。Q* 搜索使用 DQN 消除了与大动作空间相关的大部分计算和内存负担，每次迭代仅生成一个节点，并且每次迭代仅需一次启发式函数的应用。与 A* 搜索相比，Q* 搜索速度提高了 129 倍，生成的节点数减少了 1288 倍。当动作空间规模增加 157 倍时，Q* 搜索的时间仅增加 3.7 倍，生成的节点数仅增加 2.3 倍。Q* 高效扩展到大规模动作空间的能力可能在解决许多具有大动作空间的重要问题中发挥重要作用。

原文链接https://prl-theworkshop.github.io/prl2024-icaps/papers/9.pdf