A* 算法及其变种详解

本文最后更新于：2026年3月10日下午

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

概述

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

类别	算法	特点
静态环境	A、Bidirectional A	环境已知且不变
动态环境	D、D Lite、LPA、Anytime D	环境可能变化，支持增量更新
实时规划	ARA、LRTA、RTAA*	时间受限，需要在截止前返回可行解
双向搜索	Bidirectional 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}
$$

基本流程

初始化：
- 创建开放列表（优先队列）和封闭列表（哈希集合）。
- 将起点加入开放列表，设置 g(start) = 0，f(start) = h(start)。
主循环：重复以下步骤直到找到目标或开放列表为空：
- 从开放列表中取出 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 不在开放列表中，将其加入
结束条件：
- 若开放列表为空且未找到目标，说明不存在从起点到目标的路径。
- 若找到目标，返回重建的路径。

时间复杂度：最坏情况下为 $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)$，需要在所有相遇节点中选择代价最小的。

基本流程

初始化：
- 创建两个开放列表 Open_forward 和 Open_backward。
- 创建两个封闭列表 Closed_forward 和 Closed_backward。
- 将起点加入 Open_forward，g_forward(start) = 0。
- 将终点加入 Open_backward，g_backward(goal) = 0。
交替扩展：重复以下步骤直到两个搜索相遇：
- 选择 f 值较小的那个方向的开放列表进行扩展（保持两个方向的搜索进度大致平衡）。
- 从选定的开放列表中取出 f 值最小的节点 n。
- 若 n 同时在另一个方向的封闭列表中，说明两个搜索相遇，跳转到步骤 4。
- 扩展 n 的相邻节点，更新 g 值和 f 值，将新节点加入对应的开放列表。
- 将 n 移入对应的封闭列表。
检查相遇：每次扩展后检查当前节点是否在另一个方向的已访问集合中。
路径重建：
- 找到所有同时被两个方向访问的节点。
- 对于每个这样的节点 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*，保证找到最优解。

基本流程

初始化：
- 设置初始膨胀因子 $\epsilon = \epsilon_0$（如 3.0）。
- 初始化开放列表和封闭列表。
- 将起点加入开放列表，g(start) = 0，f(start) = $\epsilon \cdot h(start)$。
加权搜索阶段：
- 执行类似 A* 的搜索，但使用 $f(n) = g(n) + \epsilon \cdot h(n)$ 作为评估函数。
- 当找到目标时，记录当前解的路径和代价。
- 当前解的代价最多是最优解的 $\epsilon$ 倍。
减小膨胀因子：
- 将 $\epsilon$ 减小到下一个值（如从 3.0 减到 2.0）。
- 若 $\epsilon = 1.0$，跳转到步骤 5（最优搜索）。
增量式更新：
- 对于封闭列表中的所有节点，重新计算 $f(n) = g(n) + \epsilon \cdot h(n)$。
- 将 f 值发生变化的节点重新加入开放列表。
- 返回步骤 2，继续搜索。
最优搜索：
- 当 $\epsilon = 1.0$ 时，算法等价于标准 A*。
- 搜索完成后得到的解是最优解。
终止条件：
- 可以在任何时刻终止算法，返回当前找到的最佳解。
- 当 $\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 值会收敛到真实的最短距离，最终行为等价于最优策略。

基本流程

初始化：
- 为所有状态 s 初始化启发式值 H(s) = h(s)，其中 h(s) 是初始启发式函数（如曼哈顿距离）。
- 设置当前状态为起点。
单步决策：重复以下步骤直到到达目标：
- 计算当前状态 s 的所有邻居的 f 值：
  $$
  f(s’) = c(s, s’) + H(s’)
  $$
  其中 c(s, s’) 是从 s 到 s’ 的边代价。
- 选择 f 值最小的邻居 s_best。
- 执行移动：从 s 移动到 s_best。
学习更新：
- 更新当前状态（移动前的状态 s）的 H 值：
  $$
  H(s) \leftarrow \max{H(s), \min_{s’‘}[c(s, s’‘) + H(s’')]}
  $$
- 这个更新确保 H(s) 不会低于从 s 出发的最优一步代价。
更新当前状态：
- 将当前位置更新为 s_best。
- 若 s_best 是目标，算法结束；否则返回步骤 2。
多轮迭代（可选）：
- 若需要更优的解，可以从起点重新开始，使用更新后的 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 值，使用它们到目标的实际距离（通过局部搜索得到）来更新。

基本流程

初始化：
- 为所有状态初始化 H(s) = h(s)。
- 设置当前状态为起点。
局部搜索：
- 从当前状态 s 开始，执行深度受限的 A* 搜索（限制扩展节点数或搜索深度）。
- 搜索目标可以是全局目标，也可以是局部目标。
- 得到一条从 s 到局部目标的路径。
执行一步：
- 执行局部路径的第一步，从 s 移动到 s_next。
批量更新 H 值：
- 对于局部搜索中访问的所有节点 s_visited：
  $$
  H(s_{visited}) \leftarrow g_{goal} - g(s_{visited})
  $$
  其中 $g_{goal}$ 是局部搜索得到的目标节点的 g 值，$g(s_{visited})$ 是该节点的 g 值。
- 这个更新利用了局部搜索得到的实际距离信息，比 LRTA* 的更新更准确。
继续搜索：
- 更新当前状态为 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* 只需要更新受影响的节点。

基本流程

初始化：
- 对所有节点 s：g(s) = ∞, rhs(s) = ∞。
- rhs(start) = 0。
- 将 start 加入优先队列，Key(start) = [h(start); 0]。
计算最短路径：
- 当优先队列非空且目标不一致（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 值改变的节点，若其不一致，将其加入优先队列。
处理环境变化：
- 当边 (u, v) 的代价发生变化：
  - 更新边代价 c(u, v)。
  - 更新 rhs(v) = min(rhs(v), g(u) + c(u, v))（若 v 不是起点）。
  - 若 rhs(v) 改变，根据 v 的一致性状态决定是否加入优先队列。
- 返回步骤 2，重新计算最短路径。
提取路径：
- 从目标开始，依次选择使 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* 会将变化反向传播给其前驱节点，更新整条路径的信息。

基本流程

初始化：
- 将所有节点的标签设为 NEW，h 值设为 ∞。
- 将目标节点的 h(goal) = 0，标签设为 OPEN，加入开放列表。
初始规划：
- 执行类似 Dijkstra 的反向搜索，从目标向起点扩展。
- 对于每个从开放列表取出的节点 x：
  - 扩展 x 的所有前驱节点 y（即所有能到达 x 的节点）。
  - 若 h(y) > h(x) + c(y, x)，更新 h(y) = h(x) + c(y, x)。
  - 将更新的节点加入开放列表。
- 直到起点的 h 值确定（起点被处理）。
路径执行与监测：
- 机器人沿着 h 值递减的方向移动（贪心选择 h(y) + c(x, y) 最小的邻居 y）。
- 在移动过程中，持续监测环境。
检测到变化：
- 当检测到边 (x, y) 的代价变化时：
  - 更新 c(x, y) 为新值。
  - 若 c(x, y) 增大（出现障碍），将 x 的标签设为 RAISE，加入开放列表。
  - 若 c(x, y) 减小（障碍消失），将 x 的标签设为 LOWER，加入开放列表。
重规划：
- 处理开放列表中的节点，传播代价变化：
  - RAISE 节点：通知邻居代价可能增加。
  - LOWER 节点：通知邻居代价可能减少。
- 直到开放列表为空或起点的路径已更新。
继续执行：
- 使用更新后的 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. 处理移动过程中发现的边代价变化。

基本流程

初始化：
- 对所有节点 s：g(s) = ∞, rhs(s) = ∞。
- rhs(goal) = 0（注意：D* Lite 的目标是原问题的起点，因为反向搜索）。
- k_m = 0。
- 将 goal 加入优先队列。
计算最短路径：
- 执行类似 LPA* 的主循环，直到 s_start 一致且队列顶部的键值不小于 s_start 的键值。
- 使用带启发式的键值排序。
机器人移动：
- 机器人沿着最优路径移动一步：从 s_start 移动到 s’_start。
- 选择使 c(s_start, s’) + g(s’) 最小的邻居 s’。
处理环境变化：
- 在移动过程中，若检测到边代价变化：
  - 更新边代价。
  - 更新受影响节点的 rhs 值。
  - 将不一致节点加入优先队列。
更新起点并重规划：
- 更新 s_start = s’_start。
- 更新 k_m = k_m + h(s’_start, s_start)。
- 返回步骤 2，计算新的最短路径。
重复执行：
- 重复步骤 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$ 优化解的质量。

基本流程

初始化：
- 设置初始膨胀因子 $\epsilon = \epsilon_0$。
- 初始化 g 值、rhs 值和优先队列（类似 D* Lite）。
加权搜索：
- 使用 $Key(s) = [\min(g(s), rhs(s)) + \epsilon \cdot h(s) + k_m; \min(g(s), rhs(s))]$ 排序。
- 执行搜索直到找到可行路径。
路径执行：
- 机器人沿路径移动。
- 若检测到环境变化，更新边代价和 rhs 值，返回步骤 2 进行重规划。
优化阶段（时间允许时）：
- 减小 $\epsilon$。
- 增量式地更新和优化路径。
- 不需要从头开始搜索。
终止：
- 可以在任何时刻停止，返回当前最佳解。
- 当 $\epsilon = 1$ 且环境稳定时，得到最优解。

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

算法演示

算法对比总结

按应用场景分类

场景	推荐算法	理由
静态环境，单次查询	A*	简单高效，保证最优
静态环境，大规模图	Bidirectional A*	减少搜索空间
静态环境，时间受限	ARA*	快速返回次优解，可逐步优化
动态环境，需要重规划	D* Lite、LPA*	增量更新，高效
实时决策，未知环境	LRTA、RTAA	每步决策时间恒定
动态环境 + 时间受限	Anytime D*	兼顾两者

性能对比

算法	最优性	增量更新	实时性	实现复杂度	适用环境
A*	✓	✗	✗	低	静态
Bidirectional A*	✓	✗	✗	低	静态
ARA*	渐近最优	✗	✓	中	静态
LRTA*	渐近最优	✗	✓	中	静态/未知
RTAA*	渐近最优	✗	✓	中	静态/未知
LPA*	✓	✓	✗	中	动态
D*	✓	✓	✗	高	动态
D* Lite	✓	✓	✗	中	动态
Anytime D*	渐近最优	✓	✓	高	动态

算法选择指南

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

代码实现参考

推荐参考 PathPlanning 仓库，包含：

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

参考资料

经典论文

代码仓库

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

概述

A* 算法基础

基本概念

常用启发式函数

基本流程

算法演示

Bidirectional A*（双向 A*）

基本概念

基本流程

算法演示

ARA*（Anytime Repairing A*）

基本概念

基本流程

算法演示

LRTA*（Learning Real-time A*）

基本概念

基本流程

算法演示

RTAA*（Real-time Adaptive A*）

基本概念

基本流程

算法演示

LPA*（Lifelong Planning A*）

基本概念

基本流程

算法演示

D*（Dynamic A*）

基本概念

基本流程

算法演示

D* Lite

基本概念

基本流程

Anytime D*

基本概念

基本流程

算法演示

算法对比总结

按应用场景分类

性能对比

算法选择指南

代码实现参考

参考资料

经典论文

代码仓库

相关笔记

Bidirectional A（双向 A）

ARA（Anytime Repairing A）

LRTA（Learning Real-time A）

RTAA（Real-time Adaptive A）

LPA（Lifelong Planning A）

D（Dynamic A）