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

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

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

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

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

6、系統(tǒng)的任務(wù)與方法（續(xù)）,3、修正殆正確解 執(zhí)行與所提出的解答相對(duì)應(yīng)的操作符序列時(shí)，檢查求得的狀態(tài)，并把它與期望目標(biāo)加以比較。 修正一個(gè)殆正確的解答的較好辦法是注意有關(guān)出錯(cuò)的知識(shí)，然后加以直接修正。,第7章 規(guī)劃系統(tǒng),7.1 規(guī)劃的作用與任務(wù) 7.2 基于謂詞邏輯的規(guī)劃 7.3 STRIPS規(guī)劃系統(tǒng) 7.4 分層規(guī)劃,7.2 基于謂詞邏輯的規(guī)劃,用謂詞邏輯來(lái)描述世界模型及規(guī)劃過(guò)程的 一種規(guī)劃方法，關(guān)鍵是對(duì)待求解問(wèn)題的表示 1、規(guī)劃世界模型的謂詞邏輯表示 2、基于謂詞邏輯規(guī)劃的基本過(guò)程,1、規(guī)劃世界模型的謂詞邏輯表示,相關(guān)謂詞,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處（上）,相關(guān)謂詞,ISCLOSE(x):x處于關(guān)閉狀態(tài) ISOPEN(x):x處于打開(kāi)狀態(tài) OPEN(x, y):x把y打開(kāi) CLOSE(x, y):x把y關(guān)閉 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),目標(biāo)狀

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

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

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

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

12、ABLE(a)：積木a在桌面上。CLEAR(a)：積木a頂上沒(méi)有任何東西。HOLDING(a)：機(jī)械手正抓住積木a。HANDEMPTY：機(jī)械手為空手。,初始狀態(tài),CLEAR(B)：積木B頂部為空CLEAR(C)：積木a在桌面上。ON(C，A)：積木C堆在積木A上ONTABLE(A)：積木A置于桌面上ONTABLE(B)：積木B置于桌面上HANDEMPTY：機(jī)械手為空手,目標(biāo)狀態(tài),ON(B，C)ON(A，B),用F規(guī)則求解規(guī)劃序列,采用F規(guī)則表示機(jī)器人的動(dòng)作，這是一個(gè)叫做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動(dòng)作的搜索樹(shù),機(jī)器人的4個(gè)動(dòng)作用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),機(jī)器人的4個(gè)動(dòng)作用STRIPS形式表

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

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

16、進(jìn)系統(tǒng)觸發(fā)的信號(hào) (4)無(wú)線電通訊系統(tǒng)，用于在計(jì)算機(jī)和車(chē)輪間的數(shù)據(jù)傳送。,STRIPS系統(tǒng)的組成,STRIPS是決定把哪個(gè)指令送至機(jī)器人的程序設(shè)計(jì)。 該機(jī)器人世界包括一些房間、房間之間的門(mén)和可移動(dòng)的箱子；在比較復(fù)雜的情況下還有電燈和窗戶(hù)等。,STRIPS系統(tǒng)的組成,（1）世界模型：描述任何時(shí)刻的世界的數(shù)據(jù)庫(kù)。是一階謂詞演算公式。 （2）操作符（F規(guī)則）：包括先決條件、刪除表和添加表。 （3）操作方法：應(yīng)用狀態(tài)空間表示和中間結(jié)局分析。,系統(tǒng)的規(guī)劃過(guò)程,（1）問(wèn)題表示 （2）基于中間-結(jié)局分析方法的規(guī)劃求解,（1）問(wèn)題表示,STRIPS的一個(gè)簡(jiǎn)化模型,操作符,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)和目標(biāo)狀態(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)基于中間結(jié)局分析方法的規(guī)劃求解,1.找出M0與G0的差別（ INROOM(BOX1，R1) ）,(2)基于中間結(jié)局分析方法的規(guī)劃求解,2.選取操作符 OP2：pushthru(BOX1,d,r1,R1) 3.為OP2設(shè)置先決條件G1 INROOM(BOX1,r1)INROOM(ROBOT,r1)CONNECTS(d,r1,R1),(2)基于中間結(jié)局分析方法的規(guī)劃求解,應(yīng)用置換r1=R2, d=D1變換G1為： INROOM(BOX1，R2) INROOM(ROBOT，R2)

19、 CONNECTS(D1，R2，R1),(2)基于中間結(jié)局分析方法的規(guī)劃求解,4.重復(fù)第3步至第5步 找G1和M0的差別 INROOM(ROBOT，R2) 操作符為 OP1：gothru(d,r1,R2) OP1的先決條件G2：INROOM(ROBOT，R1)CONNECTS(d,r1,R2) 應(yīng)用置換r1=R1和d=D1,(2)基于中間結(jié)局分析方法的規(guī)劃求解,5.應(yīng)用操作符得到中間狀態(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)基于中間結(jié)局分析方法的規(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)基于中間結(jié)局分析方法的規(guī)劃求解,6. M2 = G0 end 得到的最后規(guī)劃為 gothru(D1，R1，R2)，pushthru(BOX1,D1,R2,R1),該問(wèn)題的搜索圖,該問(wèn)題的與或樹(shù),第

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

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