南郵自動化人工智能自動規(guī)劃

第八章自動規(guī)劃

教學(xué)內(nèi)容：介紹自動規(guī)劃的基本概念和各種規(guī)劃系統(tǒng)。教學(xué)重點(diǎn)：機(jī)器人規(guī)劃的作用與任務(wù)、積木世界的規(guī)劃系統(tǒng)、基于模擬退火算法的機(jī)器人局部路徑規(guī)劃。教學(xué)難點(diǎn)：Strips規(guī)劃系統(tǒng)。教學(xué)方法：課堂教學(xué)為主，注意結(jié)合例子來說明抽象概念。教學(xué)要求：本章為選修內(nèi)容，掌握機(jī)器人規(guī)劃的作用與任務(wù)，并一般了解有哪幾種規(guī)劃方法。第一節(jié)自動規(guī)劃概述

8.1.1規(guī)劃的概念和作用

1、規(guī)劃的概念及作用

規(guī)劃的概念：規(guī)劃是一種重要的問題求解技術(shù)，它從某個(gè)特定的問題狀態(tài)出發(fā)，尋求一系列行為動作，并建立一個(gè)操作序列，直到求得目標(biāo)狀態(tài)為止。

規(guī)劃的作用：規(guī)劃可用來監(jiān)控問題求解過程，并能夠在造成較大的危害之前發(fā)現(xiàn)差錯。規(guī)劃的好處可歸納為簡化搜索、解決目標(biāo)矛盾以及為差錯補(bǔ)償提供基礎(chǔ)。

戰(zhàn)略規(guī)劃：就是組織制定長期目標(biāo)并將其付諸實(shí)施。第一階段確定目標(biāo)；第二階段制定規(guī)劃。

城市規(guī)劃：指城市政府為了實(shí)現(xiàn)一定時(shí)期內(nèi)經(jīng)濟(jì)社會發(fā)展目標(biāo)，確定城市性質(zhì)，規(guī)模和發(fā)展方向，合理利用土地，協(xié)調(diào)空間布局和各項(xiàng)建設(shè)所作的綜合部署和具體安排。人生規(guī)劃：根據(jù)社會發(fā)展的需要和個(gè)人發(fā)展的志向，對自己的未來的發(fā)展道路做出一種預(yù)先的策劃和設(shè)計(jì)。包括健康規(guī)劃，事業(yè)規(guī)劃，情感規(guī)劃，晚景規(guī)劃。子規(guī)劃的分層結(jié)構(gòu)例子

規(guī)劃的作用：科學(xué)規(guī)劃方法不僅對國家和社會貢獻(xiàn)很大，對于個(gè)人學(xué)習(xí)和工作也極為有益。8.1.2規(guī)劃的分類與問題分解途徑

1、規(guī)劃的分類

(1):按規(guī)劃內(nèi)容分

(2):按規(guī)劃方法分

(3):按規(guī)劃性質(zhì)分任務(wù)規(guī)劃(高層規(guī)劃)

路徑規(guī)劃(中層規(guī)劃)

軌跡規(guī)劃(底層規(guī)劃)2、問題分解途徑及方法把某些較復(fù)雜的問題分解為一些較小的子問題。有兩條實(shí)現(xiàn)這種分解的重要途徑。第一條重要途徑是當(dāng)從一個(gè)問題狀態(tài)移動到下一個(gè)狀態(tài)時(shí)，無需計(jì)算整個(gè)新的狀態(tài)，而只要考慮狀態(tài)中可能變化了的那些部分。第二條重要途徑是把單一的困難問題分割為幾個(gè)有希望的較為容易解決的子問題。3、域的預(yù)測和規(guī)劃的修正

(1)域的預(yù)測規(guī)劃方法的成功取決于問題論域的另一特性--預(yù)測。如果通過在實(shí)際上執(zhí)行某個(gè)操作序列來尋找問題的解答，那末在這個(gè)過程的任何一步都能確信該步的結(jié)果。但對于不可預(yù)測的論域，最好能考慮可能的結(jié)果的集合，這些結(jié)果很可能按照它們出現(xiàn)的可能性以某個(gè)次序排列。然后，產(chǎn)生一個(gè)規(guī)劃，并試圖去執(zhí)行這個(gè)規(guī)劃。

(2)規(guī)劃的修正如果規(guī)劃在執(zhí)行中失敗了，那么就需要對它進(jìn)行修訂，為便于修訂，在規(guī)劃過程中不僅要記下規(guī)劃的執(zhí)行步驟，而且也要記下每一步驟必須被執(zhí)行的理由。大多規(guī)則的執(zhí)行主要是按目標(biāo)定向模式工作的。在種模式下，規(guī)劃系統(tǒng)從目標(biāo)狀態(tài)向可達(dá)到的初始狀態(tài)進(jìn)行搜索。

規(guī)劃系統(tǒng)的的任務(wù)與方方法在規(guī)劃系統(tǒng)統(tǒng)中，必須須具有執(zhí)行行下列各項(xiàng)項(xiàng)任務(wù)的方方法：(1)根據(jù)最有效效的啟發(fā)信信息，選擇擇應(yīng)用于下下一步的最最好規(guī)則。。(2)應(yīng)用所選取取的規(guī)則來來計(jì)算由于于應(yīng)用該規(guī)規(guī)則而生成成的新狀態(tài)態(tài)。(3)對所求得的的解答進(jìn)行行檢驗(yàn)。(4)檢驗(yàn)空端，，以便舍棄棄它們，使使系統(tǒng)的求求解工作向向著更有效效的方向進(jìn)進(jìn)行。(空端：即死死端，指無無法從它到到達(dá)目標(biāo)的的端點(diǎn)。)(5)檢驗(yàn)殆正確確的解答，，并應(yīng)用具具體的技術(shù)術(shù)使之完全全正確。下面討論能能夠執(zhí)行上上述5項(xiàng)任務(wù)的方方法。1、選擇和應(yīng)應(yīng)用規(guī)則在選擇合適適的應(yīng)用規(guī)規(guī)則時(shí)最廣廣泛采用的的技術(shù)是：：首先要查查出期望目目標(biāo)狀態(tài)與與現(xiàn)有狀態(tài)態(tài)之間的差差別集合，，然后辨別別出那些與與減少這些些差別有關(guān)關(guān)的規(guī)則。。2、檢驗(yàn)解答答與空端當(dāng)規(guī)劃系統(tǒng)統(tǒng)找到一個(gè)個(gè)能夠把初初始問題狀狀態(tài)變換為為目標(biāo)狀態(tài)態(tài)的操作符符序列時(shí)，，此系統(tǒng)就就成功地求求得問題的的一個(gè)解答答。如果搜索過過程是從初初始狀態(tài)正正向推理的的，那么可可以刪去任任何導(dǎo)致某種狀態(tài)的路徑，從從這種狀態(tài)態(tài)出發(fā)是無法達(dá)到目目標(biāo)狀態(tài)的的。（空端端）如果搜索過過程是從目目標(biāo)狀態(tài)逆逆向推理的的，那么當(dāng)當(dāng)確信無法法達(dá)到初始始狀態(tài)，或或者搜索過過程進(jìn)展甚甚微時(shí)，可可以終止該該路徑的搜搜索。3、修正殆正正確解一個(gè)求解殆殆可分解問問題的辦法法是：當(dāng)執(zhí)執(zhí)行與所提提出的解答答相對應(yīng)的的操作符序序列時(shí)，檢檢查求得的的狀態(tài)，并并把它與期期望目標(biāo)加加以比較。。修正一個(gè)殆殆正確的解解答的較好辦法是:注意有關(guān)出出錯的知識識，然后加加以直接修修正。修正一個(gè)殆殆正確的解解答的更好辦法是:實(shí)際上不是是對解答進(jìn)進(jìn)行全面的的修正,而是不完全全確定地讓讓它們保留留到最后的的可能時(shí)刻刻。第二節(jié)任任務(wù)規(guī)劃劃積木世界的的機(jī)器人問問題機(jī)器人問題題既比較簡簡單，又很很直觀。在在機(jī)器人問問題的典型型表示中，，機(jī)器人能能夠執(zhí)行一一套動作。。在這個(gè)例子子中機(jī)器人人能夠執(zhí)行行的動作舉舉例如下：：unstack(a,b)：把堆放在在積木b上的積木a拾起。在進(jìn)進(jìn)行這個(gè)動動作之前，，要求機(jī)器人的手手為空手，而且積木a的頂上是空空的。stack(a,b)：把積木木a堆放在積木木b上。動作之之前要求機(jī)械手必須須已抓住積積木a，而且積木b頂上必須是是空的。pickup(a)：從桌桌面上拾起起積木a，并抓住它它不放。在在動作之前前要求機(jī)械手為空手手，而且積木a頂上沒有任何何東西。putdown(a)：把積木a放置到桌面上上。要求動作作之前機(jī)械手已抓住住積木a。采用狀態(tài)描述述作為數(shù)據(jù)庫庫的產(chǎn)生式系系統(tǒng)是一種最最簡單的問題題求解系統(tǒng)。。機(jī)器人問題題的狀態(tài)描述述和目標(biāo)描述述均可用謂詞詞邏輯公式構(gòu)構(gòu)成。為了指指定機(jī)器人所所執(zhí)行的操作作和執(zhí)行操作作的結(jié)果，需需要應(yīng)用下列列謂詞：ON(a,b)：積積木a在積木b之上。ONTABLE(a)：積木a在桌面上。CLEAR(a)：積積木a頂上沒有任何何東西。HOLDING(a)：機(jī)械械手正抓住積積木a。HANDEMPTY：械手為為空手。舉例：積木世世界由一些有有標(biāo)記的立方方形積木，互互相堆迭在一一起構(gòu)成；機(jī)器器人有個(gè)可移移動的機(jī)械手手，它可以抓抓起積木塊并移動積積木從一處至至另一處。提問：請同學(xué)學(xué)就圖8.1積木世界的機(jī)機(jī)器人問題應(yīng)應(yīng)用謂詞公式式的合取描述此此目標(biāo)為：ON(B，C)∧ON(A，B)。?初始狀態(tài)的描描述:圖8.1積木世界的機(jī)機(jī)器人問題用F規(guī)則求解規(guī)劃劃序列采用F規(guī)則表示機(jī)器器人的動作，，這是一個(gè)叫叫做STRIPS規(guī)劃系統(tǒng)的規(guī)規(guī)則，它由3部分組成。第一部分是先先決條件。為了使F規(guī)則能夠應(yīng)用用到狀態(tài)描述述中去。第二部分是一一個(gè)叫做刪除除表的謂詞。。當(dāng)一條規(guī)則被被應(yīng)用于某個(gè)個(gè)狀態(tài)描述或或數(shù)據(jù)庫時(shí)，，就從該數(shù)據(jù)據(jù)庫刪去刪除除表的內(nèi)容。。第三部分叫做做添加表。當(dāng)把某條規(guī)則則應(yīng)用于某數(shù)數(shù)據(jù)庫時(shí)，就就把該添加表表的內(nèi)容添進(jìn)進(jìn)該數(shù)據(jù)庫。。對于堆積木的的例子中move這個(gè)動作可以以表示如下：：move(x,y,z)：把物體x從物體y上面移到物體體z上面。先先決條件：CLEAR(x),CLEAR(z)，ON(x,y)刪除表：ON(x,y)，CLEAR(z)添加表：ON(x,z)，CLEAR(y)如果move為此機(jī)器人僅僅有的操作符符或適用動作作，那么，可可以生成如下下圖所示的搜搜索圖或搜索索樹：8.2表示move動作的搜索樹樹下面更具體地地考慮圖8.1中所示的例子子，機(jī)器人的的4個(gè)動作(或操作符)可用STRIPS形式表示如下下：(1)stack(X,Y)先決條件和刪刪除表：HOLDING(X)∧∧CLEAR(Y)添加表：HANDEMPTY，ON(X，Y)(2)unstack(X,Y)先決條件：HANDEMPTY∧ON(X，Y)∧CLEAR(X)刪除表：ON(X，Y)，HANDEMPTY添加表：HOLDING(X)，CLEAR(Y)(3)pickup(X)先決條件：ONTABLE(X)∧∧CLEAR(X)∧HANDEMPTY刪除表：ONTABLE(X)∧∧HANDENPTY添加表：HOLDING(X)(4)putdown(X)先決條件和刪刪除表：HOLDING(X)添加表：ONTABLE(X)，HANDEMPTY假定目標(biāo)為8.1所示的狀態(tài)，，即ON(B,C)∧ON(A,B)從圖8.1（a）所示的的初始狀態(tài)描描述開始正向向操作，只有有unstack(C,A)和pickup(B)兩個(gè)動作可以以應(yīng)用F規(guī)則。圖8.3所示給出這個(gè)個(gè)問題的全部部狀態(tài)空間，，并用粗線指指出了從初始始狀態(tài)(用S0標(biāo)記)到目標(biāo)狀態(tài)(用G標(biāo)記)的解答路徑。。與習(xí)慣的狀態(tài)態(tài)空間圖畫法法不同的是，，這個(gè)狀態(tài)空空間圖顯出問問題的對稱性性，而沒有把把初始節(jié)點(diǎn)S0放在圖的頂點(diǎn)點(diǎn)上。此外，，要注意到本本例中的每條條規(guī)則都有一一條逆規(guī)則，如圖7.3所示。例:積木世界機(jī)器器人問題的狀狀態(tài)空間(見P216-217)圖8.3積木世世界機(jī)機(jī)器人人問題題的狀狀態(tài)空空間沿著粗粗線所所示的的支路路，從從初始始狀態(tài)態(tài)開始始，正正向地地依次次讀出出連接接弧線線上的的F規(guī)則，，就得得到一一個(gè)能能夠達(dá)達(dá)到目目標(biāo)狀狀態(tài)的的動作作序列列于下下：｛｛unstack(C,A),putdown(C),pickup(B)，stack(B,C),pickup(A),stack(A,B)｝就把這這個(gè)動動作序序列叫叫做達(dá)達(dá)到這這個(gè)積積木世世界機(jī)機(jī)器人人問題題目標(biāo)標(biāo)的規(guī)規(guī)劃。。系統(tǒng)統(tǒng)的的組組成成STRIPS（StanfordResearchInstituteProblemSolver）整個(gè)個(gè)STRIPS系統(tǒng)統(tǒng)的的組組成成如如下下：：(1)世界界模模型型。。為為一一階階謂謂詞詞演演算算公公式式。。(2)操作作符符(F規(guī)則則)。包包括括先先決決條條件件、、刪刪除除表表和和添添加加表表。。(3)操作作方方法法。。應(yīng)應(yīng)用用狀狀態(tài)態(tài)空空間間表表示示和和中中間間-結(jié)局局分分析析。。例如如：：狀態(tài)態(tài)：：(M，G)，包包括括初初始始狀狀態(tài)態(tài)、、中中間間狀狀態(tài)態(tài)和和目目標(biāo)標(biāo)狀狀態(tài)態(tài)。。初始始狀狀態(tài)態(tài)：：(M0，(G0))目標(biāo)標(biāo)狀狀態(tài)態(tài)：：得得到到一一個(gè)個(gè)世世界界模模型型，，其其中中不不遺遺留留任任何何未未滿滿足足的的目目標(biāo)標(biāo)。。系統(tǒng)統(tǒng)規(guī)規(guī)劃劃過過程程每個(gè)個(gè)STRIPS問題題的的解解答答為為某某個(gè)個(gè)實(shí)實(shí)現(xiàn)現(xiàn)目目標(biāo)標(biāo)的的操操作作符符序序列列，，即即達(dá)達(dá)到到目目標(biāo)標(biāo)的的規(guī)規(guī)劃劃。。下下面面舉舉例例說說明明STRIPS系統(tǒng)統(tǒng)規(guī)規(guī)劃劃的的求求解解過過程程。。例1考慮慮STRIPS系統(tǒng)統(tǒng)一一個(gè)個(gè)比比較較簡簡單單的的情情況況，，即即要要求求機(jī)機(jī)器器人人到到鄰鄰室室去去取取回回一一個(gè)個(gè)箱箱子子。。機(jī)機(jī)器器人人的的初初始始狀狀態(tài)態(tài)和和目目標(biāo)標(biāo)狀狀態(tài)態(tài)的的世世界界模模型型示示于于圖圖8.4。BOX1機(jī)器器人人箱子子r1r2dBOX1機(jī)器器人人箱子子r1r2d圖8.4STRIPS的一一個(gè)個(gè)簡簡化化模模型型設(shè)有有兩兩個(gè)個(gè)操操作作符符，，即即gothru和pushthru(“走過”和和“推過過”)，分別別描述述于下下：OP1：gothru(d,r1,r2)；機(jī)器人人通過過房間間r1和房間間r2之間的的d，即機(jī)機(jī)器人人從房間間r1走過門門d而進(jìn)入入房間間r2。先決條條件：：機(jī)器器人在在房間間r1內(nèi)，而而且門門d連接r1和r2兩個(gè)房房間。。INROOM(ROBOT，r1)∧CONNECTS(d,r1,r2)；刪除表表：INROOM(ROBOT，S)；對于任何何S值。添加表：INROOM(ROBOT，r2)。OP2：pushthru(b,d,r1,r2)機(jī)器人把物物體b從房間r1經(jīng)過門d推到房間r2。先決條件：：INROOM(b,r1)∧INROOM(ROBOT,r1)∧CONNECTS(d,r1,r2)刪除表：INROOM(ROBOT,S)，INROOM(b,S);對于任何S。添加表：INROOM(ROBOT，r2),INROOM(b,r2)。例:采用中間-結(jié)局分析方方法來逐步步求解機(jī)器器人規(guī)劃(見P219-221)差別表假定這個(gè)問問題的初始始狀態(tài)M0和目標(biāo)G0如下：M0：INROOM(ROBOT，R1)∧INROOM(BOX1,R2)∧CONNECTS(D1，R1，R2)G0：INROOM(ROBOT,R1)∧INROOM(BOX1，R1)∧CONNECTS(D1，R1，R2)假定這個(gè)問問題的初始始狀態(tài)M0和目標(biāo)G0如下：M0：INROOM(ROBOT，R1)∧INROOM(BOX1,R2)∧CONNECTS(D1，R1，R2)G0：INROOM(ROBOT,R1)∧INROOM(BOX1，R1)∧CONNECTS(D1，R1，R2)BOX1機(jī)器人箱子R1R2DBOX1機(jī)器人箱子R1R2D圖8.4STRIPS的一個(gè)簡化化模型基于中間結(jié)結(jié)局分析方方法的規(guī)劃劃求解:采用中間結(jié)結(jié)局分析方方法來逐步步求解這個(gè)個(gè)機(jī)器人規(guī)規(guī)劃：①①doGPS的主循環(huán)迭迭代，untilM0與G0匹配為止。。②②begin。③③G0不能滿足M0，找出M0與G0的差別。盡管這個(gè)問問題不能馬馬上得到解解決，但是是如果初始始數(shù)據(jù)庫含含有語句INROOM(BOX1，R1)，那那么么這這個(gè)個(gè)問問題題的的求求解解過過程程就就可可以以得得到到繼繼續(xù)續(xù)。。GPS找到到它它們們的的差差別別:d1為INROOM(BOX1，R1)，即要要把把箱箱子子(物體體)放到到目目標(biāo)標(biāo)房房間間R1內(nèi)。。④④選選取取操操作作符符：：一一個(gè)個(gè)與與減減少少差差別別d1有關(guān)關(guān)的的操操作作符符。。根根據(jù)據(jù)差差別別表表，，STRIPS選取取操操作作符符為為：：OP2：pushthru(BOX1,d,r1,R1)⑤消去去差差別別d1,為OP2設(shè)置置先先決決條條件件G1為：：G1：INROOM(BOX1,r1)∧∧INROOM(ROBOT,r1)∧CONNECTS(d,r1,R1)這個(gè)個(gè)先先決決條條件件被被設(shè)設(shè)定定為為子子目目標(biāo)標(biāo)，，而而且且STRIPS試圖圖從從M0到達(dá)達(dá)G1。盡盡管管G1仍然然不不能能得得到到滿滿足足，，也也不不可可能能馬馬上上找找到到這這個(gè)個(gè)問問題題的的直直接接解解答答。。不不過過STRIP發(fā)現(xiàn)：如如果r1=R2,d=D1，當(dāng)前數(shù)據(jù)庫庫含有INROOM(ROBOT，R1)那么此過程能能夠繼續(xù)進(jìn)行行?，F(xiàn)在新的的子目標(biāo)G1為：G1：INROOM(BOX1，R2)∧INROOM(ROBOT，R2)∧CONNECTS(D1，R2，R1)⑥GPS(p)；重復(fù)第3步至第5步，迭代調(diào)用用，以求解此此問題。步步驟3：G1和M0的差別d2為INROOM(ROBOT，R2)即要求機(jī)器人人移到房間R2。

步驟驟4：根據(jù)差別表表，對應(yīng)于d2的相關(guān)操作符符為OP1：gothru(d,r1,R2)步驟5：OP1的先決決條件件為：：G2：INROOM(ROBOT，R1)∧CONNECTS(d,r1,R2)步驟6：應(yīng)用用置換換式r1=R1和d=D1，STRIPS系統(tǒng)能能夠達(dá)達(dá)到G2。⑦把把操作作符gothru(D1,R1,R2)作用于于M0，求出出中間間狀態(tài)態(tài)M1：刪刪除表表：INROOM(ROBOT，R1)添加表表：INROOM(ROBOT，R2)M1：INROOM(ROBOT，R2)INROOM(BOX1，R2)CONNECTS(D1，R1，R2)把操作作符pushthru應(yīng)用中中間狀狀態(tài)M1，刪刪除表表：INROOM(ROBOT，R2)，INROOM(BOX1，R2)添加表表：INROOM(ROBOT，R1)，INROOM(BOX1，R1)得到另另一中中間狀狀態(tài)M2為：M2：INROOM(ROBOT，R1)INROOM(BOX1，R1)CONNECTS(D1，R1，R2)M2=G0⑧end。由于M2與G0匹配，，所以以通過過中間間結(jié)局局分析析解答答了這這個(gè)機(jī)機(jī)器人人規(guī)劃劃問題題。在求解解過程程中，，所用用到的的STRIPS規(guī)則為為操作作符OP1和OP2，即gothru(D1,R1,R2),pushthru(BOX1,D1,R2,R1)中間狀狀態(tài)模模型M1和M2，即子子目標(biāo)標(biāo)G1和G2，M2與目標(biāo)標(biāo)世界界模型型G0相同。。因因此，，得到到的最最后規(guī)規(guī)劃為為｛OP1，OP2｝，即即｛｛gothru(D1，R1，R2)，pushthru(BOX1,D1,R2,R1)｝BOX1機(jī)器人人箱子R1R2DBOX1機(jī)器人人箱子R1R2D圖8.5中間目目標(biāo)狀狀態(tài)的的目標(biāo)標(biāo)模型型（a）中間目標(biāo)狀狀態(tài)M1（b）中間目標(biāo)狀狀態(tài)M2圖8.6機(jī)器人規(guī)劃劃例題的搜搜索圖模擬退火算算法來源于固體退火原理，，將固體加加溫至充分分高，再讓讓其徐徐冷冷卻，加溫溫時(shí)，固體體內(nèi)部粒子隨溫升變?yōu)闊o序狀狀，內(nèi)能