本节课主要介绍动力学约束下的路径规划，还是有些难度的！
首先依然是课程大纲：五个部分，重点是中间的三个部分，ppt上的顺序错了，课程先讲的Hybrid A*，其次才是Kinodynamic RRT*。加上动力学的约束后，机器人的路径搜索问题依然可以分为基于图的和基于采样的。
首先Kinodynamic这个词是个合成词：运动学和动力学两部分组成，中文不是太好翻译，大概能意会就可以了。
在前端考虑动力学约束，可以很好的降低后端优化的工作压力。
而且轨迹通常只能进行部分优化，所以在初始的路径搜索时要考虑动力学约束。
学习链接
几种常见的模型，区别就在于限制的不同。
参考链接
各类算法的核心就在于search tree这一步！
将栅格地图做连接其实就是一种对控制空间的离散化(sample)。
PRM就是对状态空间的离散化。
在控制空间中 进行sample的具体例子。关于矩阵
A
A
A:nilpotent，幂零矩阵，具有很好的性质，参考此篇博客。
状态转移矩阵：涉及到控制理论，都还给老师了23333.所以得及时复习呀！如果
A
A
A是幂零矩阵，则
e
A
t
e^{At}
eAt会很简洁，因为后面的项就都是0了。
lattice graph：将加入状态输入之后的节点(子状态)继续离散化，就是lattice graph。
一个具体的lattice 过程，关于搜索树的构建。
在状态空间的离散化：直接把小汽车能够到达的状态，反算之后加进来。
上面是一个两层的lattice graph；可以看出只有第一层是不一样的，因为出状态不一样，但是第二层则是完全一样的，因为第二层都是由相同的状态扩展出来的；此外能够看出lattice的计算开销还是非常大的，所以一般来说如果是在线进行lattice，通常只会选取一部分，而没必要全部都做。
基于控制空间的采样和基于状态空间的采样的一个很明显的对比，也是非常经典的一篇论文。在控制空间采样是很没有目的性的，，有很多都是不合格的；而状态空间中采样则可以最大限度的保证有更多的局部路径是可以使用的。而且如果只离散控制空间，会使得自由度很少；状态空间采样的缺点则在于难于实现(究竟如何去反算轨迹)。
首先来看一种最简单的情况，如上图所示，我们的目标就是想办法怎样从a状态达到b状态。
将x的运动用多项式来表示 。边界条件只有两个，就是0时刻和T时刻的位置，速度是不做要求的。通过两次求导，可以得到求解的方程。但是这样肯定不会是最优解的。
下面进入到本节课最困难的部分，因为涉及到很多数学上的东西，也会涉及到一些轨迹生成的知识。
我们的目标是：让jerk(加速度的导数)的平方的积分最小；这里用的方法是：Pontryagin’s maximum principle，其实就是这是变分法中欧拉-拉格朗日方程的特例。
一些纯粹数学上的推导。
利用刚才的最优控制理论预测乒乓球的落点，用无人机去接乒乓球。
由于汽车的动力学约束复杂，所以是无法做到实时的生成lattice，而且只能做到数值解，因此需要离线去生成，然后在线搜寻，是这样的一个流程。
轨迹库：单层的lattice。工程上常用，到时候去利用打分函数去选择即可。无人车上常用这种方法。
自动驾驶领域常用的一种框架：在活动坐标系下的lattice planning。
定义好状态后(初始状态满足距离、速度、加速度，终止状态要满足贴着车道线，所以只有位置上的要求，速度和加速度均为0)，问题就相当于去求解一个OBVP问题。
参考网址
混合A*算法：把栅格地图的路径搜索算法与lattice相结合；保证一个网格里只有一个节点 。
启发函数不一样；“找邻居的依据是lattice”；更新时也是更新的“状态”。
提出Hybrid A*算法的两篇论文:
Practical Search Techniques in Path Planning for Autonomous Driving, Dmitri Dolgov, Sebastian Thrun
Path Planning for Autonomous Vehicles in Unknown Semi-structured Environments, Dmitri Dolgov, Sebastian Thrun
工程上的一些trick：在其中一棵树上直接搜索，如果满足条件则可以提前结束算法，这个涉及到一些权衡。可以利用一定的概率，比如每搜索20次来一次one shot，就像抽奖一样233333.
github链接
无人机的A矩阵是幂零矩阵，所以会在计算时带来很多优势。
回顾一下RRT*的基本流程，不再赘述。
两者不同之处也就是在于考虑了动力学约束。
也就是要求解这样的一个最优控制问题！
