第七章規(guī)劃系統(tǒng)

1、高級人工智能 第七章自動(dòng)規(guī)劃 第七章第七章 規(guī)劃系統(tǒng)規(guī)劃系統(tǒng) 自動(dòng)規(guī)劃是一種重要的問題求解技術(shù)，與一般自動(dòng)規(guī)劃是一種重要的問題求解技術(shù)，與一般問題求解相比，自動(dòng)規(guī)劃更注重于問題的求解過程，問題求解相比，自動(dòng)規(guī)劃更注重于問題的求解過程，而不是求解結(jié)果。此外，規(guī)劃要解決的問題，如機(jī)而不是求解結(jié)果。此外，規(guī)劃要解決的問題，如機(jī)器人世界問題，往往是真實(shí)世界問題，而不是比較器人世界問題，往往是真實(shí)世界問題，而不是比較抽象的數(shù)學(xué)模型問題。與前幾章介紹的求解技術(shù)相抽象的數(shù)學(xué)模型問題。與前幾章介紹的求解技術(shù)相比比,自動(dòng)規(guī)劃系統(tǒng)與專家系統(tǒng)均屬高級求解系統(tǒng)與自動(dòng)規(guī)劃系統(tǒng)與專家系統(tǒng)均屬高級求解系統(tǒng)與技術(shù)。在本章我們

2、專門研究規(guī)劃系統(tǒng)求解問題。技術(shù)。在本章我們專門研究規(guī)劃系統(tǒng)求解問題。 高級人工智能 第七章自動(dòng)規(guī)劃7.1 7.1 規(guī)劃的作用與任務(wù)規(guī)劃的作用與任務(wù) 7.1.1.7.1.1.規(guī)劃的概念規(guī)劃的概念 規(guī)劃是一種問題求解技術(shù)，它從某個(gè)特定的問題規(guī)劃是一種問題求解技術(shù)，它從某個(gè)特定的問題狀態(tài)出發(fā)，尋求一系列行為動(dòng)作，并建立一個(gè)操作序狀態(tài)出發(fā)，尋求一系列行為動(dòng)作，并建立一個(gè)操作序列，直到求得目標(biāo)狀態(tài)為止。簡而言之，規(guī)劃是一個(gè)列，直到求得目標(biāo)狀態(tài)為止。簡而言之，規(guī)劃是一個(gè)行動(dòng)過程的描述。一個(gè)總規(guī)劃可以含有若干個(gè)子規(guī)劃。行動(dòng)過程的描述。一個(gè)總規(guī)劃可以含有若干個(gè)子規(guī)劃。 高級人工智能 第七章自動(dòng)規(guī)劃7.1.2.

3、7.1.2.規(guī)劃的作用與問題分解途徑規(guī)劃的作用與問題分解途徑1.規(guī)劃的特性和作用規(guī)劃的特性和作用在日常生活中，規(guī)劃意味著在行動(dòng)之前決定行動(dòng)的進(jìn)程，或者說，在日常生活中，規(guī)劃意味著在行動(dòng)之前決定行動(dòng)的進(jìn)程，或者說，規(guī)劃這一詞指的是在執(zhí)行一個(gè)問題求解程序中任何一步之前，計(jì)算該規(guī)劃這一詞指的是在執(zhí)行一個(gè)問題求解程序中任何一步之前，計(jì)算該程序幾步的過程。一個(gè)規(guī)劃是一個(gè)行動(dòng)過程的描述。它可以像百貨清程序幾步的過程。一個(gè)規(guī)劃是一個(gè)行動(dòng)過程的描述。它可以像百貨清單一樣的沒有次序的目標(biāo)表列；但是一般來說，規(guī)劃具有某個(gè)規(guī)劃目單一樣的沒有次序的目標(biāo)表列；但是一般來說，規(guī)劃具有某個(gè)規(guī)劃目標(biāo)的蘊(yùn)含排序。例如，對于大多

4、數(shù)人來說，吃早飯之前要先洗臉和刷標(biāo)的蘊(yùn)含排序。例如，對于大多數(shù)人來說，吃早飯之前要先洗臉和刷牙或漱口。又如，一個(gè)機(jī)器人要搬動(dòng)某工件，必須先移動(dòng)到該工件附牙或漱口。又如，一個(gè)機(jī)器人要搬動(dòng)某工件，必須先移動(dòng)到該工件附近，再抓住該工件，然后帶著工件移動(dòng)。近，再抓住該工件，然后帶著工件移動(dòng)。 許多規(guī)劃所包含的步驟是含許多規(guī)劃所包含的步驟是含糊的。而且需要進(jìn)一步說明。譬如說，一個(gè)工作日規(guī)劃中有吃午飯這糊的。而且需要進(jìn)一步說明。譬如說，一個(gè)工作日規(guī)劃中有吃午飯這個(gè)目標(biāo)，但是有關(guān)細(xì)節(jié)，如在哪里吃，吃什么，什么時(shí)間去吃等等，個(gè)目標(biāo)，但是有關(guān)細(xì)節(jié)，如在哪里吃，吃什么，什么時(shí)間去吃等等，都沒有說明。與吃午飯有關(guān)的

5、詳細(xì)規(guī)劃是全日規(guī)劃的一個(gè)子規(guī)劃。大都沒有說明。與吃午飯有關(guān)的詳細(xì)規(guī)劃是全日規(guī)劃的一個(gè)子規(guī)劃。大多數(shù)規(guī)劃具有很大的子規(guī)劃結(jié)構(gòu)，規(guī)劃中的每個(gè)目標(biāo)可以由達(dá)到此目多數(shù)規(guī)劃具有很大的子規(guī)劃結(jié)構(gòu)，規(guī)劃中的每個(gè)目標(biāo)可以由達(dá)到此目標(biāo)的比較詳細(xì)的子規(guī)劃所代替。盡管最終得到的規(guī)劃是某個(gè)問題求解標(biāo)的比較詳細(xì)的子規(guī)劃所代替。盡管最終得到的規(guī)劃是某個(gè)問題求解算符的線性或分部排序，但是由算符來實(shí)現(xiàn)的目標(biāo)常常具有分層結(jié)構(gòu)，算符的線性或分部排序，但是由算符來實(shí)現(xiàn)的目標(biāo)常常具有分層結(jié)構(gòu)，如圖所示的工作日規(guī)劃就是一例。如圖所示的工作日規(guī)劃就是一例。高級人工智能 第七章自動(dòng)規(guī)劃子規(guī)劃的分層結(jié)構(gòu)例子子規(guī)劃的分層結(jié)構(gòu)例子 高級人工智能

6、 第七章自動(dòng)規(guī)劃 缺乏規(guī)劃可能導(dǎo)致不是最佳的問題求解；例如有人由于缺乏規(guī)缺乏規(guī)劃可能導(dǎo)致不是最佳的問題求解；例如有人由于缺乏規(guī)劃，為了借一本書和還一本書而跑了兩次圖書館。此外，如果目標(biāo)不劃，為了借一本書和還一本書而跑了兩次圖書館。此外，如果目標(biāo)不是獨(dú)立的，那么動(dòng)作前缺乏規(guī)劃就可能在實(shí)際上排除了該問題的某個(gè)是獨(dú)立的，那么動(dòng)作前缺乏規(guī)劃就可能在實(shí)際上排除了該問題的某個(gè)解答。例如，建筑一個(gè)變電所的規(guī)劃包括砌墻、安裝變壓器和鋪設(shè)電解答。例如，建筑一個(gè)變電所的規(guī)劃包括砌墻、安裝變壓器和鋪設(shè)電纜線等子規(guī)劃。這些子規(guī)劃不是相互獨(dú)立的，首先必須鋪設(shè)電纜，然纜線等子規(guī)劃。這些子規(guī)劃不是相互獨(dú)立的，首先必須鋪設(shè)電

7、纜，然后砌墻，最后進(jìn)行變壓器安裝。如果缺乏規(guī)劃，顛倒了次序，就建不后砌墻，最后進(jìn)行變壓器安裝。如果缺乏規(guī)劃，顛倒了次序，就建不成變電所。成變電所。規(guī)劃可用來監(jiān)控問題求解過程，并能夠在造成較大的危害之前發(fā)規(guī)劃可用來監(jiān)控問題求解過程，并能夠在造成較大的危害之前發(fā)現(xiàn)差錯(cuò)?，F(xiàn)差錯(cuò)。如果該問題求解系統(tǒng)不是問題求解環(huán)境中唯一的行動(dòng)者，以如果該問題求解系統(tǒng)不是問題求解環(huán)境中唯一的行動(dòng)者，以及如果此環(huán)境可能按照無法預(yù)計(jì)的方法變化，那么這種監(jiān)控就顯得特及如果此環(huán)境可能按照無法預(yù)計(jì)的方法變化，那么這種監(jiān)控就顯得特別重要。例如，考慮某個(gè)在遙遠(yuǎn)星球上空運(yùn)行的飛行器，它必須能夠別重要。例如，考慮某個(gè)在遙遠(yuǎn)星球上空運(yùn)行的

8、飛行器，它必須能夠規(guī)劃一條航線，然后，當(dāng)發(fā)現(xiàn)環(huán)境狀態(tài)與預(yù)期不合時(shí)，就進(jìn)行重新規(guī)規(guī)劃一條航線，然后，當(dāng)發(fā)現(xiàn)環(huán)境狀態(tài)與預(yù)期不合時(shí)，就進(jìn)行重新規(guī)劃。有關(guān)該環(huán)境狀態(tài)的反饋與預(yù)期的規(guī)劃狀態(tài)進(jìn)行比較，當(dāng)兩者存在劃。有關(guān)該環(huán)境狀態(tài)的反饋與預(yù)期的規(guī)劃狀態(tài)進(jìn)行比較，當(dāng)兩者存在差異時(shí)，就對此規(guī)劃進(jìn)行修正。差異時(shí)，就對此規(guī)劃進(jìn)行修正。規(guī)劃的好處可歸納為簡化搜索、解決規(guī)劃的好處可歸納為簡化搜索、解決目標(biāo)矛盾以及為差錯(cuò)補(bǔ)償提供基礎(chǔ)。目標(biāo)矛盾以及為差錯(cuò)補(bǔ)償提供基礎(chǔ)。高級人工智能 第七章自動(dòng)規(guī)劃2.問題分解途徑及方法問題分解途徑及方法把某些比較復(fù)雜的問題分解為一些比較小的子問題的把某些比較復(fù)雜的問題分解為一些比較小的子問題

9、的想法使我們應(yīng)用規(guī)劃方法求解問題在實(shí)際上成為可能。有想法使我們應(yīng)用規(guī)劃方法求解問題在實(shí)際上成為可能。有兩條能夠?qū)崿F(xiàn)這種分解的重要途徑。兩條能夠?qū)崿F(xiàn)這種分解的重要途徑。第一條重要途徑是，當(dāng)從一個(gè)問題狀態(tài)移動(dòng)到下一個(gè)第一條重要途徑是，當(dāng)從一個(gè)問題狀態(tài)移動(dòng)到下一個(gè)狀態(tài)時(shí)，無需計(jì)算整個(gè)新的狀態(tài)，而只要考慮狀態(tài)中可能狀態(tài)時(shí)，無需計(jì)算整個(gè)新的狀態(tài)，而只要考慮狀態(tài)中可能變化了的那些部分。變化了的那些部分。 高級人工智能 第七章自動(dòng)規(guī)劃 例如，一個(gè)機(jī)器人從一個(gè)房間走動(dòng)到另一個(gè)房間這并不改變兩例如，一個(gè)機(jī)器人從一個(gè)房間走動(dòng)到另一個(gè)房間這并不改變兩個(gè)房間內(nèi)門窗的位置。當(dāng)問題狀態(tài)的復(fù)雜程度提高時(shí)，框架個(gè)房間內(nèi)門窗的

10、位置。當(dāng)問題狀態(tài)的復(fù)雜程度提高時(shí)，框架(畫面畫面)問題問題(研究如何決定哪些事物是變化的以及哪些是不變的問題研究如何決定哪些事物是變化的以及哪些是不變的問題)就變就變得越來越重要。要表示出八數(shù)碼難題每走動(dòng)一步后的狀態(tài)如何變化得越來越重要。要表示出八數(shù)碼難題每走動(dòng)一步后的狀態(tài)如何變化是不難的，要隱含地記錄下具有適當(dāng)變化的新狀態(tài)也不需要做大量是不難的，要隱含地記錄下具有適當(dāng)變化的新狀態(tài)也不需要做大量的工作。從一個(gè)狀態(tài)移動(dòng)到另一個(gè)狀態(tài)的規(guī)則可以簡單的描述為整的工作。從一個(gè)狀態(tài)移動(dòng)到另一個(gè)狀態(tài)的規(guī)則可以簡單的描述為整盤棋如何從一種位置變換為另一種位置，不過，如果我們考慮引導(dǎo)盤棋如何從一種位置變換為另一

11、種位置，不過，如果我們考慮引導(dǎo)一個(gè)機(jī)器人圍繞著原來的房子移動(dòng)的問題，那么情況就要復(fù)雜得多。一個(gè)機(jī)器人圍繞著原來的房子移動(dòng)的問題，那么情況就要復(fù)雜得多。一個(gè)單一的狀態(tài)描述就會(huì)十分龐大，因?yàn)樗仨毭枋龇孔又械拿總€(gè)一個(gè)單一的狀態(tài)描述就會(huì)十分龐大，因?yàn)樗仨毭枋龇孔又械拿總€(gè)物體是在什么地方以及該機(jī)器人是在哪里。對機(jī)器人部件的某個(gè)給物體是在什么地方以及該機(jī)器人是在哪里。對機(jī)器人部件的某個(gè)給定動(dòng)作只改變整個(gè)狀態(tài)的一個(gè)小部分。如果該機(jī)器人推移一張桌子定動(dòng)作只改變整個(gè)狀態(tài)的一個(gè)小部分。如果該機(jī)器人推移一張桌子橫過房間，那么這張桌子和桌面上的所有物體的位置就要發(fā)生變化，橫過房間，那么這張桌子和桌面上的所有物體的

12、位置就要發(fā)生變化，而房間內(nèi)其它物體的位置并不發(fā)生變化。與其寫出敘述把一個(gè)完整而房間內(nèi)其它物體的位置并不發(fā)生變化。與其寫出敘述把一個(gè)完整狀態(tài)變換為另一個(gè)完整狀態(tài)的規(guī)則，我們寧愿只寫出敘述該狀態(tài)描狀態(tài)變換為另一個(gè)完整狀態(tài)的規(guī)則，我們寧愿只寫出敘述該狀態(tài)描述中發(fā)生變化的那部分的規(guī)則。而對于其余部分，我們可以假定保述中發(fā)生變化的那部分的規(guī)則。而對于其余部分，我們可以假定保持不變。持不變。 高級人工智能 第七章自動(dòng)規(guī)劃 第二條重要途徑是把單一的困難問題分割為幾個(gè)有希望的較為容第二條重要途徑是把單一的困難問題分割為幾個(gè)有希望的較為容易解決的子問題，這種分解能夠使困難問題的求解變得容易些。易解決的子問題，這

13、種分解能夠使困難問題的求解變得容易些。 雖然這樣做有時(shí)是可能的，但往往是不可能的。替代的辦法是，雖然這樣做有時(shí)是可能的，但往往是不可能的。替代的辦法是，可以把許多問題看做幾乎可分解的問題，即意味著它們可以被分割為可以把許多問題看做幾乎可分解的問題，即意味著它們可以被分割為只有少量互相作用的子問題。例如，假設(shè)我們要把某個(gè)房間里的所有只有少量互相作用的子問題。例如，假設(shè)我們要把某個(gè)房間里的所有家具都搬出去。這個(gè)問題可被分解為一個(gè)較小問題的集合，其中每個(gè)家具都搬出去。這個(gè)問題可被分解為一個(gè)較小問題的集合，其中每個(gè)子問題只包括把一件家具移出該房間。在每個(gè)子問題中，如考慮搬動(dòng)子問題只包括把一件家具移出該

14、房間。在每個(gè)子問題中，如考慮搬動(dòng)抽屜，可以單獨(dú)地從每件家具找到位置，不過，如果在長沙發(fā)椅后面抽屜，可以單獨(dú)地從每件家具找到位置，不過，如果在長沙發(fā)椅后面有個(gè)書架，那么在搬動(dòng)書架之前，我們必須先把長沙發(fā)椅搬開。要解有個(gè)書架，那么在搬動(dòng)書架之前，我們必須先把長沙發(fā)椅搬開。要解決這種準(zhǔn)可解問題，我們希望有一種方法能夠允許我們應(yīng)用我們已經(jīng)決這種準(zhǔn)可解問題，我們希望有一種方法能夠允許我們應(yīng)用我們已經(jīng)研究過的技術(shù)對每個(gè)子問題分別求解，然后記下這些子問題間可能出研究過的技術(shù)對每個(gè)子問題分別求解，然后記下這些子問題間可能出現(xiàn)的互相作用，并對它們加以適當(dāng)處理?，F(xiàn)的互相作用，并對它們加以適當(dāng)處理。曾經(jīng)提出過幾種進(jìn)

15、行這兩類分解的方法。這些方法主要包括把原曾經(jīng)提出過幾種進(jìn)行這兩類分解的方法。這些方法主要包括把原問題分解為適當(dāng)?shù)淖訂栴}的方法以及在問題求解過程中發(fā)現(xiàn)子問題時(shí)問題分解為適當(dāng)?shù)淖訂栴}的方法以及在問題求解過程中發(fā)現(xiàn)子問題時(shí)記錄和處理子問題間的互相作用。這些方法就是規(guī)劃的方法。記錄和處理子問題間的互相作用。這些方法就是規(guī)劃的方法。高級人工智能 第七章自動(dòng)規(guī)劃 當(dāng)描述計(jì)算機(jī)問題求解的特性時(shí)，規(guī)劃和行動(dòng)之間當(dāng)描述計(jì)算機(jī)問題求解的特性時(shí)，規(guī)劃和行動(dòng)之間的區(qū)別有點(diǎn)減少，因?yàn)槌艘?guī)劃之外，計(jì)算機(jī)實(shí)際上很的區(qū)別有點(diǎn)減少，因?yàn)槌艘?guī)劃之外，計(jì)算機(jī)實(shí)際上很少能夠做更多其它的事。舉例來說，在求解少能夠做更多其它的事。舉

16、例來說，在求解15數(shù)碼難題數(shù)碼難題時(shí)，我們實(shí)際上所做的是概括求解此問題時(shí)計(jì)算機(jī)可能時(shí)，我們實(shí)際上所做的是概括求解此問題時(shí)計(jì)算機(jī)可能生成某個(gè)規(guī)劃的途徑。對于這樣的生成某個(gè)規(guī)劃的途徑。對于這樣的15數(shù)碼難題，規(guī)劃和數(shù)碼難題，規(guī)劃和行動(dòng)之間的區(qū)別是不重要的。不過，在其它情況下，區(qū)行動(dòng)之間的區(qū)別是不重要的。不過，在其它情況下，區(qū)別可能起關(guān)鍵作用。在求解別可能起關(guān)鍵作用。在求解15數(shù)碼難題時(shí)，計(jì)算機(jī)可能數(shù)碼難題時(shí)，計(jì)算機(jī)可能用人們實(shí)際上采用的同樣方法去為解答尋找一個(gè)規(guī)劃。用人們實(shí)際上采用的同樣方法去為解答尋找一個(gè)規(guī)劃。人們試圖解答此問題時(shí)所采用的方法是走動(dòng)棋盤上的棋人們試圖解答此問題時(shí)所采用的方法是走動(dòng)

17、棋盤上的棋子。如果在真實(shí)世界中的解答步驟是不可忽略的或非進(jìn)子。如果在真實(shí)世界中的解答步驟是不可忽略的或非進(jìn)行不可的，那么，規(guī)劃就變得非常重要。盡管現(xiàn)實(shí)世界行不可的，那么，規(guī)劃就變得非常重要。盡管現(xiàn)實(shí)世界的步驟可能是無法改變的，但是這些步驟的計(jì)算機(jī)模擬的步驟可能是無法改變的，但是這些步驟的計(jì)算機(jī)模擬都是可以改變的。所以，我們可以在允許回溯的模擬世都是可以改變的。所以，我們可以在允許回溯的模擬世界中尋找一個(gè)完整的解答以避開真實(shí)世界的約束，而且界中尋找一個(gè)完整的解答以避開真實(shí)世界的約束，而且只有在找到一個(gè)解答之后，才走出到執(zhí)行規(guī)劃的世界里只有在找到一個(gè)解答之后，才走出到執(zhí)行規(guī)劃的世界里去。去。高級人

18、工智能 第七章自動(dòng)規(guī)劃3.域的預(yù)測和規(guī)劃的修正域的預(yù)測和規(guī)劃的修正(1)域的預(yù)測域的預(yù)測規(guī)劃方法的成功取決于問題論域的另一特性規(guī)劃方法的成功取決于問題論域的另一特性-預(yù)測。如預(yù)測。如果我們通過在實(shí)際上執(zhí)行某個(gè)操作序列來尋找問題的解答，果我們通過在實(shí)際上執(zhí)行某個(gè)操作序列來尋找問題的解答，那末在這個(gè)過程的任何一步我們都能確信該步的結(jié)果。但那末在這個(gè)過程的任何一步我們都能確信該步的結(jié)果。但對于不可預(yù)測的論域，我們最好能考慮可能的結(jié)果的集合，對于不可預(yù)測的論域，我們最好能考慮可能的結(jié)果的集合，這些結(jié)果很可能按照它們出現(xiàn)的可能性以某個(gè)次序排列。這些結(jié)果很可能按照它們出現(xiàn)的可能性以某個(gè)次序排列。然后，我們

19、產(chǎn)生一個(gè)規(guī)劃，并試圖去執(zhí)行這個(gè)規(guī)劃。然后，我們產(chǎn)生一個(gè)規(guī)劃，并試圖去執(zhí)行這個(gè)規(guī)劃。(2)規(guī)劃的修正規(guī)劃的修正如果規(guī)劃在執(zhí)行中失敗了，那么就需要對它進(jìn)行修訂，如果規(guī)劃在執(zhí)行中失敗了，那么就需要對它進(jìn)行修訂，為便于修訂，在規(guī)劃過程中不僅要記下規(guī)劃的執(zhí)行步驟，為便于修訂，在規(guī)劃過程中不僅要記下規(guī)劃的執(zhí)行步驟，而且也要記下每一步驟必須被執(zhí)行的理由。大多規(guī)則的執(zhí)而且也要記下每一步驟必須被執(zhí)行的理由。大多規(guī)則的執(zhí)行主要是按目標(biāo)定向模式工作的。在種模式下，規(guī)劃系統(tǒng)行主要是按目標(biāo)定向模式工作的。在種模式下，規(guī)劃系統(tǒng)從目標(biāo)狀態(tài)向可達(dá)到的初始狀態(tài)進(jìn)行搜索。從目標(biāo)狀態(tài)向可達(dá)到的初始狀態(tài)進(jìn)行搜索。 高級人工智能 第七

20、章自動(dòng)規(guī)劃7.2. 7.2. 基于謂詞邏輯的規(guī)劃基于謂詞邏輯的規(guī)劃 基于謂詞邏輯的規(guī)劃是用謂詞邏輯來描述世界基于謂詞邏輯的規(guī)劃是用謂詞邏輯來描述世界模型及規(guī)劃過程的一種規(guī)劃方法，它在人工智能模型及規(guī)劃過程的一種規(guī)劃方法，它在人工智能中有著廣泛的應(yīng)用。作為問題求解的一種方法，中有著廣泛的應(yīng)用。作為問題求解的一種方法，和其它問題求解方法一樣，首先要解決的就是待和其它問題求解方法一樣，首先要解決的就是待求解問題的表示，為此我們先從問題的表示談起。求解問題的表示，為此我們先從問題的表示談起。高級人工智能 第七章自動(dòng)規(guī)劃7.2.1 7.2.1 規(guī)劃世界模型的謂詞邏輯表示規(guī)劃世界模型的謂詞邏輯表示 為更清

21、楚地闡明問題，我們舉一個(gè)機(jī)器人的例子來說明：為更清楚地闡明問題，我們舉一個(gè)機(jī)器人的例子來說明：現(xiàn)在是現(xiàn)在是20102010年，中國年，中國“神洲神洲”號運(yùn)載火箭已把機(jī)器人號運(yùn)載火箭已把機(jī)器人R R送送到火星進(jìn)行探索，機(jī)器人正位于到火星進(jìn)行探索，機(jī)器人正位于L3L3處，它要把位于工具箱處，它要把位于工具箱T T內(nèi)內(nèi)的探測儀的探測儀W W取出并放到到探測架取出并放到到探測架F F（F F上為空時(shí)才能放）上，以上為空時(shí)才能放）上，以對火星地表進(jìn)行探測，工具箱對火星地表進(jìn)行探測，工具箱T T和探測架和探測架F F分別位于分別位于L1L1和和L2L2處，處，如圖所示。為完成這個(gè)任務(wù)，需要規(guī)劃機(jī)器人的這一

22、行動(dòng)過如圖所示。為完成這個(gè)任務(wù)，需要規(guī)劃機(jī)器人的這一行動(dòng)過程。程。高級人工智能 第七章自動(dòng)規(guī)劃首先引入相關(guān)的謂詞：首先引入相關(guān)的謂詞： CLEAR(xCLEAR(x):): x x上是空的上是空的HANDEMPTY(xHANDEMPTY(x):): x x手中是空的手中是空的HOLDING(xHOLDING(x, y):, y): x x手中拿著手中拿著y yON(xON(x, y):, y): x x在在y y之上之上NEAR(xNEAR(x, y):, y): x x在在y y的附近的附近IN(xIN(x, y):, y): x x在在y y中中AT(xAT(x, y):, y): x x

23、在在y y處（上）處（上）ISCLOSE(xISCLOSE(x):): x x處于關(guān)閉狀態(tài)處于關(guān)閉狀態(tài)ISOPEN(xISOPEN(x):): x x處于打開狀態(tài)處于打開狀態(tài)OPEN(xOPEN(x, y):, y): x x把把y y打開打開CLOSE(xCLOSE(x, y):, y): x x把把y y關(guān)閉關(guān)閉GOTO(xGOTO(x, y):, y): x x走到走到y(tǒng) y的旁邊的旁邊PICKDOWN(xPICKDOWN(x, y, z):, y, z): x x把把y y放在放在z z上上PICKUP(xPICKUP(x, y):, y): x x把把y y拿起拿起高級人工智能 第七

24、章自動(dòng)規(guī)劃機(jī)器人規(guī)劃世界機(jī)器人規(guī)劃世界 高級人工智能 第七章自動(dòng)規(guī)劃 這樣，問題的初始狀態(tài)就可以描述為：這樣，問題的初始狀態(tài)就可以描述為： AT(T, L1)IN(W, T)ISCLOSE(T)AT(F, AT(T, L1)IN(W, T)ISCLOSE(T)AT(F, L2)CLEAR(F)AT(R, L3)HANDEMPTY(R)L2)CLEAR(F)AT(R, L3)HANDEMPTY(R)目標(biāo)狀態(tài)：目標(biāo)狀態(tài)： AT(T, L1)IN(W,AT(T, L1)IN(W,T)ISOPEN (T)AT(F, T)ISOPEN (T)AT(F, L2)ON(W, F)NEAR(R, F)HAND

25、EMPTY(R) L2)ON(W, F)NEAR(R, F)HANDEMPTY(R) 一般來說，如果問題可解的話，在經(jīng)過一系列的操作一般來說，如果問題可解的話，在經(jīng)過一系列的操作后，都可以把其初始狀態(tài)轉(zhuǎn)化為目標(biāo)狀態(tài)，從而實(shí)現(xiàn)問題后，都可以把其初始狀態(tài)轉(zhuǎn)化為目標(biāo)狀態(tài)，從而實(shí)現(xiàn)問題的求解。規(guī)劃的目的就是的求解。規(guī)劃的目的就是“找出找出”這一系列的操作，然后這一系列的操作，然后把這些把這些“操作操作”告訴機(jī)器，機(jī)器就可以按預(yù)定的操作完成告訴機(jī)器，機(jī)器就可以按預(yù)定的操作完成相應(yīng)的任務(wù)。相應(yīng)的任務(wù)。 操作可以分為先決條件和行為動(dòng)作兩個(gè)部分，只有當(dāng)操作可以分為先決條件和行為動(dòng)作兩個(gè)部分，只有當(dāng)前狀態(tài)的先決

26、條件被滿足時(shí)，才能進(jìn)行相應(yīng)的動(dòng)作，同時(shí)前狀態(tài)的先決條件被滿足時(shí)，才能進(jìn)行相應(yīng)的動(dòng)作，同時(shí)使得當(dāng)前狀態(tài)轉(zhuǎn)變到下一個(gè)狀態(tài)。使得當(dāng)前狀態(tài)轉(zhuǎn)變到下一個(gè)狀態(tài)。對于上面給出的例子，其基本操作為：對于上面給出的例子，其基本操作為： 高級人工智能 第七章自動(dòng)規(guī)劃OP1OP1：OPEN(xOPEN(x, y) , y) 先決條件：先決條件：NEAR(x, y)ISCLOSE(yNEAR(x, y)ISCLOSE(y) ) 行為動(dòng)作：刪除：行為動(dòng)作：刪除：ISCLOSE(yISCLOSE(y) )OP2OP2：CLOSE(x,yCLOSE(x,y) ) 先決條件：先決條件：NEAR(x, y)ISOPEN(yNE

27、AR(x, y)ISOPEN(y) ) 行為動(dòng)作：刪除：行為動(dòng)作：刪除：ISOPEN(yISOPEN(y) ) 添加：添加：ISCLOSE(yISCLOSE(y) )OP3OP3：GOTO(xGOTO(x, y) , y) 先決條件：先決條件：NEAR(xNEAR(x, , y)y) 行為動(dòng)作：刪除：行為動(dòng)作：刪除：NEAR(xNEAR(x, ,y)y) 添加：添加：NEAR(xNEAR(x, y), y)OP4OP4：PICKDOWN(xPICKDOWN(x, y, z) , y, z) 先決條件：先決條件： NEAR(x,z)HOLDING(x,yNEAR(x,z)HOLDING(x,y)

28、 ) CLEAR(z CLEAR(z) ) 行為動(dòng)作：行為動(dòng)作： 刪除：刪除：CLEAR(z)HOLDING(xCLEAR(z)HOLDING(x, y), y) 添加：添加：ON(xON(x, z), z)OP5OP5：PICKUP(xPICKUP(x, y) , y) 先決條件：先決條件： NEAR(x,z)IN(y,zNEAR(x,z)IN(y,z) ISOPEN(z)HANDEMPTY(x ISOPEN(z)HANDEMPTY(x) ) 行為動(dòng)作：刪除：行為動(dòng)作：刪除：IN(y, z)HANDEMPTY(xIN(y, z)HANDEMPTY(x) ) 添加：添加：HOLDING(x,

29、y)IN(xHOLDING(x, y)IN(x, ,z)z)高級人工智能 第七章自動(dòng)規(guī)劃 當(dāng)然，還可以進(jìn)一步的規(guī)劃，但這里作為命題邏輯規(guī)當(dāng)然，還可以進(jìn)一步的規(guī)劃，但這里作為命題邏輯規(guī)劃方法的一個(gè)例子，為了突出關(guān)鍵事件狀態(tài)的變遷，我們劃方法的一個(gè)例子，為了突出關(guān)鍵事件狀態(tài)的變遷，我們對操作行為做了簡化，希望讀者能從這個(gè)例子中體會(huì)到這對操作行為做了簡化，希望讀者能從這個(gè)例子中體會(huì)到這種規(guī)劃方法的基本原理。另外，上述操作的先決條件也不種規(guī)劃方法的基本原理。另外，上述操作的先決條件也不是唯一的，在此我們對每一種操作僅列出一個(gè)先決條件。是唯一的，在此我們對每一種操作僅列出一個(gè)先決條件。 高級人工智能 第

30、七章自動(dòng)規(guī)劃7.2.2 7.2.2 基于謂詞邏輯規(guī)劃的基本過程基于謂詞邏輯規(guī)劃的基本過程上已述及，規(guī)劃的目的就是找到能把初始狀態(tài)轉(zhuǎn)變?yōu)樯弦咽黾埃?guī)劃的目的就是找到能把初始狀態(tài)轉(zhuǎn)變?yōu)槟繕?biāo)狀態(tài)的操作序列。為此，我們可以運(yùn)用上節(jié)介紹的問目標(biāo)狀態(tài)的操作序列。為此，我們可以運(yùn)用上節(jié)介紹的問題分解途徑的第二種方法來規(guī)劃，即把問題分割成幾個(gè)有題分解途徑的第二種方法來規(guī)劃，即把問題分割成幾個(gè)有希望的較為容易解決的子問題。依據(jù)這種思想，上述的規(guī)希望的較為容易解決的子問題。依據(jù)這種思想，上述的規(guī)劃問題就可以依序轉(zhuǎn)化為下列幾個(gè)子問題的規(guī)劃：劃問題就可以依序轉(zhuǎn)化為下列幾個(gè)子問題的規(guī)劃：高級人工智能 第七章自動(dòng)規(guī)劃 P

31、lan1 Plan1：機(jī)器人：機(jī)器人R R從從L3L3處走到工具箱處走到工具箱T T的旁邊，其先決的旁邊，其先決條件假設(shè)為條件假設(shè)為S1S1；Plan2Plan2：機(jī)器人：機(jī)器人R R打開工具箱打開工具箱T T，其先決條件假設(shè)為，其先決條件假設(shè)為S2S2；Plan3Plan3：機(jī)器人：機(jī)器人R R從工具箱中取出探測儀從工具箱中取出探測儀W W，其先決條，其先決條件假設(shè)為件假設(shè)為S3S3；Plan4Plan4：機(jī)器人：機(jī)器人R R從工具箱從工具箱T T的旁邊走到探測架的旁邊走到探測架F F的旁邊，的旁邊，其先決條件假設(shè)為其先決條件假設(shè)為S4S4；Plan5Plan5：機(jī)器人：機(jī)器人R R把探測儀

32、把探測儀W W放在探測架放在探測架F F上，其先決條上，其先決條件假設(shè)為件假設(shè)為S5S5；至此機(jī)器人至此機(jī)器人R R的任務(wù)完成。的任務(wù)完成。高級人工智能 第七章自動(dòng)規(guī)劃這一過程可用圖形簡單表示如圖所示：這一過程可用圖形簡單表示如圖所示： 機(jī)器人搬出探測儀的規(guī)劃過程機(jī)器人搬出探測儀的規(guī)劃過程 高級人工智能 第七章自動(dòng)規(guī)劃于是，我們很容易給出用謂詞邏輯描述的機(jī)器人規(guī)劃序列：于是，我們很容易給出用謂詞邏輯描述的機(jī)器人規(guī)劃序列：初始狀態(tài)：初始狀態(tài)： AT(T,L1)IN(W,T)ISCLOSE(T)AT(F,L2)CLEAR(F)AT(R,L3)HAAT(T,L1)IN(W,T)ISCLOSE(T)A

33、T(F,L2)CLEAR(F)AT(R,L3)HANDEMPTY(R)NDEMPTY(R) OP3OP3 OP3OP3：GOTO(R, T)GOTO(R, T) 注：注：AT(R, L3)AT(R, L3)滿足滿足NEAR(R, NEAR(R, T)T)，且，且HANDEMPTY(R)HANDEMPTY(R)， 故故GOTO(R, T)GOTO(R, T)的先決條件被滿足的先決條件被滿足 中間狀態(tài)中間狀態(tài) 1 1：AT(T,L1)IN(W,T)ISCLOSE(T)AT(F,L2)CLEAR(F)NEAR(R,T)HAT(T,L1)IN(W,T)ISCLOSE(T)AT(F,L2)CLEAR(F

34、)NEAR(R,T)HANDEMPTY(R) ANDEMPTY(R) Plan2Plan2 OP1OP1：OPEN(R, T)OPEN(R, T) 注：注：OPEN(R, T) OPEN(R, T) 的先決條件的先決條件NEAR(R, T)ISCLOSE(T)NEAR(R, T)ISCLOSE(T) 被滿足被滿足中間狀態(tài)中間狀態(tài) 2 2：AT(T,L1)IN(W,T)ISOPEN(T)AT(F,L2)CLEAR(F)NEAR(R,T)HAAT(T,L1)IN(W,T)ISOPEN(T)AT(F,L2)CLEAR(F)NEAR(R,T)HANDEMPTY(R)NDEMPTY(R)高級人工智能 第

35、七章自動(dòng)規(guī)劃 Plan3Plan3 OP5OP5：PICKUP(R, W)PICKUP(R, W) 注：注：PICKUP(R, W) PICKUP(R, W) 的先決條件的先決條件 NEAR(R, T)IN(W,T)ISOPEN(T)NEAR(R, T)IN(W,T)ISOPEN(T) HANDEMPTY(R) HANDEMPTY(R)被滿足被滿足 中間狀態(tài)中間狀態(tài) 3 3：AT(T,L1)IN(W,AT(T,L1)IN(W,T)ISOPEN(T)AT(F,L2)CLEAR(F)NEAR(R,T)HOLDING(R,W)T)ISOPEN(T)AT(F,L2)CLEAR(F)NEAR(R,T)H

36、OLDING(R,W) Plan4Plan4 OP3 OP3：GOTO(R, F)GOTO(R, F) 注：注：AT(R, L1)AT(R, L1)滿足滿足NEAR(R, NEAR(R, T)T)， 且且HOLDING(R, W)HOLDING(R, W)，故，故GOTO(R, T)GOTO(R, T)的先決條件被滿足的先決條件被滿足 中間狀態(tài)中間狀態(tài) 4 4：AT(T,L1)IN(W,AT(T,L1)IN(W,T)ISOPEN(T)AT(F,L2)CLEAR(F)NEAR(R,F)HOLDING(R,W)T)ISOPEN(T)AT(F,L2)CLEAR(F)NEAR(R,F)HOLDING(

37、R,W) Plan5Plan5 OP5 OP5：PICKDOWN(R, W, F)PICKDOWN(R, W, F) 注：先決條件注：先決條件NEAR(R, F)NEAR(R, F) HOLDING(R, W)CLEAR(F) HOLDING(R, W)CLEAR(F) 被滿足被滿足 目標(biāo)狀態(tài)：目標(biāo)狀態(tài)：AT(T,L1)IN(W,AT(T,L1)IN(W,T)ISOPEN(T)AT(F,L2)ON(W,F)NEAR(R,F)HANDEMPTY(R) T)ISOPEN(T)AT(F,L2)ON(W,F)NEAR(R,F)HANDEMPTY(R) 高級人工智能 第七章自動(dòng)規(guī)劃7.3. STRIPS

38、7.3. STRIPS規(guī)劃系統(tǒng)規(guī)劃系統(tǒng) 在前面兩節(jié)中，我們已經(jīng)介紹了規(guī)劃的一些基本概在前面兩節(jié)中，我們已經(jīng)介紹了規(guī)劃的一些基本概念和原理，在此基礎(chǔ)上，本節(jié)進(jìn)一步研究更為完整的規(guī)念和原理，在此基礎(chǔ)上，本節(jié)進(jìn)一步研究更為完整的規(guī)劃劃-規(guī)劃系統(tǒng)。規(guī)劃系統(tǒng)。7.3.1 7.3.1 積木世界的機(jī)器人規(guī)劃積木世界的機(jī)器人規(guī)劃問題求解是一個(gè)尋求某個(gè)動(dòng)作序列以達(dá)到目標(biāo)的過問題求解是一個(gè)尋求某個(gè)動(dòng)作序列以達(dá)到目標(biāo)的過程，機(jī)器人問題求解即尋求某個(gè)機(jī)器人的動(dòng)作序列程，機(jī)器人問題求解即尋求某個(gè)機(jī)器人的動(dòng)作序列( (可能可能包括路徑等包括路徑等) )，這個(gè)序列能夠使該機(jī)器人達(dá)到預(yù)期的工作，這個(gè)序列能夠使該機(jī)器人達(dá)到預(yù)期

39、的工作目標(biāo)，完成規(guī)定的工作任務(wù)。目標(biāo)，完成規(guī)定的工作任務(wù)。1.1.積木世界的機(jī)器人的問題積木世界的機(jī)器人的問題 機(jī)器人技術(shù)的發(fā)展為人工智能問題求解開拓了新的機(jī)器人技術(shù)的發(fā)展為人工智能問題求解開拓了新的應(yīng)用前景，并形成了一個(gè)新的研究領(lǐng)域應(yīng)用前景，并形成了一個(gè)新的研究領(lǐng)域-機(jī)器人學(xué)。許機(jī)器人學(xué)。許多問題求解系統(tǒng)的概念可以在機(jī)器人問題求解上進(jìn)行試多問題求解系統(tǒng)的概念可以在機(jī)器人問題求解上進(jìn)行試驗(yàn)研究和應(yīng)用。機(jī)器人問題既比較簡單，又很直觀。在驗(yàn)研究和應(yīng)用。機(jī)器人問題既比較簡單，又很直觀。在機(jī)器人問題的典型表示中，機(jī)器人能夠執(zhí)行一套動(dòng)作。機(jī)器人問題的典型表示中，機(jī)器人能夠執(zhí)行一套動(dòng)作。 高級人工智能 第

40、七章自動(dòng)規(guī)劃 設(shè)想有個(gè)積木世界和一個(gè)機(jī)器人。世界是幾個(gè)有標(biāo)設(shè)想有個(gè)積木世界和一個(gè)機(jī)器人。世界是幾個(gè)有標(biāo)記的立方形積木記的立方形積木( (在這里假定為一樣大小的在這里假定為一樣大小的) )，它們或者，它們或者互相堆迭在一起，或者擺在桌面上；機(jī)器人有個(gè)可移動(dòng)互相堆迭在一起，或者擺在桌面上；機(jī)器人有個(gè)可移動(dòng)的機(jī)械手，它可以抓起積木塊并移動(dòng)積木從一處至另一的機(jī)械手，它可以抓起積木塊并移動(dòng)積木從一處至另一處。在這個(gè)例子中機(jī)器人能夠執(zhí)行的動(dòng)作舉例如下：處。在這個(gè)例子中機(jī)器人能夠執(zhí)行的動(dòng)作舉例如下： unstack(a,b)unstack(a,b)：把堆放在積木：把堆放在積木b b上的積木上的積木a a拾起

41、。在進(jìn)拾起。在進(jìn) 行這個(gè)動(dòng)作之前，行這個(gè)動(dòng)作之前， 要求機(jī)器人的手為空手，要求機(jī)器人的手為空手， 而且積木而且積木a a的頂上是空的。的頂上是空的。 stack(a,bstack(a,b) )：把積木：把積木a a堆放在積木堆放在積木b b上。上。 動(dòng)作之前要求機(jī)械手必須已抓住動(dòng)作之前要求機(jī)械手必須已抓住 積木積木a a， 而且積木而且積木b b頂上必須是空的。頂上必須是空的。 pickup(apickup(a) )：從桌面上拾起積木：從桌面上拾起積木a a，并抓住它不放。，并抓住它不放。 在動(dòng)作之前要求機(jī)械在動(dòng)作之前要求機(jī)械 手為空手，手為空手， 而且積木而且積木a a頂上沒有任何東西。頂上

42、沒有任何東西。 putdown(aputdown(a) )：把積木：把積木a a放置到桌面上。放置到桌面上。 要求動(dòng)作之前機(jī)械手已抓住積木要求動(dòng)作之前機(jī)械手已抓住積木a a。高級人工智能 第七章自動(dòng)規(guī)劃 機(jī)器人規(guī)劃包括許多功能，例如識別機(jī)器人周圍世機(jī)器人規(guī)劃包括許多功能，例如識別機(jī)器人周圍世界，表述動(dòng)作規(guī)劃，并監(jiān)視這些規(guī)劃的執(zhí)行。我們所要界，表述動(dòng)作規(guī)劃，并監(jiān)視這些規(guī)劃的執(zhí)行。我們所要研究的主要是綜合機(jī)器人的動(dòng)作序列問題，即在某個(gè)給研究的主要是綜合機(jī)器人的動(dòng)作序列問題，即在某個(gè)給定初始情況下，經(jīng)過某個(gè)動(dòng)作序列而達(dá)到指定的目標(biāo)。定初始情況下，經(jīng)過某個(gè)動(dòng)作序列而達(dá)到指定的目標(biāo)。采用狀態(tài)描述作為數(shù)據(jù)

43、庫的產(chǎn)生式系統(tǒng)是一種最簡單的采用狀態(tài)描述作為數(shù)據(jù)庫的產(chǎn)生式系統(tǒng)是一種最簡單的問題求解系統(tǒng)。機(jī)器人問題的狀態(tài)描述和目標(biāo)描述均可問題求解系統(tǒng)。機(jī)器人問題的狀態(tài)描述和目標(biāo)描述均可用謂詞邏輯公式構(gòu)成。為了指定機(jī)器人所執(zhí)行的操作和用謂詞邏輯公式構(gòu)成。為了指定機(jī)器人所執(zhí)行的操作和執(zhí)行操作的結(jié)果，我們需要應(yīng)用下列謂詞：執(zhí)行操作的結(jié)果，我們需要應(yīng)用下列謂詞： 高級人工智能 第七章自動(dòng)規(guī)劃ON(a,b)： 積木積木a在積木在積木b之上。之上。ONTABLE(a)： 積木積木a在桌面上。在桌面上。CLEAR(a)： 積木積木a頂上沒有任何東西。頂上沒有任何東西。HOLDING(a)： 機(jī)械手正抓住積木機(jī)械手正抓住

44、積木a。HANDEMPTY： 機(jī)械手為空手。機(jī)械手為空手。積木世界的機(jī)器人問題積木世界的機(jī)器人問題 圖（圖（a a）所示為初始布局的機(jī)器人問題。這種布局可）所示為初始布局的機(jī)器人問題。這種布局可由下列謂詞公式的合取來表示：由下列謂詞公式的合取來表示： 高級人工智能 第七章自動(dòng)規(guī)劃CLEAR(B)：積木積木B頂部為空頂部為空CLEAR(C)：積木積木a在桌面上。在桌面上。ON(C，A)：積木積木C堆在積木堆在積木A上上ONTABLE(A)：積木積木A置于桌面上置于桌面上ONTABLE(B)：積木積木B置于桌面上置于桌面上HANDEMPTY：機(jī)械手為空手。機(jī)械手為空手。 目標(biāo)在于建立一個(gè)積木堆，其

45、中，積木目標(biāo)在于建立一個(gè)積木堆，其中，積木B B堆在積木堆在積木C C上上面，積木面，積木A A又堆在積木又堆在積木B B上面，如圖上面，如圖 (b)(b)所示。也可以用謂所示。也可以用謂詞邏輯來描述此目標(biāo)為：詞邏輯來描述此目標(biāo)為：ON(BON(B，C)ON(AC)ON(A，B)B)。高級人工智能 第七章自動(dòng)規(guī)劃2.2.用用F F規(guī)則求解規(guī)劃序列規(guī)則求解規(guī)劃序列采用采用F F規(guī)則表示機(jī)器人的動(dòng)作，這是一個(gè)叫做規(guī)則表示機(jī)器人的動(dòng)作，這是一個(gè)叫做STRIPSSTRIPS規(guī)劃系統(tǒng)的規(guī)則，它由規(guī)劃系統(tǒng)的規(guī)則，它由3 3部分組成。第一部分是先決條件。部分組成。第一部分是先決條件。為了使為了使F F規(guī)則能

46、夠應(yīng)用到狀態(tài)描述中去。這個(gè)先決條件公規(guī)則能夠應(yīng)用到狀態(tài)描述中去。這個(gè)先決條件公式必須是邏輯上遵循狀態(tài)描述中事實(shí)的謂詞演算表達(dá)式。式必須是邏輯上遵循狀態(tài)描述中事實(shí)的謂詞演算表達(dá)式。在應(yīng)用在應(yīng)用F F規(guī)則之前，必須確信先決條件是真的。規(guī)則之前，必須確信先決條件是真的。F F規(guī)則的規(guī)則的第二部分是一個(gè)叫做刪除表的謂詞。當(dāng)一條規(guī)則被應(yīng)用第二部分是一個(gè)叫做刪除表的謂詞。當(dāng)一條規(guī)則被應(yīng)用于某個(gè)狀態(tài)描述或數(shù)據(jù)庫時(shí)，就從該數(shù)據(jù)庫刪去刪除表于某個(gè)狀態(tài)描述或數(shù)據(jù)庫時(shí)，就從該數(shù)據(jù)庫刪去刪除表的內(nèi)容。的內(nèi)容。F F規(guī)則第三部分叫做添加表。當(dāng)把某條規(guī)則應(yīng)用規(guī)則第三部分叫做添加表。當(dāng)把某條規(guī)則應(yīng)用于某數(shù)據(jù)庫時(shí)，就把該添加

47、表的內(nèi)容添進(jìn)該數(shù)據(jù)庫。對于某數(shù)據(jù)庫時(shí)，就把該添加表的內(nèi)容添進(jìn)該數(shù)據(jù)庫。對于堆積木的例子中于堆積木的例子中movemove這個(gè)動(dòng)作可以表示如下：這個(gè)動(dòng)作可以表示如下： 高級人工智能 第七章自動(dòng)規(guī)劃move(x,y,z)：先決條件：先決條件：刪除表：刪除表：添加表：添加表：把物體把物體x從物體從物體y上面移到物體上面移到物體z上面。上面。CLEAR(x),CLEAR(z)，ON(x,y)ON(x,y)，CLEAR(y)ON(x,z)，CLEAR(y) 表示表示movemove動(dòng)作的搜索樹動(dòng)作的搜索樹 如果如果movemove為此機(jī)器人僅有的操作符或適用動(dòng)作，那為此機(jī)器人僅有的操作符或適用動(dòng)作，那么

48、，可以生成如圖所示的搜索圖或搜索樹。么，可以生成如圖所示的搜索圖或搜索樹。 高級人工智能 第七章自動(dòng)規(guī)劃 下面我們更具體地考慮圖中所示的例子，機(jī)器人的下面我們更具體地考慮圖中所示的例子，機(jī)器人的4 4個(gè)動(dòng)作個(gè)動(dòng)作( (或操作符或操作符) )可用可用STRIPSSTRIPS形式表示如下形式表示如下： (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

49、添加表：添加表：HOLDING(X)，CLEAR(Y)(3) pickup(X)先決條件：先決條件：ONTABLE(X)CLEAR(X)HANDEMPTY刪除表：刪除表：ONTABLE(X)HANDENPTY添加表：添加表：HOLDING(X)(4) putdown(X)先決條件和刪除表：先決條件和刪除表：HOLDING(X)添加表：添加表：ONTABLE(X)，HANDEMPTY高級人工智能 第七章自動(dòng)規(guī)劃 假定目標(biāo)為假定目標(biāo)為ON(BON(B，C)ON(AC)ON(A，B)B)。從初始狀態(tài)描述開始。從初始狀態(tài)描述開始正向操作，只有正向操作，只有unstack(C,Aunstack(C,A)

50、 )和和pickup(B)pickup(B)兩個(gè)動(dòng)作可以應(yīng)兩個(gè)動(dòng)作可以應(yīng)用用F F規(guī)則。下圖所示給出這個(gè)問題的全部狀態(tài)空間，并用粗規(guī)則。下圖所示給出這個(gè)問題的全部狀態(tài)空間，并用粗線指出了從初始狀態(tài)線指出了從初始狀態(tài)( (用用S0S0標(biāo)記標(biāo)記) )到目標(biāo)狀態(tài)到目標(biāo)狀態(tài)( (用用G G標(biāo)記標(biāo)記) )的解的解答路徑。與習(xí)慣的狀態(tài)空間圖畫法不同的是，這個(gè)狀態(tài)空答路徑。與習(xí)慣的狀態(tài)空間圖畫法不同的是，這個(gè)狀態(tài)空間圖顯出問題的對稱性，而沒有把初始節(jié)點(diǎn)間圖顯出問題的對稱性，而沒有把初始節(jié)點(diǎn)S0S0放在圖的頂放在圖的頂點(diǎn)上。此外，要注意到本例中的每條規(guī)則都有一條逆規(guī)則。點(diǎn)上。此外，要注意到本例中的每條規(guī)則都有

51、一條逆規(guī)則。沿著粗線所示的支路，從初始狀態(tài)開始，正向地依次讀出沿著粗線所示的支路，從初始狀態(tài)開始，正向地依次讀出連接弧線上的連接弧線上的F F規(guī)則，我們就得到一個(gè)能夠達(dá)到目標(biāo)狀態(tài)的規(guī)則，我們就得到一個(gè)能夠達(dá)到目標(biāo)狀態(tài)的動(dòng)作序列于下：動(dòng)作序列于下： unstack(C,A),putdown(C),pickup(Bunstack(C,A),putdown(C),pickup(B) )， stack(B,C),pickup(A),stack(A,B)stack(B,C),pickup(A),stack(A,B) 就把這個(gè)動(dòng)作序列叫做達(dá)到這個(gè)積木世界機(jī)器人問題就把這個(gè)動(dòng)作序列叫做達(dá)到這個(gè)積木世界機(jī)器人

52、問題目標(biāo)的規(guī)劃。目標(biāo)的規(guī)劃。高級人工智能 第七章自動(dòng)規(guī)劃高級人工智能 第七章自動(dòng)規(guī)劃7.3.2 STRIPS7.3.2 STRIPS系統(tǒng)規(guī)劃系統(tǒng)規(guī)劃STRIPS(STanfordSTRIPS(STanford Research Institute Problem Research Institute Problem Solver)Solver)，即斯坦福研究所問題求解系統(tǒng)，是從被求解的問，即斯坦福研究所問題求解系統(tǒng)，是從被求解的問題中引出一般性結(jié)論而產(chǎn)生規(guī)劃的。我們先從系統(tǒng)的組成題中引出一般性結(jié)論而產(chǎn)生規(guī)劃的。我們先從系統(tǒng)的組成講起，然后再討論系統(tǒng)的規(guī)劃。講起，然后再討論系統(tǒng)的規(guī)劃。1.STR

53、IPS1.STRIPS系統(tǒng)的組成系統(tǒng)的組成 STRIPSSTRIPS是由是由FikesFikes、HartHart和和NilssonNilsson三人在三人在19711971及及19721972研究成功的，它是夏凱研究成功的，它是夏凱(Shakey(Shakey) )機(jī)器人程序控制系統(tǒng)的一機(jī)器人程序控制系統(tǒng)的一個(gè)組成部分。這個(gè)機(jī)器人是一部設(shè)計(jì)用于圍繞簡單的環(huán)境個(gè)組成部分。這個(gè)機(jī)器人是一部設(shè)計(jì)用于圍繞簡單的環(huán)境移動(dòng)的自推車，它能夠按照簡單的英語命令進(jìn)行動(dòng)作。夏移動(dòng)的自推車，它能夠按照簡單的英語命令進(jìn)行動(dòng)作。夏凱包含下列凱包含下列4 4個(gè)主要部分：個(gè)主要部分： 高級人工智能 第七章自動(dòng)規(guī)劃 (1)

54、 (1) 車輪及其推進(jìn)系統(tǒng)；車輪及其推進(jìn)系統(tǒng)； (2) (2) 傳感系統(tǒng)，由電視攝象機(jī)和接觸桿組成；傳感系統(tǒng)，由電視攝象機(jī)和接觸桿組成； (3) (3) 一臺不在車體上的用來執(zhí)行程序設(shè)計(jì)的計(jì)算機(jī)。一臺不在車體上的用來執(zhí)行程序設(shè)計(jì)的計(jì)算機(jī)。它它 能夠分析由車上傳感器得到的反饋信息和輸入指令，能夠分析由車上傳感器得到的反饋信息和輸入指令，并向車輪發(fā)出使其推進(jìn)系統(tǒng)觸發(fā)的信號；并向車輪發(fā)出使其推進(jìn)系統(tǒng)觸發(fā)的信號； (4)(4) 無線電通訊系統(tǒng)，用于在計(jì)算機(jī)和車輪間的數(shù)無線電通訊系統(tǒng)，用于在計(jì)算機(jī)和車輪間的數(shù)據(jù)傳送。據(jù)傳送。 STRIPSSTRIPS是決定把哪個(gè)指令送至機(jī)器人的程序設(shè)計(jì)。是決定把哪個(gè)指令

55、送至機(jī)器人的程序設(shè)計(jì)。該機(jī)器人世界包括一些房間、房間之間的門和可移動(dòng)的該機(jī)器人世界包括一些房間、房間之間的門和可移動(dòng)的箱子；在比較復(fù)雜的情況下還有電燈和窗戶等。對于箱子；在比較復(fù)雜的情況下還有電燈和窗戶等。對于STRIPSSTRIPS來說，任何時(shí)候所存在的具體的突出的實(shí)際世界來說，任何時(shí)候所存在的具體的突出的實(shí)際世界都由一套謂詞演算子句來描述。都由一套謂詞演算子句來描述。 高級人工智能 第七章自動(dòng)規(guī)劃 例如，子句例如，子句 INROOM(ROBOTINROOM(ROBOT，R2)R2)在數(shù)據(jù)庫中為一斷言，表明該時(shí)刻機(jī)器人在在數(shù)據(jù)庫中為一斷言，表明該時(shí)刻機(jī)器人在2 2號房間內(nèi)。號房間內(nèi)。當(dāng)實(shí)際情

56、況改變時(shí)，數(shù)據(jù)庫必須進(jìn)行及時(shí)修正?？偲饋懋?dāng)實(shí)際情況改變時(shí)，數(shù)據(jù)庫必須進(jìn)行及時(shí)修正?？偲饋碚f說, ,描述任何時(shí)刻的世界的數(shù)據(jù)庫就叫做世界模型。描述任何時(shí)刻的世界的數(shù)據(jù)庫就叫做世界模型?？刂瞥绦虬S多子程序，當(dāng)這些子程序被執(zhí)行時(shí)，控制程序包含許多子程序，當(dāng)這些子程序被執(zhí)行時(shí)，它們將會(huì)使機(jī)器人移動(dòng)通過某個(gè)門，推動(dòng)某個(gè)箱子通過它們將會(huì)使機(jī)器人移動(dòng)通過某個(gè)門，推動(dòng)某個(gè)箱子通過一個(gè)門，關(guān)上某盞電燈或者執(zhí)行其它的實(shí)際動(dòng)作。這些一個(gè)門，關(guān)上某盞電燈或者執(zhí)行其它的實(shí)際動(dòng)作。這些程序本身是很復(fù)雜的，但不直接涉及問題求解。對于機(jī)程序本身是很復(fù)雜的，但不直接涉及問題求解。對于機(jī)器人問題求解來說，這些程序有點(diǎn)像人類問

57、題求解中走器人問題求解來說，這些程序有點(diǎn)像人類問題求解中走動(dòng)和拾起物體等動(dòng)作一樣的關(guān)系。動(dòng)和拾起物體等動(dòng)作一樣的關(guān)系。高級人工智能 第七章自動(dòng)規(guī)劃 上一節(jié)已介紹過上一節(jié)已介紹過STRIPSSTRIPS系統(tǒng)系統(tǒng)F F規(guī)則規(guī)則( (即操作符即操作符) )的組成。的組成。整個(gè)整個(gè)STRIPSSTRIPS系統(tǒng)的組成如下：系統(tǒng)的組成如下： (1)(1) 世界模型。為一階謂詞演算公式；世界模型。為一階謂詞演算公式； (2)(2) 操作符操作符(F(F規(guī)則規(guī)則) )。包括先決條件、刪除表和添加表；。包括先決條件、刪除表和添加表； (3)(3) 操作方法。應(yīng)用狀態(tài)空間表示和中間結(jié)局分析。例操作方法。應(yīng)用狀態(tài)空

58、間表示和中間結(jié)局分析。例如：狀態(tài)：如：狀態(tài)：(M(M，G)G)， 包括初始狀態(tài)、中間狀態(tài)和目標(biāo)狀態(tài)。包括初始狀態(tài)、中間狀態(tài)和目標(biāo)狀態(tài)。 初始狀態(tài)：初始狀態(tài)：(M0(M0，(G0)(G0) 目標(biāo)狀態(tài)：得到一個(gè)世界模型，其中不遺留任何未目標(biāo)狀態(tài)：得到一個(gè)世界模型，其中不遺留任何未 滿足的目標(biāo)。滿足的目標(biāo)。高級人工智能 第七章自動(dòng)規(guī)劃2.2.系統(tǒng)的規(guī)劃過程系統(tǒng)的規(guī)劃過程(1)(1)問題的表示問題的表示每個(gè)每個(gè)STRIPSSTRIPS問題的解答為某個(gè)實(shí)現(xiàn)目標(biāo)的操作符序問題的解答為某個(gè)實(shí)現(xiàn)目標(biāo)的操作符序列，即達(dá)到目標(biāo)的規(guī)劃。下面舉例說明列，即達(dá)到目標(biāo)的規(guī)劃。下面舉例說明STRIPSSTRIPS系統(tǒng)規(guī)劃系

59、統(tǒng)規(guī)劃的求解過程。的求解過程?？紤]考慮STRIPSSTRIPS系統(tǒng)一個(gè)比較簡單的情況，即要求機(jī)器系統(tǒng)一個(gè)比較簡單的情況，即要求機(jī)器人到鄰室去取回一個(gè)箱子。機(jī)器人的初始狀態(tài)和目標(biāo)狀人到鄰室去取回一個(gè)箱子。機(jī)器人的初始狀態(tài)和目標(biāo)狀態(tài)的世界模型示于圖。設(shè)有兩個(gè)操作符，即態(tài)的世界模型示于圖。設(shè)有兩個(gè)操作符，即gothrugothru和和pushthrupushthru(“(“走過走過”和和“推過推過”) )，分別描述于下：，分別描述于下：高級人工智能 第七章自動(dòng)規(guī)劃 OP1OP1：gothru(d,r1,r2)gothru(d,r1,r2)機(jī)器人通過房間機(jī)器人通過房間r1r1和房間和房間r2r2之間的

60、之間的d d，即機(jī)器人從房間，即機(jī)器人從房間r1r1走過門走過門d d而進(jìn)入房間而進(jìn)入房間r2r2。先決條件：先決條件：INROOM(ROBOTINROOM(ROBOT，r1)CONNECTS(d,r1,r2)r1)CONNECTS(d,r1,r2)；機(jī)器人在房間機(jī)器人在房間r1r1內(nèi)，而且門內(nèi)，而且門d d連接連接r1r1和和r2r2兩個(gè)房間。兩個(gè)房間。 STRIPSSTRIPS的一個(gè)簡化模型的一個(gè)簡化模型 高級人工智能 第七章自動(dòng)規(guī)劃 刪除表：刪除表：INROOM(ROBOTINROOM(ROBOT，S)S)；對于任何；對于任何S S值。值。添加表：添加表：INROOM(ROBOTINRO