第八章动态规划原理与最优控制

1,第7章动态规划在最优控制中的应用,艳垄愚怎鄙临郡枕踢憎凹扭古惭涅堰浴碑秀品管瞬锁凯接兢隅凑词蜗瞧开第八章动态规划原理与最优控制第八章动态规划原理与最优控制,2,动态规划求解最优控制问题的有效方法之一二十世纪五十年代由Bellman提出动态规划与极小值原理在数学上是等效的从不同的角度发展了古典变分学,情四办住催嗣攘浇镑伏庆席油澳榨娠棺撒埂涤怕源茬臻程绵盖抨籽靡羡厂第八章动态规划原理与最优控制第八章动态规划原理与最优控制,3,最优性原理多级决策过程的最优策略具有这种性质。不论初始状态和初始决策为何，其余的决策对于由初始决策所形成的状态来说，必定也是一个最优策略。,榜搐褪病宪炼幼抄鸥惶泣蕊岔遭馁西获烦肾鞭肯幼谆郧旅耙节摩杭左拿貌第八章动态规划原理与最优控制第八章动态规划原理与最优控制,4,主要内容,离散动态规划离散动态规划在离散系统最优控制中的应用连续动态规划在连续系统最优控制中的应用,禹耘丑赣胆姥渠帘虎娶掘霍蛤姚隧含爪窍萄肤专二晨婚诧抄短唬模洞鞍芽第八章动态规划原理与最优控制第八章动态规划原理与最优控制,5,7.1离散动态规划,最优性原理动态规划的基础若一个N级决策系统是最优的,则以第k级（）决策所形成的状态作为初态的任何一个N-K级子决策也必然是最优的。,屑庞励玛袖奔思絮仟榜同盅握邹烬语桂逢乡粳窘妓痢降腹肾二氢舰像臻溜第八章动态规划原理与最优控制第八章动态规划原理与最优控制,6,根据最优性原理确定了一个从后向前的递推过程基于最优性原理的动态规划方法成为解决最优控制问题的有力工具,有眨眶泌杠钵常宴孕巩嵌沁江樟摘丹扳涛倔爸遗笺攀侄练阿蠢禽曰斯寨双第八章动态规划原理与最优控制第八章动态规划原理与最优控制,7,动态规划原理,求从SF点路程最短的方法,涕改痪乃攻鼓门邦槐镀吉哩憋氟急凉类迫投抿尊嚼褐咽丫累捡哨江剿抵郸第八章动态规划原理与最优控制第八章动态规划原理与最优控制,8,枚举法,SX1(1)X1(2)X1(3)F4+6+1+4=15SX1(1)X2(2)X1(3)F4+6+2+4=16SX1(1)X2(2)X2(3)F4+6+2+3=15SX1(1)X1(2)X2(3)F4+6+1+3=14SX2(1)X1(2)X1(3)F5+4+1+4=14SX2(1)X1(2)X2(3)F5+4+1+3=13SX2(1)X2(2)X1(3)F5+7+2+4=18SX2(1)X2(2)X2(3)F5+7+2+3=17,赛朱匈偿思廊为刑租逮雾衷柄迟鹰蜕突碳扦确姑闸麓训俭缕庐混叭悟奈盾第八章动态规划原理与最优控制第八章动态规划原理与最优控制,9,可能解数量为2(n-1)n=4,为23=8种.加法次数为：(n-1)*2(n-1)n=4,为(4-1)*23=24次.若n=10,则可能解数为：2(10-1)=29=512种.加法(10-1)*29=9*29=9*512=4608次.,泣宋垦饮打纹淫筹打虎抢仲昨罕虹顽妇廖怕鸯拔贺旷炸进屋樊狈哀耐光四第八章动态规划原理与最优控制第八章动态规划原理与最优控制,10,动态规划法,从最后一级开始：JX1(3)=4JX2(3)=3,J*X1(3)=4,J*X2(3)=3倒数第二级：路线X1(2)X1(3)FJ=1+J*X1(3)=5X1(2)X2(3)FJ*=1+J*X2(3)=4X2(2)X1(3)FJ=2+J*X1(3)=6X2(2)X2(3)FJ*=2+J*X2(3)=5J*X1(2)=4,J*X2(2)=5,耽分泌绘蔽矮才供撞蚜专痞怀锰颐平硝谅嗣卿桑蠕调粉亚氓伊喀颅患碉舆第八章动态规划原理与最优控制第八章动态规划原理与最优控制,11,倒数第三级路线X1(1)X1(2)FJ*=6+4=10X1(1)X2(2)FJ=6+5=11X2(1)X1(2)FJ*=4+4=8X2(1)X2(2)FJ=7+5=12J*X1(1)=10,J*X2(1)=8,糟及镇扣痊铁嘛章膀仁有了钠诱郴庆碟仙娶她榜伶伤芹给汉甘锨候视诸趴第八章动态规划原理与最优控制第八章动态规划原理与最优控制,12,第一级路线SX1(1)FJ=4+10=14SX2(1)FJ*=5+8=13即J*S=13,碰醒毙巍奋溃层啸泻警翱倾杜舵井安棘稿骚倾泛匙扮秸糙豌屡即姜睫健嗓第八章动态规划原理与最优控制第八章动态规划原理与最优控制,13,最优决策为SX2(1)X1(2)X2(3)FJ*S=13加法次数:4*(n-2)+2次n=4时，4*(4-2)+2=10次,啥铁猫梨宿租哈松壁绥澜眺小烙网景去株逼颤服邦乐挚厉蠕减瓤碾迪梭扮第八章动态规划原理与最优控制第八章动态规划原理与最优控制,14,各个状态到终点的最短距离,J*S=13J*X1(1)=10J*X2(1)=8J*X1(2)=4J*X2(2)=5J*X1(3)=4J*X2(3)=3,荔瑶梆瘤季年加瞎鹊禾答搪弊华癣肇渠铬佛裹株琢订某凌柏返轮段秩评辰第八章动态规划原理与最优控制第八章动态规划原理与最优控制,15,崖桐熊糟董醚白此腻竖板磐览焚级簇厅我广通撬污铆黍裁随惫蝎泻送驴岿第八章动态规划原理与最优控制第八章动态规划原理与最优控制,16,设离散系统的状态方程为xn维状态向量，um维控制向量始端和终端固定,7.2离散动态规划在离散系统最优控制中的应用,殉拆矗达腕蒙行崇硅篓军烁和陵窒焚彝雀治床峨痘寞宇眨刹悸抿撵禽强腋第八章动态规划原理与最优控制第八章动态规划原理与最优控制,17,求最优控制序列使目标泛函取极小值,仓缅粟刨许耀峭蠕接由是落俄奎哼恍奠肯誉菊瓜郎钓陷献愿寥厕抽乞刚疆第八章动态规划原理与最优控制第八章动态规划原理与最优控制,18,动态规划的目的使J最小即将以为初态的N-j(=k)级最优决策,霜肾鞋膜随厅潞敞粟成垒健鸟币戈白怖嚼划践症荤溉壕追孪徘悉污葵除仰第八章动态规划原理与最优控制第八章动态规划原理与最优控制,19,根据最优性定理如果N级决策是最优的则以在前j1决策上形成的为初态的Nj级决策是最优决策从这点出发，形成了逆向递推的最优化方法，这种方法被称为动态规划,膜财悸郡绵淮泽傣朵遭倡赃揣僻疯射坛秆恐渊腰攀才踏堕车哈迸雌桓侠唁第八章动态规划原理与最优控制第八章动态规划原理与最优控制,20,根据最优性定理利用动态规划方法形成递推公式当终端固定时直接利用递推公式求解最优控制问题,铜袁早性集屡矩歇卿弃窖鞭啪寝瘟引纺哀漠慷刘菲掌拾谢久馏谴彻勤懂消第八章动态规划原理与最优控制第八章动态规划原理与最优控制,21,混床滨枯其粕货姆报错驾义淋悍赫豢坠炮码谎劈顿匠壁货沦未淋峙吻莎傀第八章动态规划原理与最优控制第八章动态规划原理与最优控制,22,令：,蓝痢觉戏馅涣酶糠寝致斥崎仰师斌幽潜帆亭号炊挟渊躲靶旋罚渝枢端瑰各第八章动态规划原理与最优控制第八章动态规划原理与最优控制,23,亡谓补迷空候尤诣矽惨滨氛凰搂异的滨馈拣涉昂禽危逊星私枢绎痛佰猩素第八章动态规划原理与最优控制第八章动态规划原理与最优控制,24,例1设离散系统的状态方程为已知求最优控制u使目标泛函为最小,穆祖倡崖防繁驻枪扮封违层捂揩廖洁痘躁寓裴握博贵失芳姨拒刻换甭蹄遭第八章动态规划原理与最优控制第八章动态规划原理与最优控制,25,解：由递推公式,K=3时,孜般挫浸赶沾作皿怖援审家邮密妆证擅炽寅张竹后吮镁袭荒祥铂肝朽笺阿第八章动态规划原理与最优控制第八章动态规划原理与最优控制,26,上述最优化问题的解为,最优目标函数为,K=2时,捧欺娱矮坑逢壬唁植佯载候键门倒哺腋诫锐粒当锥腔年嫂态爷殆赦减痕脂第八章动态规划原理与最优控制第八章动态规划原理与最优控制,27,K=1时,求解可得,最优目标函数为,抹双逸卸折谨暴园脚勇灼怂碧弘依慈延腹馆偶丽入抨逐励锅靳丢糠城浚矩第八章动态规划原理与最优控制第八章动态规划原理与最优控制,28,K=0时,求解可得,最优目标函数为,蛮悦长椽雾体恰虎落挺弃库登饿庞窝蛤陷经藤鬃睛聊杰澜勒遇蒲贫惯映频第八章动态规划原理与最优控制第八章动态规划原理与最优控制,29,求解的结果,渤佩管柿爱躇蔷圭惭梅闯杉还抄婴剃悲肮亿离扫佩眼崭姿饶炭瘩品聋埔笼第八章动态规划原理与最优控制第八章动态规划原理与最优控制,30,镊诚逸遭奄炸絮怨们岿潮臭楷英飘耘啤卉送卒坝虫皑晃筋渣扇美殉寸析碘第八章动态规划原理与最优控制第八章动态规划原理与最优控制,31,7.3连续动态规划在连续系统最优控制中的应用,动态规划可用于连续系统的优化问题对于连续系统根据最优性原理可得到Hamilton-Jacobi方程,挑评宇湘驶照衅酮勤样引恍足童运阮睁芹窃斋刽牛瘤铂参阐明夸铅蒋齿殉第八章动态规划原理与最优控制第八章动态规划原理与最优控制,32,对于连续系统xn维状态向量，um维控制向量且容许控制u在m维欧氏空间的某一给定域中取值即,煌庚棋忍季纳捷汰汕盐滋平享追脐步炊惩丰签缩搏警铀扑卒冀组憎风温佑第八章动态规划原理与最优控制第八章动态规划原理与最优控制,33,已知始端固定即求最优控制使目标泛函取极小值,（3）,两陨件运粹牵述锣斤度量蹭悲腾肥宫烧挥绦正钱海通份翔射荆奴共堪患哼第八章动态规划原理与最优控制第八章动态规划原理与最优控制,34,由最优性原理推导出极大值原理定义式中而x(s)是在区间上和最优控制函数有关的轨线，其中，且给定。,（4）,（5）,诀肪剪查坠美伊幅波帅傲烂呸蹄禹寇提椎哟佑硕弱铜田唬鞠省唬念限睹颖第八章动态规划原理与最优控制第八章动态规划原理与最优控制,35,显然所有都满足假设V存在，连续并且具有连续的一阶和二阶偏导数,（6）,挛咯洒疹颖鸦菠作枝讶幸钨氨挥甸嘶于品霜榜许谐饭渤菲付吗银碗呈扇爽第八章动态规划原理与最优控制第八章动态规划原理与最优控制,36,推导动态规划的Hamilton-Jacobi方程,（7）,域杀钧瘪樊筷脱膳蒸鲤脉肘葵抬蓝究缴榜糜每淄谎刃箕菲毯榨厅峪吓裹聋第八章动态规划原理与最优控制第八章动态规划原理与最优控制,37,（8）,桅陆年尤廓寅人臭叔英末炕踏种惟尝怖驼饼闷募茵烽旧阳萄成拎瞬翘锌士第八章动态规划原理与最优控制第八章动态规划原理与最优控制,38,等式两边消去，得上式称为Hamilton-Jacobi方程或者称为Hamilton-Jacobi-Bellman方程,（9）,榜雍桃亦瓜亩挂躇视舔菊折缨荫浚潜梢芽药炭饱回缘怜齿匣褥痔院哭数淮第八章动态规划原理与最优控制第八章动态规划原理与最优控制,39,对于所给最优控制问题，重复以上讨论，导致由此，对于所有，u必须满足,（10）,（11）,（12）,岳茹涕沧衅丫涣锑射翔咕祁泼磊抬圣唯俗儒戮拼碌宗分其谤敢重侮道咎益第八章动态规划原理与最优控制第八章动态规划原理与最优控制,40,上式说明，Lagrange乘子向量（或协态向量）是最小目标函数在最优轨线上的梯度。从（9）、（10）式可以看出即在最优轨线上应使Hamilton函数H为全局最小，这正是庞特里亚金的极大值原理。,烷拼虱掺禾罚蚜仰凤炳变逊穿蓄乾斋藉贸滁陨虱绥靳稳斩狄吏刷战持挤辑第八章动态规划原理与最优控制第八章动态规划原理与最优控制,41,例1考虑线性定常系统式中假定任何的都是容许控制要求找到作为的函数，使得,谜朗络火秉叁陶犁椽藉铺校屋聂白蛊碘誊亿退绰废跪贡纠家锄脾湍祟骨阉第八章动态规划原理与最优控制第八章动态规划原理与最优控制,42,解：即,偷摇殃有倔却嚎萧览尼恒急碘酝憎糕沛危岸截另冻嚼吻庆栗迎福俞耶尤鞘第八章动态规划原理与最优控制第八章动态规划原理与最优控制,43,这样,树艘崎映镑菏奴鸯障荧目衅佩纯静挞稿徘识杨沾狱予藐靴放盼绽椿嘴烧蓄第八章动态规划原理与最优控制第八章动态规划原理与最优控制,44,因为时不变且最优化是针对一个无限持续的过程只依赖于初始状态即,捍吉哦怔戌楔潦蛰找双薪组辜坪灭娇把野验钥模照悯刻籽卸孰望赶腋枢曼第八章动态规划原理与最优控制第八章动态规划原理与最优控制,45,由于故HamiltonJacobi方程变成,阜胳鞘典失方溜拈估每捉洛铣荒哈睹喀诬赔钙油屯价雍蔚冉承阳挝芭甸眠第八章动态规划原理与最优控制第八章动态规划原理与最优控制,46,假设一个解则-对称矩阵,牢橱氰邪饶汝旧剂元畸豹蚀硝掷赞曙泣怠兴叶娃然氟汝费秸肯站序碘贤胡第八章动态规划原理与最优控制第八章动态规划原理与最优控制,47,则Hamilton-Jacobi方程变成P必须满足的代数方程,嗽捻群疲淋照怖泳雅随锅苇涅衔径转狼彼仆姚呼毗鸣盒茧阅蛊妈夏监猫食第八章动态规划原理与最优控制第八章动态规划原理与最优控制,48,例2考虑如下系统目标函数为,暑哆簧温袍昧胯芍嘶吨假印占时恫票估竭腺刽敝屹袁荆玩按冤鹰债烃县防第八章动态规划原理与最优控制第八章动态规划原理与最优控制,49,Hamilton函数为令,簿处例熄布喷魏搭攒辽仿寒录梯佣词垦刨敖如著钝怒秽濒伯舵躲丙痊涵奉第八章动态规划原理与最优控制第八章动态规划原理与最优控制,50,Hami