最优控制.动态规划(1)

1、动态规划法动态规划是解决多级决策过程最优化的一种数学方法。所谓多级决策过程，是指把一个过程分为若干个阶段，而每一个阶段都需作出决策，以便使整个过程取得最优的效果。 最短路线问题问题: 要求从A地到F地，选择一条最短的线路。A1B2B3B1C2C3C1D2D3D1E2EF12345678965411354524244957为了便于分析，引入几个符号： N：从某点到终点之间的级数；x：表示在任一级所处的位置，称为状态变量；SN (x)：决策变量，表示当处于状态x，还有N级时，所选取的下一个点； WN(x)：表示从状态x到终点F的N级过程的最短距离； d(x, SN)：表示从状态x到点SN的距离。

2、从最后一级开始计算： 2322231133212222211222212221111122111)(, 72519min)(),()(),(min)()(, 72916min)(),()(),(min)()(, 42214min)(),()(),(min)(2)(1)(EDSEWEDdEWEDdDWEDSEWEDdEWEDdDWEDSEWEDdEWEDdDWEWEWA1B2B3B1C2C3C1D2D3D1E2EF12345678965411354524244957从哪下手？ SN (x)：决策变量，表示当处于状态x，还有N级时，所选取的下一个点； WN(x)：表示从状态x到终点F的N级过程的最

3、短距离； 同理 255234341242411414133332232311313)(,14)()(,12)()(, 9)()(,14)()(, 8)()(,11)()(, 5)(BASAWCBSBWCBSBWCBSBWDCSCWDCSCWDCSCW所以，最短路线为 FEDCBA2112最短距离为14 一个N级最优过程，不管第一级决策如何，其余N-1级，决策过程至少必须依据第一级决策所形成的状态组成一个N-1级最优过程，在此基础上，在选择第一级决策，使总的N级过程为最优。 A1B2B3B1C2C3C1D2D3D1E2EF12345678965411354524244957这种递推关系可以用下列

4、递推方程式来表达： ),()()()(,min)(11)(FxdxWxSWxSxdxWNNNxSNN是不是穷举法？ 再看一个例子最短时间问题最短时间问题问题：设有人要从 A 点开车到 E 站，中间要经过任意三个中间站，站名在图中圆圈内表示。站与站之间称为段，每段路程所需时间（小时）标在段上。现要问，这人应如何选择路线才能最快到达目的地？1C3C2CA2B1B2D1DE15414132)6()5()6(367)9()10()5()1()4(2最短时间的到由EB1什么是穷举法? 从 走到 一共有六条路线，每条路线由四段组成。这六条路线和对应的行车时间如下AE 路 线 行车时间（小时） 13 11

5、14 13 12 9EDCAB232EDCAB222EDCAB122111AB C D EEDCAB121EDCAB221显然最优路线是 ，它所花时间为9小时。 EDCAB2211C3C2CA2B1B2D1DE15414132)6()5()6(367)9()10()5()1()4(2最短时间的到由EB1 这里每条路线由四段组成，也可以说是四级决策。 为了计算每条路线所花时间，要做三次加法运算，为了计算六条路线所花的时间要作36=18次运算。这种方法称为“穷举法”。 显然当段数很多时，计算量是很大的。这种方法的特点是从起点站往前进行，而且把这四级决策一起考虑。应注意从到 下一站 所花的时间为1，

6、而到 所花时间为3，但最优路线却不经过 。 这说明只看下一步的“眼前利益眼前利益”来作决策是没有意义的。A2B1B2B为将问题表达得清楚，引进下面的术语（写法并不完全一样）。令 表示由某点 到终点的段数（如 到 为2段， 。nE2CE令 表示当前所处点的位置（如 ），称为状态变量。x12,A B C对比一下最开始的例子2n 令 为决策（控制）决策（控制）变量，它表示当处在 位置而还有 段要走时，所要选取的下一点。例如，从 出发，下一点为 时，则表示为 。)(xunxn2C2D222)(DCu令 表示在位置 ，向终点还有 段要走时，由 到终点 的最短时间。例如，从C2到E的最短时间为4，可表示为

7、T2(C2)=4。)(xTnxnxE令 表示从点 到点 的时间。例如，从 到 的时间为),(nnuxtx)(xun2C2D3),(22DCnt有了这些术语后，就可用动态规划来解这个例子。从最后一段出发进行计算，并将计算出的最短时间 用括号表示在相应的点 处（见图6-1）。)(xTnx n=1 （倒数第一段） 考虑从 和 到 的路线，由定义可知，最短时间分别为1D2DE1112()5; () 1T DT D1C3C2CA2B1B2D1DE15414132)6()5()6(367)9()10()5() 1 ()4(2最短时间的到由EB1n=2（倒数第二段）考虑从 到 的路线。 12211122,2

8、212(,)( )2 5minmin4(,)()3 1D Dt C DT DT Ct C DT D由 到 有两种路线： ， 。两种路线中的最短时间由下式确定：123,C C C2CEEDC12EDC22E最优决策为 。222DCu1C3C2CA2B1B2D1DE15414132)6()5()6(367)9()10()5() 1 ()4(2最短时间的到由EB1由 到 只有一种路线 ，其时间为1CEEDC1165112CT由 到E也只有一种路线 ，其时间为 3C51432CTEDC231C3C2CA2B1B2D1DE15414132)6()5()6(367)9()10()5() 1 ()4(2最短

9、时间的到由EB11C3C2CA2B1B2D1DE15414132)6()5()6(367)9()10()5() 1 ()4(2最短时间的到由EB1n=3（倒数第三段） 从B2到E有两种路线： 和 ECB32ECB2264264min)(),()(),(min22211211,1321CTCBtCTCBtBTCC最优决策213)(CBu最短时间为：n=4（倒数第四段） 从A到E的路线有两种： 和 。EAB1EAB21C3C2CA2B1B2D1DE15414132)6()5()6(367)9()10()5() 1 ()4(2最短时间的到由EB1 910163min)(),()(),(min2321

10、31,421BTBAtBTBAtATBB最优决策为 14)(BAu 至此求出了A到E的最短时间为9，最优路线为 。在图中用粗线表示。这里，为决定最优路线进行了10次加法，比穷举法的18次少了8次。当段数n更多时，节省计算将会更多。EDCAB2211C3C2CA2B1B2D1DE15414132)6()5()6(367)9()10()5() 1 ()4(2最短时间的到由EB1 以上面的最短时间问题为例，如把 当作初始状态，则余下的决策 对 来讲是最优策略；如把 当初始状态，则余下的决策 对 来讲也构成最优策略。一般来说，如果一个最优过程用状态 来表示，最优决策为 ，则对状态 来讲， 必定是最优的

11、，这可用图6-2来表示。2C22C D E2C1BEDCB2211BNxxx,10110,Nuuukx11,Nkkuuu1kN0 x1x01kxkxNx0u1ku最优解图6-2 最优性原理示意图动态规划的特点： 一是它从最后一级反向计算；二是其将一个N级决策问题化为N个单级决策问题。好处：将一个复杂问题化为多个简单问题加以求解。最优性原理最优性原理贝尔曼的最优性原理可叙述如下：“一个多级决策问题的最优决策具有这样的性质：当把其中任何一级及其状态作为初始级和初始状态时，则不管初始状态是什么，达到这个初始状态的决策是什么，余下的决策对此初始状态必定构成最优策略。”在多数实际问题中， 级决策的性能指

12、标 取如下形式NJ10,NkkkNuxFJ 是由某级状态和决策决定的性能函数，要求寻找决策 使J取极小值 。( , )F 110,Nuuu*NJ最优性原理可表示为 *1001111,00111100,*),(min),(),(min),(min),(),(),(min011010NuNNuuuNNuuNJuxFuxFuxFuxFuxFuxFuxFJNN根据上式就可证明最优性原理的正确性。若以 为初态时，余下的决策 不是最优的，那么就存在另一决策序列 所决定的指标值 ，于是1x11,Nuu11,Nuu *11NNJJ100*100*),(min),(min00NuNNuNJuxFJJuxFJ这与

13、 是极小值发生矛盾，所以余下的决策必须是最优的。*NJ6-2 离散最优控制问题设控制系统的状态方程为) 1, 1 , 0()(),() 1(Nkkukxfkx式中x(k)是k时刻的几维状态向量，u(k)是k时刻的p维容许控制向量，设系统在每一步转移中的性能指标为Fx(k),u(k) 如在u(0)的作用下)0(),0()0()0(),0() 1 (1uxFxJuxfx在u(1)的作用下)1 (),1 ()0(),0()0()1 (),1 ()2(2uxFuxFxJuxfx对N级决策过程)1(),1()()1 (),1 ()2()0(),0() 1 (NuNxfNxuxfxuxfx性能指标10)(

14、),()1(),1()1 (),1 ()0(),0()0(NkNkukxFNuNxFuxFuxFxJ要求选择控制序列 ) 1(,),1 (),0(Nuuu使性能指标达到极小 根据最优性原理 ) 1, 2 , 1() 1(),1()()() 1(),1(min) 1() 1 ()0(),0(min)0(*)1(*1*1)0(*NjjujxfjxjxJjujxFjxJxJuxFxJjNjujNNuN解上述递推方程，即可获得最优控制序列。例6-1 设一阶离散系统的状态方程为 ) 1, 1 , 0()()() 1(Nkkukxkx初始条件为x(0)，控制变量u不受约束，性能指标为1022)(21)(2

15、1NkkuNcxJ求最优控制u*(t)，使J达最小，为简便起见，设N2 解 设在u(0)、u(1)作用下，系统状态为x(0)、x(1)、x(2) 先考虑从x(1)到x(2)的情况，控制为u(1)cxxcxcJccxuuuxcuJuuxcucxxJ1) 1 ()2(1) 1 (211) 1 () 1 (0) 1 () 1 () 1 (0) 1 (21) 1 () 1 (21) 1 (21)2(21) 1 (2*11122221，再考虑从x(0)到x(1)的情况，控制为u(0)0(211) 1 ()21 (2)0(21)0()0(0)0()0()0(121)0(21)0() 1 (121)0(21

16、min)0(21min)0(2*2222222)0(*12)0(*2xccxccxJccxuuJuxccuxJxccuJuxJuu最优控制序列为 ccxuccxu21)0() 1 (,21)0()0(*最优性能指标为 )21 (2)0(2*ccxJ 连续系统的动态规划连续系统的动态规划设系统的状态方程和性能指标为 ),(UXtfX 00)(XtXfttffdttUXFttXJ0),(),( （6-19） （6-20） 受约束，可写成 为某一闭集。要寻找满足此约束且使 最小的最优控制 。U,UJU 设时间 在区间 内，则根据最优性原理，从 到 这一段过程应当是最优过程。把这段最优指标写成 ,则t

17、,0ftttft),(tXVdUXFttXtXJtXVfttffu),(),(min),(),(（6-21）显然 满足终端条件),(tXVffffttXttXV),(),(通常假定 对 及 的二阶偏导数存在且有界。),(tXVXt现在，考虑系统从 出发，到 分两步走：先从 到 ，再 从到 ， 是小量，则ttftttttfttttttttffufdUXFdUXFttXtXV),(),(),(min),(（6-23）根据最优性原理，从 也应是最优过程。 fttt到因 故,)(tXXttXftttffudUXFttXtttXXV),(, )(min),(这样，式（6-23）可写成)( 0),(),(

18、min),(),(min),(2tttVXXVtXVttUXFtttXXVttUXFtXVTuu（6-24）注意到 ，上式右边括号中 表示最优指标，其中 为最优控制，不需再选择， 也与 选择无关。故ttUXftXX),(),(tXVUttVU2(, )min(, )(, )(, )0()TuVVV X tF X U ttf X U ttV X tttXt 从上式两端消去 ，除以 ，再令 ，可得),(tXVt0tmin(, )(, )TuVVF X U tfX U ttX （6-25）引用以前使用过的哈密顿函数 ),(),(),(tUXftUXFtUXHT （6-26） XV （6-27）则（6

19、-25）可写成 ),(),(mintXVUXHtXVUXHtVu （6-28）（6-25）或（6-28）称为哈密顿雅可比贝尔曼方程，边界条件是：哈密顿雅可比贝尔曼方程在理论上很有价值，但它是 的一阶偏微分方程并带有取极小的运算，因此求解是非常困难的，一般情况得不到解析解，只能用计算机求数值解。对于线性二次问题，可以得到解析解，而且求解结果与用极小值原理或变分法所得结果相同。这时，哈密顿雅可比贝尔曼方程可归结为黎卡提方程。在实际计算线性二次问题时，一般用直接求解黎卡提方程来求最优控制。),(tXVffffttXttXV),(),(例6-3 设系统状态方程为 uxxx221,初始状态 )(, 0)

20、0(, 1)0(21tuxx不受约束，性能指标为 dtuxJ0221)212(求最优控制u*(t)，使性能指标J为最小。解 222112*21( , , )220 xVVVH x utxuuxxxHVuux 由于2212121minmin 22uuVVVVHxuxuttxx，因为系统是时不变的，并且性能指标的被积函数不是时间的显函数，故0Vt解 222112*21( , , )220 xVVVH x utxuuxxxHVuux 由于2212121minmin 22uuVVVVHxuxuttxx，因为系统是时不变的，并且性能指标的被积函数不是时间的显函数，故0Vt解得221122*122( )2

21、2( )22V xxx xxVu txxx 2212121202VVxxxx引用以前使用过的哈密顿函数 ),(),(),(tUXftUXFtUXHT （6-26） XV （6-27）则（6-25）可写成 ),(),(mintXVUXHtXVUXHtVu （6-28）思考题 HJB方程与极小值原理的区别和联系？动态规划与极小值原理动态规划与极小值原理动态规划和极小值原理是最优控制理论的两大基石，它们都可以解决有约束的最优控制问题，虽然在形式上和解题方法上不同，但却存在着内在的联系。下面我们从动态规划来推演极小值原理，不过要说明这种推演是基于最优指标对和两次连续可微这个条件的。 最优性能指标与状态

22、方程为),(tUXfX 00)(XtX（6-29）要求确定U(t)使性能指标fttffdttUXFttXJ0),(),( （6-30）极小。其中， 固定， 自由， 可以有约束，也可以没有。ftt ,0)(ftXU1、 （状态方程） （6-31）HX2、 （协态方程） （6-32）XH3、 （边界方程） （6-33）00)(XtX4、 （横截条件） （6-34）)()(fftXt5、 （极值条件） （6-35）),(),(mintUXHtUXHu用动态规划求解的结果已在上节中得到，现在归纳一下：在动态规划中协态变量 满足XV哈密顿雅可比贝尔曼方程（6-28）本身说明了哈密顿函数在最优控制上取极值的条件，故等同于上面极小值原理所得的条件5，不过（6-28）还多给出了一点信息，即 。tVH下面由动态规划法来推出协态方程。 由dtdxXXtXVXtXVtXtXVdtddtdT),(),(),(2XV（6-27）因假设对两次连续可微，因此上式成立，且可交换求导次序，得XHfXVFXXfXVXFtUXfXXtXVtUXfXVtUXFXtUXfXXtXVttXVXTTTTT)()(),(),(),()(),(),(),(),(22即协态方程（因都是最优解条件。故省去*号。由（6-22）和（6-27）再来推横截条件)(),()(