Optimization Inside Motion Planning
约束问题的核心:
- 第一是目标函数的定义,目标函数比较清晰,对于后面的求解更有帮助
- 第二是约束,比如路网约束、交规、动态约束等
- 第三是约束问题的优化,比如动态规划、二次规划等
动态规划
- 动态规划通过类似于有限元的方式,把问题从连续空间抽象成离散空间,然后在离散空间中进行优化
- 虽然这种方法可以逼近连续空间中的最优解,但是计算复杂度很高
- 针对计算时间长的问题,可以使用牛顿方法进行优化,它的收敛次数是指数平方,也叫二次收敛。
二次规划
- 二次规划算法的本质是牛顿法的 Taylor 展开,但是它的求解过程涉及更复杂的情况
- 因为二次规划方法并不一定是处理一维问题,可能涉及更高阶求导
- 牛顿法要求 locally convex 才能保证收敛,也就是导数是严格单调递增的
- 为了解决一般函数并没有这样的特性,动态规划或二次规划都无法获得全局最优解,通常使用启发式搜索方法
- 首先通过动态规划方式对整个问题有一个粗浅的认识,然后通过二次规划进行细化
- 这种启发式搜索方法也是目前百度 Apollo 的 EM 算法的核心思想
- 这种方法和人开车的过程是一样的,通常驾驶员会先形成一个大概的指导思想,指明往什么方向开,然后再规划一条最优路径
- 一般来说,二次规划问题会写成一个二次函数:
- X 是向量参数,Q 是一个对称的正定矩阵, cTx是偏差项
- 对于这种没有约束的二次规划问题,只需要求导数等于0的那个点,使得 Qx=-C ,即可求解二次规划问题
- 求解速度是 O(N3)
- 对于带约束的二次规划问题,情况就相对复杂一点
- 解法一:把限制条件放到上面的式子中,通过换元,变成一个全新的 QP 问题求解,但是这种方法很慢
- 解法二:Lagrangian method ,通过增加松弛变量的方式去掉约束条件,变成一个可以解决的问题
- 对于不等式的约束条件可以使用 active set method,其主要出发点是最后解,可能落到边界上,如果真的是边界最优,不等式约束就可以转化为等式约束问题求解
- 总的来说,对于求解非线性优化问题(自动驾驶中的规划基本都是非线性的),通常就是用启发式方法来求解
- 先用动态规划给出一个粗略解,给出一个凸空间,然后用二次规划方法在凸空间里去寻找最优解