3、路径规划器故障：A*算法死锁、RRT算法不收敛、Dijkstra内存溢出

做机器人轨迹规划这些年，我踩过最多的坑，就是路径规划器本身出问题。你想想看，算法在论文里跑得漂漂亮亮，一上真机就各种幺蛾子。A* 死锁、RRT 不收敛、Dijkstra 内存爆炸——这三个问题，我敢说每个做规划的工程师都遇到过。

今天咱们就一个一个掰开揉碎了讲。我会把我在项目里摔过的跟头、总结的解法，全都倒出来。

3.1 A* 算法死锁：地图明明有路，它偏说走不通

先说说 A*。这玩意儿在栅格地图上用得最多，原理不复杂：维护一个 open list 和 close list，每次选代价最小的节点扩展。但问题来了——死锁。

什么叫死锁？就是算法还在跑，open list 里还有节点，但永远找不到终点。说白了，它被困在局部区域里打转。

为什么会这样？A* 的核心是 f(n) = g(n) + h(n)。如果 h(n) 设计得不好，比如在障碍物密集区域，h(n) 严重低估了实际代价，算法就会优先扩展那些看似近、实则绕远的节点。最终 open list 里全是死胡同节点，终点永远进不了 close list。

解决方案：

• 检查启发式函数：确保 h(n) 是「可采纳的」，即不大于实际代价。我习惯用欧几里得距离，但在栅格地图上，曼哈顿距离更稳妥。
• 增加权重调节：给 g(n) 加一个权重系数 w（比如 w=1.2），让算法更倾向于走已探索的路径，减少盲目扩展。
• 设置最大迭代次数：别让 A* 无限跑下去。超过阈值就切换备选算法，比如跳点搜索（JPS）。

3.2 RRT 算法不收敛：树长得挺好，就是碰不到目标

RRT（快速随机扩展树）在高维空间里很吃香，因为它不需要显式建模障碍物。但它的毛病也明显——不收敛。

你运行 RRT，看着树在空间里疯狂生长，但就是够不到目标点。有时候跑了 10 万次迭代，终点还是遥不可及。嗯，这里要注意：RRT 是概率完备的，理论上迭代次数足够多一定能找到解。但实际中，迭代次数可能大到无法接受。

我个人的经验：有一次在机械臂的 C 空间里做路径规划，RRT 跑了 20 分钟还没收敛。我检查了一下，发现是采样策略出了问题——随机采样点太集中在起始点附近，导致树在局部区域「打转」。

核心原因：

• 采样偏差：随机采样没有偏向目标点，导致树盲目生长。
• 步长过大：扩展步长太大，新节点直接跳过目标点附近的狭窄通道。
• 障碍物检测太粗糙：碰撞检测分辨率低，导致树在障碍物边缘反复试探。

解决方案：

1. 引入目标偏置采样：以一定概率（比如 10%）直接采样目标点，其余 90% 随机采样。这样树会「有意识」地向目标生长。
2. 动态调整步长：在空旷区域用大步长快速扩展，在障碍物密集区域用小步长精细探索。
3. 使用 RRT* 或 Informed RRT*：这些变种算法会优化路径质量，收敛性更好。

3.3 Dijkstra 内存溢出：地图一大，直接崩了

Dijkstra 算法是 A* 的「老大哥」，它保证能找到最短路径，但代价是——内存消耗巨大。

你想想看，Dijkstra 需要维护一个距离数组，记录每个节点到起点的最短距离。如果地图是 1000x1000 的栅格，那就是 100 万个节点。每个节点存一个 float（4 字节），再加上父节点指针、访问标记……轻松上百 MB。要是地图再大点，比如 5000x5000，内存直接爆炸。

我踩过的坑：有一次做室外无人车的全局路径规划，地图是 10km x 10km 的栅格，分辨率 0.5 米。Dijkstra 一启动，内存直接飙到 2GB，然后进程被系统 kill 了。我当时就懵了——这算法在论文里不是挺能打吗？

为什么内存会溢出？

• 节点数量爆炸：Dijkstra 需要存储所有节点的状态，不像 A* 只维护 open list 和 close list。
• 优先级队列开销：用二叉堆实现时，每个节点入队出队都要分配内存。
• 路径回溯：找到终点后，需要从终点回溯到起点，如果路径很长，回溯栈也会占用大量内存。

解决方案：

方法	说明	适用场景
分层规划	先粗粒度规划（比如 10 米分辨率），再细粒度局部优化	大尺度地图
双向 Dijkstra	从起点和终点同时搜索，减少搜索空间	起点和终点已知
改用 A*	加入启发式函数，减少扩展节点数	有启发式信息
内存池	预分配固定大小的内存块，避免动态分配	嵌入式系统

3.4 三种故障的对比与选择

说了这么多，你可能想问：那我到底该用哪个？

我整理了一张对比表，你直接拿去用：

算法	典型故障	根本原因	首选解法
A*	死锁	启发式函数不合理	检查 h(n) 可采纳性，增加权重
RRT	不收敛	采样策略偏差	目标偏置采样，动态步长
Dijkstra	内存溢出	节点数量过大	分层规划或改用 A*

说白了，没有银弹。每个算法都有自己的脾气。你得多试、多调参，才能找到最适合你场景的那一个。

3.5 核心逻辑流程图

下面这张 SVG 图，是我梳理的路径规划器故障诊断流程。遇到问题别慌，按这个步骤来排查：

这张图的核心逻辑很简单：先看内存，再看路径，最后看收敛性。按这个顺序排查，能省下你大量 debug 时间。

可可精品资料库