第2章路径规划基础

路径规划基础：从定义到算法家族

说实话，每次带新人做项目，我都要先问一个问题：你觉得路径规划到底是什么？很多人第一反应就是「找条路呗」。嗯，对，但也不全对。

我做了这么多年机器人算法，路径规划说白了就是：在给定的环境中，找到一条从起点到终点的可行路径，同时满足各种约束条件。约束条件包括避障、运动学限制、时间最优、能量最优等等。你想想看，这其实是个多目标优化问题。

  核心三要素：
  起点与终点：明确任务边界
环境模型：地图、障碍物、动态物体
评价指标：路径长度、平滑度、安全性、实时性

我在项目中遇到过最典型的例子：一台AGV在仓库里搬运货物，如果只考虑最短路径，结果拐弯半径太小，车子直接卡在货架中间。这就是典型的「路径可行但不可执行」——路径规划必须考虑机器人的实际运动能力。

全局规划 vs 局部规划

这两个概念，我建议你从「视野范围」来理解。

维度	全局规划	局部规划
信息范围	完整地图（已知环境）	传感器局部视野
计算频率	低频（任务开始时一次或少量重规划）	高频（每帧或每控制周期）
输出	全局路径（一系列关键点）	局部轨迹（带速度/加速度指令）
典型算法	A*、Dijkstra、RRT	DWA、TEB、MPC
鲁棒性	对环境变化敏感	能应对动态障碍物

全局规划，就像你出发前看地图规划路线。它假设环境是已知的、静态的。但现实世界哪有那么完美？

局部规划，则是你开车时实时看路况、避让行人。它只关心眼前几米，反应要快。

我个人习惯的做法是：全局规划提供「大方向」，局部规划负责「微调执行」。两者缺一不可。我曾经在一个项目中只用了全局规划，结果遇到临时摆放的纸箱，机器人直接撞上去——嗯，从那以后我再也不敢省略局部规划了。

避坑指南：全局路径的离散点间距不要太大。我见过有人设成1米一个点，结果局部规划在两点之间插值，直接穿墙而过。建议间距不超过机器人半径的1/3。

常见算法分类

路径规划算法五花八门，但归纳起来就三大类。我按自己的理解给你捋一捋。

1. 图搜索算法

这类算法的核心思想：把连续空间离散化成图，然后在图上搜索最短路径。

Dijkstra：广度优先的经典算法，保证找到最短路径。但效率低，适合小规模地图。
A*：加了启发式函数（比如欧氏距离），搜索效率大幅提升。我90%的全局规划项目都用它。
JPS (Jump Point Search)：A*的优化版，在网格地图上跳过冗余节点。适合大规模栅格地图。

// A* 核心伪代码（我常用的简化版）
openSet.add(start);
while (!openSet.isEmpty()) {
    current = openSet.getLowestF();
    if (current == goal) return reconstructPath(current);
    openSet.remove(current);
    closedSet.add(current);
    for (neighbor : current.getNeighbors()) {
        if (closedSet.contains(neighbor)) continue;
        tentativeG = current.g + dist(current, neighbor);
        if (!openSet.contains(neighbor) || tentativeG < neighbor.g) {
            neighbor.g = tentativeG;
            neighbor.h = heuristic(neighbor, goal);
            neighbor.f = neighbor.g + neighbor.h;
            neighbor.parent = current;
            if (!openSet.contains(neighbor)) openSet.add(neighbor);
        }
    }
}

注意：图搜索算法的性能高度依赖离散化方式。栅格太粗会丢失可行路径，太细则计算量爆炸。我一般根据机器人尺寸和环境复杂度动态调整分辨率。

2. 采样算法

这类算法不显式构建整个图，而是随机采样点来探索空间。适合高维空间或复杂约束场景。

RRT (Rapidly-exploring Random Tree)：随机采样扩展树，快速覆盖空间。速度快但不保证最优。
RRT*：RRT的优化版，加入重连机制，渐进最优。我最近做机械臂规划都在用这个。
PRM (Probabilistic Roadmap)：先采样构建路图，再查询路径。适合静态环境的多查询场景。

为什么采样算法这么火？说白了，现实世界的很多问题根本没法用图精确建模。比如机械臂的7自由度关节空间，你用图搜索？维度灾难直接教你做人。采样算法则聪明地「哪里需要探哪里」。

我记得有一次做移动机器人在密集人群中的规划，A*算出来的路径在静态地图上完美，但人一动就失效。后来换成RRT*，每次重规划只花几十毫秒，效果出奇的好。

经验之谈：采样算法的采样点数量不是越多越好。我一般从500个点开始试，逐步增加直到路径质量满足要求。另外，采样分布也很关键——在障碍物附近多采点，能提高窄通道的通过率。

3. 智能算法

这类算法受自然界启发，适合多目标优化、非线性约束的场景。

遗传算法 (GA)：模拟进化过程，通过选择、交叉、变异优化路径。适合离线规划。
粒子群优化 (PSO)：模拟鸟群觅食，每个粒子代表一条路径，通过群体协作找到最优解。
蚁群算法 (ACO)：模拟蚂蚁觅食，通过信息素积累找到最优路径。适合动态环境。

说实话，智能算法在工业界用得不如前两类多。为什么？实时性不够。遗传算法跑一次可能要几秒甚至几分钟，而机器人控制周期是毫秒级的。但如果你做的是离线路径优化（比如工厂产线布局规划），智能算法就很有优势了。

我曾经用遗传算法优化过一条焊接路径，在满足所有工艺约束的前提下，把路径长度缩短了18%。虽然跑了20分钟才收敛，但一次优化，长期受益。

知识体系总览

下面这张图是我自己整理的路径规划知识框架，你可以把它当作学习地图。

这张图把路径规划的核心脉络理清楚了。你注意看底部的总结——全局规划定方向，局部规划做执行，算法选型看场景。这是我多年项目经验的浓缩。

选算法的时候，我一般会问自己三个问题：

环境是静态还是动态？静态用图搜索或PRM，动态用RRT*或D* Lite。
需要实时响应吗？实时性要求高，优先局部规划+轻量级全局规划。
路径质量要求多高？最优解还是可行解？最优解上RRT*或A*，可行解RRT就够了。

最后提醒一句：别迷信算法。我见过太多人一上来就上RRT*、MPC，结果连基本的地图表示都没搞对。路径规划的基础是环境建模——地图分辨率、坐标系、障碍物膨胀——这些搞定了，算法才能发挥价值。

好了，这一章的内容就到这里。路径规划的定义、全局与局部的分工、三大算法家族的适用场景，你应该心里有数了。下一章我们深入聊环境建模与地图表示——这可是所有规划算法的基础，搞不好后面全白搭。

公众号:蓝海资料掘金营，微信deep3321

📚 课程目录

路径规划基础：从定义到算法家族

全局规划 vs 局部规划

常见算法分类

1. 图搜索算法

2. 采样算法

3. 智能算法

知识体系总览