3、经典路径规划算法概览：Dijkstra、A*、人工势场法、概率路线图（PRM）的优缺点及与RRT的对比

在深入探讨RRT与RRT Connect之前，有必要先建立一张完整的路径规划算法地图。路径规划问题本质上是在一个包含障碍物的构型空间（Configuration Space, C-Space）中，寻找一条从起始状态到目标状态的无碰撞路径。根据搜索策略的不同，主流算法可分为四大类：基于图搜索的确定性算法（Dijkstra、A*）、基于势场引导的局部规划算法（人工势场法）、基于随机采样的全局规划算法（PRM、RRT）以及基于优化的算法（如CHOMP、TrajOpt）。本章将重点剖析前四类经典算法的核心机制、适用场景与固有缺陷，并通过多维度的对比揭示RRT在应对高维、非凸、动力学约束问题时的独特价值。理解这些算法的"基因"差异，是正确选型与混合使用的基石。

上图从搜索策略、最优性、维度适应性、计算开销、主要缺陷和典型应用六个维度，对四类算法进行了高维度的抽象对比。接下来，我们将逐一拆解每种算法的内部机理，并重点分析其与RRT在方法论上的根本差异。

3.1 Dijkstra算法：贪心扩展的完备性基石

核心原理

Dijkstra算法是图搜索领域的"元老"，它基于广度优先搜索（BFS）的思想，以起始节点为中心，向外层层扩展，直到遍历完所有可达节点。其核心数据结构是优先队列（最小堆），每次从队列中取出当前代价最小的节点进行扩展，并更新其邻居节点的最短距离。该算法要求所有边的权重非负，这是其正确性的前提。

判断方法与操作流程

1. 初始化：将起始节点距离设为0，其余节点设为无穷大；所有节点标记为未访问。
2. 选择节点：从未访问节点中选取距离最小的节点u。
3. 松弛操作：遍历u的所有邻居v，若 dist[u] + weight(u,v) < dist[v]，则更新dist[v]并记录前驱节点。
4. 标记访问：将u标记为已访问，重复步骤2-3，直到目标节点被访问或队列为空。

案例拆解：城市路网最短路径

假设一个简化的城市路网，包含5个路口（A-E），道路权重为行驶时间（分钟）。A为起点，E为终点。道路连接及权重为：A-B(4)、A-C(2)、B-C(1)、B-D(5)、C-D(8)、C-E(10)、D-E(2)。

最终得到最短路径为 A → C → B → D → E，总代价为 2+1+5+2=10。注意，Dijkstra虽然找到了最短路径，但遍历了图中所有节点，效率较低。

常见误区与总结

Dijkstra的核心价值在于其完备性——只要存在可行路径，它一定能找到。但代价是效率低下，尤其当目标点明确时，它仍会盲目扩展无关区域。

3.2 A*算法：启发式引导的智能搜索

核心原理

A*算法在Dijkstra的基础上引入了启发式函数h(n)，用于评估从当前节点n到目标节点的估计代价。其评价函数为 f(n) = g(n) + h(n)，其中g(n)是从起点到n的实际代价。当h(n)满足可采纳性（即h(n) ≤ 实际代价）时，A*保证找到最优路径。常见的启发式函数包括曼哈顿距离、欧几里得距离等。

判断方法与操作流程

• 开放列表：存储待考察节点，按f值排序。
• 封闭列表：存储已考察节点。
• 核心循环：从开放列表取出f值最小的节点，若为目标则结束；否则扩展其邻居，更新g值和f值，并加入开放列表。

案例拆解：二维栅格地图导航

在一个10x10的栅格地图中，起点(1,1)，终点(8,9)，障碍物若干。采用欧几里得距离作为启发式函数。A*算法会优先探索朝向终点的方向，相比Dijkstra，其扩展节点数显著减少。例如，在开阔地带，A*几乎直线走向终点；而Dijkstra则会以起点为圆心，形成等距波纹状扩展。

常见误区与总结

A*是静态环境中2D/3D路径规划的黄金标准，但其"离散化"的基因决定了它难以直接应用于机械臂的关节空间规划（通常6-7维）。

3.3 人工势场法：局部避障的实时利器

核心原理

人工势场法（APF）是一种反应式规划方法。它在构型空间中构造虚拟势场：目标点产生引力场，吸引机器人靠近；障碍物产生斥力场，推离机器人。机器人沿势场下降方向运动，即 F = -∇U(q)，其中U(q)为势能函数。

判断方法与操作流程

1. 构建势场：定义引力势能 U_att = 0.5 * ξ * ρ²(q, q_goal)，斥力势能 U_rep = 0.5 * η * (1/ρ - 1/ρ₀)²（当ρ ≤ ρ₀时）。
2. 计算合力：对势能求负梯度，得到引力和斥力。
3. 迭代运动：沿合力方向移动步长δ，直到到达目标或陷入局部极小。

案例拆解：无人机室内避障

一架四旋翼无人机在室内飞行，目标点位于墙壁后方。初始阶段，引力主导，无人机快速飞向目标。当接近墙壁时，斥力逐渐增大，无人机减速并绕行。然而，当无人机、墙壁、目标点三者共线时，引力和斥力可能恰好平衡，导致无人机悬停不前——这就是著名的局部极小值问题。

常见误区与总结

APF的优势在于计算量小、实时性强，适合动态避障。但其不完备性意味着它无法保证找到路径。工程上常将其与全局规划器结合：先用RRT/PRM生成全局路径，再用APF进行局部跟踪与避障。

3.4 概率路线图（PRM）与RRT的对比分析

核心原理

PRM和RRT都属于基于随机采样的算法，它们通过随机撒点来构建图或树，从而避免了对整个构型空间的显式离散化。PRM分为两个阶段：学习阶段在自由空间中随机采样N个点，并连接邻近点形成路线图；查询阶段将起点和终点连接到路线图上，搜索可行路径。RRT则从起点开始，通过随机采样目标点并逐步扩展树结构，直到树触及终点。

对比维度拆解

案例拆解：机械臂7自由度运动规划

考虑一个7自由度的机械臂在流水线旁执行插拔操作。构型空间维度为7，若使用栅格法，假设每个维度划分10份，则状态空间为10^7，完全不可行。使用PRM，在C-Space中随机采样10000个点，构建路线图。但问题在于，机械臂的关节限位和自碰撞约束使得有效采样率极低，且狭窄通道（如穿过夹具间隙）很难被采样点覆盖。此时，RRT的优势凸显：它通过偏向目标扩展和步长控制，能够更高效地探索高维空间。然而，RRT生成的路径往往包含大量冗余转折，且不满足机械臂的动力学约束（如关节速度、加速度限制）。

常见误区与总结