扫地机器人绕开拖鞋、无人机穿过树林、自动驾驶在路口选车道——这些场景背后是同一个问题：给一张地图和一堆约束，算出那条"能走、好走、不撞"的轨迹。这就是运动规划（Motion Planning），机器人和自动驾驶算法栈里最核心的一层。
这个领域的算法名词很多，新手经常被劝退在"先学哪个"上。其实按思路分，主流方法就四大家族：基于搜索的、基于采样的、基于优化的、处理不确定性的。搞清楚它们各自解决什么矛盾，选型就不难了。
家族一：基于搜索的规划——把地图变成图，找最短路径
最直觉的思路：把地图栅格化，每个格子是图的一个节点，相邻格子连边，问题就变成了图上的最短路径搜索。
Dijkstra 是起点：从起点向外一圈圈扩展，在非负边权的图上保证找到最短路径。缺点也明显——无方向地全图扩散，大地图上浪费严重。
A* 是对它的关键改进：给每个节点加一个启发函数（通常是到终点的直线距离估计），搜索时优先扩展"看起来离终点近"的方向。启发函数可采纳，且图搜索实现正确处理节点重开等条件时，A* 可保证最优；使用一致启发式可简化处理，但提速幅度并非固定，这也是它成为栅格地图默认答案的原因。
工程实践里还有一个常客 JPS（跳点搜索）：网格地图上大量路径是对称的，JPS 通过规则跳过这些冗余节点，在满足其网格、移动和代价假设时可减少扩展节点；非均匀代价地图不能直接照搬剪枝规则。
适用场景：室内扫地机、低速 AGV、仓储机器人——可以近似成二维栅格的环境。
家族二：基于采样的规划——高维空间的现实解法
机械臂有关节角、无人机有位置和姿态，状态空间一上三维六维，栅格化直接爆炸（维度灾难）。换个思路：不铺满地图，随机采样。
PRM（概率路线图） 分两步：先在自由空间里随机撒一批点、把相近的点连成一张"路线图"，之后查询就在这张图里搜路径。建图一次、查询多次，适合静态环境里反复规划的场景。
RRT（快速随机扩展树） 则服务于单次查询：从起点长一棵树，每次随机取一个目标方向、让最近的树节点朝它长一小步，直到树枝够到终点。优点是快、天然适应高维；缺点是路径比较"毛糙"，实际使用要接平滑后处理（剪枝、曲线拟合）。
适用场景：机械臂关节空间规划、无人机大范围航迹搜索。
搜索、采样与轨迹优化需要分别建立实验，再比较衔接处的约束。https://yunpan.plus/t/30569 教程目录里按这几类方法与 MDP 组织，并列有实践和 ROS 作业，可用作实验主题清单。
家族三：轨迹优化——从"几何路径"到"电机跟得上的轨迹"
搜索和采样给的是几何路径，但机器人不是质点：电机有加速度上限，乘客受不了顿挫，无人机急转弯会翻。所以需要轨迹优化，把折线路径变成时间参数化的平滑轨迹。
最有代表性的方法是 Minimum Snap：以位置四阶导数 snap 的平方积分最小化为常见目标；位置三阶导数 jerk 才是加加速度，分段生成多项式轨迹。物理意义很直白——最小化"顿挫感的积累"，改善轨迹平滑性，但不自动保证避障、动力学可行或能耗最优，仍需加入相应约束与验证。
家族四：不确定性下的决策——MDP
前面的方法都假设地图是准的、世界是不变的。现实是：传感器有噪声、行人会乱走、其他机器人也在动。这时规划问题升级成马尔可夫决策过程（MDP）：在每个状态选择动作，使长期期望收益最大。再往上接一层是 POMDP（部分可观测 MDP），那是自动驾驶决策研究的主战场之一。
选型速查与常见坑
| 场景 | 首选 | 备注 |
|---|---|---|
| 二维室内已知地图 | A* / JPS | 大图优先 JPS |
| 高维关节空间 | RRT | 路径需后处理平滑 |
| 静态环境多次查询 | PRM | 建图成本摊薄 |
| 无人机平滑轨迹 | Minimum Snap | 注意动力学约束 |
| 动态不确定环境 | MDP/POMDP | 算力开销大 |
几个新手高频坑：
- 把几何路径直接发给电机执行——没有速度加速度约束，机器人根本跟不上
- 代价地图分辨率拍脑袋——太粗穿模、太细算不动，按机器人尺寸膨胀障碍物才是标准动作
- 以为 RRT 出来的就是最终轨迹——它只是初解，不做后处理没法用
收尾
运动规划的选型本质是三笔账的权衡：地图维度（搜索还是采样）、轨迹质量（几何可行还是动力学可行）、环境确定性（静态规划还是概率决策）。把这三笔账算清楚，算法名字再多也不会迷路。
标签 #运动规划 #机器人路径规划 #A*算法 #RRT #MinimumSnap #无人机 #ROS #自动驾驶
