定义
给定环境，指定起点和终点，计算出连接起点与重点并满足约束的路径
运动规划平台
- Mujin
- openrave
- rosen diankov
- Kinema Systems
- MoveIt!
- Sachin Chitta
C空间—理论基础
- 拓扑变换，将机器人的体积加载周围环境上，使得构型空间求出路径曲线即可
- 大部分机构形成的构型空间均是微分流
规划器的评价标准
- Optimality(最优性)：路径最短，做功最小等
- Complete完备性）:在有限时间内解决所有有界问题
相关算法
- 网格搜索
将地图进行网格划分（四连通或者八连通建立网格图）
分辨率完备且最优：与分辨率有直接关系
缺点： 维度爆炸，需要对每个网格进行碰撞检测 - 几何算法
根据C空间的几何性质形成的算法
- 可视图法
站在机器人的位置，四周环绕一圈，将看到的障碍物顶点与自身做连接，从而将地图划分成块状，进而使用图搜索算法求解
完备 - 单元分解法
将c空间分割成若干单元，顶点向下做垂线，生成有限单元块，单元之间的连通性建立图，利用图搜索完成规划。
完备
缺点：几何算法仅能用于低维度问题，因为高维构型空间一般无法显示表示
注意：机器人自身体积，所以需要将工作空间转换为构型空间，该拓扑变换可以使用一个叫Minkowski sum的工具
- 基于回报的算法（强化学习）
动态规划 - 人工势场
- 障碍物附近建立排斥势场
- 起点到终点构建吸引势场
- 梯度下降求解即可
- 效果好，容易实现，可以与控制结合
- 缺点：陷入局部最优，不完备且不最优
- 轨迹优化
- 先随便选取一条起点与终点，然后根据各种约束调优曲线
举例1：
比如说三个路径点，两个间隔时间，这样的话，两个路径点和间隔时间构成速度约束，五个点构成加速度约束，障碍物与路径点之间直接构成约束，从而转换成图优化问题，稀疏优化->g2o 可求解问题
他的小货车例子：全局使用A算法，局部将a轨迹进行优化
缺点：偶尔陷入局部极值
举例2：
- 轨迹平滑+避障
- Factor Graph + GTSAM
将轨迹用高斯过程描述，保证前后两个点的之间的轨迹是连续变化的
- 基于采样的算法
- 只对随机采样点进行碰撞检测
- 两点之间采用简单的局部规划器进行连接
- PRM类：获得一个图，采用图搜索算法
- RRT类：获得一个连接到终点的树，反向搜索即可
- 高维空间可行，概率完备且不最优
- 这些算法计算的结果一般需要进行处理（smoothing等）
PRM
1）随机撒点
2）选取两点连线不碰撞障碍物的点
3）两点之间采用简单的局部规划器
4）将起止点炼乳路图
5）用图搜索求解
RRT
在已有树结构附近选取随机点，然后连接该点到距离最近的树上，连线上选取不予障碍物碰撞的点，这样已有树结构就做了一次扩展
上述方法的变种
- 优化碰撞检测算法 AABB
- 减少碰撞检测 Lazy-RRT
- 随机采样的方法（各种采样算法T-RRT）
- 局部规划器连接
- 举例说明：
1） RRT*
采样点一样，只要树上有比原来距离终点更近的点，我们就把原来的点删掉，选择新点，越来越趋向直线
所以它是渐进最优的
2）Informed RRT*
在起点与终点的连线构成的椭圆上内部随机生成点，因为没必要在外面继续找点，都是浪费时间
前沿研究方向
- 新问题（面向新领域）
- 重规划（re-planning）
- 运动规划+任务规划
这个等于是任务规划给原本的运动规划多加了一个维度，比如推桌子才能有解 - 考虑各种动力学
- 实用化（现实情况不可能给你足够多时间和足够多的采样点，我们应该如何使这些算法更有效）
- 轨迹复用（相对固定环境）
- 深度强化学习 因为我们路径规划其实是一个马尔科夫决策过程，该状态与上个状态没关系
从观测o到状态s，CNN的效果还不错
问答环节
- 开源库
moveit上调用的ompl库，基于采样的规划库
