第八章機器人規劃8.1

機器人規劃的作用與任務

8.2積木機器的機器人規劃8.3STRIPS規劃系統8.4具有學習能力的規劃系統8.5基于專家系統的機器人規劃8.6小結中南大學智能系統與智能軟件研究所8.1

機器人規劃的作用與任務

8.1.1 規劃的作用與問題分解途徑

規劃的概念及作用規劃的概念規劃是一種重要的問題求解技術，它從某個特定的問題狀態出發，尋求一系列行為動作，并建立一個操作序列，直到求得目標狀態為止。

圖8.1子規劃的分層結構例子工作日規劃上午子規劃中午子規劃下午子規劃吃夾心面包閱讀寫作回家去上班閱讀文章2中南大學智能系統與智能軟件研究所規劃的作用規劃可用來監控問題求解過程，并能夠在造成較大的危害之前發現差錯。規劃的好處可歸納為簡化搜索、解決目標矛盾以及為差錯補償提供基礎。問題分解途徑及方法把某些比較復雜的問題分解為一些比較小的子問題。有兩條能夠實現這種分解的重要途徑。第一條重要途徑是當從一個問題狀態移動到下一個狀態時，無需計算整個新的狀態，而只要考慮狀態中可能變化了的那些部分。第二條重要途徑是把單一的困難問題分割為幾個有希望的較為容易解決的子問題。8.1自動規劃的作用與任務3中南大學智能系統與智能軟件研究所8.1.2 機器人規劃系統的任務與方法在規劃系統中，必須具有執行下列各項任務的方法：根據最有效的啟發信息，選擇應用于下一步的最好規則。應用所選取的規則來計算由于應用該規則而生成的新狀態。對所求得的解答進行檢驗。檢驗空端，以便舍棄它們，使系統的求解工作向著更有效的方向進行。檢驗殆正確的解答，并應用具體的技術使之完全正確。8.1自動規劃的作用與任務4中南大學智能系統與智能軟件研究所8.2積木世界的機器人規劃

8.2.1積木世界的機器人問題積木世界由一些有標記的立方形積木，互相堆迭在一起構成；機器人有個可移動的機械手，它可以抓起積木塊并移動積木從一處至另一處。CBA機械手5中南大學智能系統與智能軟件研究所在這個例子中機器人能夠執行的動作舉例如下：

unstack(a,b)：把堆放在積木b上的積木a拾起。在進行這個動作之前，要求機器人的手為空手，而且積木a的頂上是空的。

stack(a,b)：把積木a堆放在積木b上。動作之前要求機械手必須已抓住積木a，而且積木b頂上必須是空的。

pickup(a)：從桌面上拾起積木a，并抓住它不放。在動作之前要求機械手為空手，而且積木a頂上沒有任何東西。

putdown(a)：把積木a放置到桌面上。要求動作之前機械手已抓住積木a。8.2積木世界的機器人規劃6中南大學智能系統與智能軟件研究所

研究內容是綜合機器人的動作序列，即在某個給定初始情況下，經過某個動作序列而達到指定的目標。機器人問題的狀態描述和目標描述均可用謂詞邏輯公式構成：

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

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

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

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

HANDEMPTY：機械手為空手。8.2積木世界的機器人規劃7中南大學智能系統與智能軟件研究所

圖8.4(a)所示為初始布局的機器人問題。目標在于建立一個積木堆，其中，積木B堆在積木C上面，積木A又堆在積木B上面，如圖8.4(b)所示。CBA機械手ABC機械手（a）初始布局（b）目標布局圖8.4積木世界的機器人問題8.2積木世界的機器人規劃8中南大學智能系統與智能軟件研究所初始布局可由下列謂詞公式的合取來表示：CLEAR(B)：積木B頂部為空CLEAR(C)：積木C頂部為空ON(C，A)：積木C堆在積木A上ONTABLE(A)：積木A置于桌面上ONTABLE(B)：積木B置于桌面上HANDEMPTY：機械手為空手8.2積木世界的機器人規劃9中南大學智能系統與智能軟件研究所8.2.2 用F規則求解規劃序列

STRIPS規劃系統的規則由3部分組成：第一部分是先決條件。第二部分是一個叫做刪除表的謂詞。

第三部分叫做添加表。

8.2積木世界的機器人規劃10中南大學智能系統與智能軟件研究所例：表示堆積木的例子中move這個動作，如下所示：

move(x,y,z)：把物體x從物體y上面移到物體z上面。先決條件：CLEAR(x),CLEAR(z)，ON(x,y)

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

添加表：ON(x,z)，CLEAR(y)如果move為此機器人僅有的操作符或適用動作，那么，可以生成如圖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動作的搜索樹8.2積木世界的機器人規劃11中南大學智能系統與智能軟件研究所機器人的4個動作(或操作符)可用STRIPS形式表示如下：

stack(X,Y)

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

添加表：

HANDEMPTY，ON(X，Y)

unstack(X,Y)

先決條件：

HANDEMPTY∧ON(X，Y)∧CLEAR(X)

刪除表：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積木世界的機器人規劃12中南大學智能系統與智能軟件研究所

從初始狀態開始，正向地依次讀出連接弧線上的F規則，我們就得到一個能夠達到目標狀態的動作序列（如圖8.6中粗線所示）于下：

{unstack(C,A),putdown(C),pickup(B),stack(B,C),pickup(A),stack(A,B)}

就把這個動作序列叫做達到這個積木世界機器人問題目標的規劃。8.2積木世界的機器人規劃13中南大學智能系統與智能軟件研究所8.3STRIPS規劃系統STRIPS的介紹

STRIPS是由Fikes、Hart和Nilsson3人在1981及1982研究成功的，它是夏凱(Shakey)機器人程序控制系統的一個組成部分。STRIPS系統組成世界模型：為一階謂詞演算公式；

操作符(F規則)：包括先決條件、刪除表和添加表；

操作方法：應用狀態空間表示和中間-結局分析。14中南大學智能系統與智能軟件研究所8.4具有學習能力的規劃系統

PULP-Ⅰ機器人規劃系統

PULP-Ⅰ機器人規劃系統是一種具有學習能力的系統，它采用管理式學習，其作用原理是建立在類比(analogue)的基礎上的。

STRIPS的弱點需要極其大量計算機內存和時間等。應用具有學習能力的規劃系統能夠克服這一缺點。15中南大學智能系統與智能軟件研究所8.4.1 PULP-Ⅰ系統的結構與操作方式PULP-Ⅰ系統的結構

“字典”是英語詞匯的集合。“模型”部分包括模型世界物體現有狀態的事實。“過程”集中了予先準備好的過程知識。“方塊”集中了LISP程序，它配合“規劃”對“模型”進行搜索和修正。SENEF程序規劃與學習字典模型過程方塊響應輸入圖8.14PULP-Ⅰ系統的總體結構

8.4具有學習能力的規劃系統16中南大學智能系統與智能軟件研究所PULP-Ⅰ系統的操作方式

PULP-Ⅰ系統具有兩種操作方式：

學習方式

在學習方式下，輸入至系統的知識是由操作人員或者所謂“教師”提供的。圖8.15表示出在學習方式下的系統操作。

存儲任務分析方塊匹配過程分解學習教師輸入任務知識響應圖8.15學習方式下PULP-Ⅰ系統的結構

8.4具有學習能力的規劃系統17中南大學智能系統與智能軟件研究所規劃方式當某個命令句子送入系統時，PULP-Ⅰ就進入規劃方式。上圖表示PULP-Ⅰ系統在規劃方式下的結構。檢索混合規劃方塊目標檢驗匹配單一規劃規劃輸入命令響應過程模型圖8.16規劃方式下PULP-Ⅰ系統的結構

8.4具有學習能力的規劃系統18中南大學智能系統與智能軟件研究所8.5基于專家系統的機器人規劃機器人規劃專家系統就是用專家系統的結構和技術建立起來的機器人規劃系統。管理式學習能力的機器人規劃系統的不足：表達子句的語義網絡結構過于復雜。與復雜的系統內部數據結構有關的是，

PULP-Ⅰ系統具有許多子系統。而且需要花費大量時間來編寫程序。盡管PULP-Ⅰ系統的執行速度要比

STRIPS

系列快得多，然而它仍然不夠快。19中南大學智能系統與智能軟件研究所8.5.1系統結構和規劃機理系統結構及規劃機理機器人用戶機器人專家知識用戶接口知識庫推理機控制策略工具專家系統知識獲取說明與分析問題輸入或新情況描述回答問題或建議與解釋圖8.20機器人規劃專家系統的結構20中南大學智能系統與智能軟件研究所基于規劃的機器人規劃專家系統由5個部分組成，如圖8.20所示。知識庫控制策略推理機知識獲取解釋與說明基于規則的專家系統的目標就是要通過逐條執行規則及其有關操作來逐步地改變總數據庫的狀況，直到得到一個可接受的數據庫(稱為目標數據庫)為止。8.5基于專家系統的機器人規劃21中南大學智能系統與智能軟件研究所任務級機器人規劃三要素任務規劃是機器人高層規劃最重要的一個方面，它包含下列3個要素：建立模型建立機器人工作環境的世界模型。任務說明程序綜合任務級機器人規劃的最后一步是綜合機械