1、人 工 智 能1第八章 自動(dòng)規(guī)劃8.1 機(jī)器人規(guī)劃的作用與任務(wù) 8.2 積木機(jī)器的機(jī)器人規(guī)劃8.3 STRIPS規(guī)劃系統(tǒng)8.4 具有學(xué)習(xí)能力的規(guī)劃系統(tǒng)8.5 基于專家系統(tǒng)的機(jī)器人規(guī)劃8.6 小結(jié)28.1 機(jī)器人規(guī)劃的作用與任務(wù)8.1.1規(guī)劃的作用與問題分解途徑規(guī)劃的概念及作用規(guī)劃的概念 規(guī)劃是一種重要的問題求解技術(shù)，它從某個(gè)特定的問題狀態(tài)出發(fā)，尋求一系列行為動(dòng)作，并建立一個(gè)操作序列，直到求得目標(biāo)狀態(tài)為止。 圖8.1 子規(guī)劃的分層結(jié)構(gòu)例子工 作 日 規(guī) 劃上午子規(guī)劃中午子規(guī)劃下午子規(guī)劃吃夾心面包閱讀寫作回家去上班閱讀文章3規(guī)劃的作用 規(guī)劃可用來監(jiān)控問題求解過程，并能夠在造成較大的危害之前發(fā)現(xiàn)差錯(cuò)

2、。規(guī)劃的好處可歸納為簡化搜索、解決目標(biāo)矛盾以及為差錯(cuò)補(bǔ)償提供基礎(chǔ)。問題分解途徑及方法把某些比較復(fù)雜的問題分解為一些比較小的子問題。有兩條能夠?qū)崿F(xiàn)這種分解的重要途徑。第一條重要途徑是當(dāng)從一個(gè)問題狀態(tài)移動(dòng)到下一個(gè)狀態(tài)時(shí)，無需計(jì)算整個(gè)新的狀態(tài)，而只要考慮狀態(tài)中可能變化了的那些部分。第二條重要途徑是把單一的困難問題分割為幾個(gè)有希望的較為容易解決的子問題。問題域的預(yù)測于規(guī)劃的修正（1）問題論域的預(yù)測（2）規(guī)劃的修正，問題分解使得影響局部化 8.1自動(dòng)規(guī)劃的作用與任務(wù)48.1.2機(jī)器人規(guī)劃系統(tǒng)的任務(wù)與方法在規(guī)劃系統(tǒng)中，必須具有執(zhí)行下列各項(xiàng)任務(wù)的方法：根據(jù)最有效的啟發(fā)信息，選擇應(yīng)用于下一步的最好規(guī)則。 應(yīng)用

3、所選取的規(guī)則來計(jì)算由于應(yīng)用該規(guī)則而生成的新狀態(tài)。 對所求得的解答進(jìn)行檢驗(yàn)。 檢驗(yàn)空端，以便舍棄它們，使系統(tǒng)的求解工作向著更有效的方向進(jìn)行。 檢驗(yàn)殆正確的解答，并應(yīng)用具體的技術(shù)使之完全正確。8.1自動(dòng)規(guī)劃的作用與任務(wù)5選擇于應(yīng)用規(guī)則檢驗(yàn)解答與空端修正殆正確解68.2 積木世界的機(jī)器人規(guī)劃 8.2.1 積木世界的機(jī)器人問題 積木世界由一些有標(biāo)記的立方形積木，互相堆迭在一起構(gòu)成；機(jī)器人有個(gè)可移動(dòng)的機(jī)械手，它可以抓起積木塊并移動(dòng)積木從一處至另一處。CBA機(jī)械手7在這個(gè)例子中機(jī)器人能夠執(zhí)行的動(dòng)作舉例如下： unstack(a,b)：把堆放在積木b上的積木a拾起。在進(jìn)行這個(gè)動(dòng)作之前，要求機(jī)器人的手為空手，

4、而且積木a的頂上是空的。 stack(a,b)：把積木a堆放在積木b上。動(dòng)作之前要求機(jī)械手必須已抓住積木a，而且積木b頂上必須是空的。 pickup(a)：從桌面上拾起積木a，并抓住它不放。在動(dòng)作之前要求機(jī)械手為空手，而且積木a頂上沒有任何東西。 putdown(a)：把積木a放置到桌面上。要求動(dòng)作之前機(jī)械手已抓住積木a。8.2 積木世界的機(jī)器人規(guī)劃8 研究內(nèi)容是綜合機(jī)器人的動(dòng)作序列，即在某個(gè)給定初始情況下，經(jīng)過某個(gè)動(dòng)作序列而達(dá)到指定的目標(biāo)。 機(jī)器人問題的狀態(tài)描述和目標(biāo)描述均可用謂詞邏輯公式構(gòu)成： ON(a,b)：積木a在積木b之上。 ONTABLE(a)：積木a在桌面上。 CLEAR(a)：

5、積木a頂上沒有任何東西。 HOLDING(a)：機(jī)械手正抓住積木a。 HANDEMPTY：機(jī)械手為空手。8.2 積木世界的機(jī)器人規(guī)劃9 圖8.4(a)所示為初始布局的機(jī)器人問題。 目標(biāo)在于建立一個(gè)積木堆，其中，積木B堆在積木C上面，積木 A又堆在積木B上面，如圖8.4(b)所示。CBA機(jī)械手ABC機(jī)械手（a）初始布局 （b）目標(biāo)布局圖8.4 積木世界的機(jī)器人問題8.2 積木世界的機(jī)器人規(guī)劃10初始布局可由下列謂詞公式的合取來表示：CLEAR(B)：積木B頂部為空CLEAR(C)：積木C頂部為空ON(C，A)：積木C堆在積木A上ONTABLE(A)：積木A置于桌面上ONTABLE(B)：積木B置

6、于桌面上HANDEMPTY：機(jī)械手為空手目標(biāo)布局：ON(B,C) and ON(A,B)8.2 積木世界的機(jī)器人規(guī)劃118.2.2用F規(guī)則求解規(guī)劃序列 STRIPS規(guī)劃系統(tǒng)的規(guī)則由3部分組成： 第一部分是先決條件。第二部分是一個(gè)叫做刪除表的謂詞。 第三部分叫做添加表。 8.2 積木世界的機(jī)器人規(guī)劃12例：表示堆積木的例子中move這個(gè)動(dòng)作，如下所示：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ī)器人僅有的操

7、作符或適用動(dòng)作，那么，可以生成如圖8.5所示的搜索圖或搜索樹。CLEAR(X)CLEAR(Z)ON(X,Y)ONTABLE(Y)ONTABLE(Z)CLEAR(X)CLEAR(Y)ON(X,Z)ONTABLE(Y)ONTABLE(z)move(X,Y,Z)圖8.5 表示move動(dòng)作的搜索樹8.2 積木世界的機(jī)器人規(guī)劃13機(jī)器人的4個(gè)動(dòng)作(或操作符)可用STRIPS形式表示如下： stack(X,Y) 先決條件和刪除表： HOLDING(X)CLEAR(Y) 添加表： HANDEMPTY，ON(X，Y) unstack(X,Y) 先決條件： HANDEMPTYON(X，Y)CLEAR(X) 刪除

8、表： ON(X，Y)，HANDEMPTY 添加表： HOLDING(X)，CLEAR(Y) pickup(X) 先決條件：ONTABLE(X)CLEAR(X)HANDEMPTY 刪除表： ONTABLE(X)HANDENPTY 添加表： HOLDING(X) putdown(X) 先決條件和刪除表： HOLDING(X) 添加表： ONTABLE(X)，HANDEMPTY8.2 積木世界的機(jī)器人規(guī)劃14 從初始狀態(tài)開始，正向地依次讀出連接弧線上的F規(guī)則，我們就得到一個(gè)能夠達(dá)到目標(biāo)狀態(tài)的動(dòng)作序列（如圖8.3中粗線所示）于下： unstack(C,A), putdown(C), pickup(B)

9、, stack(B,C),pickup(A),stack(A,B) 就把這個(gè)動(dòng)作序列叫做達(dá)到這個(gè)積木世界機(jī)器人問題目標(biāo)的規(guī)劃。8.2 積木世界的機(jī)器人規(guī)劃15168.3 STRIPS規(guī)劃系統(tǒng)STRIPS的介紹 STRIPS是由Fikes、Hart和Nilsson3人在1981及1982研究成功的，它是夏凱(Shakey)機(jī)器人程序控制系統(tǒng)的一個(gè)組成部分。STRIPS系統(tǒng)組成 世界模型：為一階謂詞演算公式； 操作符(F規(guī)則)：包括先決條件、刪除表和添加表； 操作方法：應(yīng)用狀態(tài)空間表示和中間-結(jié)局分析。17Strips是Shakey機(jī)器人系統(tǒng)的一個(gè)組成部分，Shakey機(jī)器人系統(tǒng)包括：（1）車輪及

10、其推進(jìn)系統(tǒng)；（2）傳感器，由電視攝像機(jī)和接觸桿組成；（3）計(jì)算機(jī)，接受機(jī)器人的傳感器信息與輸入指令，經(jīng)過計(jì)算后向車輪及其推進(jìn)系統(tǒng)發(fā)出信號(hào)；（4）無線通信系統(tǒng)，用于在車輪與計(jì)算機(jī)之間的數(shù)據(jù)傳遞8.3 Strips規(guī)劃系統(tǒng)18Strips的規(guī)劃過程問題：(1) 初始狀態(tài)：INROOM(Robot,R1) and INROOM(Box1,R2) and CONNECTS(D1,R1,R2)(2) 目標(biāo)狀態(tài)：INROOM（Robot,R1) and INROOM(BOX1,R1) and CONNECTS(D1,R1,R2)操作符OP1:gothru(d,r1,r2);先決條件：INROOM(b,r1

11、) and CONNECTS(d,r1,r2)刪除表：對所有S, INROOM(Robot,s) 添加表： INROOM(Robot,r2) 8.3 Strips規(guī)劃系統(tǒng)19操作符OP2:pushthru(b,d,r1,r2)先決條件：INROOM(b,r1) and INROOM(Robot,r1) and CONNECTS(d,r1,r2)刪除表：對所有S, INROOM(b,s) , INROOM(Robot,s) 添加表： INROOM(b,r2) , INROOM(Robot,r2) 問題的差別表：8.3 Strips規(guī)劃系統(tǒng)差別操作符gothrupushthru物體不在目標(biāo)房間內(nèi)機(jī)

12、器人不在目標(biāo)房間內(nèi)機(jī)器人和物體不在同一房間內(nèi)機(jī)器人和物體在同一房間內(nèi)，但不是目標(biāo)房間XXXX20采用中間結(jié)局分析方法求解步驟：do GPS的主循環(huán)迭代，until M0 與 G0 匹配為止BeginG0不能滿足M0，找出M0與G0的差別；選擇操作符OP2：一個(gè)與減少差別d1有關(guān)的操作符；消去差別d1,為操作符OP2設(shè)置先決條件G1：INROOM(b,r1) and INROOM(Robot,r1) and CONNECTS(d,r1,r2)采用置換：R2/r1 ， D1/d 則G1為：INROOM(BOX1,R2) and INROOM(Robot,R2) and CONNECTS(D1,R2

13、,R1)重復(fù)上述步驟，差異：INROOM(Robot，R2)；選擇操作符OP1；設(shè)置先決條件G2：INROOM(Robot,R1) and CONNECTS(d,r1,R2)采用置換：R1/r1 ， D1/d 則 G2滿足把gothru(D1,R1,R2)作用于M0，得中間狀態(tài)M1；把pushthru(BOX1,D1,R2,R1)于M1得中間狀態(tài)M2=G0END8.3 Strips規(guī)劃系統(tǒng)21最后的規(guī)劃為：gothru(D1,R1,R2) , pushthru(BOX1,D1,R2,R1) 8.3 Strips規(guī)劃系統(tǒng)2223含有多重解答的規(guī)劃例如：要求機(jī)器人ROBOT把3個(gè)不同區(qū)域的箱子推倒

14、同一區(qū)域；采用歸結(jié)反演和中間-結(jié)局分析來求解；得到多重解答。248.4 具有學(xué)習(xí)能力的規(guī)劃系統(tǒng) PULP-機(jī)器人規(guī)劃系統(tǒng) PULP-機(jī)器人規(guī)劃系統(tǒng)是一種具有學(xué)習(xí)能力的系統(tǒng)，它采用管理式學(xué)習(xí)，其作用原理是建立在類比(analogue)的基礎(chǔ)上的。 STRIPS的弱點(diǎn) 需要極其大量計(jì)算機(jī)內(nèi)存和時(shí)間等。 應(yīng)用具有學(xué)習(xí)能力的規(guī)劃系統(tǒng)能夠克服這一缺點(diǎn)。258.4.1 PULP-系統(tǒng)的結(jié)構(gòu)與操作方式PULP-系統(tǒng)的結(jié)構(gòu)“字典”是英語詞 匯的集合?！澳Ｐ汀辈糠职Ｐ褪澜?物體現(xiàn)有狀態(tài)的事實(shí)?！斑^程”集中了予先準(zhǔn)備好的過程知識(shí)。“方塊”集中了LISP程序，它配合“規(guī)劃”對“模型”進(jìn)行搜索和修正。SENEF程

15、序規(guī)劃與學(xué)習(xí)字典模型過程方塊響應(yīng)輸入圖 8.14 PULP-系統(tǒng)的總體結(jié)構(gòu) 8.4 具有學(xué)習(xí)能力的規(guī)劃系統(tǒng)26PULP-系統(tǒng)的操作方式 PULP-系統(tǒng)具有兩種操作方式： 學(xué)習(xí)方式 在學(xué)習(xí)方式下，輸入至系統(tǒng)的知識(shí)是由操作人員或者所謂“教師”提供的。圖8.15表示出在學(xué)習(xí)方式下的系統(tǒng)操作。 存儲(chǔ)任務(wù)分析方塊匹配過程分解學(xué)習(xí)教師輸入任務(wù)知識(shí)響應(yīng)圖8.15 PULP-系統(tǒng)結(jié)構(gòu) 8.4 具有學(xué)習(xí)能力的規(guī)劃系統(tǒng)27規(guī)劃方式當(dāng)某個(gè)命令句子送入系統(tǒng)時(shí)，PULP-就進(jìn)入規(guī)劃方式。上圖表示PULP-系統(tǒng)在規(guī)劃方式下的結(jié)構(gòu)。檢索混合規(guī)劃方塊目標(biāo)檢驗(yàn)匹配單一規(guī)劃規(guī)劃輸入命令響應(yīng)過程模型圖8.16 規(guī)劃方式下PULP-系統(tǒng)的結(jié)構(gòu) 8.4 具有學(xué)習(xí)能力的規(guī)劃系統(tǒng)28分層規(guī)劃的思想長度優(yōu)先搜索NOAH規(guī)劃系統(tǒng)298.5 基于專家系統(tǒng)的機(jī)器人規(guī)劃機(jī)器人規(guī)劃專家系統(tǒng)就是用專家系統(tǒng)的結(jié)構(gòu)和技術(shù)建立起來的機(jī)器人規(guī)劃系統(tǒng)。管理式學(xué)習(xí)能力的機(jī)器人規(guī)劃系統(tǒng)的不足： 表達(dá)子句的語義網(wǎng)絡(luò)結(jié)構(gòu)過于 復(fù)雜。 與復(fù)雜的系統(tǒng)內(nèi)部數(shù)據(jù)結(jié)構(gòu)有關(guān)的是， PULP-系統(tǒng)具有許多子系統(tǒng)。而且需要 花費(fèi)大量時(shí)間來編寫程序。 盡管PULP-系統(tǒng)的執(zhí)行速度要比 STRIPS 系列快得多，然而它仍然