南郵自動(dòng)化人工智能8-自動(dòng)規(guī)劃課件

第八章自動(dòng)規(guī)劃

第八章自動(dòng)規(guī)劃教學(xué)內(nèi)容：介紹自動(dòng)規(guī)劃的基本概念和各種規(guī)劃系統(tǒng)。教學(xué)重點(diǎn)：機(jī)器人規(guī)劃的作用與任務(wù)、積木世界的規(guī)劃系統(tǒng)、基于模擬退火算法的機(jī)器人局部路徑規(guī)劃。教學(xué)難點(diǎn)：Strips規(guī)劃系統(tǒng)。教學(xué)方法：課堂教學(xué)為主，注意結(jié)合例子來(lái)說(shuō)明抽象概念。教學(xué)要求：本章為選修內(nèi)容，掌握機(jī)器人規(guī)劃的作用與任務(wù)，并一般了解有哪幾種規(guī)劃方法。教學(xué)內(nèi)容：介紹自動(dòng)規(guī)劃的基本概念和各種規(guī)劃系統(tǒng)。第一節(jié)自動(dòng)規(guī)劃概述

第一節(jié)自動(dòng)規(guī)劃概述8.1.1規(guī)劃的概念和作用

1、規(guī)劃的概念及作用

規(guī)劃的概念：規(guī)劃是一種重要的問(wèn)題求解技術(shù)，它從某個(gè)特定的問(wèn)題狀態(tài)出發(fā)，尋求一系列行為動(dòng)作，并建立一個(gè)操作序列，直到求得目標(biāo)狀態(tài)為止。

規(guī)劃的作用：規(guī)劃可用來(lái)監(jiān)控問(wèn)題求解過(guò)程，并能夠在造成較大的危害之前發(fā)現(xiàn)差錯(cuò)。規(guī)劃的好處可歸納為簡(jiǎn)化搜索、解決目標(biāo)矛盾以及為差錯(cuò)補(bǔ)償提供基礎(chǔ)。8.1.1規(guī)劃的概念和作用

戰(zhàn)略規(guī)劃：就是組織制定長(zhǎng)期目標(biāo)并將其付諸實(shí)施。第一階段確定目標(biāo)；第二階段制定規(guī)劃。

城市規(guī)劃：指城市政府為了實(shí)現(xiàn)一定時(shí)期內(nèi)經(jīng)濟(jì)社會(huì)發(fā)展目標(biāo)，確定城市性質(zhì)，規(guī)模和發(fā)展方向，合理利用土地，協(xié)調(diào)空間布局和各項(xiàng)建設(shè)所作的綜合部署和具體安排。人生規(guī)劃：根據(jù)社會(huì)發(fā)展的需要和個(gè)人發(fā)展的志向，對(duì)自己的未來(lái)的發(fā)展道路做出一種預(yù)先的策劃和設(shè)計(jì)。包括健康規(guī)劃，事業(yè)規(guī)劃，情感規(guī)劃，晚景規(guī)劃。戰(zhàn)略規(guī)劃：就是組織制定長(zhǎng)期目標(biāo)并將其付諸實(shí)施。第一階子規(guī)劃的分層結(jié)構(gòu)例子

子規(guī)劃的分層結(jié)構(gòu)例子

規(guī)劃的作用：科學(xué)規(guī)劃方法不僅對(duì)國(guó)家和社會(huì)貢獻(xiàn)很大，對(duì)于個(gè)人學(xué)習(xí)和工作也極為有益。規(guī)劃的作用：科學(xué)規(guī)劃方法不僅對(duì)國(guó)家和社會(huì)貢獻(xiàn)很大，對(duì)8.1.2規(guī)劃的分類(lèi)與問(wèn)題分解途徑

1、規(guī)劃的分類(lèi)

(1):按規(guī)劃內(nèi)容分

(2):按規(guī)劃方法分

(3):按規(guī)劃性質(zhì)分任務(wù)規(guī)劃(高層規(guī)劃)

路徑規(guī)劃(中層規(guī)劃)

軌跡規(guī)劃(底層規(guī)劃)8.1.2規(guī)劃的分類(lèi)與問(wèn)題分解途徑2、問(wèn)題分解途徑及方法把某些較復(fù)雜的問(wèn)題分解為一些較小的子問(wèn)題。有兩條實(shí)現(xià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)題。2、問(wèn)題分解途徑及方法3、域的預(yù)測(cè)和規(guī)劃的修正

(1)域的預(yù)測(cè)規(guī)劃方法的成功取決于問(wèn)題論域的另一特性--預(yù)測(cè)。如果通過(guò)在實(shí)際上執(zhí)行某個(gè)操作序列來(lái)尋找問(wèn)題的解答，那末在這個(gè)過(guò)程的任何一步都能確信該步的結(jié)果。但對(duì)于不可預(yù)測(cè)的論域，最好能考慮可能的結(jié)果的集合，這些結(jié)果很可能按照它們出現(xiàn)的可能性以某個(gè)次序排列。然后，產(chǎn)生一個(gè)規(guī)劃，并試圖去執(zhí)行這個(gè)規(guī)劃。

(2)規(guī)劃的修正如果規(guī)劃在執(zhí)行中失敗了，那么就需要對(duì)它進(jìn)行修訂，為便于修訂，在規(guī)劃過(guò)程中不僅要記下規(guī)劃的執(zhí)行步驟，而且也要記下每一步驟必須被執(zhí)行的理由。大多規(guī)則的執(zhí)行主要是按目標(biāo)定向模式工作的。在種模式下，規(guī)劃系統(tǒng)從目標(biāo)狀態(tài)向可達(dá)到的初始狀態(tài)進(jìn)行搜索。

3、域的預(yù)測(cè)和規(guī)劃的修正8.1.3規(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)行。

(空端：即死端，指無(wú)法從它到達(dá)目標(biāo)的端點(diǎn)。)(5)檢驗(yàn)殆正確的解答，并應(yīng)用具體的技術(shù)使之完全正確。8.1.3規(guī)劃系統(tǒng)的任務(wù)與方法

下面討論能夠執(zhí)行上述5項(xiàng)任務(wù)的方法。

1、選擇和應(yīng)用規(guī)則在選擇合適的應(yīng)用規(guī)則時(shí)最廣泛采用的技術(shù)是：首先要查出期望目標(biāo)狀態(tài)與現(xiàn)有狀態(tài)之間的差別集合，然后辨別出那些與減少這些差別有關(guān)的規(guī)則。

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í)，可以終止該路徑的搜索。

下面討論能夠執(zhí)行上述5項(xiàng)任務(wù)的方法。3、修正殆正確解一個(gè)求解殆可分解問(wèn)題的辦法是：當(dāng)執(zhí)行與所提出的解答相對(duì)應(yīng)的操作符序列時(shí)，檢查求得的狀態(tài)，并把它與期望目標(biāo)加以比較。修正一個(gè)殆正確的解答的較好辦法是:注意有關(guān)出錯(cuò)的知識(shí)，然后加以直接修正。修正一個(gè)殆正確的解答的更好辦法是:實(shí)際上不是對(duì)解答進(jìn)行全面的修正,而是不完全確定地讓它們保留到最后的可能時(shí)刻。3、修正殆正確解第二節(jié)任務(wù)規(guī)劃第二節(jié)任務(wù)規(guī)劃8.2.1積木世界的機(jī)器人問(wèn)題

機(jī)器人問(wèn)題既比較簡(jiǎn)單，又很直觀。在機(jī)器人問(wèn)題的典型表示中，機(jī)器人能夠執(zhí)行一套動(dòng)作。在這個(gè)例子中機(jī)器人能夠執(zhí)行的動(dòng)作舉例如下：

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

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

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

putdown(a)：把積木a放置到桌面上。要求動(dòng)作之前機(jī)械手已抓住積木a。8.2.1積木世界的機(jī)器人問(wèn)題

采用狀態(tài)描述作為數(shù)據(jù)庫(kù)的產(chǎn)生式系統(tǒng)是一種最簡(jiǎn)單的問(wèn)題求解系統(tǒng)。機(jī)器人問(wèn)題的狀態(tài)描述和目標(biāo)描述均可用謂詞邏輯公式構(gòu)成。為了指定機(jī)器人所執(zhí)行的操作和執(zhí)行操作的結(jié)果，需要應(yīng)用下列謂詞：

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

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

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

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

HANDEMPTY：械手為空手。采用狀態(tài)描述作為數(shù)據(jù)庫(kù)的產(chǎn)生式系統(tǒng)是一種最簡(jiǎn)舉例：積木世界由一些有標(biāo)記的立方形積木，互相堆迭在一起構(gòu)成；機(jī)器人有個(gè)可移動(dòng)的機(jī)械手，它可以抓起積木塊并移動(dòng)積木從一處至另一處。提問(wèn)：請(qǐng)同學(xué)就圖8.1積木世界的機(jī)器人問(wèn)題應(yīng)用謂詞公式的合取描述此目標(biāo)為：

ON(B，C)∧ON(A，B)。

?初始狀態(tài)的描述:圖8.1積木世界的機(jī)器人問(wèn)題舉例：積木世界由一些有標(biāo)記的立方形積木，互相堆迭在一圖8.18.2.2用F規(guī)則求解規(guī)劃序列

采用F規(guī)則表示機(jī)器人的動(dòng)作，這是一個(gè)叫做STRIPS規(guī)劃系統(tǒng)的規(guī)則，它由3部分組成。第一部分是先決條件。為了使F規(guī)則能夠應(yīng)用到狀態(tài)描述中去。第二部分是一個(gè)叫做刪除表的謂詞。當(dāng)一條規(guī)則被應(yīng)用于某個(gè)狀態(tài)描述或數(shù)據(jù)庫(kù)時(shí)，就從該數(shù)據(jù)庫(kù)刪去刪除表的內(nèi)容。第三部分叫做添加表。當(dāng)把某條規(guī)則應(yīng)用于某數(shù)據(jù)庫(kù)時(shí)，就把該添加表的內(nèi)容添進(jìn)該數(shù)據(jù)庫(kù)。8.2.2用F規(guī)則求解規(guī)劃序列

對(duì)于堆積木的例子中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)對(duì)于堆積木的例子中move這個(gè)動(dòng)作可以表示如下：

如果move為此機(jī)器人僅有的操作符或適用動(dòng)作，那么，可以生成如下圖所示的搜索圖或搜索樹(shù)：

8.2表示move動(dòng)作的搜索樹(shù)如果move為此機(jī)器人僅有的操作符或適用動(dòng)作，那么，

下面更具體地考慮圖8.1中所示的例子，機(jī)器人的4個(gè)動(dòng)作(或操作符)可用STRIPS形式表示如下：

(1)stack(X,Y)

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

添加表：HANDEMPTY，ON(X，Y)(2)unstack(X,Y)

先決條件：HANDEMPTY∧ON(X，Y)∧CLEAR(X)

刪除表：ON(X，Y)，HANDEMPTY

添加表：HOLDING(X)，CLEAR(Y)下面更具體地考慮圖8.1中所示的例子，機(jī)器人的4個(gè)動(dòng)

(3)pickup(X)

先決條件：ONTABLE(X)∧CLEAR(X)∧HANDEMPTY

刪除表：ONTABLE(X)∧HANDENPTY

添加表：HOLDING(X)(4)putdown(X)

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

添加表：ONTABLE(X)，HANDEMPTY

假定目標(biāo)為8.1所示的狀態(tài)，即

ON(B,C)∧ON(A,B)(3)pickup(X)

從圖8.1（a）所示的初始狀態(tài)描述開(kāi)始正向操作，只有unstack(C,A)和pickup(B)兩個(gè)動(dòng)作可以應(yīng)用F規(guī)則。圖8.3所示給出這個(gè)問(wèn)題的全部狀態(tài)空間，并用粗線指出了從初始狀態(tài)(用S0標(biāo)記)到目標(biāo)狀態(tài)(用G標(biāo)記)的解答路徑。

與習(xí)慣的狀態(tài)空間圖畫(huà)法不同的是，這個(gè)狀態(tài)空間圖顯出問(wèn)題的對(duì)稱(chēng)性，而沒(méi)有把初始節(jié)點(diǎn)S0放在圖的頂點(diǎn)上。此外，要注意到本例中的每條規(guī)則都有一條逆規(guī)則，如圖7.3所示。例:積木世界機(jī)器人問(wèn)題的狀態(tài)空間(見(jiàn)P216-217)從圖8.1（a）所示的初始狀態(tài)描圖8.3

積木世界機(jī)器人問(wèn)題的狀態(tài)空間圖8.3積木世界機(jī)器人問(wèn)題的狀態(tài)空間

沿著粗線所示的支路，從初始狀態(tài)開(kāi)始，正向地依次讀出連接弧線上的F規(guī)則，就得到一個(gè)能夠達(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ī)劃。

沿著粗線所示的支路，從初始狀態(tài)開(kāi)始，正向地依次讀出連接8.3.1STRIPS系統(tǒng)的組成

STRIPS（StanfordResearchInstituteProblemSolver）整個(gè)STRIPS系統(tǒng)的組成如下：

(1)世界模型。為一階謂詞演算公式。

(2)操作符(F規(guī)則)。包括先決條件、刪除表和添加表。

(3)操作方法。應(yīng)用狀態(tài)空間表示和中間-結(jié)局分析。例如：狀態(tài)：(M，G)，包括初始狀態(tài)、中間狀態(tài)和目標(biāo)狀態(tài)。初始狀態(tài)：(M0，(G0))

目標(biāo)狀態(tài)：得到一個(gè)世界模型，其中不遺留任何未滿足的目標(biāo)。8.3.1STRIPS系統(tǒng)的組成8.2.3STRIPS系統(tǒng)規(guī)劃過(guò)程

每個(gè)STRIPS問(wèn)題的解答為某個(gè)實(shí)現(xiàn)目標(biāo)的操作符序列，即達(dá)到目標(biāo)的規(guī)劃。下面舉例說(shuō)明STRIPS系統(tǒng)規(guī)劃的求解過(guò)程。例1考慮STRIPS系統(tǒng)一個(gè)比較簡(jiǎn)單的情況，即要求機(jī)器人到鄰室去取回一個(gè)箱子。機(jī)器人的初始狀態(tài)和目標(biāo)狀態(tài)的世界模型示于圖8.4。BOX1機(jī)器人箱子r1r2dBOX1機(jī)器人箱子r1r2d圖8.4

STRIPS的一個(gè)簡(jiǎn)化模型8.2.3STRIPS系統(tǒng)規(guī)劃過(guò)程BOX1機(jī)器人

設(shè)有兩個(gè)操作符，即gothru和pushthru(“走過(guò)”和“推過(guò)”)，分別描述于下：

OP1：gothru(d,r1,r2)；機(jī)器人通過(guò)房間r1

和房間r2

之間的d，即機(jī)器人從房間r1

走過(guò)門(mén)d而進(jìn)入房間r2。先決條件：機(jī)器人在房間r1

內(nèi)，而且門(mén)d連接r1

和r2

兩個(gè)房間。

INROOM(ROBOT，r1)∧CONNECTS(d,r1,r2)；刪除表：INROOM(ROBOT，S)；對(duì)于任何S值。添加表：INROOM(ROBOT，r2)。設(shè)有兩個(gè)操作符，即gothru和pus

OP2：pushthru(b,d,r1,r2)

機(jī)器人把物體b從房間r1

經(jīng)過(guò)門(mén)d推到房間r2。先決條件：INROOM(b,r1)∧INROOM(ROBOT,r1)∧CONNECTS(d,r1,r2)

刪除表：INROOM(ROBOT,S)，

INROOM(b,S);

對(duì)于任何S。添加表：INROOM(ROBOT，r2),INROOM(b,r2)。

例:采用中間-結(jié)局分析方法來(lái)逐步求解機(jī)器人規(guī)劃(見(jiàn)P219-221)例:采用中間-結(jié)局分析方法來(lái)逐步求解機(jī)器人

差別表假定這個(gè)問(wèn)題的初始狀態(tài)M0和目標(biāo)G0如下：

M0：INROOM(ROBOT，R1)∧INROOM(BOX1,R2)∧CONNECTS(D1，R1，R2)

G0：INROOM(ROBOT,R1)∧INROOM(BOX1，R1)∧CONNECTS(D1，R1，R2)差別表假定這個(gè)問(wèn)題的初始狀態(tài)M0和目標(biāo)G0如下：

M假定這個(gè)問(wèn)題的初始狀態(tài)M0和目標(biāo)G0如下：

M0：INROOM(ROBOT，R1)∧INROOM(BOX1,R2)∧CONNECTS(D1，R1，R2)

G0：INROOM(ROBOT,R1)∧INROOM(BOX1，R1)∧CONNECTS(D1，R1，R2)BOX1機(jī)器人箱子R1R2DBOX1機(jī)器人箱子R1R2D圖8.4

STRIPS的一個(gè)簡(jiǎn)化模型假定這個(gè)問(wèn)題的初始狀態(tài)M0和目標(biāo)G0如下：

M0：INROO基于中間結(jié)局分析方法的規(guī)劃求解:采用中間結(jié)局分析方法來(lái)逐步求解這個(gè)機(jī)器人規(guī)劃：

①doGPS的主循環(huán)迭代，untilM0與G0匹配為止。

②begin。

③G0

不能滿足M0，找出M0與G0的差別。盡管這個(gè)問(wèn)題不能馬上得到解決，但是如果初始數(shù)據(jù)庫(kù)含有語(yǔ)句INROOM(BOX1，R1)，那么這個(gè)問(wèn)題的求解過(guò)程就可以得到繼續(xù)。GPS找到它們的差別:d1

為INROOM(BOX1，R1)，即要把箱子(物體)放到目標(biāo)房間R1

內(nèi)。

④選取操作符：一個(gè)與減少差別d1有關(guān)的操作符。根據(jù)差別表，STRIPS選取操作符為：

OP2：pushthru(BOX1,d,r1,R1)基于中間結(jié)局分析方法的規(guī)劃求解:采用中間結(jié)局分析方法來(lái)逐步求⑤消去差別d1,為OP2設(shè)置先決條件G1為：

G1：INROOM(BOX1,r1)∧INROOM(ROBOT,r1)∧CONNECTS(d,r1,R1)

這個(gè)先決條件被設(shè)定為子目標(biāo)，而且STRIPS試圖從M0到達(dá)G1。盡管G1仍然不能得到滿足，也不可能馬上找到這個(gè)問(wèn)題的直接解答。不過(guò)STRIP發(fā)現(xiàn)：

如果r1=R2,d=D1，當(dāng)前數(shù)據(jù)庫(kù)含有

INROOM(ROBOT，R1)

那么此過(guò)程能夠繼續(xù)進(jìn)行?，F(xiàn)在新的子目標(biāo)G1為：

G1：INROOM(BOX1，R2)∧INROOM(ROBOT，R2)∧CONNECTS(D1，R2，R1)⑤消去差別d1,為OP2設(shè)置先決條件G1為：

G1：⑥GPS(p)；重復(fù)第3步至第5步，迭代調(diào)用，以求解此問(wèn)題。

步驟3：G1和M0的差別d2為INROOM(ROBOT，R2)即要求機(jī)器人移到房間R2。

步驟4：根據(jù)差別表，對(duì)應(yīng)于d2的相關(guān)操作符為

OP1：gothru(d,r1,R2)

步驟5：OP1的先決條件為：

G2：INROOM(ROBOT，R1)∧CONNECTS(d,r1,R2)

步驟6：應(yīng)用置換式r1=R1

和d=D1，

STRIPS系統(tǒng)能夠達(dá)到G2。⑥GPS(p)；重復(fù)第3步至第5步，迭代調(diào)用，以求解此問(wèn)題

⑦把操作符gothru(D1,R1,R2)作用于M0，求出中間狀態(tài)M1：

刪除表：INROOM(ROBOT，R1)

添加表：INROOM(ROBOT，R2)

M1：INROOM(ROBOT，R2)

INROOM(BOX1，R2)

CONNECTS(D1，R1，R2)

把操作符pushthru應(yīng)用中間狀態(tài)M1，

刪除表：INROOM(ROBOT，R2)，

INROOM(BOX1，R2)

添加表：INROOM(ROBOT，R1)，

INROOM(BOX1，R1)⑦把操作符gothru(D1,R1,R2)作用于M0

得到另一中間狀態(tài)M2為：

M2：INROOM(ROBOT，R1)

INROOM(BOX1，R1)

CONNECTS(D1，R1，R2)

M2=G0

⑧end。得到另一中間狀態(tài)M2為：

M2：INROOM(RO由于M2與G0匹配，所以通過(guò)中間結(jié)局分析解答了這個(gè)機(jī)器人規(guī)劃問(wèn)題。在求解過(guò)程中，所用到的STRIPS規(guī)則為操作符OP1和OP2，即

gothru(D1,R1,R2),

pushthru(BOX1,D1,R2,R1)中間狀態(tài)模型M1和M2，即子目標(biāo)G1和G2，M2與目標(biāo)世界模型G0相同。

因此，得到的最后規(guī)劃為｛OP1，OP2｝，即

｛gothru(D1，R1，R2)，

pushthru(BOX1,D1,R2,R1)｝由于M2與G0匹配，所以通過(guò)中間結(jié)局分析解答了這BOX1機(jī)器人箱子R1R2DBOX1機(jī)器人箱子R1R2D圖8.5中間目標(biāo)狀態(tài)的目標(biāo)模型（a）中間目標(biāo)狀態(tài)M1（b）中間目標(biāo)狀態(tài)M2BOX1機(jī)器人箱子R1R2DBOX1機(jī)器人箱子R1R2D圖8圖8.6機(jī)器人規(guī)劃例題的搜索圖

圖8.6機(jī)器人規(guī)劃例題的搜索圖

模擬退火算法來(lái)源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o(wú)序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小

。該思想是由N.Metropolis等人于1953年提出。1983年,S.Kirkpatrick等成功地將退火思想引入到組合優(yōu)化領(lǐng)域。它是基于Monte-Carlo迭代求解策略的一種隨機(jī)尋優(yōu)算法，其出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過(guò)程與一般組合優(yōu)化問(wèn)題之間的相似性。模擬退火算法從某一較高初溫出發(fā)，伴隨溫度參數(shù)的不斷下降,結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解，即在局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)。模擬退火算法是一種通用的優(yōu)化算法，理論上算法具有概率的全局優(yōu)化性能,目前已在工程中得到了廣泛應(yīng)用，諸如VLSI、生產(chǎn)調(diào)度、控制工程、機(jī)器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)、信號(hào)處理等領(lǐng)域。

模擬退火算法來(lái)源于固體退火原理，將固體加溫至充分高，蟻群優(yōu)化算法是模擬螞蟻覓食的原理，設(shè)計(jì)出的一種群集智能算法。螞蟻在覓食過(guò)程中能夠在其經(jīng)過(guò)的路徑上留下一種稱(chēng)之為信息素的物質(zhì)，并在覓食過(guò)程中能夠感知這種物質(zhì)的強(qiáng)度，并指導(dǎo)自己行動(dòng)方向，它們總是朝著該物質(zhì)強(qiáng)度高的方向移動(dòng)，因此大量螞蟻組成的集體覓食就表現(xiàn)為一種對(duì)信息素的正反饋現(xiàn)象。某一條路徑越短，路徑上經(jīng)過(guò)的螞蟻越多，其信息素遺留的也就越多，信息素的濃度也就越高，螞蟻選擇這條路徑的幾率也就越高，由此構(gòu)成的正反饋過(guò)程，從而逐漸的逼近最優(yōu)路徑，找到最優(yōu)路徑。蟻群優(yōu)化算法是模擬螞蟻覓食的原理，設(shè)計(jì)出的一種群集智能算法。第八章自動(dòng)規(guī)劃

第八章自動(dòng)規(guī)劃教學(xué)內(nèi)容：介紹自動(dòng)規(guī)劃的基本概念和各種規(guī)劃系統(tǒng)。教學(xué)重點(diǎn)：機(jī)器人規(guī)劃的作用與任務(wù)、積木世界的規(guī)劃系統(tǒng)、基于模擬退火算法的機(jī)器人局部路徑規(guī)劃。教學(xué)難點(diǎn)：Strips規(guī)劃系統(tǒng)。教學(xué)方法：課堂教學(xué)為主，注意結(jié)合例子來(lái)說(shuō)明抽象概念。教學(xué)要求：本章為選修內(nèi)容，掌握機(jī)器人規(guī)劃的作用與任務(wù)，并一般了解有哪幾種規(guī)劃方法。教學(xué)內(nèi)容：介紹自動(dòng)規(guī)劃的基本概念和各種規(guī)劃系統(tǒng)。第一節(jié)自動(dòng)規(guī)劃概述

第一節(jié)自動(dòng)規(guī)劃概述8.1.1規(guī)劃的概念和作用

1、規(guī)劃的概念及作用

規(guī)劃的概念：規(guī)劃是一種重要的問(wèn)題求解技術(shù)，它從某個(gè)特定的問(wèn)題狀態(tài)出發(fā)，尋求一系列行為動(dòng)作，并建立一個(gè)操作序列，直到求得目標(biāo)狀態(tài)為止。

規(guī)劃的作用：規(guī)劃可用來(lái)監(jiān)控問(wèn)題求解過(guò)程，并能夠在造成較大的危害之前發(fā)現(xiàn)差錯(cuò)。規(guī)劃的好處可歸納為簡(jiǎn)化搜索、解決目標(biāo)矛盾以及為差錯(cuò)補(bǔ)償提供基礎(chǔ)。8.1.1規(guī)劃的概念和作用

戰(zhàn)略規(guī)劃：就是組織制定長(zhǎng)期目標(biāo)并將其付諸實(shí)施。第一階段確定目標(biāo)；第二階段制定規(guī)劃。

城市規(guī)劃：指城市政府為了實(shí)現(xiàn)一定時(shí)期內(nèi)經(jīng)濟(jì)社會(huì)發(fā)展目標(biāo)，確定城市性質(zhì)，規(guī)模和發(fā)展方向，合理利用土地，協(xié)調(diào)空間布局和各項(xiàng)建設(shè)所作的綜合部署和具體安排。人生規(guī)劃：根據(jù)社會(huì)發(fā)展的需要和個(gè)人發(fā)展的志向，對(duì)自己的未來(lái)的發(fā)展道路做出一種預(yù)先的策劃和設(shè)計(jì)。包括健康規(guī)劃，事業(yè)規(guī)劃，情感規(guī)劃，晚景規(guī)劃。戰(zhàn)略規(guī)劃：就是組織制定長(zhǎng)期目標(biāo)并將其付諸實(shí)施。第一階子規(guī)劃的分層結(jié)構(gòu)例子

子規(guī)劃的分層結(jié)構(gòu)例子

規(guī)劃的作用：科學(xué)規(guī)劃方法不僅對(duì)國(guó)家和社會(huì)貢獻(xiàn)很大，對(duì)于個(gè)人學(xué)習(xí)和工作也極為有益。規(guī)劃的作用：科學(xué)規(guī)劃方法不僅對(duì)國(guó)家和社會(huì)貢獻(xiàn)很大，對(duì)8.1.2規(guī)劃的分類(lèi)與問(wèn)題分解途徑

1、規(guī)劃的分類(lèi)

(1):按規(guī)劃內(nèi)容分

(2):按規(guī)劃方法分

(3):按規(guī)劃性質(zhì)分任務(wù)規(guī)劃(高層規(guī)劃)

路徑規(guī)劃(中層規(guī)劃)

軌跡規(guī)劃(底層規(guī)劃)8.1.2規(guī)劃的分類(lèi)與問(wèn)題分解途徑2、問(wèn)題分解途徑及方法把某些較復(fù)雜的問(wèn)題分解為一些較小的子問(wèn)題。有兩條實(shí)現(xià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)題。2、問(wèn)題分解途徑及方法3、域的預(yù)測(cè)和規(guī)劃的修正

(1)域的預(yù)測(cè)規(guī)劃方法的成功取決于問(wèn)題論域的另一特性--預(yù)測(cè)。如果通過(guò)在實(shí)際上執(zhí)行某個(gè)操作序列來(lái)尋找問(wèn)題的解答，那末在這個(gè)過(guò)程的任何一步都能確信該步的結(jié)果。但對(duì)于不可預(yù)測(cè)的論域，最好能考慮可能的結(jié)果的集合，這些結(jié)果很可能按照它們出現(xiàn)的可能性以某個(gè)次序排列。然后，產(chǎn)生一個(gè)規(guī)劃，并試圖去執(zhí)行這個(gè)規(guī)劃。

(2)規(guī)劃的修正如果規(guī)劃在執(zhí)行中失敗了，那么就需要對(duì)它進(jìn)行修訂，為便于修訂，在規(guī)劃過(guò)程中不僅要記下規(guī)劃的執(zhí)行步驟，而且也要記下每一步驟必須被執(zhí)行的理由。大多規(guī)則的執(zhí)行主要是按目標(biāo)定向模式工作的。在種模式下，規(guī)劃系統(tǒng)從目標(biāo)狀態(tài)向可達(dá)到的初始狀態(tài)進(jìn)行搜索。

3、域的預(yù)測(cè)和規(guī)劃的修正8.1.3規(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)行。

(空端：即死端，指無(wú)法從它到達(dá)目標(biāo)的端點(diǎn)。)(5)檢驗(yàn)殆正確的解答，并應(yīng)用具體的技術(shù)使之完全正確。8.1.3規(guī)劃系統(tǒng)的任務(wù)與方法

下面討論能夠執(zhí)行上述5項(xiàng)任務(wù)的方法。

1、選擇和應(yīng)用規(guī)則在選擇合適的應(yīng)用規(guī)則時(shí)最廣泛采用的技術(shù)是：首先要查出期望目標(biāo)狀態(tài)與現(xiàn)有狀態(tài)之間的差別集合，然后辨別出那些與減少這些差別有關(guān)的規(guī)則。

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í)，可以終止該路徑的搜索。

下面討論能夠執(zhí)行上述5項(xiàng)任務(wù)的方法。3、修正殆正確解一個(gè)求解殆可分解問(wèn)題的辦法是：當(dāng)執(zhí)行與所提出的解答相對(duì)應(yīng)的操作符序列時(shí)，檢查求得的狀態(tài)，并把它與期望目標(biāo)加以比較。修正一個(gè)殆正確的解答的較好辦法是:注意有關(guān)出錯(cuò)的知識(shí)，然后加以直接修正。修正一個(gè)殆正確的解答的更好辦法是:實(shí)際上不是對(duì)解答進(jìn)行全面的修正,而是不完全確定地讓它們保留到最后的可能時(shí)刻。3、修正殆正確解第二節(jié)任務(wù)規(guī)劃第二節(jié)任務(wù)規(guī)劃8.2.1積木世界的機(jī)器人問(wèn)題

機(jī)器人問(wèn)題既比較簡(jiǎn)單，又很直觀。在機(jī)器人問(wèn)題的典型表示中，機(jī)器人能夠執(zhí)行一套動(dòng)作。在這個(gè)例子中機(jī)器人能夠執(zhí)行的動(dòng)作舉例如下：

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

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

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

putdown(a)：把積木a放置到桌面上。要求動(dòng)作之前機(jī)械手已抓住積木a。8.2.1積木世界的機(jī)器人問(wèn)題

采用狀態(tài)描述作為數(shù)據(jù)庫(kù)的產(chǎn)生式系統(tǒng)是一種最簡(jiǎn)單的問(wèn)題求解系統(tǒng)。機(jī)器人問(wèn)題的狀態(tài)描述和目標(biāo)描述均可用謂詞邏輯公式構(gòu)成。為了指定機(jī)器人所執(zhí)行的操作和執(zhí)行操作的結(jié)果，需要應(yīng)用下列謂詞：

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

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

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

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

HANDEMPTY：械手為空手。采用狀態(tài)描述作為數(shù)據(jù)庫(kù)的產(chǎn)生式系統(tǒng)是一種最簡(jiǎn)舉例：積木世界由一些有標(biāo)記的立方形積木，互相堆迭在一起構(gòu)成；機(jī)器人有個(gè)可移動(dòng)的機(jī)械手，它可以抓起積木塊并移動(dòng)積木從一處至另一處。提問(wèn)：請(qǐng)同學(xué)就圖8.1積木世界的機(jī)器人問(wèn)題應(yīng)用謂詞公式的合取描述此目標(biāo)為：

ON(B，C)∧ON(A，B)。

?初始狀態(tài)的描述:圖8.1積木世界的機(jī)器人問(wèn)題舉例：積木世界由一些有標(biāo)記的立方形積木，互相堆迭在一圖8.18.2.2用F規(guī)則求解規(guī)劃序列

采用F規(guī)則表示機(jī)器人的動(dòng)作，這是一個(gè)叫做STRIPS規(guī)劃系統(tǒng)的規(guī)則，它由3部分組成。第一部分是先決條件。為了使F規(guī)則能夠應(yīng)用到狀態(tài)描述中去。第二部分是一個(gè)叫做刪除表的謂詞。當(dāng)一條規(guī)則被應(yīng)用于某個(gè)狀態(tài)描述或數(shù)據(jù)庫(kù)時(shí)，就從該數(shù)據(jù)庫(kù)刪去刪除表的內(nèi)容。第三部分叫做添加表。當(dāng)把某條規(guī)則應(yīng)用于某數(shù)據(jù)庫(kù)時(shí)，就把該添加表的內(nèi)容添進(jìn)該數(shù)據(jù)庫(kù)。8.2.2用F規(guī)則求解規(guī)劃序列

對(duì)于堆積木的例子中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)對(duì)于堆積木的例子中move這個(gè)動(dòng)作可以表示如下：

如果move為此機(jī)器人僅有的操作符或適用動(dòng)作，那么，可以生成如下圖所示的搜索圖或搜索樹(shù)：

8.2表示move動(dòng)作的搜索樹(shù)如果move為此機(jī)器人僅有的操作符或適用動(dòng)作，那么，

下面更具體地考慮圖8.1中所示的例子，機(jī)器人的4個(gè)動(dòng)作(或操作符)可用STRIPS形式表示如下：

(1)stack(X,Y)

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

添加表：HANDEMPTY，ON(X，Y)(2)unstack(X,Y)

先決條件：HANDEMPTY∧ON(X，Y)∧CLEAR(X)

刪除表：ON(X，Y)，HANDEMPTY

添加表：HOLDING(X)，CLEAR(Y)下面更具體地考慮圖8.1中所示的例子，機(jī)器人的4個(gè)動(dòng)

(3)pickup(X)

先決條件：ONTABLE(X)∧CLEAR(X)∧HANDEMPTY

刪除表：ONTABLE(X)∧HANDENPTY

添加表：HOLDING(X)(4)putdown(X)

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

添加表：ONTABLE(X)，HANDEMPTY

假定目標(biāo)為8.1所示的狀態(tài)，即

ON(B,C)∧ON(A,B)(3)pickup(X)

從圖8.1（a）所示的初始狀態(tài)描述開(kāi)始正向操作，只有unstack(C,A)和pickup(B)兩個(gè)動(dòng)作可以應(yīng)用F規(guī)則。圖8.3所示給出這個(gè)問(wèn)題的全部狀態(tài)空間，并用粗線指出了從初始狀態(tài)(用S0標(biāo)記)到目標(biāo)狀態(tài)(用G標(biāo)記)的解答路徑。

與習(xí)慣的狀態(tài)空間圖畫(huà)法不同的是，這個(gè)狀態(tài)空間圖顯出問(wèn)題的對(duì)稱(chēng)性，而沒(méi)有把初始節(jié)點(diǎn)S0放在圖的頂點(diǎn)上。此外，要注意到本例中的每條規(guī)則都有一條逆規(guī)則，如圖7.3所示。例:積木世界機(jī)器人問(wèn)題的狀態(tài)空間(見(jiàn)P216-217)從圖8.1（a）所示的初始狀態(tài)描圖8.3

積木世界機(jī)器人問(wèn)題的狀態(tài)空間圖8.3積木世界機(jī)器人問(wèn)題的狀態(tài)空間

沿著粗線所示的支路，從初始狀態(tài)開(kāi)始，正向地依次讀出連接弧線上的F規(guī)則，就得到一個(gè)能夠達(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ī)劃。

沿著粗線所示的支路，從初始狀態(tài)開(kāi)始，正向地依次讀出連接8.3.1STRIPS系統(tǒng)的組成

STRIPS（StanfordResearchInstituteProblemSolver）整個(gè)STRIPS系統(tǒng)的組成如下：

(1)世界模型。為一階謂詞演算公式。

(2)操作符(F規(guī)則)。包括先決條件、刪除表和添加表。

(3)操作方法。應(yīng)用狀態(tài)空間表示和中間-結(jié)局分析。例如：狀態(tài)：(M，G)，包括初始狀態(tài)、中間狀態(tài)和目標(biāo)狀態(tài)。初始狀態(tài)：(M0，(G0))

目標(biāo)狀態(tài)：得到一個(gè)世界模型，其中不遺留任何未滿足的目標(biāo)。8.3.1STRIPS系統(tǒng)的組成8.2.3STRIPS系統(tǒng)規(guī)劃過(guò)程

每個(gè)STRIPS問(wèn)題的解答為某個(gè)實(shí)現(xiàn)目標(biāo)的操作符序列，即達(dá)到目標(biāo)的規(guī)劃。下面舉例說(shuō)明STRIPS系統(tǒng)規(guī)劃的求解過(guò)程。例1考慮STRIPS系統(tǒng)一個(gè)比較簡(jiǎn)單的情況，即要求機(jī)器人到鄰室去取回一個(gè)箱子。機(jī)器人的初始狀態(tài)和目標(biāo)狀態(tài)的世界模型示于圖8.4。BOX1機(jī)器人箱子r1r2dBOX1機(jī)器人箱子r1r2d圖8.4

STRIPS的一個(gè)簡(jiǎn)化模型8.2.3STRIPS系統(tǒng)規(guī)劃過(guò)程BOX1機(jī)器人

設(shè)有兩個(gè)操作符，即gothru和pushthru(“走過(guò)”和“推過(guò)”)，分別描述于下：

OP1：gothru(d,r1,r2)；機(jī)器人通過(guò)房間r1

和房間r2

之間的d，即機(jī)器人從房間r1

走過(guò)門(mén)d而進(jìn)入房間r2。先決條件：機(jī)器人在房間r1

內(nèi)，而且門(mén)d連接r1

和r2

兩個(gè)房間。

INROOM(ROBOT，r1)∧CONNECTS(d,r1,r2)；刪除表：INROOM(ROBOT，S)；對(duì)于任何S值。添加表：INROOM(ROBOT，r2)。設(shè)有兩個(gè)操作符，即gothru和pus

OP2：pushthru(b,d,r1,r2)

機(jī)器人把物體b從房間r1

經(jīng)過(guò)門(mén)d推到房間r2。先決條件：INROOM(b,r1)∧INROOM(ROBOT,r1)∧CONNECTS(d,r1,r2)

刪除表：INROOM(ROBOT,S)，

INROOM(b,S);

對(duì)于任何S。添加表：INROOM(ROBOT，r2),INROOM(b,r2)。

例:采用中間-結(jié)局分析方法來(lái)逐步求解機(jī)器人規(guī)劃(見(jiàn)P219-221)例:采用中間-結(jié)局分析方法來(lái)逐步求解機(jī)器人

差別表假定這個(gè)問(wèn)題的初始狀態(tài)M0和目標(biāo)G0如下：

M0：INROOM(ROBOT，R1)∧INROOM(BOX1,R2)∧CONNECTS(D1，R1，R2)

G0：INROOM(ROBOT,R1)∧INROOM(BOX1，R1)∧CONNECTS(D1，R1，R2)差別表假定這個(gè)問(wèn)題的初始狀態(tài)M0和目標(biāo)G0如下：

M假定這個(gè)問(wèn)題的初始狀態(tài)M0和目標(biāo)G0如下：

M0：INROOM(ROBOT，R1)∧INROOM(BOX1,R2)∧CONNECTS(D1，R1，R2)

G0：INROOM(ROBOT,R1)∧INROOM(BOX1，R1)∧CONNECTS(D1，R1，R2)BOX1機(jī)器人箱子R1R2DBOX1機(jī)器人箱子R1R2D圖8.4

STRIPS的一個(gè)簡(jiǎn)化模型假定這個(gè)問(wèn)題的初始狀態(tài)M0和目標(biāo)G0如下：

M0：INROO基于中間結(jié)局分析方法的規(guī)劃求解:采用中間結(jié)局分析方法來(lái)逐步求解這個(gè)機(jī)器人規(guī)劃：

①doGPS的主循環(huán)迭代，untilM0與G0匹配為止。

②begin。

③G0

不能滿足M0，找出M0與G0的差別。盡管這個(gè)問(wèn)題不能馬上得到解決，但是如果初始數(shù)據(jù)庫(kù)含有語(yǔ)句INROOM(BOX1，R1)，那么這個(gè)問(wèn)題的求解過(guò)程就可以得到繼續(xù)。GPS找到它們的差別:d1

為INROOM(BOX1，R1)，即要把箱子(物體)放到目標(biāo)房間R1

內(nèi)。

④選取操作符：一個(gè)與減少差別d1有關(guān)的操作符。根據(jù)差別表，STRIPS選取操作符為：

OP2：pushthru(BOX1,d,r1,R1)基于中間結(jié)局分析方法的規(guī)劃求解:采用中間結(jié)局分析方法來(lái)逐步求⑤消去差別d1,為OP2設(shè)置先決條件G1為：

G1：INROOM(BOX1,r1)∧INROOM(ROBOT,r1)∧CONNECTS(d,r1,R1)

這個(gè)先決條件被設(shè)定為子目標(biāo)，而且STRIPS試圖從M0到達(dá)G1。盡管G1仍然不能得到滿足，也不可能馬上找到這個(gè)問(wèn)題的直接解答。不過(guò)STRIP發(fā)現(xiàn)：

如果r1=R2,d=D1，當(dāng)前數(shù)據(jù)庫(kù)含有

INROOM(ROBOT，R1)

那么此過(guò)程能夠繼續(xù)進(jìn)行。現(xiàn)在新的子目標(biāo)G1為：

G1：INROOM(BOX1，R2)∧INROOM(ROBOT，R2)∧CONNECTS(D1，R2，R1)⑤消去差別d1,為OP2設(shè)置先決條件G1為：

G1：⑥GPS(p)；重復(fù)第3步至第5步，迭代調(diào)用，以求解此問(wèn)題。

步驟3：G1和M0的差別d2為INROOM(ROBOT，R2)即要求機(jī)器人移到房間R2。