第7章 自動規(guī)劃系統(tǒng)

1、第7章 自動規(guī)劃系統(tǒng),課前思考 知識點 學習要求,課前思考,什么是規(guī)劃？規(guī)劃的作用是什么？ 基于謂詞邏輯規(guī)劃的基本過程怎樣？ STRIPS系統(tǒng)的規(guī)劃過程如何？ NOAH規(guī)劃系統(tǒng)求解問題過程怎樣？,知識點,規(guī)劃相關概念 基于謂詞邏輯的規(guī)劃 STRIPS（斯坦福研究所問題求解系統(tǒng)）規(guī)劃系統(tǒng) NOAH規(guī)劃系統(tǒng),學習要求,掌握規(guī)劃概念、作用與任務 了解各種規(guī)劃系統(tǒng),第7章 自動規(guī)劃系統(tǒng),7.1 自動規(guī)劃概述 7.2 基于謂詞邏輯的規(guī)劃 7.3 STRIPS規(guī)劃系統(tǒng) 7.4 分層規(guī)劃,自動規(guī)劃概述,自動規(guī)劃是一種重要的問題求解技術，與一般問題求解相比，自動規(guī)劃更注重于問題的求解過程，而不是求解結果。 規(guī)

2、劃要解決的問題，如機器人世界問題，往往是真實世界問題，而不是比較抽象的數(shù)學模型問題。,規(guī)劃的概念,規(guī)劃是一種問題求解技術，它從某個特定的問題狀態(tài)出發(fā)，尋求一系列行為動作，并建立一個操作序列，直到求得目標狀態(tài)為止。簡而言之，規(guī)劃是一個行動過程的描述。一個總規(guī)劃可以含有若干個子規(guī)劃。,規(guī)劃的特性和作用,在日常生活中，規(guī)劃意味著在行動之前決定行動的進程。 一個規(guī)劃是一個行動過程的描述 ?？梢允菦]有次序的目標表列；一般來說，規(guī)劃具有某個問題目標的蘊含排序。,規(guī)劃的特性和作用,大多數(shù)規(guī)劃具有很大的子規(guī)劃結構，規(guī)劃中的每個目標可以由達到此目標的比較詳細的子規(guī)劃所代替。,子規(guī)劃的分層結構例子,規(guī)劃的特性和作

3、用,規(guī)劃可用來監(jiān)控問題求解過程，并能夠在造成較大的危害之前發(fā)現(xiàn)差錯。規(guī)劃的好處可歸納為簡化搜索、解決目標矛盾以及為差錯補償提供基礎。,規(guī)劃的分類,按內容分 按方法分 非分層與分層、線性與非線性、同步與異步，基于消解原理的規(guī)劃 基于演繹規(guī)則的規(guī)劃等 按實質分 目標、任務、途徑、代價,問題分解途徑及方法,把比較復雜的問題分解為一些比較小的子問題。分解有兩種重要途徑。 第一條重要途徑是當從一個問題狀態(tài)移動到下一個狀態(tài)時，無需計算整個新的狀態(tài)，而只要考慮狀態(tài)中可能變化了的那些部分。 第二條重要途徑是把單一的困難問題分割為幾個有希望的較為容易解決的子問題。,域的預測和規(guī)劃的修正,a)域的預測 我們最好能

4、考慮可能的結果的集合，這些結果很可能按照它們出現(xiàn)的可能性以某個次序排列。然后，我們產生一個規(guī)劃，并試圖去執(zhí)行這個規(guī)劃。 b)規(guī)劃的修正 如果規(guī)劃在執(zhí)行中失敗了，那么就需要對它進行修訂，為便于修訂，在規(guī)劃過程中不僅要記下規(guī)劃的執(zhí)行步驟，而且也要記下每一步驟必須被執(zhí)行的理由。,機器人規(guī)劃系統(tǒng)的任務與方法,在規(guī)劃系統(tǒng)中，必須具有執(zhí)行下列各項任務的方法： （1）根據最有效的啟發(fā)信息，選擇應用于下一步的最好規(guī)則。 （2）應用所選取的規(guī)則來計算由于應用該規(guī)則而生成的新狀態(tài)。 （3）對所求得的解答進行檢驗。 （4）檢驗空端，以便舍棄它們，使系統(tǒng)的求解工作向著更有效的方向進行。 （5）檢驗殆正確的解答，并應用

5、具體的技術使之完全正確。,機器人規(guī)劃系統(tǒng)的任務與方法（續(xù)）,1、選擇和應用規(guī)則 在選擇合適的應用規(guī)則時最廣泛采用的技術是：首先要查出期望目標狀態(tài)與現(xiàn)有狀態(tài)之間的差別集合，然后辨別出那些與減少這些差別有關的規(guī)則。,機器人規(guī)劃系統(tǒng)的任務與方法（續(xù)）,2、檢驗解答與空端 當規(guī)劃系統(tǒng)找到一個能夠把初始問題狀態(tài)變換為目標狀態(tài)的操作符序列時，此系統(tǒng)就成功地求得問題的一個解答。 如果搜索過程是從初始狀態(tài)正向推理的，那么可以刪去任何導致某種狀態(tài)的路徑，從這種狀態(tài)出發(fā)是無法達到目標狀態(tài)的。 如果搜索過程是從目標狀態(tài)逆向推理的，那么當確信無法達到初始狀態(tài)，或者搜索過程進展甚微時，可以終止該路徑的搜索。,機器人規(guī)劃

6、系統(tǒng)的任務與方法（續(xù)）,3、修正殆正確解 執(zhí)行與所提出的解答相對應的操作符序列時，檢查求得的狀態(tài)，并把它與期望目標加以比較。 修正一個殆正確的解答的較好辦法是注意有關出錯的知識，然后加以直接修正。,第7章 規(guī)劃系統(tǒng),7.1 規(guī)劃的作用與任務 7.2 基于謂詞邏輯的規(guī)劃 7.3 STRIPS規(guī)劃系統(tǒng) 7.4 分層規(guī)劃,7.2 基于謂詞邏輯的規(guī)劃,用謂詞邏輯來描述世界模型及規(guī)劃過程的 一種規(guī)劃方法，關鍵是對待求解問題的表示 1、規(guī)劃世界模型的謂詞邏輯表示 2、基于謂詞邏輯規(guī)劃的基本過程,1、規(guī)劃世界模型的謂詞邏輯表示,相關謂詞,CLEAR(x):x上是空 HANDEMPTY(x):x手中是空 HO

7、LDING(x, y):x手中拿著y ON(x, y):x在y之上 NEAR(x, y):x在y的附近 IN(x, y):x在y中 AT(x, y):x在y處（上）,相關謂詞,ISCLOSE(x):x處于關閉狀態(tài) ISOPEN(x):x處于打開狀態(tài) OPEN(x, y):x把y打開 CLOSE(x, y):x把y關閉 GOTO(x, y):x走到y(tǒng)的旁邊 PICKDOWN(x, y, z):x把y放在z上 PICKUP(x, y):x把y拿起,初始狀態(tài),AT(T, L1)IN(W, T)ISCLOSE(T) AT(F, L2)CLEAR(F)AT(R, L3) HANDEMPTY(R),目標狀

8、態(tài),AT(T, L1)IN(W,T)ISOPEN (T) AT(F, L2)ON(W, F)NEAR(R, F) HANDEMPTY(R),機器人的規(guī)劃世界,規(guī)劃的目的就是找到能把初始狀態(tài)轉變?yōu)槟繕藸顟B(tài)的操作序列 操作可以分為先決條件和行為動作兩個部分,基本操作,OP1：OPEN(x, y) 先決條件：NEAR(x, y)ISCLOSE(y)行為動作：刪除：ISCLOSE(y) OP2：CLOSE(x,y) 先決條件：NEAR(x, y)ISOPEN(y) 行為動作： 刪除：ISOPEN(y) 添加：ISCLOSE(y),基本操作,OP3：GOTO(x, y) 先決條件：NEAR(x, y)

9、行為動作： 刪除：NEAR(x,y) 添加：NEAR(x, y) OP4：PICKDOWN(x, y, z) 先決條件：NEAR(x,z)HOLDING(x,y)CLEAR(z) 行為動作： 刪除：CLEAR(z)HOLDING(x, y) 添加：ON(x, z),基本操作,OP5：PICKUP(x, y) 先決條件：NEAR(x,z)IN(y,z)ISOPEN(z)HANDEMPTY(x) 行為動作： 刪除：IN(y, z)HANDEMPTY(x) 添加：HOLDING(x, y)IN(x,z),2 基于謂詞邏輯規(guī)劃的基本過程,把問題分割成幾個比較容易解決的子問題,子問題的規(guī)劃,Plan1：

10、R從L3處走到工具箱T的旁邊， Plan2：R打開工具箱T Plan3：R從工具箱中取出探測儀W， Plan4：R從工具箱T的旁邊走到探測架F旁 Plan5：R把探測儀W放在探測架F上,第7章 規(guī)劃系統(tǒng),7.1 規(guī)劃的作用與任務 7.2 基于謂詞邏輯的規(guī)劃 7.3 STRIPS規(guī)劃系統(tǒng) 7.4 分層規(guī)劃,7.3 STRIPS規(guī)劃系統(tǒng),1.積木世界的機器人規(guī)劃 2. STRIPS規(guī)劃系統(tǒng),1.積木世界的機器人規(guī)劃,機器人問題求解即尋求某個機器人的動作序列，這個序列能夠使該機器人達到預期的工作目標，完成規(guī)定的工作任務。,1.積木世界的機器人的問題,在機器人問題的典型表示中，機器人能夠執(zhí)行一套動作,

11、機器人能夠執(zhí)行的動作,unstack(a,b)：把放在b上的a拾起。要求機器人的手為空手，積木a上是空的。 stack(a,b)：把a堆放在b上。要求機械手已抓住a，且b頂上是空。 pickup(a)：從桌面上拾起a，并抓住它不放。要求機械手為空手，且a上沒有東西。 putdown(a)：把a放置到桌面上。要求機械手已抓住a。,積木世界的機器人的問題,機器人規(guī)劃包括許多功能，如識別機器人周圍世界、表述動作規(guī)劃并監(jiān)視這些規(guī)劃的執(zhí)行。所要研究的主要是綜合機器人的動作序列問題，即在某個給定的初始狀態(tài)下，經過動作序列而達到指定的目標。,積木世界的機器人的問題,ON(a,b)：積木a在積木b之上。ONT

12、ABLE(a)：積木a在桌面上。CLEAR(a)：積木a頂上沒有任何東西。HOLDING(a)：機械手正抓住積木a。HANDEMPTY：機械手為空手。,初始狀態(tài),CLEAR(B)：積木B頂部為空CLEAR(C)：積木a在桌面上。ON(C，A)：積木C堆在積木A上ONTABLE(A)：積木A置于桌面上ONTABLE(B)：積木B置于桌面上HANDEMPTY：機械手為空手,目標狀態(tài),ON(B，C)ON(A，B),用F規(guī)則求解規(guī)劃序列,采用F規(guī)則表示機器人的動作，這是一個叫做STRIPS規(guī)劃系統(tǒng)的規(guī)則 。它由3部分組成。 先決條件 刪除表 添加表,用F規(guī)則求解規(guī)劃序列,move(x,y,z)： 把物

13、體x從物體y上面移到物體z上面先決條件： CLEAR(x)，CLEAR(z)，ON(x,y) 刪除表： ON(x,y)，CLEAR(y) 添加表：ON(x,z)，CLEAR(y),表示move動作的搜索樹,機器人的4個動作用STRIPS形式表示,(1) stack(X,Y) 先決條件和刪除表：HOLDING(X)CLEAR(Y) 添加表：HANDEMPTY，ON(X，Y) (2) unstack(X,Y) 先決條件： HANDEMPTYON(X，Y)CLEAR(X) 刪除表：ON(X，Y)，HANDEMPTY 添加表：HOLDING(X)，CLEAR(Y),機器人的4個動作用STRIPS形式表

14、示,(3)pickup(X) 先決條件：ONTABLE(X)CLEAR(X)HANDEMPTY刪除表：ONTABLE(X)HANDENPTY添加表：HOLDING(X) (4)putdown(X) 先決條件和刪除表：HOLDING(X)添加表：ONTABLE(X)，HANDEMPTY,能夠達到目標狀態(tài)的動作序列,unstack(C,A),putdown(C),pickup(B)，stack(B,C),pickup(A),stack(A,B) 把這個動作序列叫做達到這個積木世界機器 人問題目標的規(guī)劃,STRIPS規(guī)劃系統(tǒng),STRIPS(STanford Research Institute Pr

15、oblem Solver) 斯坦福研究所問題求解系統(tǒng)，是從被求解的問 題中引出一般性結論而產生規(guī)劃的。,STRIPS系統(tǒng)的組成,STRIPS是由Fikes、Hart和Nilsson三人在1971及1972研究成功的，它是夏凱(Shakey)機器人程序控制系統(tǒng)的一個組成部分。 這個機器人是一部設計用于圍繞簡單的環(huán)境移動的自推車，它能夠按照簡單的英語命令進行動作。,STRIPS系統(tǒng)的組成,夏凱包含下列4個主要部分： (1)車輪及其推進系統(tǒng)； (2)傳感系統(tǒng)，由電視攝象機和接觸桿組成； (3)一臺不在車體上的用來執(zhí)行程序設計的計算機。它能夠分析由車上傳感器得到的反饋信息和輸入指令，并向車輪發(fā)出使其推

16、進系統(tǒng)觸發(fā)的信號 (4)無線電通訊系統(tǒng)，用于在計算機和車輪間的數(shù)據傳送。,STRIPS系統(tǒng)的組成,STRIPS是決定把哪個指令送至機器人的程序設計。 該機器人世界包括一些房間、房間之間的門和可移動的箱子；在比較復雜的情況下還有電燈和窗戶等。,STRIPS系統(tǒng)的組成,（1）世界模型：描述任何時刻的世界的數(shù)據庫。是一階謂詞演算公式。 （2）操作符（F規(guī)則）：包括先決條件、刪除表和添加表。 （3）操作方法：應用狀態(tài)空間表示和中間結局分析。,系統(tǒng)的規(guī)劃過程,（1）問題表示 （2）基于中間-結局分析方法的規(guī)劃求解,（1）問題表示,STRIPS的一個簡化模型,操作符,OP1：gothru(d,r1,r2)

17、 先決條件： INROOM(ROBOT,r1)CONNECTS(d,r1,r2) 刪除表：INROOM(ROBOT，S)； 添加表：INROOM(ROBOT，r2)。,操作符,OP2： pushthru(b,d,r1,r2) 先決條件： INROOM(b,r1)INROOM(ROBOT,r1) CONNECTS(d,r1,r2) 刪除表： INROOM(ROBOT，S)，INROOM(b，S)； 添加表： INROOM(ROBOT，r2),INROOM(b,r2)。,初始狀態(tài)和目標狀態(tài),M0： INROOM(ROBOT，R1) INROOM(BOX1,R2) CONNECTS(D1，R1，R2

18、) G0： INROOM(ROBOT,R1) INROOM(BOX1，R1) CONNECTS(D1，R1，R2),(2)基于中間結局分析方法的規(guī)劃求解,1.找出M0與G0的差別（ INROOM(BOX1，R1) ）,(2)基于中間結局分析方法的規(guī)劃求解,2.選取操作符 OP2：pushthru(BOX1,d,r1,R1) 3.為OP2設置先決條件G1 INROOM(BOX1,r1)INROOM(ROBOT,r1)CONNECTS(d,r1,R1),(2)基于中間結局分析方法的規(guī)劃求解,應用置換r1=R2, d=D1變換G1為： INROOM(BOX1，R2) INROOM(ROBOT，R2)

19、 CONNECTS(D1，R2，R1),(2)基于中間結局分析方法的規(guī)劃求解,4.重復第3步至第5步 找G1和M0的差別 INROOM(ROBOT，R2) 操作符為 OP1：gothru(d,r1,R2) OP1的先決條件G2：INROOM(ROBOT，R1)CONNECTS(d,r1,R2) 應用置換r1=R1和d=D1,(2)基于中間結局分析方法的規(guī)劃求解,5.應用操作符得到中間狀態(tài)M1、M2， 用OP1:gothru(D1,R1,R2) 刪除表：INROOM(ROBOT，R1) 添加表：INROOM(ROBOT，R2)M1： INROOM(ROBOT，R2) INROOM(BOX1，R2

20、) CONNECTS(D1，R1，R2),(2)基于中間結局分析方法的規(guī)劃求解,用OP2:pushthru(BOX1,D1,R2,R1) 刪除表：INROOM(ROBOT，R2)， INROOM(BOX1，R2)添加表：INROOM(ROBOT，R1)， INROOM(BOX1，R1)M2： INROOM(ROBOT，R1) INROOM(BOX1，R1) CONNECTS(D1，R1，R2),(2)基于中間結局分析方法的規(guī)劃求解,6. M2 = G0 end 得到的最后規(guī)劃為 gothru(D1，R1，R2)，pushthru(BOX1,D1,R2,R1),該問題的搜索圖,該問題的與或樹,第

21、7章 規(guī)劃系統(tǒng),7.1 規(guī)劃的作用與任務 7.2 基于謂詞邏輯的規(guī)劃 7.3 STRIPS規(guī)劃系統(tǒng) 7.4 分層規(guī)劃,分層規(guī)劃,為了有效地對問題進行求解，重要的是主要解答之前，能夠暫時刪去某些細節(jié)。然后設法填入適當?shù)募毠?jié)。 在ABSTRIPS系統(tǒng)(Sacerdoti,1974年)中，研究出一種較好的方法。這個系統(tǒng)實際上在抽象空間的某一層進行規(guī)劃，而不管抽象空間中較低層的每個先決條件。,分層規(guī)劃,1.長度優(yōu)先搜索 2.NOAH規(guī)劃系統(tǒng),1.長度優(yōu)先搜索,首先，只考慮可能具有最高臨界值的先決條件， 第二步，用初步規(guī)劃作為完整規(guī)劃的一個輪廓，并 考慮下一個臨界層的先決條件。用滿足那些先決條件 的操作

22、符來證明此規(guī)劃。 第三步，考慮越來越低層的臨界先決條件，直至全 部先決條件均被考慮到為止。,1.長度優(yōu)先搜索,重點：適當?shù)呐R界值,2.NOAH規(guī)劃系統(tǒng),1、應用最小約束策略 一個尋找非線性規(guī)劃而不必考慮操作符序列的所有排列的方法是把最少約束策略應用來選擇操作符執(zhí)行次序的問題。所需要的是某個能夠發(fā)現(xiàn)哪些需要的操作符的規(guī)劃過程，以及這些操作符間的任何需要的排序(例如，在能夠執(zhí)行某個已知的操作符之前，必須先執(zhí)行其它一些操作符以建立該操作符的先決條件)。在應用這種過程之后，才能應用第二個方法來尋求那些能夠滿足所有要求約束的操作符的某個排序,2.NOAH規(guī)劃系統(tǒng)（續(xù)）,問題求解系統(tǒng)NOAHSacerdoti在1975年提出和1977年進一步完善的正好能夠進行此項工作，它采用一種網絡結構來記錄它所選取的操作符之間所需要的排序。它也分層進行操作運算，即首先建立起規(guī)劃的抽象輪廓，然后在后續(xù)的各步中，填入越來越多的細節(jié)。,NOAH規(guī)劃系統(tǒng)例,書243頁圖7.11,2.NOAH規(guī)劃系統(tǒng)（續(xù)）,2、檢驗準則 NOAH系統(tǒng)應用一套準則來檢驗規(guī)劃并查出子規(guī)劃間的互相作用。每個準則都是一個小程序，它對所提出的規(guī)則進行專門觀測。準則法已被應用于各種規(guī)劃生成系統(tǒng)。在NOAH系統(tǒng)中，準則被用來提出推定的方法