优控制第七章动态规划法.ppt

第七章 动态规划法,动态规划是贝尔曼在50年代作为多段决策过程 研究出来的，现已在许多技术领域中获得广泛应 用。动态规划是一种分段最优化方法，它既可用来 求解约束条件下的函数极值问题，也可用于求解约 束条件下的泛函极值问题。它与极小值原理一样， 是处理控制矢量被限制在一定闭集内，求解最优控 制问题的有效数学方法之一。,动态最优的核心是最优性原理，它首先将一个 多段决策问题转化为一系列单段决策问题，然后从 最后一段状态开始逆向递推到初始段状态为止的一 套求解最优策略的完整方法。 下面先介绍动态规划的基本概念，然后讨论连 续型动态规划。,一、多段决策问题 动态规划是解决多段决策过程优化问题的一 种强有力的工具。所谓多段决策过程，是指把一 个过程按时间或空间顺序分为若干段，然后给每 一步作出“决策”(或控制)，以使整个过程取得最优 的效果。,如图1所示，对于中间的任意一段，例如第k+1 段作出相应的“决策”(或控制)uk后，才能确定该段输 入状态与输出状态间的关系，即从xk变化到xk+1的状 态转移规律。在选择好每一段的“决策”(或控制) uk 以后，那么整个过程的状态转移规律从x0经xk一直到 xN也就被完全确定。全部“决策”的总体，称为“策 略”。,当然，如果对每一段的决策都是按照使某种性 能指标为最优的原则作出的，那么这就是一个多段 最优决策过程。,图1 多段决策过程示意图,容易理解，在多段决策过程中，每一段(如第 k+1段)的输出状态(xk+1)都仅仅与该段的决策(uk)及 该段的初始状态(xk)有关。而与其前面各段的决策 及状态的转移规律无关。这种性质称为无后效性。 下面以最优路线问题为例，来讨论动态规划求 解多段决策问题。,设汽车从A城出发到B城，途中需穿越三条河 流，它们各有两座桥P、Q可供选择通过，如图2所 示。各段间的行车时间(或里程、费用等)已标注在 相应段旁。问题是要确定一条最优行驶路线，使从 A城出发到B城的行车时间最短。,现将A到B分成四段，每一段都要作一最优决策，使总过程时间为最短。所以这是一个多段最优决策问题。 由图2可知，所有可能的行车路线共有8条。如果将各条路线所需的时间都一一计算出来，并作一比较，便可求得最优路线是AQ1P2Q3B，历时12。这种一一计算的方法称为穷举算法。这种方法计算量大，如本例就要做323=24次加法和7次比较。如果决策一个n段过程，则共需(n-1)2n-1次加法和(2n-1-1)次比较。可见随着段数的增多，计算量将急剧增加。,应用动态规划法可使计算量减少许多。动态规 划法遵循一个最优化原则：即所选择的最优路线必 须保证其后部子路线是最优的。 例如在图2中，如果AQ1P2Q3B是最优路线，那么 从这条路线上任一中间点到终点之间的一段路线必 定也是最优的。否则AQ1P2Q3B就不能是最优路线 了。,根据这一原则，求解最优路线问题，最好的办 法就是从终点开始，按时间最短为目标，逐段向前 逆推。依次计算出各站至终点之间的时间最优值， 并据此决策出每一站的最优路线。如在图2中，从终 点B开始逆推。,最后一段(第四段)：终点B的前站是P3或Q3，不 论汽车先从哪一站始发，行驶路线如何，在这最后 一段，总不外乎是从P3到B，历时为4，或从Q3到B， 历时为2，将其标明在图3中相应的圆圈内。比较P3与 Q3这一最后一段最优决策为Q3B。,最后一段(第四段)：终点B的前站是P3或Q3，不 论汽车先从哪一站始发，行驶路线如何，在这最后 一段，总不外乎是从P3到B，历时为4，或从Q3到B， 历时为2，将其标明在图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，标注在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，历时为 13，取最短历时8，标注在Q1旁。比较P1与Q1的 最优值，可知这一段的最优路线是Q1P2Q3B。,第一段：P1、Q1的前站是始发站A。显见从 A到B的最优值为12，故得最优路线为AQ1P2Q3B。,综上可见，动态规划法的特点是： 1) 与穷举算法相比，可使计算量大大减少。如 上述最优路线问题，用动态规划法只须做10次 加法和6次比较。如果过程为n段，则需做加 法。以上例为例，用穷举法需作4608次加法， 而后者只需做34次加法。,2) 最优路线的整体决策是从终点开始，采用逆推方法，通过计算、比较各段性能指标，逐段决策逐步延伸完成的。 全部最优路线的形成过程已充分表达在图3中。 从最后一段开始，通过比较P3、Q3，得到Q3B； 倒数第二段，通过比较P2、Q2，得到P2Q3B； 倒数第三段，通过比较P1、Q1，得到最优决策为Q1P2Q3B； 直至最后形成最优路线AQ1P2Q3B。 象这样将一个多段决策问题转化为多个单段决策的简单问题来处理，正是动态规划法的重要特点之一。,3) 动态规划法体现了多段最优决策的一个重要 规律，即所谓最优性原理。它是动态规划的理 论基础。,对图4所示的N段决策过程，如果在第k+1段处把全 过程看成前k段子过程和后N-k段子过程两部分。对于后 部子过程来说，xk可看作是由x0及前k段初始决策(或控 制) u0,u1, uk-1所形成的初始状态。那么，多段决策的 最优决策略具有这样的性质：不论初始状态和初始决策 如何，其余(后段)决策(或控制)对于由初始决策所形成的 状态来说，必定也是一个最优策略。这个性质称为最优 性原理。,图4 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)的轨线就不是最优的，这 与假设矛盾。因此，最优性原理成立。,应用最优性原理可以将一个N段最优决策问题转 化为N个一段最优决策问题，从而大大减少求解最优 决策问题的计算量。,图5 连续系统的状态转移过程,图5 连续系统的状态转移过程,二、连续系统的动态规划 利用动态规划最优性原理，可以推导出性能 泛函为极小应满足的条件哈密尔顿雅可比 方程。它是动态规划的连续形式，解此方程可求 得最优控制u*(t)。现在来推导这一方程。,设连续方程为,(1),终端约束,使性能泛函,求最优控制u*(t)， 或u任意。,初始状态,(2),(3),(4),根据最优性原理，如果x*(t)是以x(t0)为初始 状态的最优轨线。如图6所示。,图6 连续系统最优轨线,(5),设t = t ( t0 t tf)时，状态为x(t)，它将轨线分成前后两半断。那么以x(t)为初始状态的后半段也必是最优轨线。而与系统先前如何到达x(t)无关。 若取t0= t, t= t + t，式(4)可写成,根据最优性原理，如果t到tf的过程是最优的， 则从t + t到tf的后部子过程也是最优的，其中 t t + t tf。因此可写成,(6),(7),当t很小时，有,式(5)可近似表示为,(8),(5),将x(t + t)进行泰勒展开，取一次近似，有,(9),(10),(11),将上式在x,t领域展成泰勒级数，考虑到 J*x+x, t+t既是x的函数，也与t有关，所以,(12),(8),代入式(8)，得,(13),(12),(8),考察上式因为J*x, t与u无关，故J*x, t与,可提到min号外面。经整理可得,式(14)称为连续系统动态规划基本方程或贝尔曼方程。,(14),贝尔曼方程。它是一个关于J*x, t的偏微分 方程。解此方程可求得最优控制使J为极小。它 的边界条件为,(15),(14),如果令哈密尔顿函数为,式中,则式(14)可写成,(17),(16),当控制矢量u(t)不受限制时，则有,上两式称为哈密尔顿雅可比方程。上式说明， 在最优轨线上，最优控制必须使H达全局最小。 实际上这就是极小值原理的另一种形式。,(18),由贝尔曼方程可推导出协态方程和横截条件。 式(14)可写成,对x求偏导数，得,(20),(19),(14),由于对t的 全导数，为,(22),(21),代入式(20)可写成,(20),令 ，则上式可写成,(23),这就是所求的协态方程 ，与以前结果 完全一致。,(22),在t= tf时，在终端处性能泛函为,式中与N同维的乘子矢量。,(24),对x(tf)求偏导数，得,(25),(26),即,(24),将式(24)对tf求偏导数，得,(27),(24),考虑式(17)、式(20)得,上述结果与极小值原理中推导的完全一致。 上述推导过程实际上等于用动态规划方法间接证 明了极小值原理。,(28),(17),(20),(27),应当指出，与极小值原理相比，动态规划法需 要解偏微分方程式(14)，它要求J x, t具有连续的 偏导数，但在实际工程中，这一点常常不能满足， 因而限制了动态规划法的使用范围。,例1：设 ，求最优控制u*(t)使,解：构造哈密尔顿函数,根据哈密尔顿雅可比方程，有,考虑控制u不受限制，得,故,边界条件，因x(tf), tf=0，故Jx(tf)=0 如果令 ，则得,这正是应用极小值原理所得的结果，二者 完全一致。,例2：设受控系统状态方程为,初始状态为,性能泛函为,试求在u无限制情况下，使J取极小时的最优控制。,解：构造哈密尔顿函数,由哈密尔顿雅可比方程,因u无限制，可从,求得,代入上式，并注意到J*与t无关，因而 ， 有,为求解此偏微分方程，设其解为,满足方程，得,各项系数为,可得,解为,最优控制,最优控制可由状态反馈实现，如图7所示。,进一步考察系统的状态轨线。系统的状态方程,为齐次方程。,它的解为,于是最优控制为,性能泛函最优值为,例3：设受控系统的微分方程为,使性能指标,即要求快速响应，求最优控制u*，且满足 。,解：若选,，可得系统的状态方程,根据哈密尔顿贝尔曼方程,为使,取全局最小，可得,在所论情况下，因J*与t无关，故哈密尔顿贝 尔曼方程为,这是一个非线性偏微分方程，需借助电子计算 机求解J*，再求J*对x2的偏导数便可求得最优控制。,综上所述，可将连续型动态规划求解最优控制 问题的