A*算法是路径规划领域的经典算法，在实际应用中衍生出多种变种以适应不同场景。本文系统梳理 A* 算法及其主要变种，包括适用于动态环境的 D*、D* Lite、LPA*，以及实时规划的 ARA*、LRTA*、RTAA* 等。

概述

A* 算法家族可以按照应用场景分为以下几类：

A* 算法基础

A*算法是一种启发式搜索算法，用于在图形或网络中找到最短路径。它结合了Dijkstra算法的广度优先搜索和启发式函数的评估，以提高搜索效率。

基本概念

• 评估函数：A*算法的核心是评估函数 $f(n) = g(n) + h(n)$，其中：

  1. g(n)：从起点到当前节点 n 的实际路径代价，这个值是确定的，通过路径累加得到。
  2. h(n)：从当前节点 n 到目标节点的估计代价（启发式函数），这是一个预测值。
  3. f(n)：从起点经过节点 n 到达目标节点的总估计代价。

• 启发式函数的设计原则：

  1. 可采纳性（Admissible）：启发式函数 $h(n)$ 必须不高估从节点 n 到目标的实际代价，即 $h(n) \leq h^(n)$，其中 $h^(n)$ 是真实的最短距离。只有满足可采纳性，A* 才能保证找到最优解。
  2. 一致性（Consistent）：对于所有节点 n 和其后继节点 n’，满足 $h(n) \leq c(n, n’) + h(n’)$，其中 $c(n, n’)$ 是从 n 到 n’ 的实际代价。一致性保证了 A* 在扩展节点时一旦找到目标就可以立即停止。

• 开放列表（Open List）：存储待扩展的节点，通常使用优先队列（最小堆）实现，按照 f(n) 值从小到大排序。

• 封闭列表（Closed List）：存储已经扩展过的节点，避免重复处理。通常使用哈希集合实现。

• 最优性保证：当启发式函数满足可采纳性时，A* 算法保证能找到从起点到目标的最短路径。这是因为 A* 总是优先扩展 f(n) 最小的节点，而可采纳的启发式保证了 f(n) 不会低估真实代价。

常用启发式函数

对于网格形式的图，有以下这些启发函数可以使用：

• 若图形中只允许朝上下左右四个方向移动，使用曼哈顿距离：
  $$
  h(n) = |x_n - x_{goal}| + |y_n - y_{goal}|
  $$

• 若图形中允许朝八个方向移动（包括对角线），使用对角距离（切比雪夫距离）：
  $$
  h(n) = \max(|x_n - x_{goal}|, |y_n - y_{goal}|)
  $$

• 若图形中允许朝任何方向移动，使用欧几里得距离：
  $$
  h(n) = \sqrt{(x_n - x_{goal})^2 + (y_n - y_{goal})^2}
  $$

基本流程

1. 初始化：

   • 创建开放列表（优先队列）和封闭列表（哈希集合）。
   • 将起点加入开放列表，设置 g(start) = 0，f(start) = h(start)。

2. 主循环：重复以下步骤直到找到目标或开放列表为空：

   • 从开放列表中取出 f(n) 值最小的节点 n。
   • 若 n 是目标节点，则通过回溯父节点指针重建路径，算法结束。
   • 将 n 从开放列表移除，加入封闭列表。
   • 扩展节点 n：遍历 n 的所有相邻节点 m：
     • 若 m 在封闭列表中，跳过该节点。
     • 计算 m 的新 g 值：g_new = g(n) + c(n, m)，其中 c(n, m) 是从 n 到 m 的边代价。
     • 若 m 不在开放列表中，或 g_new < g(m)：
       • 更新 g(m) = g_new
       • 更新 f(m) = g(m) + h(m)
       • 设置 m 的父节点为 n
       • 若 m 不在开放列表中，将其加入

3. 结束条件：

   • 若开放列表为空且未找到目标，说明不存在从起点到目标的路径。
   • 若找到目标，返回重建的路径。

时间复杂度：最坏情况下为 $O(b^d)$，其中 b 是分支因子（每个节点的平均邻居数），d 是解的深度。使用好的启发式函数可以大幅减少实际搜索的节点数。

空间复杂度：$O(b^d)$，需要存储所有已访问和待访问的节点。

算法演示

Bidirectional A*（双向 A*）

双向 A* 算法同时从起点和终点进行搜索，当两个搜索方向的"前沿"相遇时，合并得到完整路径。

基本概念

• 双向搜索思想：同时从起点向终点搜索（前向搜索）和从终点向起点搜索（后向搜索）。当两个搜索方向扩展到同一个节点时，就可以合并两条路径得到完整解。

• 搜索空间减少：单向搜索的搜索空间约为 $O(b^d)$，而双向搜索理论上可以将搜索空间减少到 $O(2b^{d/2})$，其中 b 是分支因子，d 是解的深度。当 d 较大时，这种减少是显著的。

• 相遇条件：当某个节点同时被前向搜索和后向搜索扩展时，或者当一个方向的搜索扩展到另一个方向已经访问过的节点时，可以认为两个搜索"相遇"了。

• 启发式函数：

  • 前向搜索：$f_{forward}(n) = g_{forward}(n) + h(n, goal)$
  • 后向搜索：$f_{backward}(n) = g_{backward}(n) + h(n, start)$

• 路径合并：当两个搜索相遇时，完整路径代价为 $g_{forward}(n) + g_{backward}(n)$，需要在所有相遇节点中选择代价最小的。

基本流程

1. 初始化：

   • 创建两个开放列表 Open_forward 和 Open_backward。
   • 创建两个封闭列表 Closed_forward 和 Closed_backward。
   • 将起点加入 Open_forward，g_forward(start) = 0。
   • 将终点加入 Open_backward，g_backward(goal) = 0。

2. 交替扩展：重复以下步骤直到两个搜索相遇：

   • 选择 f 值较小的那个方向的开放列表进行扩展（保持两个方向的搜索进度大致平衡）。
   • 从选定的开放列表中取出 f 值最小的节点 n。
   • 若 n 同时在另一个方向的封闭列表中，说明两个搜索相遇，跳转到步骤 4。
   • 扩展 n 的相邻节点，更新 g 值和 f 值，将新节点加入对应的开放列表。
   • 将 n 移入对应的封闭列表。

3. 检查相遇：每次扩展后检查当前节点是否在另一个方向的已访问集合中。

4. 路径重建：

   • 找到所有同时被两个方向访问的节点。
   • 对于每个这样的节点 n，计算总路径代价：cost = g_forward(n) + g_backward(n)。
   • 选择代价最小的节点作为相遇点。
   • 合并前向路径和后向路径得到完整路径。

注意：双向搜索的效率取决于两个搜索方向能否在搜索空间的"中间"相遇。如果相遇点靠近起点或终点，效率提升有限。

算法演示

ARA*（Anytime Repairing A*）

ARA* 是一种任意时间算法，可以在有限时间内返回一个可行解（可能不是最优），然后随着时间增加逐步优化解的质量，最终收敛到最优解。

基本概念

• 任意时间特性：ARA* 可以在任何时刻被中断并返回当前找到的解。时间越充裕，解的质量越好。这对于实时系统非常重要，因为系统可能无法等待最优解的计算完成。

• 膨胀因子（Inflation Factor）：ARA* 引入一个膨胀因子 $\epsilon \geq 1$，将评估函数修改为：
  $$
  f(n) = g(n) + \epsilon \cdot h(n)
  $$
  当 $\epsilon > 1$ 时，启发式函数被放大，算法会更激进地朝目标方向搜索，速度更快但可能错过最优解。

• 加权 A*：当 $\epsilon > 1$ 时，算法称为加权 A*（Weighted A*）。它找到的解的代价最多是最优解的 $\epsilon$ 倍，即 $cost \leq \epsilon \cdot cost_{optimal}$。

• 增量式优化：ARA* 不是每次从头开始搜索，而是复用上一轮搜索的结果。当减小 $\epsilon$ 后，只需要更新受影响的节点，而不是重新计算所有节点。

• 膨胀因子序列：通常使用递减序列，如 $\epsilon = {3.0, 2.0, 1.5, 1.0}$。当 $\epsilon = 1.0$ 时，算法退化为标准 A*，保证找到最优解。

基本流程

1. 初始化：

   • 设置初始膨胀因子 $\epsilon = \epsilon_0$（如 3.0）。
   • 初始化开放列表和封闭列表。
   • 将起点加入开放列表，g(start) = 0，f(start) = $\epsilon \cdot h(start)$。

2. 加权搜索阶段：

   • 执行类似 A* 的搜索，但使用 $f(n) = g(n) + \epsilon \cdot h(n)$ 作为评估函数。
   • 当找到目标时，记录当前解的路径和代价。
   • 当前解的代价最多是最优解的 $\epsilon$ 倍。

3. 减小膨胀因子：

   • 将 $\epsilon$ 减小到下一个值（如从 3.0 减到 2.0）。
   • 若 $\epsilon = 1.0$，跳转到步骤 5（最优搜索）。

4. 增量式更新：

   • 对于封闭列表中的所有节点，重新计算 $f(n) = g(n) + \epsilon \cdot h(n)$。
   • 将 f 值发生变化的节点重新加入开放列表。
   • 返回步骤 2，继续搜索。

5. 最优搜索：

   • 当 $\epsilon = 1.0$ 时，算法等价于标准 A*。
   • 搜索完成后得到的解是最优解。

6. 终止条件：

   • 可以在任何时刻终止算法，返回当前找到的最佳解。
   • 当 $\epsilon = 1.0$ 的搜索完成时，得到最优解。

优势：ARA* 非常适合实时系统。例如，机器人导航时，可以先快速得到一条可行路径让机器人开始移动，然后在移动过程中不断优化路径。

解的质量保证：在膨胀因子为 $\epsilon$ 时找到的解，其代价满足 $cost \leq \epsilon \cdot cost_{optimal}$。

算法演示

LRTA*（Learning Real-time A*）

LRTA* 是一种实时启发式搜索算法，每次只扩展一个节点并立即执行移动。它通过"学习"不断改进启发式函数的估计值，在多次迭代后收敛到最优解。

基本概念

• 实时性：LRTA* 的关键特点是每次决策的时间是恒定的，与问题规模无关。这使得它非常适合实时系统，如游戏 AI 或在线机器人导航。

• 边走边学：LRTA* 不是先规划完整路径再执行，而是边搜索边移动。每次选择一个邻居节点移动过去，然后更新当前状态的知识。

• 启发式值表（H值）：LRTA* 为每个状态维护一个启发式值 H(s)，初始时等于初始启发式函数 h(s)。随着搜索进行，H(s) 会不断更新，越来越接近真实的最短距离。

• 学习更新规则：当从状态 s 移动到 s’ 后，更新 H(s) 为：
  $$
  H(s) \leftarrow \max{H(s), \min_{s’‘}[c(s, s’‘) + H(s’')]}
  $$
  这个更新的含义是：H(s) 应该至少等于"从 s 到最近邻居的代价 + 该邻居的 H 值"。

• 收敛性：在有限状态空间中，如果 LRTA* 反复从起点到目标执行搜索，H 值会收敛到真实的最短距离，最终行为等价于最优策略。

基本流程

1. 初始化：

   • 为所有状态 s 初始化启发式值 H(s) = h(s)，其中 h(s) 是初始启发式函数（如曼哈顿距离）。
   • 设置当前状态为起点。

2. 单步决策：重复以下步骤直到到达目标：

   • 计算当前状态 s 的所有邻居的 f 值：
     $$
     f(s’) = c(s, s’) + H(s’)
     $$
     其中 c(s, s’) 是从 s 到 s’ 的边代价。
   • 选择 f 值最小的邻居 s_best。
   • 执行移动：从 s 移动到 s_best。

3. 学习更新：

   • 更新当前状态（移动前的状态 s）的 H 值：
     $$
     H(s) \leftarrow \max{H(s), \min_{s’‘}[c(s, s’‘) + H(s’')]}
     $$
   • 这个更新确保 H(s) 不会低于从 s 出发的最优一步代价。

4. 更新当前状态：

   • 将当前位置更新为 s_best。
   • 若 s_best 是目标，算法结束；否则返回步骤 2。

5. 多轮迭代（可选）：

   • 若需要更优的解，可以从起点重新开始，使用更新后的 H 值。
   • 经过足够多轮迭代后，H 值会收敛到真实最短距离。

时间复杂度：每步决策的时间为 O(d)，其中 d 是每个节点的平均邻居数，与总状态数无关。

适用场景：LRTA* 特别适合状态空间巨大但需要实时响应的场景，如视频游戏中的 NPC 导航、大规模地图上的在线路径规划。

算法演示

RTAA*（Real-time Adaptive A*）

RTAA* 是 LRTA* 的改进版本，主要的改进在于一次更新多个节点的启发式值，从而加速学习过程。

基本概念

• 与 LRTA 的关系*：RTAA* 继承了 LRTA* 的实时特性，每次决策时间恒定。但 RTAA* 的学习效率更高，收敛到最优解所需的迭代次数更少。

• 多节点更新：LRTA* 每次只更新当前状态的一个 H 值，而 RTAA* 会更新整个当前搜索局部区域内所有节点的 H 值。

• 局部搜索：RTAA* 每次不是只扩展一个节点，而是进行一个深度受限的局部搜索，得到一个局部最优路径，然后执行该路径的第一步。

• 更新范围：在一次更新中，RTAA* 会更新局部搜索范围内所有已访问节点的 H 值，使用它们到目标的实际距离（通过局部搜索得到）来更新。

基本流程

1. 初始化：

   • 为所有状态初始化 H(s) = h(s)。
   • 设置当前状态为起点。

2. 局部搜索：

   • 从当前状态 s 开始，执行深度受限的 A* 搜索（限制扩展节点数或搜索深度）。
   • 搜索目标可以是全局目标，也可以是局部目标。
   • 得到一条从 s 到局部目标的路径。

3. 执行一步：

   • 执行局部路径的第一步，从 s 移动到 s_next。

4. 批量更新 H 值：

   • 对于局部搜索中访问的所有节点 s_visited：
     $$
     H(s_{visited}) \leftarrow g_{goal} - g(s_{visited})
     $$
     其中 $g_{goal}$ 是局部搜索得到的目标节点的 g 值，$g(s_{visited})$ 是该节点的 g 值。
   • 这个更新利用了局部搜索得到的实际距离信息，比 LRTA* 的更新更准确。

5. 继续搜索：

   • 更新当前状态为 s_next。
   • 若到达目标，算法结束；否则返回步骤 2。

优势：RTAA* 的学习速度比 LRTA* 快，因为每次更新多个节点的 H 值，信息的传播更迅速。

算法演示

LPA*（Lifelong Planning A*）

LPA* 是一种增量式搜索算法，专门用于解决连续路径规划问题。当环境的边代价发生变化时，LPA* 可以高效地更新路径，而不需要从头开始重新搜索。

基本概念

• 增量式搜索：LPA* 不是每次环境变化后从头搜索，而是复用之前的搜索结果，只更新受变化影响的部分。这大大提高了重复规划的效率。

• 两个 g 值：LPA* 为每个节点维护两个代价值：

  1. g(s)：从起点到节点 s 的当前最优已知代价。
  2. rhs(s)（Right-Hand Side）：s 的"前瞻值"，定义为：
     $$
     rhs(s) = \begin{cases}
     0 & \text{if } s = start \
     \min_{s’ \in pred(s)}[g(s’) + c(s’, s)] & \text{otherwise}
     \end{cases}
     $$
     rhs(s) 表示"如果选择最优前驱，从起点到 s 的代价是多少"。

• 节点状态：

  1. 一致（Consistent）：g(s) = rhs(s)，表示当前 g 值是最优的。
  2. 过一致（Overconsistent）：g(s) > rhs(s)，表示 g(s) 太大，需要减小。
  3. 欠一致（Underconsistent）：g(s) < rhs(s)，表示 g(s) 太小，需要增大。

• 优先队列的键值：LPA* 使用一个特殊的键值来排序优先队列：
  $$
  Key(s) = [\min(g(s), rhs(s)) + h(s); \min(g(s), rhs(s))]
  $$
  键值是一个二元组，首先比较第一个元素，相同时比较第二个元素。

• 与 A 的关系*：LPA* 可以看作是 A* 的增量式扩展。当环境不变化时，LPA* 的行为与 A* 相同。当环境变化时，LPA* 只需要更新受影响的节点。

基本流程

1. 初始化：

   • 对所有节点 s：g(s) = ∞, rhs(s) = ∞。
   • rhs(start) = 0。
   • 将 start 加入优先队列，Key(start) = [h(start); 0]。

2. 计算最短路径：

   • 当优先队列非空且目标不一致（g(goal) ≠ rhs(goal)）或队列顶部键值小于目标的键值：
     • 取出键值最小的节点 u。
     • 更新节点：
       • 若 g(u) > rhs(u)（过一致）：设置 g(u) = rhs(u)，更新 u 的所有后继的 rhs 值。
       • 若 g(u) < rhs(u)（欠一致）：设置 g(u) = ∞，更新 u 和 u 的所有后继的 rhs 值。
     • 对于每个 rhs 值改变的节点，若其不一致，将其加入优先队列。

3. 处理环境变化：

   • 当边 (u, v) 的代价发生变化：
     • 更新边代价 c(u, v)。
     • 更新 rhs(v) = min(rhs(v), g(u) + c(u, v))（若 v 不是起点）。
     • 若 rhs(v) 改变，根据 v 的一致性状态决定是否加入优先队列。
   • 返回步骤 2，重新计算最短路径。

4. 提取路径：

   • 从目标开始，依次选择使 g(s’) + c(s’, s) 最小的前驱 s’，回溯到起点。

适用场景：LPA* 适用于起点固定，目标可能变化的连续规划问题。例如，游戏中的 NPC 从固定位置出发，玩家位置不断变化。

算法演示

D*（Dynamic A*）

D* 是专为动态环境设计的增量式路径规划算法。它从目标向起点反向搜索，这使得当机器人移动时能够高效地响应环境变化。

基本概念

• 反向搜索：与 A* 从起点向目标搜索不同，D* 从目标向起点搜索。这样做的好处是：当机器人（在起点）移动时，目标不变，之前计算的路径信息可以复用。

• 环境变化处理：当机器人发现环境变化（如发现新的障碍物）时，D* 不需要重新规划整条路径，而是局部更新受影响节点的信息，然后快速得到新路径。

• 节点标签：D* 中的每个节点有一个标签：

  1. NEW：从未被访问过。
  2. OPEN：在开放列表中，待处理。
  3. CLOSED：已处理完毕。
  4. RAISE：代价增加，需要传播给邻居。
  5. LOWER：代价减少，需要传播给邻居。

• 代价函数：

  1. h(x)：从节点 x 到目标的当前最优路径代价。
  2. k(x)：节点 x 被放入开放列表时的最小 h 值，用于确定处理优先级。

• 反向传播：当某个节点的代价发生变化时，D* 会将变化反向传播给其前驱节点，更新整条路径的信息。

基本流程

1. 初始化：

   • 将所有节点的标签设为 NEW，h 值设为 ∞。
   • 将目标节点的 h(goal) = 0，标签设为 OPEN，加入开放列表。

2. 初始规划：

   • 执行类似 Dijkstra 的反向搜索，从目标向起点扩展。
   • 对于每个从开放列表取出的节点 x：
     • 扩展 x 的所有前驱节点 y（即所有能到达 x 的节点）。
     • 若 h(y) > h(x) + c(y, x)，更新 h(y) = h(x) + c(y, x)。
     • 将更新的节点加入开放列表。
   • 直到起点的 h 值确定（起点被处理）。

3. 路径执行与监测：

   • 机器人沿着 h 值递减的方向移动（贪心选择 h(y) + c(x, y) 最小的邻居 y）。
   • 在移动过程中，持续监测环境。

4. 检测到变化：

   • 当检测到边 (x, y) 的代价变化时：
     • 更新 c(x, y) 为新值。
     • 若 c(x, y) 增大（出现障碍），将 x 的标签设为 RAISE，加入开放列表。
     • 若 c(x, y) 减小（障碍消失），将 x 的标签设为 LOWER，加入开放列表。

5. 重规划：

   • 处理开放列表中的节点，传播代价变化：
     • RAISE 节点：通知邻居代价可能增加。
     • LOWER 节点：通知邻居代价可能减少。
   • 直到开放列表为空或起点的路径已更新。

6. 继续执行：

   • 使用更新后的 h 值继续沿最优路径移动。
   • 若再次检测到变化，返回步骤 4。

优势：D* 的反向搜索使得当机器人在起点附近移动时，大部分已计算的路径信息仍然有效，只需要更新局部区域。

缺点：D* 的实现较为复杂，且需要维护较多的状态信息。

算法演示

D* Lite

D* Lite 是 D* 的简化和改进版本。它基于 LPA* 的框架，通过添加启发式函数来加速搜索，同时保持了 D* 处理动态环境的能力。

基本概念

• 与 LPA 的关系*：D* Lite 本质上是 LPA* 的变种，专门针对起点移动、目标固定的场景优化。它继承了 LPA* 的增量更新机制（g 值和 rhs 值）。

• 与 D 的关系*：D* Lite 的功能与 D* 相同，但实现更简单、效率更高。D* Lite 的代码量约为 D* 的一半，更容易理解和实现。

• 启发式函数：D* Lite 在 LPA* 的基础上添加了启发式函数 h(s, s_start)，用于估计从当前节点到机器人当前位置（起点）的距离。这使得搜索更有方向性。

• 键值计算：D* Lite 的优先队列键值为：
  $$
  Key(s) = [\min(g(s), rhs(s)) + h(s, s_{start}) + k_m; \min(g(s), rhs(s))]
  $$
  其中 $k_m$ 是一个修饰值，用于在机器人移动后调整键值，避免重新计算所有节点的键值。

• 机器人移动：当机器人从 s_start 移动到 s’_start 时：

  1. 更新 $k_m = k_m + h(s’{start}, s{start})$。
  2. 更新启发式函数（因为起点变了）。
  3. 处理移动过程中发现的边代价变化。

基本流程

1. 初始化：

   • 对所有节点 s：g(s) = ∞, rhs(s) = ∞。
   • rhs(goal) = 0（注意：D* Lite 的目标是原问题的起点，因为反向搜索）。
   • k_m = 0。
   • 将 goal 加入优先队列。

2. 计算最短路径：

   • 执行类似 LPA* 的主循环，直到 s_start 一致且队列顶部的键值不小于 s_start 的键值。
   • 使用带启发式的键值排序。

3. 机器人移动：

   • 机器人沿着最优路径移动一步：从 s_start 移动到 s’_start。
   • 选择使 c(s_start, s’) + g(s’) 最小的邻居 s’。

4. 处理环境变化：

   • 在移动过程中，若检测到边代价变化：
     • 更新边代价。
     • 更新受影响节点的 rhs 值。
     • 将不一致节点加入优先队列。

5. 更新起点并重规划：

   • 更新 s_start = s’_start。
   • 更新 k_m = k_m + h(s’_start, s_start)。
   • 返回步骤 2，计算新的最短路径。

6. 重复执行：

   • 重复步骤 3-5，直到机器人到达目标。

优势：D* Lite 结合了 LPA* 的增量更新和 A* 的启发式搜索，效率高且易于实现。它是目前动态环境路径规划中最实用的算法之一。

适用场景：移动机器人导航、未知环境探索、自动驾驶车辆的重规划。

Anytime D*

Anytime D* 结合了 Anytime 和 D* 的思想，既支持动态环境下的增量更新，又能在时间受限时返回次优解并逐步优化。

基本概念

• 任意时间特性：与 ARA* 类似，Anytime D* 可以在任何时刻返回当前找到的解，并随时间增加优化解的质量。

• 动态环境支持：与 D* Lite 类似，Anytime D* 可以高效处理环境变化，增量更新路径。

• 膨胀因子：Anytime D* 使用膨胀因子 $\epsilon \geq 1$：

  • $\epsilon > 1$：快速找到次优解。
  • $\epsilon = 1$：保证最优解。

• 结合两种能力：

  • 当时间受限时，使用较大的 $\epsilon$ 快速得到可行解。
  • 当环境变化时，增量更新路径。
  • 当时间充裕时，减小 $\epsilon$ 优化解的质量。

基本流程

1. 初始化：

   • 设置初始膨胀因子 $\epsilon = \epsilon_0$。
   • 初始化 g 值、rhs 值和优先队列（类似 D* Lite）。

2. 加权搜索：

   • 使用 $Key(s) = [\min(g(s), rhs(s)) + \epsilon \cdot h(s) + k_m; \min(g(s), rhs(s))]$ 排序。
   • 执行搜索直到找到可行路径。

3. 路径执行：

   • 机器人沿路径移动。
   • 若检测到环境变化，更新边代价和 rhs 值，返回步骤 2 进行重规划。

4. 优化阶段（时间允许时）：

   • 减小 $\epsilon$。
   • 增量式地更新和优化路径。
   • 不需要从头开始搜索。

5. 终止：

   • 可以在任何时刻停止，返回当前最佳解。
   • 当 $\epsilon = 1$ 且环境稳定时，得到最优解。

适用场景：Anytime D* 适合动态环境下的实时系统，如自动驾驶、机器人足球、动态游戏环境。

算法演示

算法对比总结

按应用场景分类

性能对比

算法选择指南

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

                  环境是否动态？
                  /            \
                否              是
                |               |
          时间受限？         时间受限？
          /      \           /        \
        否        是        否          是
        |         |         |           |
       A*       ARA*     D* Lite    Anytime D*
        |         |
  起点终点固定？  |
  /      \       |
单向     双向    |
 |        |      |
A*   Bidir A*   LRTA*
               RTAA*

代码实现参考

推荐参考 PathPlanning 仓库，包含：

• Python 实现的完整代码
• 动画演示
• 详细注释

参考资料

经典论文

• A*: A Formal Basis for the heuristic Determination of Minimum Cost Paths
• ARA*: Anytime A* with Provable Bounds on Sub-Optimality
• Learning Real-Time A*: Learning in Real-Time Search: A Unifying Framework
• Real-Time Adaptive A*
• Lifelong Planning A*
• D*: Optimal and Efficient Path Planning for Partially-Known Environments
• D* Lite
• Anytime D*: Anytime Dynamic A*: An Anytime, Replanning Algorithm

代码仓库

• PathPlanning - zhm-real：包含搜索式和采样式路径规划算法的可视化实现

相关笔记

• A* 算法详解
• 路径规划算法简介
• Hybrid A* 混合路径规划

文章链接：
https://www.zywvvd.com/notes/study/algorithm/graph/astar-variants/astar-variants/