Basic Motion Planning and Overview

运动规划（Motion Planning）就是在给定的位置A与位置B之间为机器人找到一条符合约束条件的路径
规划问题本质上是一个搜索问题，即对一个给定的函数，寻找最优解
规划问题涉及三个领域，机器人领域，控制领域和人工智能
- robotic fields，规划就是如何产生轨迹以完成目标，涉及RRT， A*，D* lite等
- 控制领域，规划理解为到达目标状态的动态系统，涉及MPC， LQR等
- artificial intellegence（AI），是生成状态到动作的映射，涉及reinforcement learning，end-to-end imitation learning等

如何构建汽车的运动规划问题

从最简单问题出发，把运动规划抽象成一个path finding problem（路径查找问题），只关心无人车怎样走，周围环境是不变的

想寻找最短路径，可通过广度优先的方法，也可以使用深度优先方法
但是对于最短路径优化问题，深度优先方法的效率太低
没有利用起点和终点之间的信息，breadth first search（BFS）和 depth first search（DFS）都属于non-information search
A-star算法了解起点与终点的位置，花费时间比广度优先算法时间更短
A-star算法还不能直接用在规划模块上，因为A-star算法本身要求对整个环境全知
无人车的传感器系统只能部分观察环境
利用D-star算法对部分观察的数据进行控制规划，D-star的特点是处理在看到的有限范围的条件下，如何到达预定地点的搜索问题方法
这种增量搜索很难通过一步步的迭代达到全局最优解
另外路径的直接90度转弯是不合理的，可以通过平滑性曲线的方式来优化折线，换成一些较为平滑的曲线来完成
距离：
- 规划模块怎么处理动态障碍物是关键并且是有难度的
- 自动驾驶汽车能否按照规划的行驶？
- 将交通规则融入规划也是一个难点
- 实时计算：目前来说百度要求规划模块运转周期是100毫秒

运动规划可以获得两部分信息

自动驾驶车辆的规划决策模块负责生成车辆的行驶行为，是体现车辆智慧水平的关键
规划决策模块中的运动规划环节负责生成车辆的局部运动轨迹，是决定车辆行驶质量的直接因素。
运动规划基本方法有：RRT、Lattice、Spira、Polynomial、Functional Optimization等
现实之中无法像上面的内容一样，把物体看作一个质点，所以需要Configuration Space （构造空间）来解决这一问题
规划问题中涉及到一些约束条件大概分为三类：
- 一个是Local Constraint，例如避免和障碍物碰撞
- 第二是Differential Constraint，比如边界曲率
- 最后是Global Constraint。比如最短路径

运动规划是在连续空间的一种优化，对于连续空间过程的优化往往比较难，需将连续空间问题离散化表示
Roadmap：使用简单的连通图表示配置空间，使连续空间离散化
Visibility Graph将起始节点，所有障碍物的顶点和目标节点相互连接来构建路线图
除了Roadmap之外，还有Cell decomposition（网格分解方法）和Potential field（势场法）等路径规划方法
- Cell decomposition将整个空间分割成一个个cell，通过cell的连接图表示自由空间的连接属性
- Potential field就是直接用微分方法处理
一种常用的抽象连续空间的方法叫做PRM：
- 它在整个配置空间随机采样一些点，如果点在障碍物上则去掉，然后将这些点连接起来
- 最短路径就可以利用A-Star算法进行求解

RRT (基于快速扩展随机树算法)
- 它构造一个根结点为起始点的配置空间树，通过随机采样增加叶子节点的方式，生成一个随机扩展树，当随机树中的叶子节点包含了目标点或进入了目标区域，便可以在随机树中找到一条由从初始点到目标点的路径
- 通过这种方式离散化的线是不适合无人车行驶的，因为这些线的curvature不连续，甚至curvature都没有
Lattice网格方法
- 最原始的Lattice网格方法非常简单，它在XY世界坐标系中，以1米为单位进行网格划分，然后用无人车可以行进的、曲率连续的曲线将起始点和目标点连接起来
Polynomial方法
- 它将问题降维，分成了path 和 speed两个维度逐渐优化，这是一种iterative的处理方式
Functional Optimization方法
- 二次规划就是其中一种常用的方法