增量启发式搜索是人工智能中的一类算法，用于解决图随时间变化时在图中的路径查找问题。与经典启发式搜索方法（如A*）不同，后者在环境每次变化时都会从头重新计算完整解，而增量启发式搜索算法则尽可能复用先前搜索努力中的信息。这种复用可以显著降低动态或部分已知环境中的计算成本，使其在机器人导航、视频游戏寻路和自动驾驶车辆路线规划等应用中特别有价值。
其核心思想是维护一个启发式函数和一棵搜索树，随着边成本变化或发现新障碍物而增量更新。当发生变化时，算法会识别先前搜索中哪些部分仍然有效、哪些需要修订，然后传播必要的更新。这种方法既不同于经典启发式搜索（假设图是静态的），也不同于无启发式的增量搜索（可能复用路径但缺乏启发式的引导）。
历史发展
增量启发式搜索的基础奠定于20世纪90年代末和21世纪初。最具影响力的算法D Lite由Sven Koenig和Maxim Likhachev于2002年提出。D Lite基于Anthony Stentz于1994年为移动机器人导航设计的早期D算法。D Lite简化了原始D*，同时保持了其效率，并已成为该领域的标准参考。
另一个关键算法是终身规划A（LPA），也由Koenig和Likhachev于2001年提出。LPA处理边成本变化，同时保持启发式的一致性，并构成了D Lite的基础。该领域此后扩展出多种变体，如广义自适应A（GAA）和任意时间D*，这些变体在解质量与计算时间之间进行权衡。
算法原理
增量启发式搜索算法通常为每个节点维护两类值：g值（从起点到该节点的已知最优路径成本）和h值（到目标的启发式估计）。它们还跟踪节点是否一致，即其g值是否等于其前驱节点中的最小值。当边成本变化时，算法更新受影响节点的g值，并通过按f = g + h排序的优先队列在搜索树中传播变化。
关键创新在于LPA和D Lite中使用“rhs值”（右侧值），它表示前驱节点g值加上边成本的最小值。如果节点的g值等于其rhs值，则该节点是局部一致的。算法维护一个局部不一致节点的列表，并按其键（一对值(min(g, rhs) + h, min(g, rhs))）的顺序处理它们。这确保了只重新计算搜索中必要的部分。
在机器人和人工智能中的应用
增量启发式搜索广泛用于机器人在未知或变化环境中的路径规划。例如，探索建筑物的机器人可能最初基于地图规划路径，但随着发现新障碍物（如关闭的门），它可以增量更新计划而无需重新开始。这对于计算时间有限的实时导航至关重要。
在视频游戏中，非玩家角色（NPC）通常需要在具有移动障碍物或变化目标的动态地形中导航。增量启发式搜索支持高效重规划，提高游戏响应性。该技术还应用于物流领域，其中配送路线必须适应交通状况，以及网络路由中链路成本波动的场景。
与其他搜索方法的比较
经典A搜索在静态图上是最优且完备的，但在动态环境中效率低下，因为图变化时会丢弃所有先前工作。增量启发式搜索保留了A的最优性保证，同时复用先前计算。然而，它需要额外内存来存储搜索树和一致性信息。
另一种相关方法是任意时间搜索，旨在快速找到良好解，然后在更多时间内改进。一些增量算法，如任意时间D*，结合了这两种特性：它们可以快速返回次优解，并随时间允许而细化。这在时间关键的应用中特别有用。
当前研究与未来方向
增量启发式搜索的近期研究聚焦于扩展到非常大的图、处理连续状态空间以及与机器学习集成。例如，基于学习的启发式可用于改进初始h值，减少扩展次数。还有关于在多核处理器上并行化增量搜索以及将其与基于采样的规划器（如RRT*）结合用于高维问题的研究。
在现代人工智能系统的背景下，增量启发式搜索对于具身代理仍然相关，例如Waymo自动驾驶车辆或特斯拉自动驾驶系统中的代理，其中实时重规划至关重要。这些原理也影响机器学习和深度学习中学习搜索的研究，尽管经典算法仍是保证最优性的标准。
参见
参考文献
- Koenig, S., & Likhachev, M. (2002). D* Lite. Proceedings of the National Conference on Artificial Intelligence.
- Koenig, S., & Likhachev, M. (2001). Lifelong Planning A*. Artificial Intelligence.
- Stentz, A. (1994). Optimal and Efficient Path Planning for Partially-Known Environments. IEEE International Conference on Robotics and Automation.