路径规划

Path Planning

The path planning problem is a subproblem of the general 运动规划 problem. Path planning is the purely geometric problem of finding a collision-free path $q(s),s\in [0,1]$, from a start configuration $q(0)=q_{\mathrm{start}}$ to a goal configuration $q(1)=q_{\mathrm{goal}}$, without concern for the dynamics, the duration of motion, or constraints on the motion or on the control inputs.

路径规划是运动规划中的一个纯几何子问题：在构型空间的自由构型空间中，寻找一条从起始构型到目标构型的无碰撞连续路径，不考虑时间、速度、力矩或控制输入。

This problem is sometimes called the piano mover's problem, emphasizing the focus on the geometry of cluttered spaces.

“钢琴搬运工问题”这一别名强调了路径规划的本质：在杂乱空间中只关心物体形状和空间几何，不考虑运动时间或动力学。

数学形式化

一条无碰撞路径是连续映射

If the path returned by the path planner can be time scaled to create a feasible trajectory (Chapter 9).

连通性

若 $q_{\mathrm{start}}$ 或 $q_{\mathrm{goal}}$ 不在 ${\mathcal{C}}_{\mathrm{free}}$ 中，问题本身不可行。若构型空间障碍将 ${\mathcal{C}}_{\mathrm{free}}$ 分割为多个连通分量，而 $q_{\mathrm{start}}$ 与 $q_{\mathrm{goal}}$ 分属不同连通分量，则即使规划器搜索无限久，也不存在无碰撞路径。因此，连通性是路径规划可行性的基本判据：只有当起点和目标处于 ${\mathcal{C}}_{\mathrm{free}}$ 的同一连通分量中，无碰撞路径才可能存在。

找到路径后，再由轨迹生成分配时间标定，检查动力学和执行约束。一条几何路径成功不代表可执行：还需要考虑奇异位形、窄通道、碰撞裕度以及力矩/速度限制。

采样方法和网格方法是路径规划的主流手段。近年来运动规划的趋势是采样运动规划方法（如 PRM、RRT），它们易于实现、概率完备，且能处理高维问题。