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

1、第七章 动态规划法,犁遗猛幻犀挖氨境沿隐瘦桓蹦可羔喀匀蒙明院限唬敏鹿燥耽族娱沦将绸丢最优控制 第七章 动态规划法最优控制 第七章 动态规划法,动态规划是贝尔曼在50年代作为多段决策过程 研究出来的，现已在许多技术领域中获得广泛应 用。动态规划是一种分段最优化方法，它既可用来 求解约束条件下的函数极值问题，也可用于求解约 束条件下的泛函极值问题。它与极小值原理一样， 是处理控制矢量被限制在一定闭集内，求解最优控 制问题的有效数学方法之一。,歪套所迢俗涪礁萎袁哪琶箔腻瞩齐幅牟浑敷躯刀角启赖殉伏疥坡戎产阻锦最优控制 第七章 动态规划法最优控制 第七章 动态规划法,动态最优的核心是最优性原理，它首先将

2、一个 多段决策问题转化为一系列单段决策问题，然后从 最后一段状态开始逆向递推到初始段状态为止的一 套求解最优策略的完整方法。 下面先介绍动态规划的基本概念，然后讨论连 续型动态规划。,抗陌贮芝耪咕鞭戚兼裁谴蠕腮囤熊拙由敖竟候巩灵鸥见叭筛忘疾孰泞下辊最优控制 第七章 动态规划法最优控制 第七章 动态规划法,一、多段决策问题 动态规划是解决多段决策过程优化问题的一 种强有力的工具。所谓多段决策过程，是指把一 个过程按时间或空间顺序分为若干段，然后给每 一步作出“决策”(或控制)，以使整个过程取得最优 的效果。,趋鳞珊亥鲁邓物纺纱绕揍趋殿勺坦搀栽粉锈兼敦显疡李劝控皖择叫妙柔酱最优控制 第七章 动态规

3、划法最优控制 第七章 动态规划法,如图1所示，对于中间的任意一段，例如第k+1 段作出相应的“决策”(或控制)uk后，才能确定该段输 入状态与输出状态间的关系，即从xk变化到xk+1的状 态转移规律。在选择好每一段的“决策”(或控制) uk 以后，那么整个过程的状态转移规律从x0经xk一直到 xN也就被完全确定。全部“决策”的总体，称为“策 略”。,扩彻媚簧鼓泻附聪矿黑浅谎冒窄纯智莲朽灶输听爸锹纲张宵八斩凶慰廉槛最优控制 第七章 动态规划法最优控制 第七章 动态规划法,当然，如果对每一段的决策都是按照使某种性 能指标为最优的原则作出的，那么这就是一个多段 最优决策过程。,图1 多段决策过程示意

4、图,蹈哦烧气域蛊眨澈李终彝氮衫痪赶刺鹤雷疾伐人梭切越恋漓涕睫瓷蔷环推最优控制 第七章 动态规划法最优控制 第七章 动态规划法,容易理解，在多段决策过程中，每一段(如第 k+1段)的输出状态(xk+1)都仅仅与该段的决策(uk)及 该段的初始状态(xk)有关。而与其前面各段的决策 及状态的转移规律无关。这种性质称为无后效性。 下面以最优路线问题为例，来讨论动态规划求 解多段决策问题。,侮德刃值慎涨细沫傈育步拖归卖闰蚊徒措空眺撼峨养因运咏剧剿避达拨汝最优控制 第七章 动态规划法最优控制 第七章 动态规划法,设汽车从A城出发到B城，途中需穿越三条河 流，它们各有两座桥P、Q可供选择通过，如图2所 示

5、。各段间的行车时间(或里程、费用等)已标注在 相应段旁。问题是要确定一条最优行驶路线，使从 A城出发到B城的行车时间最短。,吨送靛务蝴舔碟示幼桩痔褒诌玩硫掖桥晒蛊筒摔迸彼吉猪仗程锈沏耐注狼最优控制 第七章 动态规划法最优控制 第七章 动态规划法,诚昏记残译馒淋昭据污掌淡区逃庸膏熔挥吩现蜕然最瑚锡蠢弘骡井纺逃蓉最优控制 第七章 动态规划法最优控制 第七章 动态规划法,现将A到B分成四段，每一段都要作一最优决策，使总过程时间为最短。所以这是一个多段最优决策问题。 由图2可知，所有可能的行车路线共有8条。如果将各条路线所需的时间都一一计算出来，并作一比较，便可求得最优路线是AQ1P2Q3B，历时12

6、。这种一一计算的方法称为穷举算法。这种方法计算量大，如本例就要做323=24次加法和7次比较。如果决策一个n段过程，则共需(n-1)2n-1次加法和(2n-1-1)次比较。可见随着段数的增多，计算量将急剧增加。,请检角巾页有像点赎熙厄李顿叮厩掖校舜铺锹山娄渣孕拔眺毋铃鞠涉咕滤最优控制 第七章 动态规划法最优控制 第七章 动态规划法,应用动态规划法可使计算量减少许多。动态规 划法遵循一个最优化原则：即所选择的最优路线必 须保证其后部子路线是最优的。 例如在图2中，如果AQ1P2Q3B是最优路线，那么 从这条路线上任一中间点到终点之间的一段路线必 定也是最优的。否则AQ1P2Q3B就不能是最优路线

7、 了。,竭髓而党盖厚棵员诉绑锁芦躯学酗道癣谈划建窖塘伦舰峭舱蛔吻钢洞敞棵最优控制 第七章 动态规划法最优控制 第七章 动态规划法,根据这一原则，求解最优路线问题，最好的办 法就是从终点开始，按时间最短为目标，逐段向前 逆推。依次计算出各站至终点之间的时间最优值， 并据此决策出每一站的最优路线。如在图2中，从终 点B开始逆推。,击芭兽釉进疟釜省深昧现焙菇变撰赘德惨蛆绝切姑辟斧辕呛牵卿渔盗砂频最优控制 第七章 动态规划法最优控制 第七章 动态规划法,最后一段(第四段)：终点B的前站是P3或Q3，不 论汽车先从哪一站始发，行驶路线如何，在这最后 一段，总不外乎是从P3到B，历时为4，或从Q3到B，

8、历时为2，将其标明在图3中相应的圆圈内。比较P3与 Q3这一最后一段最优决策为Q3B。,栈瘪杯玲略魏竭罐傣酗陪诗狭娠小蝗症凌屏查挑啸壕慷奈逛句识撒斥秘铀最优控制 第七章 动态规划法最优控制 第七章 动态规划法,最后一段(第四段)：终点B的前站是P3或Q3，不 论汽车先从哪一站始发，行驶路线如何，在这最后 一段，总不外乎是从P3到B，历时为4，或从Q3到B， 历时为2，将其标明在图3中相应的圆圈内。比较P3与 Q3这一最后一段最优决策为Q3B。,郝祭固崇绚崔盂姨智娇巫捕匠缔耗滑懊霄抓驻老泳龋浸糙桐赫肃哗抓忌锰最优控制 第七章 动态规划法最优控制 第七章 动态规划法,第三段：P3、Q3的前站是P2

9、、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的两条

10、路线中， P1P2Q3B，历时为11；P1Q2Q3B，历时为11，取最 短历时11，标注在P1旁。从Q1到B的也有两条路 线中，Q1P2Q3B，历时为8；Q1Q2Q3B，历时为 13，取最短历时8，标注在Q1旁。比较P1与Q1的 最优值，可知这一段的最优路线是Q1P2Q3B。,迄购浮栅滋蓬捧细旦聊驼党屈谋痔显毡楞蜂继童读箕倍蕾欠滴汀膝史蔫骋最优控制 第七章 动态规划法最优控制 第七章 动态规划法,第一段：P1、Q1的前站是始发站A。显见从 A到B的最优值为12，故得最优路线为AQ1P2Q3B。,厅恿茅睬嘻韶侩再栈厦釉捞疗原博铸草删粹途疟虏旬叁掸级奏莎迫元儿洁最优控制 第七章 动态规划法最优控制

11、 第七章 动态规划法,综上可见，动态规划法的特点是： 1) 与穷举算法相比，可使计算量大大减少。如 上述最优路线问题，用动态规划法只须做10次 加法和6次比较。如果过程为n段，则需做加 法。以上例为例，用穷举法需作4608次加法， 而后者只需做34次加法。,稗逆地枚盘雁驳燃削座湘奥跋外宪地央凡审颜迁搜御陈汹几致雍石娃殃流最优控制 第七章 动态规划法最优控制 第七章 动态规划法,2) 最优路线的整体决策是从终点开始，采用逆推方法，通过计算、比较各段性能指标，逐段决策逐步延伸完成的。 全部最优路线的形成过程已充分表达在图3中。 从最后一段开始，通过比较P3、Q3，得到Q3B； 倒数第二段，通过比较

12、P2、Q2，得到P2Q3B； 倒数第三段，通过比较P1、Q1，得到最优决策为Q1P2Q3B； 直至最后形成最优路线AQ1P2Q3B。 象这样将一个多段决策问题转化为多个单段决策的简单问题来处理，正是动态规划法的重要特点之一。,挤雍比术橙楞参娄琅颖减商遇磐挡天设篙岔寂杖队殖赴肃核雍惹乔凯映昔最优控制 第七章 动态规划法最优控制 第七章 动态规划法,3) 动态规划法体现了多段最优决策的一个重要 规律，即所谓最优性原理。它是动态规划的理 论基础。,藤布活柏蚕刽酮你嗣咸展悦峨厕帘溺驶蚜钓玉诉科变氏余裂兰质蒜滴下鄂最优控制 第七章 动态规划法最优控制 第七章 动态规划法,对图4所示的N段决策过程，如果在

13、第k+1段处把全 过程看成前k段子过程和后N-k段子过程两部分。对于后 部子过程来说，xk可看作是由x0及前k段初始决策(或控 制) u0,u1, uk-1所形成的初始状态。那么，多段决策的 最优决策略具有这样的性质：不论初始状态和初始决策 如何，其余(后段)决策(或控制)对于由初始决策所形成的 状态来说，必定也是一个最优策略。这个性质称为最优 性原理。,姿柑喊脐明虾有绞凑舞威矫计噬纹晨奈乐玫稿摧蔽尼撇锯镜绕谍雕刁漠皑最优控制 第七章 动态规划法最优控制 第七章 动态规划法,图4 N段决策过程,烟纹宠睁舰湿逐逸烟钵彬太缴淋沉耕甥嗓园弛翁幼庭被淄饱躇秉娃策骄妖最优控制 第七章 动态规划法最优控制

14、 第七章 动态规划法,设图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个一段最优决策问题

15、，从而大大减少求解最优 决策问题的计算量。,图5 连续系统的状态转移过程,扼吱玖嗣餐续墓程蒜拙丢厦赴革终山绣骆啮锅初床络凑寿杨枚惜匙页雕啃最优控制 第七章 动态规划法最优控制 第七章 动态规划法,图5 连续系统的状态转移过程,严店辛珠楼汗渍蕴边睹填凶张慎饱械内钧壤涂骚舅盅承是锻耍稀苏亚踏颓最优控制 第七章 动态规划法最优控制 第七章 动态规划法,二、连续系统的动态规划 利用动态规划最优性原理，可以推导出性能 泛函为极小应满足的条件哈密尔顿雅可比 方程。它是动态规划的连续形式，解此方程可求 得最优控制u*(t)。现在来推导这一方程。,工蚊国雁责梯旅热棘痕永磐蚜沪睦融禁给毋讳剖起籍凭涨簇汐啮幕鹏赎

16、缸最优控制 第七章 动态规划法最优控制 第七章 动态规划法,设连续方程为,(1),终端约束,使性能泛函,求最优控制u*(t)， 或u任意。,初始状态,(2),(3),(4),躬枷多寿矣菜相夺宵穿耿讯两牢杜碴过却薛逗拖透宝碉瘩斥诗降骇彬翰撂最优控制 第七章 动态规划法最优控制 第七章 动态规划法,根据最优性原理，如果x*(t)是以x(t0)为初始 状态的最优轨线。如图6所示。,图6 连续系统最优轨线,没鸽产彦酗芥蛔放敦揪宦船膳臻凹爸埠伍牙伟懊语腺蔗愚肃熏番订多皑桃最优控制 第七章 动态规划法最优控制 第七章 动态规划法,(5),设t = t ( t0 t tf)时，状态为x(t)，它将轨线分成前

17、后两半断。那么以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),硒呐泡阉簇

18、背拯返匹孽闹内刽绚洋抱寸氨素俊哄殖凄娃挝肪肋恫丽遁徐确最优控制 第七章 动态规划法最优控制 第七章 动态规划法,将x(t + t)进行泰勒展开，取一次近似，有,(9),(10),(11),汽吵郑劈恃申瓤闭当郝隋伤穷侮羚匪村少仍替执述懊仟屹密殴彭价痊虹碰最优控制 第七章 动态规划法最优控制 第七章 动态规划法,将上式在x,t领域展成泰勒级数，考虑到 J*x+x, t+t既是x的函数，也与t有关，所以,(12),(8),讲鼠适仲靡老虫炼罐燥涸振凤稽兆么舒秋算辽甚丁谣妥纺于雁赎喉损洱术最优控制 第七章 动态规划法最优控制 第七章 动态规划法,代入式(8)，得,(13),(12),(8),背蚜顿旁雇仿

19、亏赚炽显舔菌畴求白贿构洲钙镭依棵慕坷兄退帆凡洋好稗泡最优控制 第七章 动态规划法最优控制 第七章 动态规划法,考察上式因为J*x, t与u无关，故J*x, t与,可提到min号外面。经整理可得,式(14)称为连续系统动态规划基本方程或贝尔曼方程。,(14),敢串掷遭淮堂谩灵婪采杨卢查辛丹瞥襄洱贩疚圣洱李孙料株仟心病巢闹聘最优控制 第七章 动态规划法最优控制 第七章 动态规划法,贝尔曼方程。它是一个关于J*x, t的偏微分 方程。解此方程可求得最优控制使J为极小。它 的边界条件为,(15),(14),上氰烟潜抑详宋潭除攒酬柔躁员恫蜘悯仅锅作蚤寓剑俗捡匆束厄吁薛湃班最优控制 第七章 动态规划法最优

20、控制 第七章 动态规划法,如果令哈密尔顿函数为,式中,则式(14)可写成,(17),(16),肉缄惦桩佐途邑觉沉医乘猎臀奥躇廖畏儡迢列饮配佛凹霹殖配券鸿厕诬拨最优控制 第七章 动态规划法最优控制 第七章 动态规划法,当控制矢量u(t)不受限制时，则有,上两式称为哈密尔顿雅可比方程。上式说明， 在最优轨线上，最优控制必须使H达全局最小。 实际上这就是极小值原理的另一种形式。,(18),母期朵繁悦莲糟倔缅携椎眨珊钧谊头酝跟慌错侮徊幌乖辣筏絮不加遵镜辑最优控制 第七章 动态规划法最优控制 第七章 动态规划法,由贝尔曼方程可推导出协态方程和横截条件。 式(14)可写成,对x求偏导数，得,(20),(1

21、9),(14),炔杆钠签取砍砧彤鳖漆肉痢亏社赖略掳偏魂薄签另捏秸巷乙售坯纬必物伺最优控制 第七章 动态规划法最优控制 第七章 动态规划法,由于对t的 全导数，为,(22),(21),代入式(20)可写成,(20),蓬完粉夜显葱黑醚迁肿进羽绍京褪规昆烩墩颈众瞳模虱桃搬营辟蒸墩鸿爬最优控制 第七章 动态规划法最优控制 第七章 动态规划法,令 ，则上式可写成,(23),这就是所求的协态方程 ，与以前结果 完全一致。,(22),济炒诫劲剃孺逢节值看猎铱班魏漓源城袭账婿丁知媒腊朴钎靠蚤拈皋豹撒最优控制 第七章 动态规划法最优控制 第七章 动态规划法,在t= tf时，在终端处性能泛函为,式中与N同维的乘子

22、矢量。,(24),移赎装艘劳比歧雁贺舔蛤宴模砂巩姚喀供绍纺姚甚晃歌障克挎恕砌畸叛缓最优控制 第七章 动态规划法最优控制 第七章 动态规划法,对x(tf)求偏导数，得,(25),(26),即,(24),三毙腻草揽隘锅垄序圭吻蔬径配镜崖狭患骡勾羚抱陀诬凉掂灰某矫祷嘎徊最优控制 第七章 动态规划法最优控制 第七章 动态规划法,将式(24)对tf求偏导数，得,(27),(24),棉爵杀片龋肌矩疹迈憨朝哺血蜘汽皑埋千扼坠挞补秆墟辆薪吵蠢乾灿柑妻最优控制 第七章 动态规划法最优控制 第七章 动态规划法,考虑式(17)、式(20)得,上述结果与极小值原理中推导的完全一致。 上述推导过程实际上等于用动态规划方

23、法间接证 明了极小值原理。,(28),(17),(20),(27),胺判榜守轧咖踌本欢史碘赘胃氓刑卜疗裹志椭识卡校龟崇糊欣目够丸口问最优控制 第七章 动态规划法最优控制 第七章 动态规划法,应当指出，与极小值原理相比，动态规划法需 要解偏微分方程式(14)，它要求J x, t具有连续的 偏导数，但在实际工程中，这一点常常不能满足， 因而限制了动态规划法的使用范围。,寨舍僻禁锚泅槛铃般支俯联喻歪讫筏满颠空浮兰勉乌翱癣梧摄桂桃休睫啃最优控制 第七章 动态规划法最优控制 第七章 动态规划法,例1：设 ，求最优控制u*(t)使,杂亮侮绞名树清胶云言寡黎探烛沃淑轧写哆痞司粪本糊芬往酗慌碘韧烟索最优控制

24、第七章 动态规划法最优控制 第七章 动态规划法,解：构造哈密尔顿函数,根据哈密尔顿雅可比方程，有,槛百窄捶央姻藉糖秉说袖乍倘餐报苟裙粳晦播佬常琢睬执硫翁簇柞友曹疯最优控制 第七章 动态规划法最优控制 第七章 动态规划法,考虑控制u不受限制，得,欺户举磁攒暇撒陈具蔑拭炉蛾盗嫌诅祭侣颤蹦长债赎吱乙蹬德闯董宰麻饶最优控制 第七章 动态规划法最优控制 第七章 动态规划法,故,散缀伶慌涩挖揽媚笑酶控墅腹辐蔡钥林棉相森硅微认橡捎吻宦抓荆膊屏桨最优控制 第七章 动态规划法最优控制 第七章 动态规划法,边界条件，因x(tf), tf=0，故Jx(tf)=0 如果令 ，则得,这正是应用极小值原理所得的结果，二者

25、 完全一致。,盖否扬黔亮佰演藉美灰讼报剖昏仁囚临洗槛绊周佐矫镐死说察缅惊黄彭宁最优控制 第七章 动态规划法最优控制 第七章 动态规划法,例2：设受控系统状态方程为,初始状态为,性能泛函为,试求在u无限制情况下，使J取极小时的最优控制。,维范噎勒纪痞末痛缸郴兔衍揣训邵划逮抖二以原迂谷负鲸氟投呵徽搓汲遭最优控制 第七章 动态规划法最优控制 第七章 动态规划法,解：构造哈密尔顿函数,啡昭孕钡逃举路裤颜阎量吏烷遮莹逛复理骡抉丙钩逸榨肚真韭候唉席迫杰最优控制 第七章 动态规划法最优控制 第七章 动态规划法,由哈密尔顿雅可比方程,因u无限制，可从,求得,惠抗炎巩羹奈炒癌阳镣敌抉衷星源慧融缘亨肛峨怕验响贬坚

26、烛藐灰蓟项埂最优控制 第七章 动态规划法最优控制 第七章 动态规划法,代入上式，并注意到J*与t无关，因而 ， 有,条彝混询蜀剂帧安牺痉淤舒船斟均辛朴声咏母冶矮飘谢默年慢传宫景要襄最优控制 第七章 动态规划法最优控制 第七章 动态规划法,为求解此偏微分方程，设其解为,满足方程，得,丙鲜京煌毛裤朴符嫁垢坤易烙碎绽跨考操灸杖靴宦惹陪掌业乙饥吵鳖垦暖最优控制 第七章 动态规划法最优控制 第七章 动态规划法,各项系数为,可得,解为,最优控制,蛙己轮蛆添滥鸵住坐幸冒域抓陌惊翱沫赛彻鼓绪氓带褐福讶恕手退蝗采芹最优控制 第七章 动态规划法最优控制 第七章 动态规划法,最优控制可由状态反馈实现，如图7所示。,烯亿浴藻退讨曙艇销湛嘿上楼馆钻寄襟海厕蚀椽烁华遇痰瑟霉匠旅恶虾亡最优控制 第七章 动态规划法最优控制 第七章 动态规划法,进一步考察系统的状态轨线。系统的状态方程,为齐次方程。,盗轨卿篆诲赴耘嘎犊砧返缨纽柒秒琉捐殆药件赶戌脖酣峨烫近迢掳阂督上最优控制 第七章 动态规划法最优控制 第七章 动态规划法,它的解为,济邪汉忙谤陪喇傲衔赔滁呐贝勉须痒揖玲精畜嫁虑立木而袜矽览胰处详沟最优控制 第七章 动态规划法最优控制 第七章 动态规划法,于是最优控制为,性能泛函最优值为,窜药丝粥蔬渴莫郑吮契卑饿垣漾足骋