最优控制第七章动态规划法

1、第七章第七章 动态规划法动态规划法 动态规划是贝尔曼在动态规划是贝尔曼在50年代作为多段决策过程年代作为多段决策过程研究出来的，现已在许多技术领域中获得广泛应研究出来的，现已在许多技术领域中获得广泛应用。动态规划是一种用。动态规划是一种分段最优化方法分段最优化方法，它，它既可用来既可用来求解约束条件下的函数极值问题，也可用于求解约求解约束条件下的函数极值问题，也可用于求解约束条件下的泛函极值问题束条件下的泛函极值问题。它与极小值原理一样，。它与极小值原理一样，是处理控制矢量被限制在一定闭集内，求解最优控是处理控制矢量被限制在一定闭集内，求解最优控制问题的有效数学方法之一。制问题的有效数学方法之

2、一。 动态最优的核心是动态最优的核心是最优性原理最优性原理，它首先将一个，它首先将一个多段决策问题转化为一系列单段决策问题，然后从多段决策问题转化为一系列单段决策问题，然后从最后一段状态开始逆向递推到初始段状态为止的一最后一段状态开始逆向递推到初始段状态为止的一套求解最优策略的完整方法。套求解最优策略的完整方法。 下面先介绍动态规划的基本概念，然后讨论连下面先介绍动态规划的基本概念，然后讨论连续型动态规划。续型动态规划。 一、多段决策问题一、多段决策问题 动态规划是解决多段决策过程优化问题的一动态规划是解决多段决策过程优化问题的一种强有力的工具。所谓多段决策过程，是指把一种强有力的工具。所谓多

3、段决策过程，是指把一个过程按时间或空间顺序分为若干段，然后给每个过程按时间或空间顺序分为若干段，然后给每一步作出一步作出“决策决策”(或控制或控制)，以使整个过程取得最，以使整个过程取得最优优的效果。的效果。 如图如图1所示，对于中间的任意一段，例如第所示，对于中间的任意一段，例如第k+1段作出相应的段作出相应的“决策决策”(或控制或控制)uk后，才能确定该段后，才能确定该段输输入状态与输出状态间的关系，即从入状态与输出状态间的关系，即从xk变化到变化到xk+1的状的状态转移规律。在选择好每一段的态转移规律。在选择好每一段的“决策决策”(或控制或控制) uk以后，那么整个过程的状态转移规律从以

4、后，那么整个过程的状态转移规律从x0经经xk一直到一直到xN也就被完全确定。全部也就被完全确定。全部“决策决策”的总体，称为的总体，称为“策策略略”。 当然，如果对每一段的决策都是按照使某种性当然，如果对每一段的决策都是按照使某种性能指标为最优的原则作出的，那么这就是一个多段能指标为最优的原则作出的，那么这就是一个多段最优决策过程。最优决策过程。 图图1 多段决策过程示意图多段决策过程示意图 容易理解，在多段决策过程中，每一段容易理解，在多段决策过程中，每一段(如第如第k+1段段)的输出状态的输出状态(xk+1)都仅仅与该段的决策都仅仅与该段的决策(uk)及及该段的初始状态该段的初始状态(xk

5、)有关。而与其前面各段的决策有关。而与其前面各段的决策及状态的转移规律无关。这种性质称为及状态的转移规律无关。这种性质称为无后效性无后效性。 下面以最优路线问题为例，来讨论动态规划求下面以最优路线问题为例，来讨论动态规划求解多段决策问题。解多段决策问题。 设汽车从设汽车从A城出发到城出发到B城，途中需穿越三条河城，途中需穿越三条河流，它们各有两座桥流，它们各有两座桥P、Q可供选择通过，如图可供选择通过，如图2所所示。各段间的行车时间示。各段间的行车时间(或里程、费用等或里程、费用等)已标注在已标注在相应段旁。问题是要确定一条最优行驶路线，使从相应段旁。问题是要确定一条最优行驶路线，使从A城出发

6、到城出发到B城的行车时间最短。城的行车时间最短。 现将现将A到到B分成四段，每一段都要作一最优决分成四段，每一段都要作一最优决策，使总过程时间为最短。所以这是一个多段最策，使总过程时间为最短。所以这是一个多段最优决策问题。优决策问题。 由图由图2可知，所有可能的行车路线共有可知，所有可能的行车路线共有8条。条。如果将各条路线所需的时间都一一计算出来，并如果将各条路线所需的时间都一一计算出来，并作一比较，便可求得最优路线是作一比较，便可求得最优路线是AQ1P2Q3B，历时，历时12。这种一一计算的方法称为穷举算法。这种方。这种一一计算的方法称为穷举算法。这种方法计算量大，如本例就要做法计算量大，

7、如本例就要做323=24次加法和次加法和7次次比较。如果决策一个比较。如果决策一个n段过程，则共需段过程，则共需(n-1)2n-1次次加法和加法和(2n-1-1)次比较。可见随着段数的增多，计次比较。可见随着段数的增多，计算量将急剧增加。算量将急剧增加。 应用动态规划法可使计算量减少许多。动态规应用动态规划法可使计算量减少许多。动态规划法遵循一个最优化原则：即所选择的最优路线必划法遵循一个最优化原则：即所选择的最优路线必须保证其后部子路线是最优的。须保证其后部子路线是最优的。 例如在图例如在图2中，如果中，如果AQ1P2Q3B是最优路线，那么是最优路线，那么从这条路线上任一中间点到终点之间的一

8、段路线必从这条路线上任一中间点到终点之间的一段路线必定也是最优的。否则定也是最优的。否则AQ1P2Q3B就不能是最优路线就不能是最优路线了。了。 根据这一原则，求解最优路线问题，最好的办根据这一原则，求解最优路线问题，最好的办法就是从终点开始，按时间最短为目标，逐段向前法就是从终点开始，按时间最短为目标，逐段向前逆推。依次计算出各站至终点之间的时间最优值，逆推。依次计算出各站至终点之间的时间最优值，并据此决策出每一站的最优路线。如在图并据此决策出每一站的最优路线。如在图2中，从终中，从终点点B开始逆推。开始逆推。 最后一段最后一段(第四段第四段)：终点：终点B的前站是的前站是P3或或Q3，不，

9、不论汽车先从哪一站始发，行驶路线如何，在这最后论汽车先从哪一站始发，行驶路线如何，在这最后一段，总不外乎是从一段，总不外乎是从P3到到B，历时为，历时为4，或从，或从Q3到到B，历时为历时为2，将其标明在图，将其标明在图3中相应的圆圈内。比较中相应的圆圈内。比较P3与与Q3这一最后一段最优决策为这一最后一段最优决策为Q3B。 最后一段最后一段(第四段第四段)：终点：终点B的前站是的前站是P3或或Q3，不，不论汽车先从哪一站始发，行驶路线如何，在这最后论汽车先从哪一站始发，行驶路线如何，在这最后一段，总不外乎是从一段，总不外乎是从P3到到B，历时为，历时为4，或从，或从Q3到到B，历时为历时为2

10、，将其标明在图，将其标明在图3中相应的圆圈内。比较中相应的圆圈内。比较P3与与Q3这一最后一段最优决策为这一最后一段最优决策为Q3B。 第三段：第三段：P3、Q3的前站是的前站是P2、Q2。在这一段也。在这一段也不论其先后的情况如何，只需对从不论其先后的情况如何，只需对从P2或或Q2到到B进行最进行最优决策。从优决策。从P2到到B有两条路线：有两条路线：P2P3B，历时为，历时为6；P2Q3B，历时为，历时为4，取最短历时，取最短历时4，标注在，标注在P2旁。从旁。从Q2到到B也有两条路线：也有两条路线：Q2P3B，历时为，历时为7；Q2Q3B，历时，历时为为5，取最短历时，取最短历时5，标注

11、在，标注在Q2旁。比较旁。比较P2与与Q2的最的最优值，可知这一段的最优路线是优值，可知这一段的最优路线是P2Q3B。 第二段：第二段： P2、Q2的前站是的前站是P1、Q1。同样不管。同样不管汽车是如何到达的汽车是如何到达的P1、Q1，重要的是保证从，重要的是保证从P1或或Q1到到B要构成最优路线。从要构成最优路线。从P1到到B的两条路线中，的两条路线中，P1P2Q3B，历时为，历时为11；P1Q2Q3B，历时为，历时为11，取最，取最短历时短历时11，标注在，标注在P1旁。从旁。从Q1到到B的也有两条路的也有两条路线中，线中，Q1P2Q3B，历时为，历时为8；Q1Q2Q3B，历时为，历时为

12、13，取最短历时，取最短历时8，标注在，标注在Q1旁。比较旁。比较P1与与Q1的的最优值，可知这一段的最优路线是最优值，可知这一段的最优路线是Q1P2Q3B。 第一段：第一段：P1、Q1的前站是始发站的前站是始发站A。显见从。显见从A到到B的最优值为的最优值为12，故得最优路线为，故得最优路线为AQ1P2Q3B。 综上可见，动态规划法的特点是：综上可见，动态规划法的特点是：1) 与穷举算法相比，可使计算量大大减少。如与穷举算法相比，可使计算量大大减少。如上述最优路线问题，用动态规划法只须做上述最优路线问题，用动态规划法只须做10次次加法和加法和6次比较。如果过程为次比较。如果过程为n段，则需做

13、加段，则需做加法。以上例为例，用穷举法需作法。以上例为例，用穷举法需作4608次加法，次加法，而后者只需做而后者只需做34次加法。次加法。 2) 最优路线的整体决策是从终点开始，采用逆推方最优路线的整体决策是从终点开始，采用逆推方法，通过计算、比较各段性能指标，逐段决策逐步法，通过计算、比较各段性能指标，逐段决策逐步延伸完成的。延伸完成的。 全部最优路线的形成过程已充分表达在图全部最优路线的形成过程已充分表达在图3中。中。 从最后一段开始，通过比较从最后一段开始，通过比较P3、Q3，得到，得到Q3B； 倒数第二段，通过比较倒数第二段，通过比较P2、Q2，得到，得到P2Q3B； 倒数第三段，通过

14、比较倒数第三段，通过比较P1、Q1，得到最优决策，得到最优决策为为Q1P2Q3B； 直至最后形成最优路线直至最后形成最优路线AQ1P2Q3B。 象这样将一个多段决策问题转化为多个单段决象这样将一个多段决策问题转化为多个单段决策的简单问题来处理，正是动态规划法的重要特点策的简单问题来处理，正是动态规划法的重要特点之一。之一。 3) 动态规划法体现了多段最优决策的一个重要动态规划法体现了多段最优决策的一个重要规律，即所谓规律，即所谓最优性原理最优性原理。它是动态规划的理。它是动态规划的理论基础。论基础。 对图对图4所示的所示的N段决策过程，如果在第段决策过程，如果在第k+1段处把全段处把全过程看成

15、前过程看成前k段子过程和后段子过程和后N-k段子过程两部分。对于后段子过程两部分。对于后部子过程来说，部子过程来说，xk可看作是由可看作是由x0及前及前k段初始决策段初始决策(或控或控制制) u0,u1, uk-1所形成的初始状态。那么，多段决策的所形成的初始状态。那么，多段决策的最优决策略具有这样的性质：不论初始状态和初始决策最优决策略具有这样的性质：不论初始状态和初始决策如何，其余如何，其余(后段后段)决策决策(或控制或控制)对于由初始决策所形成的对于由初始决策所形成的状态来说，必定也是一个最优策略。这个性质称为最优状态来说，必定也是一个最优策略。这个性质称为最优性原理。性原理。 图图4

16、N段决策过程段决策过程 设图设图5中中x*(t)是连续系统的一条最优轨线。是连续系统的一条最优轨线。x(t1)是最优轨线上的一点，那么最优性原理说明，不管是最优轨线上的一点，那么最优性原理说明，不管t=t1, t0 t1 tf时，系统是怎样转移到状态时，系统是怎样转移到状态x(t1)的，但的，但从从x(t1)到到x(tf)这段轨线必定是最优的。因为最优轨线这段轨线必定是最优的。因为最优轨线的后一段从的后一段从x(t1)到到x(tf)如果还有另一条轨线是最优的如果还有另一条轨线是最优的话，那么原来从话，那么原来从x(t0)到到x(tf)的轨线就不是最优的，这的轨线就不是最优的，这与假设矛盾。因此

17、，最优性原理成立。与假设矛盾。因此，最优性原理成立。 应用最优性原理可以将一个应用最优性原理可以将一个N段最优决策问题转段最优决策问题转化为化为N个一段最优决策问题，从而大大减少求解最优个一段最优决策问题，从而大大减少求解最优决策问题的计算量。决策问题的计算量。 图图5 连续系统的状态转移过程连续系统的状态转移过程 图图5 连续系统的状态转移过程连续系统的状态转移过程 二、连续系统的动态规划二、连续系统的动态规划 利用动态规划最优性原理，可以推导出性能利用动态规划最优性原理，可以推导出性能泛函为极小应满足的条件泛函为极小应满足的条件哈密尔顿雅可比哈密尔顿雅可比方程。它是动态规划的连续形式，解此

18、方程可求方程。它是动态规划的连续形式，解此方程可求得最优控制得最优控制u*(t)。现在来推导这一方程。现在来推导这一方程。 tuxfx, 00 xtx 0,ffttxN ftttxttuxLtxJfd,min,00Uu设连续方程为设连续方程为(1)终端约束终端约束使性能泛函使性能泛函求最优控制求最优控制u*(t)， 或或u任意。任意。初始状态初始状态(2)(3)(4) 根据最优性原理，如果根据最优性原理，如果x*(t)是以是以x(t0)为初始为初始状态的最优轨线。如图状态的最优轨线。如图6所示。所示。图图6 连续系统最优轨线连续系统最优轨线 fttUutxttuxLtxJfd,min,0* f

19、ttttttUutxttuxLttuxLfd,d,min(5) 设设t = t ( t0 t tf)时，状态为时，状态为x(t)，它将轨线，它将轨线分成前后两半断。那么以分成前后两半断。那么以x(t)为初始状态的后半为初始状态的后半段也必是最优轨线。而与系统先前如何到达段也必是最优轨线。而与系统先前如何到达x(t)无关。无关。 若取若取t0= t, t= t + t，式，式(4)可写成可写成 ftttUutxttuxLttttxJfd,min,*ttuxLttuxLttt,d, 根据最优性原理，如果根据最优性原理，如果t到到tf的过程是最优的，的过程是最优的，则从则从t + t到到tf的后部子

20、过程也是最优的，其中的后部子过程也是最优的，其中t t + t tf。因此可写成。因此可写成 (6)(7) 当当t很小时，有很小时，有式式(5)可近似表示为可近似表示为ttttxJttuxLtxJUu,min,*(8) fttUutxttuxLtxJfd,min,0* fttttttUutxttuxLttuxLfd,d,min(5) ttuxLttuxLttt,d, ftttUutxttuxLttttxJfd,min,*xxttxxttxddttuxfttxx,ddttxxJttttxJ,*将将x(t + t)进行泰勒展开，取一次近似，有进行泰勒展开，取一次近似，有(9)(10)(11)ttt

21、xJxxtxJtxJttxxJT,* 将上式在将上式在x,t领域展成泰勒级数，考虑到领域展成泰勒级数，考虑到J*x+x, t+t既是既是x的函数，也与的函数，也与t有关，所以有关，所以(12)ttttxJttuxLtxJUu,min,*(8)tttxJxxtxJtxJttuxLtxJTUu,min,*ttuxfxtxJttuxLtttxJtxJTUu,min,* 代入式代入式(8)，得，得(13)tttxJxxtxJtxJttxxJT,*(12)ttttxJttuxLtxJUu,min,*(8)tttxJ,*tuxfxtxJtuxLttxJTUu,min,*考察上式因为考察上式因为J*x, t

22、与与u无关，故无关，故J*x, t与与可提到可提到min号外面。经整理可得号外面。经整理可得式式(14)称为连续系统动态规划基本方程或贝尔曼方程。称为连续系统动态规划基本方程或贝尔曼方程。 (14) 贝尔曼方程。它是一个关于贝尔曼方程。它是一个关于J*x, t的偏微分的偏微分方程。解此方程可求得最优控制使方程。解此方程可求得最优控制使J为极小。它为极小。它的边界条件为的边界条件为 ffffttxttxJ,*(15) tuxfxtxJtuxLttxJTUu,min,*(14)tuxfxtxJtuxLtuxHT,*tuxftuxLT,xtxJ,*tuxHttxJUu,min,*如果令哈密尔顿函数为

23、如果令哈密尔顿函数为式中式中则式则式(14)可写成可写成(17) (16)当控制矢量当控制矢量u(t)不受限制时，则有不受限制时，则有tuxHttxJ,*上两式称为哈密尔顿雅可比方程。上式说明，上两式称为哈密尔顿雅可比方程。上式说明，在最优轨线上，最优控制必须使在最优轨线上，最优控制必须使H达全局最小。达全局最小。实际上这就是极小值原理的另一种形式。实际上这就是极小值原理的另一种形式。 (18)0,*tuxfxtxJtuxLttxJT0,2*2*2tuxfxtxJxtuxfxtxJxtuxLtxtxJT 由贝尔曼方程可推导出协态方程和横截条件。由贝尔曼方程可推导出协态方程和横截条件。式式(14

24、)可写成可写成 对对x求偏导数，得求偏导数，得(20)(19)tuxfxtxJtuxLttxJTUu,min,*(14)xJ*txxtxJtxtxJxtxJtdd,dd2*2*2*0,dd*xtuxfxtxJxtuxLxtxJtT由于对由于对t的的 全导数，为全导数，为(22) (21)代入式代入式(20)可写成可写成0,2*2*2tuxfxtxJxtuxfxtxJxtuxLtxtxJT(20) xtxJt,* xHxtuxftxtuxLttT,ddxH令令 ，则上式可写成，则上式可写成(23)这就是所求的协态方程这就是所求的协态方程 ，与以前结果，与以前结果完全一致。完全一致。0,dd*xt

25、uxfxtxJxtuxLxtxJtT(22) 在在t= tf时，在终端处性能泛函为时，在终端处性能泛函为 ffTffffttxNttxttxJ,*式中式中与与N同维的乘子矢量。同维的乘子矢量。 (24) ffttTffffffttffftxttxNtxttxtxttxJ,* fttfTfftxNtxt对对x(tf)求偏导数，得求偏导数，得(25)(26)即即 ffTffffttxNttxttxJ,*(24)将式将式(24)对对tf求偏导数，得求偏导数，得 ffttfffTfffttffftttxNtttxtttxJ,*(27) ffTffffttxNttxttxJ,*(24)考虑式考虑式(17

26、)、式、式(20)得得0fttfTftNtH 上述结果与极小值原理中推导的完全一致。上述结果与极小值原理中推导的完全一致。上述推导过程实际上等于用动态规划方法间接证上述推导过程实际上等于用动态规划方法间接证明了极小值原理。明了极小值原理。 (28)tuxHttxJUu,min,*(17) 0,2*2*2tuxfxtxJxtuxfxtxJxtuxLtxtxJT(20) ffttfffTfffttffftttxNtttxtttxJ,*(27) 应当指出，与极小值原理相比，动态规划法需应当指出，与极小值原理相比，动态规划法需要解偏微分方程式要解偏微分方程式(14)，它要求，它要求J x, t具有连续

27、的具有连续的偏导数，但在实际工程中，这一点常常不能满足，偏导数，但在实际工程中，这一点常常不能满足，因而限制了动态规划法的使用范围。因而限制了动态规划法的使用范围。 ux tuxxJftud21min0242例例1：设：设 ，求最优控制，求最优控制u*(t)使使uxJuxxfxJLH24221uxJuxxfxJLtJuu*242*21minmin解：构造哈密尔顿函数解：构造哈密尔顿函数 根据哈密尔顿雅可比方程，有根据哈密尔顿雅可比方程，有考虑控制考虑控制u不受限制，得不受限制，得0221*242xJuuuxJuxxuH xJtu*212*2*42*214121xJxJxxtJ2*424121x

28、Jxx故故 xJt* ttu21* 边界条件，因边界条件，因x(tf), tf=0，故，故Jx(tf)=0 如果令如果令 ，则得，则得 这正是应用极小值原理所得的结果，二者这正是应用极小值原理所得的结果，二者完全一致。完全一致。 uxx100010 010 xtuxJd2120221例例2：设受控系统状态方程为：设受控系统状态方程为初始状态为初始状态为性能泛函为性能泛函为试求在试求在u无限制情况下，使无限制情况下，使J取极小时的最优控制。取极小时的最优控制。 uxxJxJuxfxJLHT22*1*221*212uxJxxJux2*21*221212解：构造哈密尔顿函数解：构造哈密尔顿函数uxJ

29、xxJuxHtJuu2*21*221*212minmin0uuH2*xJu由哈密尔顿雅可比方程由哈密尔顿雅可比方程因因u无限制，可从无限制，可从求得求得0*tJ021222*21*21xJxxJx代入上式，并注意到代入上式，并注意到J*与与t无关，因而无关，因而 ，有有223212211*2xaxxaxaJ02122232213212122xaaxxaaaxa 为求解此偏微分方程，设其解为为求解此偏微分方程，设其解为满足方程，得满足方程，得0, 02, 0123232122aaaaaa1, 2321aaa222121*22xxxxJ 212*2xxxtxJu各项系数为各项系数为可得可得解为解为最优控制最优控制最优控制可由状态反馈实现，如图最优控制可由状态反馈实现，如图7所示。所示。进一步考察系统的状态轨线。系统的状态方程进一步考察系统的状态轨线。系统的状态方程*2210 xx为齐次方程。为齐次方程。 0011*xAsILxetxAt011121201221111j