from:https://en.wikipedia.org/wiki/Differential_dynamic_programming
深入理解DDP
DDP是一种轨迹优化类别问题中的最优控制算法。这种算法在1966年被Mayne提出。
该算法使用动态模型(dynamics)以及代价函数(cost functions)的局部二次(locally-quadratic)模型,并且展现二次收敛(displays quadratic convergence)性质。它与Pantoja's step-wise Newton's method有很大关联。
Finite-horizon discrete-time problems
下面我们来看看所要研究的问题:
The dynamics:
从状态x出发,使用控制序列 直到horizon is reached。
其中 ,这个最优控制问题的解就是要寻找一个最优控制序列来最小化上面的代价函数
轨迹优化(Trajectory optimization)意味着对于某一个 找到一个 使得代价函数最小,而不是对于所有可能的初始状态(rather than for all possible initial states)。
Dynamic programming
设 是控制序列中的一部分 ,并且定义 cost-to-go 作为从
到 的一个部分和代价。
其中令 ,动态规划原理指的是在时间上backwards,并且每一次都是基于单个控制步来减少cost function的:
这就是Bellman equation。
Differential dynamic programming
DDP是如何运行的呢?
它通过迭代运行backward pass和forward pass来进行规划求解的。
DDP proceeds by iteratively performing a backward pass on the nominal trajectory to generate a new control sequence, and then a forward pass to compute and evalute a new nominal trajectory.
首先,我们看看backward pass是一个什么样的东西。
在上面一节的Bellman方程中,需要最小化的项为:
设 为该量在 -th 处的变分:
(我们知道,变分为0时也就达到了极值)。
将该式展开为二阶形式(Taylor展开即可,比如先按delta_x展开,再按delta_u展开):
为了方便,我们将i去掉,并且利用prime(单引号)表示下一个时间步,该展开的系数分别为:
关于 最小化上面的二阶展开式,有
上面是通过线性二次最优问题的解得出,这里为什么要最小化变分呢?首先,上面的变分作为一个二次项形式,总是大于等于0的,我们并不去直接求解变分为0,而是最小化变分,这样的话假使变分不能为0,也即没有0解,同样也可以得到一个 使得变分尽可能小,也就是代价函数的变化尽可能小,也即趋于收敛。
定义一个open-loop term ,以及一个feedback gain term ,将上面的最优 代入上面的二次展开式中,可以得到:
实际上,这里的Delta_V是1的系数,Vx是delta_x的系数,Vxx是(delta_x)^2的系数。
然后,我们反复递归计算的局部二次模型(local quadratic models)以及control modifications ,from down to 。
上面这些也就组成了backward pass。
其中 。
一旦上面的backward pass完成之后,我们就可以通过forward pass来计算一个新的轨迹(trajectory):
backward pass 和 forward pass将会一直迭代,直到收敛。