第8章 自動規(guī)劃

8.1自動規(guī)劃概述8.2任務(wù)規(guī)劃8.3路經(jīng)規(guī)劃8.4軌跡規(guī)劃簡介8.5小結(jié)Ch.8AutomaticPlanning

第八章自動規(guī)劃8.1自動規(guī)劃概述IntroductionAnotherimportantapplicationareasofAI

√Expertsystem

√

MachinelearningNaturelanguageprocessing

AutomaticplanningDefinitionofplanning

Planning－onesdecidearouteorprocessbeforeactiontoathing

2

8.1.1 規(guī)劃的概念和作用1.規(guī)劃的概念定義8.1從某個特定的問題狀態(tài)出發(fā)，尋求一系列行為動作，并建立一個操作序列，直到求得目標(biāo)狀態(tài)為止。這個求解過程就稱為規(guī)劃。定義8.2規(guī)劃是關(guān)于動作的推理。它是一種抽象的和清晰的深思熟慮過程，該過程通過預(yù)期動作的期望效果，選擇和組織一組動作，其目的是盡可能好地實現(xiàn)一個預(yù)先給定的目標(biāo)。人工智能辭典對規(guī)劃和規(guī)劃系統(tǒng)給出如下定義：定義8.3規(guī)劃是對某個待求解問題給出求解過程的步驟。規(guī)劃涉及如何將問題分解為若干個相應(yīng)的子問題，以及如何記錄和處理問題求解過程中發(fā)現(xiàn)的子問題間的關(guān)系。定義8.4規(guī)劃系統(tǒng)是一個涉及有關(guān)問題求解過程的步驟的系統(tǒng)。例如，計算機或飛機設(shè)計、火車或汽車運輸路徑、財政和軍事等規(guī)劃問題。3

2.規(guī)劃的作用在科學(xué)發(fā)展觀的指導(dǎo)下，對于國民經(jīng)濟和社會的重大問題，對于科學(xué)技術(shù)、工程和民生的重要問題，都需要進行科學(xué)規(guī)劃和決策。決策的優(yōu)劣將決定行動的成敗。智能決策系統(tǒng)和自動規(guī)劃系統(tǒng)是科學(xué)決策的重要手段，它們同專家系統(tǒng)一起將成為21世紀(jì)智能管理與決策的得力工具。例如：國家和地區(qū)國民經(jīng)濟和社會發(fā)展計劃、財政預(yù)算、三峽工程、南水北調(diào)工程、大飛機制造項目、財政與金融調(diào)控等。48.1.2 規(guī)劃的分類和問題分解途經(jīng)1.規(guī)劃的分類按規(guī)劃內(nèi)容分按規(guī)劃方法分按規(guī)劃實質(zhì)分任務(wù)規(guī)劃對求解問題的目標(biāo)和任務(wù)等進行規(guī)劃，又可稱為高層規(guī)劃。路徑規(guī)劃對求解問題的途徑、路徑、代價等進行規(guī)劃，又可稱為中層規(guī)劃。軌跡規(guī)劃對求解問題的空間幾何軌跡及其生成進行規(guī)劃，又可稱為底層規(guī)劃。2.問題分解途徑3.域的預(yù)測和規(guī)劃的修正58.1.3 執(zhí)行規(guī)劃系統(tǒng)任務(wù)的一般方法機器人規(guī)劃系統(tǒng)必須具有執(zhí)行下列各項任務(wù)的方法：根據(jù)最有效的啟發(fā)信息，選擇要用的最好規(guī)則。應(yīng)用所選規(guī)則計算因應(yīng)用該規(guī)則而生成的新狀態(tài)。檢驗求得的解答。檢驗空端(deadend)，以便舍棄它們，使系統(tǒng)的求解工作向著更有效的方向進行。檢驗殆正確(almostcorrectsolution)的解答，并應(yīng)用具體的技術(shù)使之完全正確。選擇和應(yīng)用規(guī)則

檢驗解答與空端

修正殆正確解

68.2任務(wù)規(guī)劃TaskPlanning

8.2.1積木世界的機器人規(guī)劃1.積木世界的機器人問題積木世界由一些有標(biāo)記的立方形積木互相堆迭在一起構(gòu)成；機器人有個可移動的機械手，它可以抓起積木塊并把積木從一處移動至另一處。見右例。ACB機械手7在這類例子中機器人能夠執(zhí)行的動作舉例如下：

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

stack(a,b)：把積木A堆放在積木B上。動作之前要求機械手必須已抓住積木

A，而且積木B頂上必須是空的。

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

putdown(a)：把積木A放置到桌面上。要求動作之前機械手已抓住積木A。ACB機械手8

規(guī)劃工作內(nèi)容就是綜合機器人的動作序列，即在某個給定初始情況下，經(jīng)過某個動作序列而達到指定的目標(biāo)。機器人問題的狀態(tài)描述和目標(biāo)描述均可用謂詞邏輯公式構(gòu)成：

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

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

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

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

HANDEMPTY：機械手為空手。ACB機械手9

積木世界機器人規(guī)劃問題示例機器人初始布局問題,如圖8.1(a)所示。目標(biāo)問題：在于建立一個如圖8.1(b)所示的積木堆。其中，積木B堆在積木C上面，積木A又堆在積木B上面。圖8.1積木世界的機器人問題CBA機械手ABC機械手（a）初始布局（b）目標(biāo)布局10初始布局可由下列謂詞公式的合取來表示：CLEAR(B)：積木B頂部為空CLEAR(C)：積木C頂部為空ON(C，A)：積木C堆在積木A上ONTABLE(A)：積木A置于桌面上ONTABLE(B)：積木B置于桌面上HANDEMPTY：機械手為空手CBA112.FindingplanningsequenceusingFrule

用F規(guī)則求解規(guī)劃序列規(guī)劃系統(tǒng)的規(guī)則由3部分組成：第一部分是確信滿足先決條件公式（preconditionWFF）。第二部分是一個叫做刪除表（deletelist）。

第三部分叫做添加表(addlist)。

12

例子：表示堆積木的例子中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為此機器人僅有的操作符或適用動作，那么，可以生成如圖8.2所示的搜索圖或搜索樹。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.2表示move動作的搜索樹XZY機械手XZY機械手13機器人的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)，HANDEMPTY14積木世界機器人規(guī)劃問題示例

對于圖8.1的例子，從初始狀態(tài)開始，正向地依次讀出連接弧線上的F規(guī)則，我們就得到一個能夠達到目標(biāo)狀態(tài)的動作序列于下：

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

這個動作序列叫做達到這個積木世界機器人問題目標(biāo)的規(guī)劃。CBA機械手ABC機械手（a）初始布局（b）目標(biāo)布局15圖8.3積木世界機器人問題的狀態(tài)空間168.2.2STRIPS

PlanningSystem

STRIPS規(guī)劃系統(tǒng)STRIPS的介紹

STRIPS是由Fikes、Hart和Nilsson3人在1981及1982研究成功的，它是夏凱(Shakey)機器人程序控制系統(tǒng)的一個組成部分。STRIPS系統(tǒng)組成世界模型：為一階謂詞演算公式；操作符(F規(guī)則)：包括先決條件、刪除表和添加表；操作方法：應(yīng)用狀態(tài)空間表示和中間-結(jié)局分析（means-endsanalysis）。178.2.3PlanningSystemwithLearningCapability

具有學(xué)習(xí)能力的規(guī)劃系統(tǒng)1.

PULP-Ⅰ機器人規(guī)劃系統(tǒng)

PULP-Ⅰ(PurdueLearningPlanning-Ⅰ)機器人規(guī)劃系統(tǒng)是一種具有學(xué)習(xí)能力的系統(tǒng)，它采用管理式學(xué)習(xí)，其作用原理是建立在類比(analogue)的基礎(chǔ)上的。

STRIPS的弱點需要極其大量計算機內(nèi)存和時間等。應(yīng)用具有學(xué)習(xí)能力的規(guī)劃系統(tǒng)能夠克服這一缺點。182.Architectureandoperation

of

PULP-Ⅰ

PULP-Ⅰ系統(tǒng)的結(jié)構(gòu)與操作方式PULP-Ⅰ系統(tǒng)的結(jié)構(gòu)

“字典”

是英語詞匯的集合?！澳Ｐ汀?/p>

包括世界模型內(nèi)物體現(xiàn)有狀態(tài)和事實?！斑^程”

集中了預(yù)先準(zhǔn)備好的過程知識?！胺綁K”

LISP程序，通過“規(guī)劃”對“模型”進行搜索和修正。

SENEF(SEmentic

NEtworkFormation)

用于表示知識的語義網(wǎng)絡(luò)程序。圖8.8PULP-Ⅰ系統(tǒng)的總體結(jié)構(gòu)

SENEF程序規(guī)劃與學(xué)習(xí)字典模型過程方塊響應(yīng)輸入19PULP-Ⅰ系統(tǒng)的操作方式

PULP-Ⅰ系統(tǒng)具有兩種操作方式

學(xué)習(xí)方式

在學(xué)習(xí)方式下，輸入至系統(tǒng)的知識是由操作人員或者所謂“教師”提供的。圖8.9表示出在學(xué)習(xí)方式下的系統(tǒng)操作。

存儲任務(wù)分析方塊匹配過程分解學(xué)習(xí)教師輸入任務(wù)知識響應(yīng)圖8.9學(xué)習(xí)方式下PULP-Ⅰ系統(tǒng)的結(jié)構(gòu)

20規(guī)劃方式當(dāng)某個命令句子送入系統(tǒng)時，PULP-Ⅰ就進入規(guī)劃方式。右圖表示PULP-Ⅰ系統(tǒng)在規(guī)劃方式下的結(jié)構(gòu)。檢索混合規(guī)劃方塊目標(biāo)檢驗匹配單一規(guī)劃規(guī)劃輸入命令響應(yīng)過程模型圖8.10規(guī)劃方式下PULP-Ⅰ系統(tǒng)的結(jié)構(gòu)

21PULP-Ⅰ規(guī)劃系統(tǒng)的規(guī)劃性能與STRIPS及ABSTRIPS系統(tǒng)相比，PULP-Ⅰ系統(tǒng)的規(guī)劃時間幾乎可以略之不計。這就表明，具有學(xué)習(xí)能力的機器人規(guī)劃系統(tǒng)，能夠極大地提高系統(tǒng)的規(guī)劃速度。具有學(xué)習(xí)能力的機器人問題求解與規(guī)劃系統(tǒng)PULP-Ⅰ已經(jīng)顯示出規(guī)劃性能的改善。這個改善不僅表現(xiàn)在規(guī)劃速度方面，而且也表現(xiàn)在建立復(fù)雜的規(guī)劃能力方面。22圖8.11PULP-Ⅰ模擬例子的初始世界模型23圖8.12規(guī)劃時間的比較248.2.5RobotPlanningBasedonExpertSystem

基于專家系統(tǒng)的機器人規(guī)劃Definition:機器人規(guī)劃專家系統(tǒng)就是用專家系統(tǒng)的結(jié)構(gòu)和技術(shù)建立起來的機器人規(guī)劃系統(tǒng)。Shortcomings：（管理式學(xué)習(xí)機器人規(guī)劃系統(tǒng)）：表達子句的語義網(wǎng)絡(luò)結(jié)構(gòu)過于復(fù)雜。復(fù)雜的系統(tǒng)內(nèi)部數(shù)據(jù)結(jié)構(gòu)，

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

STRIPS

系列快得多，然而它仍然不夠快。251.系統(tǒng)結(jié)構(gòu)和規(guī)劃機理機器人用戶機器人專家知識用戶接口知識庫推理機控制策略工具專家系統(tǒng)知識獲取說明與分析問題輸入或新情況描述回答問題或建議與解釋圖8.14機器人規(guī)劃專家系統(tǒng)的結(jié)構(gòu)26Systemarchitecture基于規(guī)劃的機器人規(guī)劃專家系統(tǒng)由5個部分組成，如圖8.14所示。知識庫控制策略推理機知識獲取解釋與說明基于規(guī)則的專家系統(tǒng)的目標(biāo)就是要通過逐條執(zhí)行規(guī)則及其有關(guān)操作來逐步地改變總數(shù)據(jù)庫的狀況，直到得到一個可接受的數(shù)據(jù)庫(稱為目標(biāo)數(shù)據(jù)庫)為止。272.ROPESrobotplanningsystemROPES系統(tǒng)，即RObot

PlanningExpertSystems(機器人規(guī)劃專家系統(tǒng)，Cai&Fu,1985)。采用基于規(guī)則的系統(tǒng)和C-PROLOG程序設(shè)計語言來建立這一系統(tǒng)。下圖（圖8.15）表示ROPES規(guī)劃系統(tǒng)的簡化框圖。專家知識知識庫搜索、匹配與回溯推理機

用戶知識獲取輸入或提問回答問題或規(guī)劃序列28Mailstrategies

本系統(tǒng)的主要控制策略為searching，matchingandback-tracking。

世界模型與假設(shè)

ROPES系統(tǒng)含有幾個子系統(tǒng)，它們分別用于進行機器人的任務(wù)規(guī)劃、路徑規(guī)劃、搬運作業(yè)規(guī)劃以及尋找機器人無碰撞路徑。這里僅以搬運作業(yè)規(guī)劃系統(tǒng)為例來說明本系統(tǒng)的一些具體問題。29圖8.16機器人裝配線環(huán)境模型30圖8.17搬運機器人操作流程圖31Planningresults本規(guī)劃系統(tǒng)共使用15條規(guī)則，每條規(guī)則包含二條子規(guī)則，因此實際上共使用30條規(guī)則。把這些規(guī)則存入系統(tǒng)的知識庫內(nèi),并與C-PROLOG的可估價謂詞(evaluatedpredicates)一起使用，能夠很快得到推理結(jié)果。

表8.2各規(guī)劃系統(tǒng)世界模型的比較32圖8.18規(guī)劃速度的比較33ROPES系統(tǒng)結(jié)論本規(guī)劃系統(tǒng)與STRIPS、ABSTRIPS以及PULP-Ⅰ比較，具有更好的規(guī)劃性能和更快的規(guī)劃速度。本系統(tǒng)能夠輸出某個指定任務(wù)的所有可能解答序列，而以前的其它系統(tǒng)只能給出任意一個解。本系統(tǒng)可用于含有不確定問題的規(guī)劃;這時規(guī)劃將變得復(fù)雜起來。這時可用概率、可信度和(或)模糊理論來表示知識和任務(wù)，并求解此類問題。C-PROLOG語言對許多規(guī)劃和決策系統(tǒng)是合適和有效的；它比LISP更加有效而且簡單。當(dāng)規(guī)劃系統(tǒng)的操作符數(shù)目增大時，本系統(tǒng)的規(guī)劃時間增加很少。因此，ROPES系統(tǒng)特別適用于大規(guī)模的規(guī)劃系統(tǒng)。348.3路徑規(guī)劃PathPlanning

8.3.1機器人路徑規(guī)劃的主要方法和發(fā)展趨勢1.移動機器人路徑規(guī)劃的