把机器人抽象成构型空间中的一个点，障碍物映射成 C-障碍，规划就成了在高维空间找路。低维问题可以离散化成图，用 Dijkstra / A* 及其增量、任意时间变体求解；这也是导航栅格规划和足步规划的基础。
核心要点
- 构型空间 C、C-障碍、自由空间；碰撞检测（FCL、GJK、BVH）是规划器的主要开销
- Dijkstra、A*、加权 A*、ARA*（任意时间）、D* Lite（增量重规划）
- 格点 / 状态栅格（lattice）规划，运动基元；导航中的代价地图
- 足步规划：把行走当离散搜索或混合整数优化
关键公式
自测：学完应该能回答
- 启发式不可采纳时 A* 会失去什么？加权 A* 为什么仍然有用？
- 为什么 7 自由度机械臂不能直接用栅格 A*？
推荐资料（全部免费）
- 📘
- 🎓
- 📄
D* Lite Koenig & Likhachev · AAAI 2002
- 📄
高维空间里显式构造自由空间不可行，随机采样 + 局部连接是实用解：PRM 建图多次查询，RRT 单次查询快速探索，RRT* / PRM* 通过重连获得渐近最优。理解概率完备性与 Voronoi 偏置，就能理解为什么它们在 7–30 维上仍然可用。
核心要点
- PRM 与 RRT 的基本循环；采样、最近邻（kd-tree）、局部规划器
- 概率完备、Voronoi 偏置、窄通道问题与改进采样（高斯、桥采样）
- RRT-Connect（双向）、RRT*、PRM*、Informed RRT*、BIT*：渐近最优的代价
- 运动学 / 动力学约束下的规划（kinodynamic RRT、SST）；约束流形上的规划
- 路径后处理：捷径、平滑；OMPL / MoveIt 的实际使用
自测：学完应该能回答
- RRT 为什么天然偏向探索未访问区域（Voronoi bias）？
- RRT* 与 RRT 相比多做了哪两步？为什么因此渐近最优？
把碰撞代价光滑化后，规划可以直接做梯度下降（CHOMP / STOMP / TrajOpt），得到平滑、局部最优的轨迹；再用多项式 / B 样条与时间最优参数化（TOPP-RA）生成满足速度 / 加速度限制的可执行轨迹。四旋翼的最小 snap 轨迹与微分平坦性是这一思路的经典应用。
核心要点
- CHOMP（协变梯度、有符号距离场）、STOMP（随机）、TrajOpt（序列凸优化 + 凸包碰撞约束）
- 样条与多项式轨迹：三次 / 五次多项式、B 样条、最小 snap；微分平坦性让四旋翼规划变成几何问题
- 时间参数化：TOPP / TOPP-RA 在给定路径上求时间最优速度曲线
- 规划、轨迹优化与 MPC 的分工：全局路径 → 局部轨迹 → 实时跟踪
关键公式
自测：学完应该能回答
- 为什么 CHOMP 需要有符号距离场？它在窄通道中会遇到什么问题？
- 微分平坦性为什么能把四旋翼的轨迹规划简化为对位置多项式的优化？
真实世界状态不完全可观、动作会失败，长时程任务需要在符号层（先拿杯子再倒水）与几何层（怎么抓、走哪条路）之间来回。POMDP / 信念空间规划处理不确定性，TAMP 把符号规划与运动规划耦合，近年 LLM / VLM 又被用作高层规划器。
核心要点
- MDP → POMDP，信念状态与信念空间规划；在线 POMDP 求解（POMCP、DESPOT）
- 任务规划：PDDL 与启发式搜索；TAMP 的接口（可行性检查、几何约束回传）
- LLM / VLM 作为任务规划器（SayCan、Code as Policies）及其与底层技能库的组合
- 行为树与状态机：工程上组织长时程行为的标准工具
自测：学完应该能回答
- 为什么 POMDP 精确求解不可行？在线求解器用了什么近似？
- TAMP 里几何不可行时如何反馈给符号规划器？