最優(yōu)控制第七章動態(tài)規(guī)劃法

最優(yōu)控制第七章動態(tài)規(guī)劃法第1頁，共68頁，2023年，2月20日，星期六動態(tài)規(guī)劃是貝爾曼在50年代作為多段決策過程研究出來的，現(xiàn)已在許多技術(shù)領(lǐng)域中獲得廣泛應(yīng)用。動態(tài)規(guī)劃是一種分段最優(yōu)化方法，它既可用來求解約束條件下的函數(shù)極值問題，也可用于求解約束條件下的泛函極值問題。它與極小值原理一樣，是處理控制矢量被限制在一定閉集內(nèi)，求解最優(yōu)控制問題的有效數(shù)學方法之一。第2頁，共68頁，2023年，2月20日，星期六動態(tài)最優(yōu)的核心是最優(yōu)性原理，它首先將一個多段決策問題轉(zhuǎn)化為一系列單段決策問題，然后從最后一段狀態(tài)開始逆向遞推到初始段狀態(tài)為止的一套求解最優(yōu)策略的完整方法。下面先介紹動態(tài)規(guī)劃的基本概念，然后討論連續(xù)型動態(tài)規(guī)劃。第3頁，共68頁，2023年，2月20日，星期六一、多段決策問題動態(tài)規(guī)劃是解決多段決策過程優(yōu)化問題的一種強有力的工具。所謂多段決策過程，是指把一個過程按時間或空間順序分為若干段，然后給每一步作出“決策”(或控制)，以使整個過程取得最優(yōu)的效果。第4頁，共68頁，2023年，2月20日，星期六如圖1所示，對于中間的任意一段，例如第k+1段作出相應(yīng)的“決策”(或控制)uk后，才能確定該段輸入狀態(tài)與輸出狀態(tài)間的關(guān)系，即從xk變化到xk+1的狀態(tài)轉(zhuǎn)移規(guī)律。在選擇好每一段的“決策”(或控制)uk以后，那么整個過程的狀態(tài)轉(zhuǎn)移規(guī)律從x0經(jīng)xk一直到xN也就被完全確定。全部“決策”的總體，稱為“策略”。

第5頁，共68頁，2023年，2月20日，星期六當然，如果對每一段的決策都是按照使某種性能指標為最優(yōu)的原則作出的，那么這就是一個多段最優(yōu)決策過程。圖1多段決策過程示意圖第6頁，共68頁，2023年，2月20日，星期六容易理解，在多段決策過程中，每一段(如第k+1段)的輸出狀態(tài)(xk+1)都僅僅與該段的決策(uk)及該段的初始狀態(tài)(xk)有關(guān)。而與其前面各段的決策及狀態(tài)的轉(zhuǎn)移規(guī)律無關(guān)。這種性質(zhì)稱為無后效性。下面以最優(yōu)路線問題為例，來討論動態(tài)規(guī)劃求解多段決策問題。第7頁，共68頁，2023年，2月20日，星期六設(shè)汽車從A城出發(fā)到B城，途中需穿越三條河流，它們各有兩座橋P、Q可供選擇通過，如圖2所示。各段間的行車時間(或里程、費用等)已標注在相應(yīng)段旁。問題是要確定一條最優(yōu)行駛路線，使從A城出發(fā)到B城的行車時間最短。第8頁，共68頁，2023年，2月20日，星期六第9頁，共68頁，2023年，2月20日，星期六現(xiàn)將A到B分成四段，每一段都要作一最優(yōu)決策，使總過程時間為最短。所以這是一個多段最優(yōu)決策問題。由圖2可知，所有可能的行車路線共有8條。如果將各條路線所需的時間都一一計算出來，并作一比較，便可求得最優(yōu)路線是AQ1P2Q3B，歷時12。這種一一計算的方法稱為窮舉算法。這種方法計算量大，如本例就要做3×23=24次加法和7次比較。如果決策一個n段過程，則共需(n-1)2n-1次加法和(2n-1-1)次比較?？梢婋S著段數(shù)的增多，計算量將急劇增加。第10頁，共68頁，2023年，2月20日，星期六應(yīng)用動態(tài)規(guī)劃法可使計算量減少許多。動態(tài)規(guī)劃法遵循一個最優(yōu)化原則：即所選擇的最優(yōu)路線必須保證其后部子路線是最優(yōu)的。例如在圖2中，如果AQ1P2Q3B是最優(yōu)路線，那么從這條路線上任一中間點到終點之間的一段路線必定也是最優(yōu)的。否則AQ1P2Q3B就不能是最優(yōu)路線了。第11頁，共68頁，2023年，2月20日，星期六根據(jù)這一原則，求解最優(yōu)路線問題，最好的辦法就是從終點開始，按時間最短為目標，逐段向前逆推。依次計算出各站至終點之間的時間最優(yōu)值，并據(jù)此決策出每一站的最優(yōu)路線。如在圖2中，從終點B開始逆推。第12頁，共68頁，2023年，2月20日，星期六最后一段(第四段)：終點B的前站是P3或Q3，不論汽車先從哪一站始發(fā)，行駛路線如何，在這最后一段，總不外乎是從P3到B，歷時為4，或從Q3到B，歷時為2，將其標明在圖3中相應(yīng)的圓圈內(nèi)。比較P3與Q3這一最后一段最優(yōu)決策為Q3B。第13頁，共68頁，2023年，2月20日，星期六最后一段(第四段)：終點B的前站是P3或Q3，不論汽車先從哪一站始發(fā)，行駛路線如何，在這最后一段，總不外乎是從P3到B，歷時為4，或從Q3到B，歷時為2，將其標明在圖3中相應(yīng)的圓圈內(nèi)。比較P3與Q3這一最后一段最優(yōu)決策為Q3B。第14頁，共68頁，2023年，2月20日，星期六第三段：P3、Q3的前站是P2、Q2。在這一段也不論其先后的情況如何，只需對從P2或Q2到B進行最優(yōu)決策。從P2到B有兩條路線：P2P3B，歷時為6；P2Q3B，歷時為4，取最短歷時4，標注在P2旁。從Q2到B也有兩條路線：Q2P3B，歷時為7；Q2Q3B，歷時為5，取最短歷時5，標注在Q2旁。比較P2與Q2的最優(yōu)值，可知這一段的最優(yōu)路線是P2Q3B。第15頁，共68頁，2023年，2月20日，星期六第二段：P2、Q2的前站是P1、Q1。同樣不管汽車是如何到達的P1、Q1，重要的是保證從P1或Q1到B要構(gòu)成最優(yōu)路線。從P1到B的兩條路線中，P1P2Q3B，歷時為11；P1Q2Q3B，歷時為11，取最短歷時11，標注在P1旁。從Q1到B的也有兩條路線中，Q1P2Q3B，歷時為8；Q1Q2Q3B，歷時為13，取最短歷時8，標注在Q1旁。比較P1與Q1的最優(yōu)值，可知這一段的最優(yōu)路線是Q1P2Q3B。第16頁，共68頁，2023年，2月20日，星期六第一段：P1、Q1的前站是始發(fā)站A。顯見從A到B的最優(yōu)值為12，故得最優(yōu)路線為AQ1P2Q3B。第17頁，共68頁，2023年，2月20日，星期六綜上可見，動態(tài)規(guī)劃法的特點是：1)與窮舉算法相比，可使計算量大大減少。如上述最優(yōu)路線問題，用動態(tài)規(guī)劃法只須做10次加法和6次比較。如果過程為n段，則需做加法。以上例為例，用窮舉法需作4608次加法，而后者只需做34次加法。第18頁，共68頁，2023年，2月20日，星期六2)最優(yōu)路線的整體決策是從終點開始，采用逆推方法，通過計算、比較各段性能指標，逐段決策逐步延伸完成的。全部最優(yōu)路線的形成過程已充分表達在圖3中。從最后一段開始，通過比較P3、Q3，得到Q3B；倒數(shù)第二段，通過比較P2、Q2，得到P2Q3B；倒數(shù)第三段，通過比較P1、Q1，得到最優(yōu)決策為Q1P2Q3B；直至最后形成最優(yōu)路線AQ1P2Q3B。象這樣將一個多段決策問題轉(zhuǎn)化為多個單段決策的簡單問題來處理，正是動態(tài)規(guī)劃法的重要特點之一。第19頁，共68頁，2023年，2月20日，星期六3)動態(tài)規(guī)劃法體現(xiàn)了多段最優(yōu)決策的一個重要規(guī)律，即所謂最優(yōu)性原理。它是動態(tài)規(guī)劃的理論基礎(chǔ)。第20頁，共68頁，2023年，2月20日，星期六對圖4所示的N段決策過程，如果在第k+1段處把全過程看成前k段子過程和后N-k段子過程兩部分。對于后部子過程來說，xk可看作是由x0及前k段初始決策(或控制)u0,u1,…,uk-1所形成的初始狀態(tài)。那么，多段決策的最優(yōu)決策略具有這樣的性質(zhì)：不論初始狀態(tài)和初始決策如何，其余(后段)決策(或控制)對于由初始決策所形成的狀態(tài)來說，必定也是一個最優(yōu)策略。這個性質(zhì)稱為最優(yōu)性原理。第21頁，共68頁，2023年，2月20日，星期六圖4N段決策過程第22頁，共68頁，2023年，2月20日，星期六設(shè)圖5中x*(t)是連續(xù)系統(tǒng)的一條最優(yōu)軌線。x(t1)是最優(yōu)軌線上的一點，那么最優(yōu)性原理說明，不管t=t1,t0<t1<tf時，系統(tǒng)是怎樣轉(zhuǎn)移到狀態(tài)x(t1)的，但從x(t1)到x(tf)這段軌線必定是最優(yōu)的。因為最優(yōu)軌線的后一段從x(t1)到x(tf)如果還有另一條軌線是最優(yōu)的話，那么原來從x(t0)到x(tf)的軌線就不是最優(yōu)的，這與假設(shè)矛盾。因此，最優(yōu)性原理成立。第23頁，共68頁，2023年，2月20日，星期六應(yīng)用最優(yōu)性原理可以將一個N段最優(yōu)決策問題轉(zhuǎn)化為N個一段最優(yōu)決策問題，從而大大減少求解最優(yōu)決策問題的計算量。圖5連續(xù)系統(tǒng)的狀態(tài)轉(zhuǎn)移過程第24頁，共68頁，2023年，2月20日，星期六圖5連續(xù)系統(tǒng)的狀態(tài)轉(zhuǎn)移過程第25頁，共68頁，2023年，2月20日，星期六二、連續(xù)系統(tǒng)的動態(tài)規(guī)劃利用動態(tài)規(guī)劃最優(yōu)性原理，可以推導出性能泛函為極小應(yīng)滿足的條件——哈密爾頓－雅可比方程。它是動態(tài)規(guī)劃的連續(xù)形式，解此方程可求得最優(yōu)控制u*(t)。現(xiàn)在來推導這一方程。第26頁，共68頁，2023年，2月20日，星期六設(shè)連續(xù)方程為(1)終端約束使性能泛函求最優(yōu)控制u*(t)，或u任意。初始狀態(tài)(2)(3)(4)第27頁，共68頁，2023年，2月20日，星期六根據(jù)最優(yōu)性原理，如果x*(t)是以x(t0)為初始狀態(tài)的最優(yōu)軌線。如圖6所示。圖6連續(xù)系統(tǒng)最優(yōu)軌線第28頁，共68頁，2023年，2月20日，星期六(5)設(shè)t=t′

(t0<t′<tf)時，狀態(tài)為x(t′)，它將軌線分成前后兩半斷。那么以x(t′)為初始狀態(tài)的后半段也必是最優(yōu)軌線。而與系統(tǒng)先前如何到達x(t′)無關(guān)。若取t0=t,t′=t+?t，式(4)可寫成第29頁，共68頁，2023年，2月20日，星期六根據(jù)最優(yōu)性原理，如果t到tf的過程是最優(yōu)的，則從t+?t到tf的后部子過程也是最優(yōu)的，其中t<t+?t<tf。因此可寫成(6)(7)當?t很小時，有第30頁，共68頁，2023年，2月20日，星期六式(5)可近似表示為(8)(5)第31頁，共68頁，2023年，2月20日，星期六將x(t+?t)進行泰勒展開，取一次近似，有(9)(10)(11)第32頁，共68頁，2023年，2月20日，星期六將上式在[x,t]領(lǐng)域展成泰勒級數(shù)，考慮到J*[x+?x,t+?t]既是x的函數(shù)，也與t有關(guān)，所以(12)(8)第33頁，共68頁，2023年，2月20日，星期六代入式(8)，得(13)(12)(8)第34頁，共68頁，2023年，2月20日，星期六考察上式因為J*[x,t]與u無關(guān)，故J*[x,t]與可提到min號外面。經(jīng)整理可得式(14)稱為連續(xù)系統(tǒng)動態(tài)規(guī)劃基本方程或貝爾曼方程。(14)第35頁，共68頁，2023年，2月20日，星期六貝爾曼方程。它是一個關(guān)于J*[x,t]的偏微分方程。解此方程可求得最優(yōu)控制使J為極小。它的邊界條件為

(15)(14)第36頁，共68頁，2023年，2月20日，星期六如果令哈密爾頓函數(shù)為式中則式(14)可寫成(17)(16)第37頁，共68頁，2023年，2月20日，星期六當控制矢量u(t)不受限制時，則有上兩式稱為哈密爾頓－雅可比方程。上式說明，在最優(yōu)軌線上，最優(yōu)控制必須使H達全局最小。實際上這就是極小值原理的另一種形式。(18)第38頁，共68頁，2023年，2月20日，星期六由貝爾曼方程可推導出協(xié)態(tài)方程和橫截條件。式(14)可寫成對x求偏導數(shù)，得(20)(19)(14)第39頁，共68頁，2023年，2月20日，星期六由于對t的全導數(shù)，為(22)(21)代入式(20)可寫成(20)第40頁，共68頁，2023年，2月20日，星期六令，則上式可寫成(23)這就是所求的協(xié)態(tài)方程，與以前結(jié)果完全一致。(22)第41頁，共68頁，2023年，2月20日，星期六在t=tf時，在終端處性能泛函為式中μ——與N同維的乘子矢量。(24)第42頁，共68頁，2023年，2月20日，星期六對x(tf)求偏導數(shù)，得(25)(26)即(24)第43頁，共68頁，2023年，2月20日，星期六將式(24)對tf求偏導數(shù)，得(27)(24)第44頁，共68頁，2023年，2月20日，星期六考慮式(17)、式(20)得上述結(jié)果與極小值原理中推導的完全一致。上述推導過程實際上等于用動態(tài)規(guī)劃方法間接證明了極小值原理。(28)(17)(20)(27)第45頁，共68頁，2023年，2月20日，星期六應(yīng)當指出，與極小值原理相比，動態(tài)規(guī)劃法需要解偏微分方程式(14)，它要求J[x,t]具有連續(xù)的偏導數(shù)，但在實際工程中，這一點常常不能滿足，因而限制了動態(tài)規(guī)劃法的使用范圍。第46頁，共68頁，2023年，2月20日，星期六例1：設(shè)，求最優(yōu)控制u*(t)使第47頁，共68頁，2023年，2月20日，星期六解：構(gòu)造哈密爾頓函數(shù)根據(jù)哈密爾頓－雅可比方程，有第48頁，共68頁，2023年，2月20日，星期六考慮控制u不受限制，得第49頁，共68頁，2023年，2月20日，星期六故第50頁，共68頁，2023年，2月20日，星期六邊界條件，因Φ[x(tf),tf]=0，故J[x(tf)]=0

如果令，則得這正是應(yīng)用極小值原理所得的結(jié)果，二者完全一致。第51頁，共68頁，2023年，2月20日，星期六例2：設(shè)受控系統(tǒng)狀態(tài)方程為初始狀態(tài)為性能泛函為試求在u無限制情況下，使J取極小時的最優(yōu)控制。第52頁，共68頁，2023年，2月20日，星期六解：構(gòu)造哈密爾頓函數(shù)第53頁，共68頁，2023年，2月20日，星期六由哈密爾頓－雅可比方程因u無限制，可從求得第54頁，共68頁，2023年，2月20日，星期六代入上式，并注意到J*與t無關(guān)，因而，有第55頁，共68頁，2023年，2月20日，星期六為求解此偏微分方程，設(shè)其解為滿足方程，得第56頁，共68頁，2023年，2月20日，星期六各項系數(shù)為可得解為最優(yōu)控制第57頁，共68頁，2023年，2月20日，星期六最優(yōu)控制可由狀態(tài)反饋實現(xiàn)，如圖7所示。第58頁，共68頁，2023年，2月20日，星期六進一步考察系統(tǒng)的狀態(tài)軌線。系統(tǒng)的狀態(tài)方程為齊次方程。第59頁，共68頁，2023年，2月20日，星期六它的解為第60頁，共68頁，2023年，2月20日，星期六于是最優(yōu)控制為性能泛函最優(yōu)值為第61頁，共68頁，2023年，2月20日，星期六例3：設(shè)受控系統(tǒng)的微分方程為使性能指標即要求快速響應(yīng)，求最優(yōu)控制u*，且滿足。第62頁，共68頁，2023年，2