- 中文名
- 运动规划
- 外文名
- Motion Planning
- 应用领域
- 机械工程
构型（Configuration）是机器人的一个状态，如平面机器人，构型可以是
机器人所有构型的集合则形成构型空间（Configuration Space，C-Space）。构型空间的维度就是机器人的自由度，在构型空间中，机器人可以描述成一个点，一般运动规划算法均是在构型空间中进行的，这样可以防止奇异。 [1]
对低维度机器人，构型空间可以通过空间离散法进行映射：
运动规划（Motion Planning）就是在给定的位置A 与位置 B 之间为机器人找到一条符合约束条件的路径。这个约束可以是无碰撞、路径最短、机械功最小等。具体的案例可以是为移动机器人规划出到达指定地点的最短距离，或者是为机械臂规划出一条无碰撞的运动轨迹，从而实现物体抓取等。
在数学角度而言，运动规划（Motion Planning）与路径规划（Path Planning）属于同一问题，但路径规划一般用于平面无人车/机器人的规划，问题维度较低，常用的算法也不同，所以习惯上将两者区别称呼。
基本的运动规划就是在起始构型与目标构型之间找到一条连续运动轨迹，同时避开环境中的障碍物。
自由空间（Free Space）是满足规划约束的那部分构型空间，对于基本的运动规划来说，自由空间就是指没有跟环境发生碰撞的那部分构型空间。
对于常见的机构形成的构型空间均为微分流形，在任一点的局部均与欧式空间同态。这样，我们便可以将在欧式空间的大部分分析直接应用到构型空间中。
低维度的问题一般可以采用基于网格的算法。直接将构型空间按照一定分辨率划分为网格，之后用四连通、八连通准则连接网格，之后在网格上进行搜索求解。
而对于高维度的规划问题，我们没办法显式地描述构型空间，而直接划分网格会引入极大的计算量。人工势场等优化算法在高维情况下效果不错，但很容易陷入局部极值。而基于采样的算法是目前主流的算法，它可以避免局部极值问题，同时在实际实施中效率很高。此外，直接对轨迹进行修正优化的算法也有不错的性能。
这类算法直接将构型空间按照一定分辨率划分网格，在每个网格，机器人可以运动到相邻网格（基于四连通或八连通准则）。只要在自由空间中指定起始点与目标点，我们就可以使用 Dijkstar 和 A* 等图搜索算法进行搜索求解。
这类算法依赖于构型空间的几何信息，所以只能在低维度。而由于机器人具有一定体积，不是一个点，所以需要将工作空间转换成构型空间，这个拓扑变换可以使用一个叫做Minkowski sum 的工具。
可视图法（Visibility graph）：可视图法用封闭多面体描述障碍物；并将连接所有多面体的所有顶点，去除与障碍物相交的连线；之后将起始点与目标点与所有顶点连接，并去除与障碍物相交的连线。由此可得到一个图。之后在图上使用图搜索算法即可。
单元分解法（Cell decomposition）：按照一定规则进行单元分解，得到一系列完全属于自由空间的单元。
这类算法为机器人的每一个状态与动作赋予一定的回报，机器人通过一定方法学习得到每一个动作的价值，之后只需每一步沿着价值最高的路径走即可。这类算法其实属于强化学习（Reinforcement Learning）的范畴，是另外一大块内容，这里便不赘述了。
受此现象的启发，人们便想到人工势场法，人工添加势场函数，让目标点处于谷底，距离目标点越远的势场越高，同时，为了避免发生碰撞，可以在障碍物四周添加排斥势场（障碍物处势能最大）。
人工势场非常直观，且对运算量要求不高，可以跟机器人的控制相结合。当然，势场法的一个问题就是没办法避开局部极小值问题，所以该方法是不完备的，同时也是非最优化的。 [2]
这类算法并不去直接求取构型空间，而是在构型空间内随机采样，只对采样点进行碰撞检测，判断其是否位于自由空间内。之后，将该点连接到一个图或者树状结构中。用这个图或者树来描述自由空间。这类算法效率非常高，但规划的结果不稳定。
概率路图（Probabilistic Road Maps，PRM）就是在规划空间内随机选取N个节点，之后连接各节点，并去除与障碍物接触的连线，由此得到一个随机路图。显然，当采样点太少，或者分布不合理时，PRM算法是不完备的，但是随着采用点的增加，也可以达到完备。所以PRM是概率完备且不最优的。
快速扩展随机树法（Randomly Exploring Randomized Trees，RRT）是从起始点开始向外拓展一个树状结构，而树状结构的拓展方向是通过在规划空间内随机采点确定的。与PRM类似，该方法是概率完备且不最优的。
当然，除了RRT和PRM，还有一大堆基于两者的变种算法，如 RRT*，lazy-PRM, SBL 等等。
轨迹优化（Trajectory Optimization）也是运动规划的一个常用算法，这类算法一般是基于先用一个初始轨迹连接起始点与目标点，之后利用梯度下降或者图优化算法调整轨迹。
2、全局路径规划（global path planning）和局部路径规划（local path planning）：
3、离线路径规划和在线路径规划：
