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

第八章自動規(guī)劃

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

第一節(jié)自動規(guī)劃概述8.1.1規(guī)劃的概念和作用

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

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

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

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

城市規(guī)劃：指城市政府為了實現一定時期內經濟社會發(fā)展目標，確定城市性質，規(guī)模和發(fā)展方向，合理利用土地，協(xié)調空間布局和各項建設所作的綜合部署和具體安排。人生規(guī)劃：根據社會發(fā)展的需要和個人發(fā)展的志向，對自己的未來的發(fā)展道路做出一種預先的策劃和設計。包括健康規(guī)劃，事業(yè)規(guī)劃，情感規(guī)劃，晚景規(guī)劃。戰(zhàn)略規(guī)劃：就是組織制定長期目標并將其付諸實施。第一階子規(guī)劃的分層結構例子

子規(guī)劃的分層結構例子

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

1、規(guī)劃的分類

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

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

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

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

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

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

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

3、域的預測和規(guī)劃的修正8.1.3規(guī)劃系統(tǒng)的任務與方法

在規(guī)劃系統(tǒng)中，必須具有執(zhí)行下列各項任務的方法：

(1)根據最有效的啟發(fā)信息，選擇應用于下一步的最好規(guī)則。

(2)應用所選取的規(guī)則來計算由于應用該規(guī)則而生成的新狀態(tài)。

(3)對所求得的解答進行檢驗。

(4)檢驗空端，以便舍棄它們，使系統(tǒng)的求解工作向著更有效的方向進行。

(空端：即死端，指無法從它到達目標的端點。)(5)檢驗殆正確的解答，并應用具體的技術使之完全正確。8.1.3規(guī)劃系統(tǒng)的任務與方法

下面討論能夠執(zhí)行上述5項任務的方法。

1、選擇和應用規(guī)則在選擇合適的應用規(guī)則時最廣泛采用的技術是：首先要查出期望目標狀態(tài)與現有狀態(tài)之間的差別集合，然后辨別出那些與減少這些差別有關的規(guī)則。

2、檢驗解答與空端當規(guī)劃系統(tǒng)找到一個能夠把初始問題狀態(tài)變換為目標狀態(tài)的操作符序列時，此系統(tǒng)就成功地求得問題的一個解答。如果搜索過程是從初始狀態(tài)正向推理的，那么可以刪去任何導致某種狀態(tài)的路徑，從這種狀態(tài)出發(fā)是無法達到目標狀態(tài)的。（空端）如果搜索過程是從目標狀態(tài)逆向推理的，那么當確信無法達到初始狀態(tài)，或者搜索過程進展甚微時，可以終止該路徑的搜索。

下面討論能夠執(zhí)行上述5項任務的方法。3、修正殆正確解一個求解殆可分解問題的辦法是：當執(zhí)行與所提出的解答相對應的操作符序列時，檢查求得的狀態(tài)，并把它與期望目標加以比較。修正一個殆正確的解答的較好辦法是:注意有關出錯的知識，然后加以直接修正。修正一個殆正確的解答的更好辦法是:實際上不是對解答進行全面的修正,而是不完全確定地讓它們保留到最后的可能時刻。3、修正殆正確解第二節(jié)任務規(guī)劃第二節(jié)任務規(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。8.2.1積木世界的機器人問題

采用狀態(tài)描述作為數據庫的產生式系統(tǒng)是一種最簡單的問題求解系統(tǒng)。機器人問題的狀態(tài)描述和目標描述均可用謂詞邏輯公式構成。為了指定機器人所執(zhí)行的操作和執(zhí)行操作的結果，需要應用下列謂詞：

ON(a,b)：積木a在積木b之上。

ONTABLE(a)：積木a在桌面上。

CLEAR(a)：積木a頂上沒有任何東西。

HOLDING(a)：機械手正抓住積木a。

HANDEMPTY：械手為空手。采用狀態(tài)描述作為數據庫的產生式系統(tǒng)是一種最簡舉例：積木世界由一些有標記的立方形積木，互相堆迭在一起構成；機器人有個可移動的機械手，它可以抓起積木塊并移動積木從一處至另一處。提問：請同學就圖8.1積木世界的機器人問題應用謂詞公式的合取描述此目標為：

ON(B，C)∧ON(A，B)。

?初始狀態(tài)的描述:圖8.1積木世界的機器人問題舉例：積木世界由一些有標記的立方形積木，互相堆迭在一圖8.18.2.2用F規(guī)則求解規(guī)劃序列

采用F規(guī)則表示機器人的動作，這是一個叫做STRIPS規(guī)劃系統(tǒng)的規(guī)則，它由3部分組成。第一部分是先決條件。為了使F規(guī)則能夠應用到狀態(tài)描述中去。第二部分是一個叫做刪除表的謂詞。當一條規(guī)則被應用于某個狀態(tài)描述或數據庫時，就從該數據庫刪去刪除表的內容。第三部分叫做添加表。當把某條規(guī)則應用于某數據庫時，就把該添加表的內容添進該數據庫。8.2.2用F規(guī)則求解規(guī)劃序列

對于堆積木的例子中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)對于堆積木的例子中move這個動作可以表示如下：

如果move為此機器人僅有的操作符或適用動作，那么，可以生成如下圖所示的搜索圖或搜索樹：

8.2表示move動作的搜索樹如果move為此機器人僅有的操作符或適用動作，那么，

下面更具體地考慮圖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)下面更具體地考慮圖8.1中所示的例子，機器人的4個動

(3)pickup(X)

先決條件：ONTABLE(X)∧CLEAR(X)∧HANDEMPTY

刪除表：ONTABLE(X)∧HANDENPTY

添加表：HOLDING(X)(4)putdown(X)

先決條件和刪除表：HOLDING(X)

添加表：ONTABLE(X)，HANDEMPTY

假定目標為8.1所示的狀態(tài)，即

ON(B,C)∧ON(A,B)(3)pickup(X)

從圖8.1（a）所示的初始狀態(tài)描述開始正向操作，只有unstack(C,A)和pickup(B)兩個動作可以應用F規(guī)則。圖8.3所示給出這個問題的全部狀態(tài)空間，并用粗線指出了從初始狀態(tài)(用S0標記)到目標狀態(tài)(用G標記)的解答路徑。

與習慣的狀態(tài)空間圖畫法不同的是，這個狀態(tài)空間圖顯出問題的對稱性，而沒有把初始節(jié)點S0放在圖的頂點上。此外，要注意到本例中的每條規(guī)則都有一條逆規(guī)則，如圖7.3所示。例:積木世界機器人問題的狀態(tài)空間(見P216-217)從圖8.1（a）所示的初始狀態(tài)描圖8.3

積木世界機器人問題的狀態(tài)空間圖8.3積木世界機器人問題的狀態(tài)空間

沿著粗線所示的支路，從初始狀態(tài)開始，正向地依次讀出連接弧線上的F規(guī)則，就得到一個能夠達到目標狀態(tài)的動作序列于下：

｛unstack(C,A),

putdown(C),

pickup(B)，

stack(B,C),

pickup(A),

stack(A,B)｝就把這個動作序列叫做達到這個積木世界機器人問題目標的規(guī)劃。

沿著粗線所示的支路，從初始狀態(tài)開始，正向地依次讀出連接8.3.1STRIPS系統(tǒng)的組成

STRIPS（StanfordResearchInstituteProblemSolver）整個STRIPS系統(tǒng)的組成如下：

(1)世界模型。為一階謂詞演算公式。

(2)操作符(F規(guī)則)。包括先決條件、刪除表和添加表。

(3)操作方法。應用狀態(tài)空間表示和中間-結局分析。例如：狀態(tài)：(M，G)，包括初始狀態(tài)、中間狀態(tài)和目標狀態(tài)。初始狀態(tài)：(M0，(G0))

目標狀態(tài)：得到一個世界模型，其中不遺留任何未滿足的目標。8.3.1STRIPS系統(tǒng)的組成8.2.3STRIPS系統(tǒng)規(guī)劃過程

每個STRIPS問題的解答為某個實現目標的操作符序列，即達到目標的規(guī)劃。下面舉例說明STRIPS系統(tǒng)規(guī)劃的求解過程。例1考慮STRIPS系統(tǒng)一個比較簡單的情況，即要求機器人到鄰室去取回一個箱子。機器人的初始狀態(tài)和目標狀態(tài)的世界模型示于圖8.4。BOX1機器人箱子r1r2dBOX1機器人箱子r1r2d圖8.4

STRIPS的一個簡化模型8.2.3STRIPS系統(tǒng)規(guī)劃過程BOX1機器人

設有兩個操作符，即gothru和pushthru(“走過”和“推過”)，分別描述于下：

OP1：gothru(d,r1,r2)；機器人通過房間r1

和房間r2

之間的d，即機器人從房間r1

走過門d而進入房間r2。先決條件：機器人在房間r1

內，而且門d連接r1

和r2

兩個房間。

INROOM(ROBOT，r1)∧CONNECTS(d,r1,r2)；刪除表：INROOM(ROBOT，S)；對于任何S值。添加表：INROOM(ROBOT，r2)。設有兩個操作符，即gothru和pus

OP2：pushthru(b,d,r1,r2)

機器人把物體b從房間r1

經過門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)。

例:采用中間-結局分析方法來逐步求解機器人規(guī)劃(見P219-221)例:采用中間-結局分析方法來逐步求解機器人

差別表假定這個問題的初始狀態(tài)M0和目標G0如下：

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

G0：INROOM(ROBOT,R1)∧INROOM(BOX1，R1)∧CONNECTS(D1，R1，R2)差別表假定這個問題的初始狀態(tài)M0和目標G0如下：

M假定這個問題的初始狀態(tài)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.4

STRIPS的一個簡化模型假定這個問題的初始狀態(tài)M0和目標G0如下：

M0：INROO基于中間結局分析方法的規(guī)劃求解:采用中間結局分析方法來逐步求解這個機器人規(guī)劃：

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

②begin。

③G0

不能滿足M0，找出M0與G0的差別。盡管這個問題不能馬上得到解決，但是如果初始數據庫含有語句INROOM(BOX1，R1)，那么這個問題的求解過程就可以得到繼續(xù)。GPS找到它們的差別:d1

為INROOM(BOX1，R1)，即要把箱子(物體)放到目標房間R1

內。

④選取操作符：一個與減少差別d1有關的操作符。根據差別表，STRIPS選取操作符為：

OP2：pushthru(BOX1,d,r1,R1)基于中間結局分析方法的規(guī)劃求解:采用中間結局分析方法來逐步求⑤消去差別d1,為OP2設置先決條件G1為：

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

這個先決條件被設定為子目標，而且STRIPS試圖從M0到達G1。盡管G1仍然不能得到滿足，也不可能馬上找到這個問題的直接解答。不過STRIP發(fā)現：

如果r1=R2,d=D1，當前數據庫含有

INROOM(ROBOT，R1)

那么此過程能夠繼續(xù)進行?，F在新的子目標G1為：

G1：INROOM(BOX1，R2)∧INROOM(ROBOT，R2)∧CONNECTS(D1，R2，R1)⑤消去差別d1,為OP2設置先決條件G1為：

G1：⑥GPS(p)；重復第3步至第5步，迭代調用，以求解此問題。

步驟3：G1和M0的差別d2為INROOM(ROBOT，R2)即要求機器人移到房間R2。

步驟4：根據差別表，對應于d2的相關操作符為

OP1：gothru(d,r1,R2)

步驟5：OP1的先決條件為：

G2：INROOM(ROBOT，R1)∧CONNECTS(d,r1,R2)

步驟6：應用置換式r1=R1

和d=D1，

STRIPS系統(tǒng)能夠達到G2。⑥GPS(p)；重復第3步至第5步，迭代調用，以求解此問題

⑦把操作符gothru(D1,R1,R2)作用于M0，求出中間狀態(tài)M1：

刪除表：INROOM(ROBOT，R1)

添加表：INROOM(ROBOT，R2)

M1：INROOM(ROBOT，R2)

INROOM(BOX1，R2)

CONNECTS(D1，R1，R2)

把操作符pushthru應用中間狀態(tài)M1，

刪除表：INROOM(ROBOT，R2)，

INROOM(BOX1，R2)

添加表：INROOM(ROBOT，R1)，

INROOM(BOX1，R1)⑦把操作符gothru(D1,R1,R2)作用于M0

得到另一中間狀態(tài)M2為：

M2：INROOM(ROBOT，R1)

INROOM(BOX1，R1)

CONNECTS(D1，R1，R2)

M2=G0

⑧end。得到另一中間狀態(tài)M2為：

M2：INROOM(RO由于M2與G0匹配，所以通過中間結局分析解答了這個機器人規(guī)劃問題。在求解過程中，所用到的STRIPS規(guī)則為操作符OP1和OP2，即

gothru(D1,R1,R2),

pushthru(BOX1,D1,R2,R1)中間狀態(tài)模型M1和M2，即子目標G1和G2，M2與目標世界模型G0相同。

因此，得到的最后規(guī)劃為｛OP1，OP2｝，即

｛gothru(D1，R1，R2)，

pushthru(BOX1,D1,R2,R1)｝由于M2與G0匹配，所以通過中間結局分析解答了這BOX1機器人箱子R1R2DBOX1機器人箱子R1R2D圖8.5中間目標狀態(tài)的目標模型（a）中間目標狀態(tài)M1（b）中間目標狀態(tài)M2BOX1機器人箱子R1R2DBOX1機器人箱子R1R2D圖8圖8.6機器人規(guī)劃例題的搜索圖

圖8.6機器人規(guī)劃例題的搜索圖

模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升變?yōu)闊o序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態(tài)，最后在常溫時達到基態(tài)，內能減為最小

。該思想是由N.Metropolis等人于1953年提出。1983年,S.Kirkpatrick等成功地將退火思想引入到組合優(yōu)化領域。它是基于Monte-Carlo迭代求解策略的一種隨機尋優(yōu)算法，其出發(fā)點是基于物理中固體物質的退火過程與一般組合優(yōu)化問題之間的相似性。模擬退火算法從某一較高初溫出發(fā)，伴隨溫度參數的不斷下降,結合概率突跳特性在解空間中隨機尋找目標函數的全局最優(yōu)解，即在局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)。模擬退火算法是一種通用的優(yōu)化算法，理論上算法具有概率的全局優(yōu)化性能,目前已在工程中得到了廣泛應用，諸如VLSI、生產調度、控制工程、機器學習、神經網絡、信號處理等領域。

模擬退火算法來源于固體退火原理，將固體加溫至充分高，蟻群優(yōu)化算法是模擬螞蟻覓食的原理，設計出的一種群集智能算法。螞蟻在覓食過程中能夠在其經過的路徑上留下一種稱之為信息素的物質，并在覓食過程中能夠感知這種物質的強度，并指導自己行動方向，它們總是朝著該物質強度高的方向移動，因此大量螞蟻組成的集體覓食就表現為一種對信息素的正反饋現象。某一條路徑越短，路徑上經過的螞蟻越多，其信息素遺留的也就越多，信息素的濃度也就越高，螞蟻選擇這條路徑的幾率也就越高，由此構成的正反饋過程，從而逐漸的逼近最優(yōu)路徑，找到最優(yōu)路徑。蟻群優(yōu)化算法是模擬螞蟻覓食的原理，設計出的一種群集智能算法。第八章自動規(guī)劃

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

第一節(jié)自動規(guī)劃概述8.1.1規(guī)劃的概念和作用

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

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

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

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

城市規(guī)劃：指城市政府為了實現一定時期內經濟社會發(fā)展目標，確定城市性質，規(guī)模和發(fā)展方向，合理利用土地，協(xié)調空間布局和各項建設所作的綜合部署和具體安排。人生規(guī)劃：根據社會發(fā)展的需要和個人發(fā)展的志向，對自己的未來的發(fā)展道路做出一種預先的策劃和設計。包括健康規(guī)劃，事業(yè)規(guī)劃，情感規(guī)劃，晚景規(guī)劃。戰(zhàn)略規(guī)劃：就是組織制定長期目標并將其付諸實施。第一階子規(guī)劃的分層結構例子

子規(guī)劃的分層結構例子

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

1、規(guī)劃的分類

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

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

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

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

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

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

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

3、域的預測和規(guī)劃的修正8.1.3規(guī)劃系統(tǒng)的任務與方法

在規(guī)劃系統(tǒng)中，必須具有執(zhí)行下列各項任務的方法：

(1)根據最有效的啟發(fā)信息，選擇應用于下一步的最好規(guī)則。

(2)應用所選取的規(guī)則來計算由于應用該規(guī)則而生成的新狀態(tài)。

(3)對所求得的解答進行檢驗。

(4)檢驗空端，以便舍棄它們，使系統(tǒng)的求解工作向著更有效的方向進行。

(空端：即死端，指無法從它到達目標的端點。)(5)檢驗殆正確的解答，并應用具體的技術使之完全正確。8.1.3規(guī)劃系統(tǒng)的任務與方法

下面討論能夠執(zhí)行上述5項任務的方法。

1、選擇和應用規(guī)則在選擇合適的應用規(guī)則時最廣泛采用的技術是：首先要查出期望目標狀態(tài)與現有狀態(tài)之間的差別集合，然后辨別出那些與減少這些差別有關的規(guī)則。

2、檢驗解答與空端當規(guī)劃系統(tǒng)找到一個能夠把初始問題狀態(tài)變換為目標狀態(tài)的操作符序列時，此系統(tǒng)就成功地求得問題的一個解答。如果搜索過程是從初始狀態(tài)正向推理的，那么可以刪去任何導致某種狀態(tài)的路徑，從這種狀態(tài)出發(fā)是無法達到目標狀態(tài)的。（空端）如果搜索過程是從目標狀態(tài)逆向推理的，那么當確信無法達到初始狀態(tài)，或者搜索過程進展甚微時，可以終止該路徑的搜索。

下面討論能夠執(zhí)行上述5項任務的方法。3、修正殆正確解一個求解殆可分解問題的辦法是：當執(zhí)行與所提出的解答相對應的操作符序列時，檢查求得的狀態(tài)，并把它與期望目標加以比較。修正一個殆正確的解答的較好辦法是:注意有關出錯的知識，然后加以直接修正。修正一個殆正確的解答的更好辦法是:實際上不是對解答進行全面的修正,而是不完全確定地讓它們保留到最后的可能時刻。3、修正殆正確解第二節(jié)任務規(guī)劃第二節(jié)任務規(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。8.2.1積木世界的機器人問題

采用狀態(tài)描述作為數據庫的產生式系統(tǒng)是一種最簡單的問題求解系統(tǒng)。機器人問題的狀態(tài)描述和目標描述均可用謂詞邏輯公式構成。為了指定機器人所執(zhí)行的操作和執(zhí)行操作的結果，需要應用下列謂詞：

ON(a,b)：積木a在積木b之上。

ONTABLE(a)：積木a在桌面上。

CLEAR(a)：積木a頂上沒有任何東西。

HOLDING(a)：機械手正抓住積木a。

HANDEMPTY：械手為空手。采用狀態(tài)描述作為數據庫的產生式系統(tǒng)是一種最簡舉例：積木世界由一些有標記的立方形積木，互相堆迭在一起構成；機器人有個可移動的機械手，它可以抓起積木塊并移動積木從一處至另一處。提問：請同學就圖8.1積木世界的機器人問題應用謂詞公式的合取描述此目標為：

ON(B，C)∧ON(A，B)。

?初始狀態(tài)的描述:圖8.1積木世界的機器人問題舉例：積木世界由一些有標記的立方形積木，互相堆迭在一圖8.18.2.2用F規(guī)則求解規(guī)劃序列

采用F規(guī)則表示機器人的動作，這是一個叫做STRIPS規(guī)劃系統(tǒng)的規(guī)則，它由3部分組成。第一部分是先決條件。為了使F規(guī)則能夠應用到狀態(tài)描述中去。第二部分是一個叫做刪除表的謂詞。當一條規(guī)則被應用于某個狀態(tài)描述或數據庫時，就從該數據庫刪去刪除表的內容。第三部分叫做添加表。當把某條規(guī)則應用于某數據庫時，就把該添加表的內容添進該數據庫。8.2.2用F規(guī)則求解規(guī)劃序列

對于堆積木的例子中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)對于堆積木的例子中move這個動作可以表示如下：

如果move為此機器人僅有的操作符或適用動作，那么，可以生成如下圖所示的搜索圖或搜索樹：

8.2表示move動作的搜索樹如果move為此機器人僅有的操作符或適用動作，那么，

下面更具體地考慮圖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)下面更具體地考慮圖8.1中所示的例子，機器人的4個動

(3)pickup(X)

先決條件：ONTABLE(X)∧CLEAR(X)∧HANDEMPTY

刪除表：ONTABLE(X)∧HANDENPTY

添加表：HOLDING(X)(4)putdown(X)

先決條件和刪除表：HOLDING(X)

添加表：ONTABLE(X)，HANDEMPTY

假定目標為8.1所示的狀態(tài)，即

ON(B,C)∧ON(A,B)(3)pickup(X)

從圖8.1（a）所示的初始狀態(tài)描述開始正向操作，只有unstack(C,A)和pickup(B)兩個動作可以應用F規(guī)則。圖8.3所示給出這個問題的全部狀態(tài)空間，并用粗線指出了從初始狀態(tài)(用S0標記)到目標狀態(tài)(用G標記)的解答路徑。

與習慣的狀態(tài)空間圖畫法不同的是，這個狀態(tài)空間圖顯出問題的對稱性，而沒有把初始節(jié)點S0放在圖的頂點上。此外，要注意到本例中的每條規(guī)則都有一條逆規(guī)則，如圖7.3所示。例:積木世界機器人問題的狀態(tài)空間(見P216-217)從圖8.1（a）所示的初始狀態(tài)描圖8.3

積木世界機器人問題的狀態(tài)空間圖8.3積木世界機器人問題的狀態(tài)空間

沿著粗線所示的支路，從初始狀態(tài)開始，正向地依次讀出連接弧線上的F規(guī)則，就得到一個能夠達到目標狀態(tài)的動作序列于下：

｛unstack(C,A),

putdown(C),

pickup(B)，

stack(B,C),

pickup(A),

stack(A,B)｝就把這個動作序列叫做達到這個積木世界機器人問題目標的規(guī)劃。

沿著粗線所示的支路，從初始狀態(tài)開始，正向地依次讀出連接8.3.1STRIPS系統(tǒng)的組成

STRIPS（StanfordResearchInstituteProblemSolver）整個STRIPS系統(tǒng)的組成如下：

(1)世界模型。為一階謂詞演算公式。

(2)操作符(F規(guī)則)。包括先決條件、刪除表和添加表。

(3)操作方法。應用狀態(tài)空間表示和中間-結局分析。例如：狀態(tài)：(M，G)，包括初始狀態(tài)、中間狀態(tài)和目標狀態(tài)。初始狀態(tài)：(M0，(G0))

目標狀態(tài)：得到一個世界模型，其中不遺留任何未滿足的目標。8.3.1STRIPS系統(tǒng)的組成8.2.3STRIPS系統(tǒng)規(guī)劃過程

每個STRIPS問題的解答為某個實現目標的操作符序列，即達到目標的規(guī)劃。下面舉例說明STRIPS系統(tǒng)規(guī)劃的求解過程。例1考慮STRIPS系統(tǒng)一個比較簡單的情況，即要求機器人到鄰室去取回一個箱子。機器人的初始狀態(tài)和目標狀態(tài)的世界模型示于圖8.4。BOX1機器人箱子r1r2dBOX1機器人箱子r1r2d圖8.4

STRIPS的一個簡化模型8.2.3STRIPS系統(tǒng)規(guī)劃過程BOX1機器人

設有兩個操作符，即gothru和pushthru(“走過”和“推過”)，分別描述于下：

OP1：gothru(d,r1,r2)；機器人通過房間r1

和房間r2

之間的d，即機器人從房間r1

走過門d而進入房間r2。先決條件：機器人在房間r1

內，而且門d連接r1

和r2

兩個房間。

INROOM(ROBOT，r1)∧CONNECTS(d,r1,r2)；刪除表：INROOM(ROBOT，S)；對于任何S值。添加表：INROOM(ROBOT，r2)。設有兩個操作符，即gothru和pus

OP2：pushthru(b,d,r1,r2)

機器人把物體b從房間r1

經過門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)。

例:采用中間-結局分析方法來逐步求解機器人規(guī)劃(見P219-221)例:采用中間-結局分析方法來逐步求解機器人

差別表假定這個問題的初始狀態(tài)M0和目標G0如下：

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

G0：INROOM(ROBOT,R1)∧INROOM(BOX1，R1)∧CONNECTS(D1，R1，R2)差別表假定這個問題的初始狀態(tài)M0和目標G0如下：

M假定這個問題的初始狀態(tài)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.4

STRIPS的一個簡化模型假定這個問題的初始狀態(tài)M0和目標G0如下：

M0：INROO基于中間結局分析方法的規(guī)劃求解:采用中間結局分析方法來逐步求解這個機器人規(guī)劃：

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

②begin。

③G0

不能滿足M0，找出M0與G0的差別。盡管這個問題不能馬上得到解決，但是如果初始數據庫含有語句INROOM(BOX1，R1)，那么這個問題的求解過程就可以得到繼續(xù)。GPS找到它們的差別:d1

為INROOM(BOX1，R1)，即要把箱子(物體)放到目標房間R1

內。

④選取操作符：一個與減少差別d1有關的操作符。根據差別表，STRIPS選取操作符為：

OP2：pushthru(BOX1,d,r1,R1)基于中間結局分析方法的規(guī)劃求解:采用中間結局分析方法來逐步求⑤消去差別d1,為OP2設置先決條件G1為：

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

這個先決條件被設定為子目標，而且STRIPS試圖從M0到達G1。盡管G1仍然不能得到滿足，也不可能馬上找到這個問題的直接解答。不過STRIP發(fā)現：

如果r1=R2,d=D1，當前數據庫含有

INROOM(ROBOT，R1)

那么此過程能夠繼續(xù)進行。現在新的子目標G1為：

G1：INROOM(BOX1，R2)∧INROOM(ROBOT，R2)∧CONNECTS(D1，R2，R1)⑤消去差別d1,為OP2設置先決條件G1為：

G1：⑥GPS(p)；重復第3步至第5步，迭代調用，以求解此問題。

步驟3：G1和M0的差別d2為INROOM(ROBOT，R2)即要求機器人移到房間R2。