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

第八章自動規(guī)劃教學(xué)內(nèi)容：引見自動規(guī)劃的根本概念和各種規(guī)劃系統(tǒng)。教學(xué)重點：機器人規(guī)劃的作用與義務(wù)、積木世界的規(guī)劃系統(tǒng)、基于模擬退火算法的機器人部分途徑規(guī)劃。教學(xué)難點：Strips規(guī)劃系統(tǒng)。教學(xué)方法：課堂教學(xué)為主，留意結(jié)合例子來闡明籠統(tǒng)概念。教學(xué)要求：本章為選修內(nèi)容，掌握機器人規(guī)劃的作用與任務(wù)，并普通了解有哪幾種規(guī)劃方法。第一節(jié)自動規(guī)劃概述8.1.1規(guī)劃的概念和作用1、規(guī)劃的概念及作用規(guī)劃的概念：規(guī)劃是一種重要的問題求解技術(shù)，它從某個特定的問題形狀出發(fā)，尋求一系列行為動作，并建立一個操作序列，直到求得目的形狀為止。規(guī)劃的作用：規(guī)劃可用來監(jiān)控問題求解過程，并可以在呵斥較大的危害之前發(fā)現(xiàn)過失。規(guī)劃的益處可歸納為簡化搜索、處理目的矛盾以及為過失補償提供根底。戰(zhàn)略規(guī)劃：就是組織制定長期目的并將其付諸實施。第一階段確定目的；第二階段制定規(guī)劃。城市規(guī)劃：指城市政府為了實現(xiàn)一定時期內(nèi)經(jīng)濟社會開展目的，確定城市性質(zhì)，規(guī)模和開展方向，合理利用土地，協(xié)調(diào)空間規(guī)劃和各項建立所作的綜合部署和詳細(xì)安排。人生規(guī)劃：根據(jù)社會開展的需求和個人開展的志向，對本人的未來的開展道路做出一種預(yù)先的謀劃和設(shè)計。包括安康規(guī)劃，事業(yè)規(guī)劃，情感規(guī)劃，晚景規(guī)劃。子規(guī)劃的分層構(gòu)造例子規(guī)劃的作用：科學(xué)規(guī)劃方法不僅對國家和社會奉獻很大，對于個人學(xué)習(xí)和任務(wù)也極為有益。8.1.2規(guī)劃的分類與問題分解途徑1、規(guī)劃的分類(1):按規(guī)劃內(nèi)容分(2):按規(guī)劃方法分(3):按規(guī)劃性質(zhì)分義務(wù)規(guī)劃(高層規(guī)劃)途徑規(guī)劃(中層規(guī)劃)軌跡規(guī)劃(底層規(guī)劃)2、問題分解途徑及方法把某些較復(fù)雜的問題分解為一些較小的子問題。有兩條實現(xiàn)這種分解的重要途徑。第一條重要途徑是當(dāng)從一個問題形狀挪動到下一個形狀時，無需計算整個新的形狀，而只需思索形狀中能夠變化了的那些部分。第二條重要途徑是把單一的困難問題分割為幾個有希望的較為容易處理的子問題。3、域的預(yù)測和規(guī)劃的修正(1)域的預(yù)測規(guī)劃方法的勝利取決于問題論域的另一特性--預(yù)測。假設(shè)經(jīng)過在實踐上執(zhí)行某個操作序列來尋覓問題的解答，那末在這個過程的任何一步都能確信該步的結(jié)果。但對于不可預(yù)測的論域，最好能思索能夠的結(jié)果的集合，這些結(jié)果很能夠按照它們出現(xiàn)的能夠性以某個次序陳列。然后，產(chǎn)生一個規(guī)劃，并試圖去執(zhí)行這個規(guī)劃。

(2)規(guī)劃的修正假設(shè)規(guī)劃在執(zhí)行中失敗了，那么就需求對它進展修訂，為便于修訂，在規(guī)劃過程中不僅要記下規(guī)劃的執(zhí)行步驟，而且也要記下每一步驟必需被執(zhí)行的理由。大多規(guī)那么的執(zhí)行主要是按目的定向方式任務(wù)的。在種方式下，規(guī)劃系統(tǒng)從目的形狀向可到達的初始形狀進展搜索。8.1.3規(guī)劃系統(tǒng)的義務(wù)與方法在規(guī)劃系統(tǒng)中，必需具有執(zhí)行以下各項義務(wù)的方法：(1)根據(jù)最有效的啟發(fā)信息，選擇運用于下一步的最好規(guī)那么。(2)運用所選取的規(guī)那么來計算由于運用該規(guī)那么而生成的新形狀。(3)對所求得的解答進展檢驗。(4)檢驗空端，以便舍棄它們，使系統(tǒng)的求解任務(wù)向著更有效的方向進展。(空端：即死端，指無法從它到達目的的端點。)(5)檢驗殆正確的解答，并運用詳細(xì)的技術(shù)使之完全正確。下面討論可以執(zhí)行上述5項義務(wù)的方法。1、選擇和運用規(guī)那么在選擇適宜的運用規(guī)那么時最廣泛采用的技術(shù)是：首先要查出期望目的形狀與現(xiàn)有形狀之間的差別集合，然后區(qū)分出那些與減少這些差別有關(guān)的規(guī)那么。2、檢驗解答與空端當(dāng)規(guī)劃系統(tǒng)找到一個可以把初始問題形狀變換為目的形狀的操作符序列時，此系統(tǒng)就勝利地求得問題的一個解答。假設(shè)搜索過程是從初始形狀正向推理的，那么可以刪去任何導(dǎo)致某種形狀的途徑，從這種形狀出發(fā)是無法到達目的形狀的?！部斩恕臣僭O(shè)搜索過程是從目的形狀逆向推理的，那么當(dāng)確信無法到達初始形狀，或者搜索過程進展甚微時，可以終止該途徑的搜索。3、修正殆正確解一個求解殆可分解問題的方法是：當(dāng)執(zhí)行與所提出的解答相對應(yīng)的操作符序列時，檢查求得的形狀，并把它與期望目的加以比較。修正一個殆正確的解答的較好方法是:留意有關(guān)出錯的知識，然后加以直接修正。修正一個殆正確的解答的更好方法是:實踐上不是對解答進展全面的修正,而是不完全確定地讓它們保管到最后的能夠時辰。第二節(jié)義務(wù)規(guī)劃8.2.1積木世界的機器人問題機器人問題既比較簡單，又很直觀。在機器人問題的典型表示中，機器人可以執(zhí)行一套動作。在這個例子中機器人可以執(zhí)行的動作舉例如下：unstack(a,b)：把堆放在積木b上的積木a拾起。在進展這個動作之前，要求機器人的手為空手，而且積木a的頂上是空的。stack(a,b)：把積木a堆放在積木b上。動作之前要求機械手必需已抓住積木a，而且積木b頂上必需是空的。pickup(a)：從桌面上拾起積木a，并抓住它不放。在動作之前要求機械手為空手，而且積木a頂上沒有任何東西。putdown(a)：把積木a放置到桌面上。要求動作之前機械手已抓住積木a。采用形狀描畫作為數(shù)據(jù)庫的產(chǎn)生式系統(tǒng)是一種最簡單的問題求解系統(tǒng)。機器人問題的形狀描畫和目的描畫均可用謂詞邏輯公式構(gòu)成。為了指定機器人所執(zhí)行的操作和執(zhí)行操作的結(jié)果，需求運用以下謂詞：ON(a,b)：積木a在積木b之上。ONTABLE(a)：積木a在桌面上。CLEAR(a)：積木a頂上沒有任何東西。HOLDING(a)：機械手正抓住積木a。HANDEMPTY：械手為空手。舉例：積木世界由一些有標(biāo)志的立方形積木，相互堆迭在一起構(gòu)成；機器人有個可挪動的機械手，它可以抓起積木塊并挪動積木從一處至另一處。提問：請同窗就圖8.1積木世界的機器人問題運用謂詞公式的合取描畫此目的為：ON(B，C)∧ON(A，B)。?初始形狀的描畫:圖8.1積木世界的機器人問題8.2.2用F規(guī)那么求解規(guī)劃序列采用F規(guī)那么表示機器人的動作，這是一個叫做STRIPS規(guī)劃系統(tǒng)的規(guī)那么，它由3部分組成。第一部分是先決條件。為了使F規(guī)那么可以運用到形狀描畫中去。第二部分是一個叫做刪除表的謂詞。當(dāng)一條規(guī)那么被運用于某個形狀描畫或數(shù)據(jù)庫時，就從該數(shù)據(jù)庫刪去刪除表的內(nèi)容。第三部分叫做添加表。當(dāng)把某條規(guī)那么運用于某數(shù)據(jù)庫時，就把該添加表的內(nèi)容添進該數(shù)據(jù)庫。對于堆積木的例子中move這個動作可以表示如下：

move(x,y,z)：把物體x從物體y上面移到物體z上面。

先決條件：CLEAR(x),CLEAR(z)，ON(x,y)

刪除表：ON(x,y)，CLEAR(z)

添加表：ON(x,z)，CLEAR(y)假設(shè)move為此機器人僅有的操作符或適用動作，那么，可以生成如以下圖所示的搜索圖或搜索樹：8.2表示move動作的搜索樹下面更詳細(xì)地思索圖8.1中所示的例子，機器人的4個動作(或操作符)可用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

假定目的為8.1所示的形狀，即ON(B,C)∧ON(A,B)從圖8.1〔a〕所示的初始形狀描畫開場正向操作，只需unstack(C,A)和pickup(B)兩個動作可以運用F規(guī)那么。圖8.3所示給出這個問題的全部形狀空間，并用粗線指出了從初始形狀(用S0標(biāo)志)到目的形狀(用G標(biāo)志)的解答途徑。與習(xí)慣的形狀空間圖畫法不同的是，這個形狀空間圖顯出問題的對稱性，而沒有把初始節(jié)點S0放在圖的頂點上。此外，要留意到本例中的每條規(guī)那么都有一條逆規(guī)那么，如圖7.3所示。例:積木世界機器人問題的形狀空間(見P216-217)圖8.3積木世界機器人問題的形狀空間沿著粗線所示的支路，從初始形狀開場，正向地依次讀出銜接弧線上的F規(guī)那么，就得到一個可以到達目的形狀的動作序列于下：

｛unstack(C,A),putdown(C),pickup(B)，stack(B,C),pickup(A),stack(A,B)｝就把這個動作序列叫做到達這個積木世界機器人問標(biāo)題的的規(guī)劃。

8.3.1STRIPS系統(tǒng)的組成STRIPS〔StanfordResearchInstituteProblemSolver〕整個STRIPS系統(tǒng)的組成如下：(1)世界模型。為一階謂詞演算公式。(2)操作符(F規(guī)那么)。包括先決條件、刪除表和添加表。(3)操作方法。運用形狀空間表示和中間-結(jié)局分析。例如：形狀：(M，G)，包括初始形狀、中間形狀和目的形狀。初始形狀：(M0，(G0))目的形狀：得到一個世界模型，其中不遺留任何未滿足的目的。8.2.3STRIPS系統(tǒng)規(guī)劃過程

每個STRIPS問題的解答為某個實現(xiàn)目的的操作符序列，即到達目的的規(guī)劃。下面舉例闡明STRIPS系統(tǒng)規(guī)劃的求解過程。例1思索STRIPS系一致個比較簡單的情況，即要求機器人到鄰室去取回一個箱子。機器人的初始形狀和目的形狀的世界模型示于圖8.4。BOX1機器人箱子r1r2dBOX1機器人箱子r1r2d圖8.4STRIPS的一個簡化模型設(shè)有兩個操作符，即gothru和pushthru(“走過〞和“推過〞)，分別描畫于下：OP1：gothru(d,r1,r2)；機器人經(jīng)過房間r1和房間r2之間的d，即機器人從房間r1走過門d而進入房間r2。先決條件：機器人在房間r1內(nèi)，而且門d銜接r1和r2兩個房間。INROOM(ROBOT，r1)∧CONNECTS(d,r1,r2)；刪除表：INROOM(ROBOT，S)；對于任何S值。添加表：INROOM(ROBOT，r2)。

OP2：pushthru(b,d,r1,r2)機器人把物體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é)局分析方法來逐漸求解機器人規(guī)劃(見P219-221)差別表假定這個問題的初始形狀M0和目的G0如下：

M0：INROOM(ROBOT，R1)∧INROOM(BOX1,R2)∧CONNECTS(D1，R1，R2)

G0：INROOM(ROBOT,R1)∧INROOM(BOX1，R1)∧CONNECTS(D1，R1，R2)假定這個問題的初始形狀M0和目的G0如下：

M0：INROOM(ROBOT，R1)∧INROOM(BOX1,R2)∧CONNECTS(D1，R1，R2)

G0：INROOM(ROBOT,R1)∧INROOM(BOX1，R1)∧CONNECTS(D1，R1，R2)BOX1機器人箱子R1R2DBOX1機器人箱子R1R2D圖8.4STRIPS的一個簡化模型基于中間結(jié)局分析方法的規(guī)劃求解:采用中間結(jié)局分析方法來逐漸求解這個機器人規(guī)劃：

①doGPS的主循環(huán)迭代，untilM0與G0匹配為止。

②begin。

③G0不能滿足M0，找出M0與G0的差別。雖然這個問題不能馬上得到處理，但是假設(shè)初始數(shù)據(jù)庫含有語句INROOM(BOX1，R1)，那么這個問題的求解過程就可以得到繼續(xù)。GPS找到它們的差別:d1為INROOM(BOX1，R1)，即要把箱子(物體)放到目的房間R1內(nèi)。

④選取操作符：一個與減少差別d1有關(guān)的操作符。根據(jù)差別表，STRIPS選取操作符為：

OP2：pushthru(BOX1,d,r1,R1)⑤消去差別d1,為OP2設(shè)置先決條件G1為：

G1：INROOM(BOX1,r1)∧INROOM(ROBOT,r1)∧CONNECTS(d,r1,R1)

這個先決條件被設(shè)定為子目的，而且STRIPS試圖從M0到達G1。雖然G1依然不能得到滿足，也不能夠馬上找到這個問題的直接解答。不過STRIP發(fā)現(xiàn)：

假設(shè)r1=R2,d=D1，當(dāng)前數(shù)據(jù)庫含有INROOM(ROBOT，R1)

那么此過程可以繼續(xù)進展。如今新的子目的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)即要求機器人移到房間R2。

步驟4：根據(jù)差別表，對應(yīng)于d2的相關(guān)操作符為OP1：gothru(d,r1,R2)

步驟5：OP1的先決條件為：G2：INROOM(ROBOT，R1)∧CONNECTS(d,r1,R2)

步驟6：運用置換式r1=R1和d=D1，STRIPS系統(tǒng)可以到達G2。⑦把操作符gothru(D1,R1,R2)作用于M0，求出中間形狀M1：

刪除表：INROOM(ROBOT，R1)

添加表：INROOM(ROBOT，R2)

M1：INROOM(ROBOT，R2)INROOM(BOX1，R2)CONNECTS(D1，R1，R2)把操作符pushthru運用中間形狀M1，

刪除表：INROOM(ROBOT，R2)，INROOM(BOX1，R2)

添加表：INROOM(ROBOT，R1)，INROOM(BOX1，R1)得到另一中間形狀M2為：

M2：INROOM(ROBOT，R1)INROOM(BOX1，R1)CONNECTS(D1，R1，R2)

M2=G0⑧end。由于M2與G0匹配，所以經(jīng)過中間結(jié)局分析解答了這個機器人規(guī)劃問題。在求解過程中，所用到的STRIPS規(guī)那么為操作符OP1和OP2，即gothru(D1,R1,R2),pushthru(BOX1,D1,R2,R1)中間形狀模型M1和M2，即子目的G1和G2，M2與目的世界