1、1/20目錄o 第一章第一章緒論緒論o 第二章第二章知識(shí)表示知識(shí)表示 o 第三章搜索技術(shù)第三章搜索技術(shù)o 第四章推理技術(shù)第四章推理技術(shù)o 第五章機(jī)器學(xué)習(xí)第五章機(jī)器學(xué)習(xí) o 第六章專家系統(tǒng)第六章專家系統(tǒng) o 第七章自動(dòng)規(guī)劃系統(tǒng)第七章自動(dòng)規(guī)劃系統(tǒng)o 第八章第八章 自然語言理解自然語言理解o 第九章第九章 智能控制智能控制o 第十章第十章 人工智能程序設(shè)計(jì)人工智能程序設(shè)計(jì)2/207.1 自動(dòng)規(guī)劃概述7.1.1 規(guī)劃的概念及作用規(guī)劃的概念及作用 1. 規(guī)劃的概念規(guī)劃的概念 定義定義7.1 從某個(gè)特定的問題狀態(tài)出發(fā)，尋求一系列行為從某個(gè)特定的問題狀態(tài)出發(fā)，尋求一系列行為動(dòng)作，并建立一個(gè)操作序列，直到求得

2、目標(biāo)狀態(tài)為止。這個(gè)求動(dòng)作，并建立一個(gè)操作序列，直到求得目標(biāo)狀態(tài)為止。這個(gè)求解過程就稱為解過程就稱為規(guī)劃規(guī)劃。 定義定義7.2 規(guī)劃是對(duì)某個(gè)待求解問題給出求解過程的步驟。規(guī)劃是對(duì)某個(gè)待求解問題給出求解過程的步驟。規(guī)劃涉及如何將問題分解為若干相應(yīng)的子問題，以及如何記錄規(guī)劃涉及如何將問題分解為若干相應(yīng)的子問題，以及如何記錄和處理問題求解過程中發(fā)現(xiàn)的各子問題間的關(guān)系。和處理問題求解過程中發(fā)現(xiàn)的各子問題間的關(guān)系。 定義定義7.3 規(guī)劃系統(tǒng)是一個(gè)涉及有關(guān)問題求解過程步驟的系規(guī)劃系統(tǒng)是一個(gè)涉及有關(guān)問題求解過程步驟的系統(tǒng)。如計(jì)算機(jī)或飛機(jī)設(shè)計(jì)、火車或汽車運(yùn)輸路徑、財(cái)政和軍事統(tǒng)。如計(jì)算機(jī)或飛機(jī)設(shè)計(jì)、火車或汽車運(yùn)輸

3、路徑、財(cái)政和軍事規(guī)劃等問題。規(guī)劃等問題。3/207.1 自動(dòng)規(guī)劃概述7.1.1 規(guī)劃的概念及作用規(guī)劃的概念及作用 例：例：救援仿真機(jī)器人系統(tǒng)救援仿真機(jī)器人系統(tǒng)（RoboCup Rescue Simulation System，RCRSS） 消防智能體消防智能體 醫(yī)療智能體醫(yī)療智能體 警察智能體警察智能體 普通市民普通市民 中心智能體中心智能體 路障路障 避難所避難所 著火建筑物著火建筑物 普通建筑物）普通建筑物） 4/207.1 自動(dòng)規(guī)劃概述7.1.1 規(guī)劃的概念及作用規(guī)劃的概念及作用 2. 規(guī)劃的作用規(guī)劃的作用 規(guī)劃可用來監(jiān)控問題求解過程，并能夠在造成較大的危害規(guī)劃可用來監(jiān)控問題求解過程，并

4、能夠在造成較大的危害之前發(fā)現(xiàn)差錯(cuò)。規(guī)劃的好處可歸納為簡化搜索、解決目標(biāo)矛盾之前發(fā)現(xiàn)差錯(cuò)。規(guī)劃的好處可歸納為簡化搜索、解決目標(biāo)矛盾以及為差錯(cuò)補(bǔ)償提供基礎(chǔ)。以及為差錯(cuò)補(bǔ)償提供基礎(chǔ)。 “十二五十二五”規(guī)劃、城市規(guī)劃、企業(yè)發(fā)展規(guī)劃規(guī)劃、城市規(guī)劃、企業(yè)發(fā)展規(guī)劃5/207.1 自動(dòng)規(guī)劃概述7.1.2 規(guī)劃的分類和問題分解途徑規(guī)劃的分類和問題分解途徑 1. 規(guī)劃的分類規(guī)劃的分類 （1）按規(guī)劃內(nèi)容分）按規(guī)劃內(nèi)容分 國家、地方、重大項(xiàng)目、企業(yè)、交通、城市、環(huán)境國家、地方、重大項(xiàng)目、企業(yè)、交通、城市、環(huán)境 （2）按規(guī)劃方法分）按規(guī)劃方法分 非遞階（非分層）規(guī)劃與遞階（分層）規(guī)劃；線性規(guī)劃與非遞階（非分層）規(guī)劃與遞

5、階（分層）規(guī)劃；線性規(guī)劃與非線性規(guī)劃；同步規(guī)劃與異步規(guī)劃；基于腳本、框架和本體的非線性規(guī)劃；同步規(guī)劃與異步規(guī)劃；基于腳本、框架和本體的規(guī)劃；基于專家系統(tǒng)的規(guī)劃；基于競爭機(jī)制的規(guī)劃；規(guī)劃；基于專家系統(tǒng)的規(guī)劃；基于競爭機(jī)制的規(guī)劃； （3）按規(guī)劃實(shí)質(zhì)分）按規(guī)劃實(shí)質(zhì)分 任務(wù)規(guī)劃、路徑規(guī)劃、軌跡規(guī)劃任務(wù)規(guī)劃、路徑規(guī)劃、軌跡規(guī)劃6/207.1 自動(dòng)規(guī)劃概述7.1.2 規(guī)劃的分類和問題分解途徑規(guī)劃的分類和問題分解途徑 2. 問題分解途徑問題分解途徑把某些較復(fù)雜的問題分解為一些較小的子問題。有兩條實(shí)把某些較復(fù)雜的問題分解為一些較小的子問題。有兩條實(shí)現(xiàn)這種分解的重要途徑。現(xiàn)這種分解的重要途徑。第一條重要途徑是當(dāng)

6、從一個(gè)問題狀態(tài)移動(dòng)到下一個(gè)狀態(tài)時(shí)第一條重要途徑是當(dāng)從一個(gè)問題狀態(tài)移動(dòng)到下一個(gè)狀態(tài)時(shí)，無需計(jì)算整個(gè)新的狀態(tài)，而只要考慮狀態(tài)中可能變化了的那，無需計(jì)算整個(gè)新的狀態(tài)，而只要考慮狀態(tài)中可能變化了的那些部分。些部分。第二條重要途徑是把單一的困難問題分割為幾個(gè)有希望的第二條重要途徑是把單一的困難問題分割為幾個(gè)有希望的較為容易解決的子問題。較為容易解決的子問題。7/207.1 自動(dòng)規(guī)劃概述7.1.2 規(guī)劃的分類和問題分解途徑規(guī)劃的分類和問題分解途徑 3. 域的預(yù)測和規(guī)劃的修正域的預(yù)測和規(guī)劃的修正 （1）域的預(yù)測）域的預(yù)測 問題論域的預(yù)測。對(duì)于不可預(yù)測的論域，考慮可能的結(jié)果問題論域的預(yù)測。對(duì)于不可預(yù)測的論域，

7、考慮可能的結(jié)果集合，按照它們出現(xiàn)的可能性以某個(gè)次序排列。然后，產(chǎn)生一集合，按照它們出現(xiàn)的可能性以某個(gè)次序排列。然后，產(chǎn)生一個(gè)規(guī)劃、并試圖去執(zhí)行這個(gè)規(guī)劃。個(gè)規(guī)劃、并試圖去執(zhí)行這個(gè)規(guī)劃。 （2）規(guī)劃的修正）規(guī)劃的修正 規(guī)劃執(zhí)行失敗導(dǎo)致對(duì)規(guī)劃的修正。規(guī)劃執(zhí)行失敗導(dǎo)致對(duì)規(guī)劃的修正。 在規(guī)劃過程中不僅要記錄規(guī)劃的執(zhí)行步驟，而且要記錄每在規(guī)劃過程中不僅要記錄規(guī)劃的執(zhí)行步驟，而且要記錄每一步必須要執(zhí)行的理由。一步必須要執(zhí)行的理由。8/207.2 基于謂詞邏輯的規(guī)劃 用謂詞邏輯來描述世界模型及規(guī)劃過程。用謂詞邏輯來描述世界模型及規(guī)劃過程。o 世界模型的謂詞邏輯表示世界模型的謂詞邏輯表示n 定義謂詞定義謂詞n

8、確定問題初始狀態(tài)確定問題初始狀態(tài)n 確定問題目標(biāo)狀態(tài)確定問題目標(biāo)狀態(tài)n 確定基本操作確定基本操作o 基于謂詞邏輯規(guī)劃的基本過程基于謂詞邏輯規(guī)劃的基本過程n 問題分解問題分解n 子問題規(guī)劃子問題規(guī)劃n 得到操作序列得到操作序列9/207.3 STRIPS規(guī)劃系統(tǒng) 7.3.1 積木世界的機(jī)器人規(guī)劃積木世界的機(jī)器人規(guī)劃BACCBA機(jī)械手機(jī)械手機(jī)械手機(jī)械手(a)(b)10/207.3 STRIPS規(guī)劃系統(tǒng) 7.3.1 積木世界的機(jī)器人規(guī)劃積木世界的機(jī)器人規(guī)劃 1. 積木世界的機(jī)器人問題積木世界的機(jī)器人問題 機(jī)器人能夠執(zhí)行的動(dòng)作機(jī)器人能夠執(zhí)行的動(dòng)作舉例如下：舉例如下： unstack(a,b)：把堆放在

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

10、積木a放置到桌面上。要求動(dòng)作之前機(jī)械放置到桌面上。要求動(dòng)作之前機(jī)械手已抓住積木手已抓住積木a。11/207.3 STRIPS規(guī)劃系統(tǒng) 7.3.1 積木世界的機(jī)器人規(guī)劃積木世界的機(jī)器人規(guī)劃 1. 積木世界的機(jī)器人問題積木世界的機(jī)器人問題狀態(tài)描述謂詞狀態(tài)描述謂詞：ON(a,b)： 積木積木a在積木在積木b之上。之上。ONTABLE(a)： 積木積木a在桌面上。在桌面上。CLEAR(a)： 積木積木a頂上沒有任何東西。頂上沒有任何東西。HOLDING(a)： 機(jī)械手正抓住積木機(jī)械手正抓住積木a。HANDEMPTY： 機(jī)械手為空手。機(jī)械手為空手。12/207.3 STRIPS規(guī)劃系統(tǒng) 7.3.1 積木

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

12、第三部分叫做添加表。當(dāng)把某條規(guī)則應(yīng)用于某數(shù)據(jù)庫時(shí)，就把該添加表的內(nèi)容添進(jìn)該數(shù)據(jù)庫。就把該添加表的內(nèi)容添進(jìn)該數(shù)據(jù)庫。13/207.3 STRIPS規(guī)劃系統(tǒng) 7.3.1 積木世界的機(jī)器人規(guī)劃積木世界的機(jī)器人規(guī)劃 2.用用F規(guī)則求解規(guī)劃序列規(guī)則求解規(guī)劃序列例：例： move(x, y, z): 把物體把物體x從物體從物體y上面移到物體上面移到物體z上面。上面。 先決條件：先決條件：CLEAR(x), CLEAR(z), ON(x,y) 刪除表：刪除表：ON(x, y), CLEAR(z) 添加表：添加表：ON(x, z), CLEAR(y)14/207.3 STRIPS規(guī)劃系統(tǒng) 7.3.2 STRI

13、PS規(guī)劃系統(tǒng)規(guī)劃系統(tǒng) STanford Research Institute Problem SolverSTRIPSSTRIPS系統(tǒng)的組成如下：系統(tǒng)的組成如下：(1) 世界模型。為一階謂詞演算公式。世界模型。為一階謂詞演算公式。(2) 操作符操作符(F規(guī)則規(guī)則)。包括先決條件、刪除表和添加表。包括先決條件、刪除表和添加表。(3) 操作方法。應(yīng)用狀態(tài)空間表示和中間操作方法。應(yīng)用狀態(tài)空間表示和中間-結(jié)局分析。結(jié)局分析。規(guī)劃過程規(guī)劃過程每個(gè)每個(gè)STRIPS問題的解答為某個(gè)實(shí)現(xiàn)目標(biāo)的操作符序列，問題的解答為某個(gè)實(shí)現(xiàn)目標(biāo)的操作符序列，即達(dá)到目標(biāo)的規(guī)劃。即達(dá)到目標(biāo)的規(guī)劃。 15/207.4 分層規(guī)劃 探

14、索規(guī)劃時(shí)首先只考慮一層的細(xì)節(jié)，然后再注意規(guī)劃中比探索規(guī)劃時(shí)首先只考慮一層的細(xì)節(jié)，然后再注意規(guī)劃中比這一層低一層的細(xì)節(jié)，所以把它叫做長度優(yōu)先搜索。這一層低一層的細(xì)節(jié)，所以把它叫做長度優(yōu)先搜索。NOAH規(guī)劃系統(tǒng)規(guī)劃系統(tǒng)1. 應(yīng)用最小約束策略應(yīng)用最小約束策略一個(gè)尋找非線性規(guī)劃而不必考慮操作符序列的所有排列的一個(gè)尋找非線性規(guī)劃而不必考慮操作符序列的所有排列的方法是把最少約束策略應(yīng)用來選擇操作符執(zhí)行次序的問題。方法是把最少約束策略應(yīng)用來選擇操作符執(zhí)行次序的問題。問題求解系統(tǒng)問題求解系統(tǒng)NOAH采用一種網(wǎng)絡(luò)結(jié)構(gòu)來記錄它所選取的采用一種網(wǎng)絡(luò)結(jié)構(gòu)來記錄它所選取的操作符之間所需要的排序。它也分層進(jìn)行操作運(yùn)算，即

15、首先建操作符之間所需要的排序。它也分層進(jìn)行操作運(yùn)算，即首先建立起規(guī)劃的抽象輪廓，然后在后續(xù)的各步中，填入越來越多的立起規(guī)劃的抽象輪廓，然后在后續(xù)的各步中，填入越來越多的細(xì)節(jié)。細(xì)節(jié)。16/207.4 分層規(guī)劃 2. 檢驗(yàn)準(zhǔn)則檢驗(yàn)準(zhǔn)則準(zhǔn)則法已被應(yīng)用于各種規(guī)劃生成系統(tǒng)。對(duì)于早期的系統(tǒng)，準(zhǔn)則法已被應(yīng)用于各種規(guī)劃生成系統(tǒng)。對(duì)于早期的系統(tǒng)，如如HACKER系統(tǒng)，準(zhǔn)則只用于舍棄不滿足的規(guī)劃。在系統(tǒng)，準(zhǔn)則只用于舍棄不滿足的規(guī)劃。在NOAH系統(tǒng)中，準(zhǔn)則被用來提出推定的方法以便修正所產(chǎn)生的規(guī)劃。系統(tǒng)中，準(zhǔn)則被用來提出推定的方法以便修正所產(chǎn)生的規(guī)劃。第一個(gè)涉及的準(zhǔn)則是歸結(jié)矛盾準(zhǔn)則。第一個(gè)涉及的準(zhǔn)則是歸結(jié)矛盾準(zhǔn)則。第

16、二個(gè)準(zhǔn)則叫做消除多余先決條件準(zhǔn)則，包括除去對(duì)子目第二個(gè)準(zhǔn)則叫做消除多余先決條件準(zhǔn)則，包括除去對(duì)子目標(biāo)的多余說明。標(biāo)的多余說明。可以把分層規(guī)劃和最少約定策略十分直接地結(jié)合起來，以可以把分層規(guī)劃和最少約定策略十分直接地結(jié)合起來，以求得非線性規(guī)劃而不產(chǎn)生一個(gè)龐大的搜索樹。求得非線性規(guī)劃而不產(chǎn)生一個(gè)龐大的搜索樹。 17/207.5 基于專家系統(tǒng)的機(jī)器人規(guī)劃1. 系統(tǒng)結(jié)構(gòu)及規(guī)劃機(jī)理系統(tǒng)結(jié)構(gòu)及規(guī)劃機(jī)理（1）知識(shí)庫：用于存儲(chǔ)某些特定領(lǐng)域的專家知識(shí)和經(jīng)驗(yàn)）知識(shí)庫：用于存儲(chǔ)某些特定領(lǐng)域的專家知識(shí)和經(jīng)驗(yàn)，包括機(jī)器人工作環(huán)境的世界模型、狀態(tài)、物體描述等事實(shí)和，包括機(jī)器人工作環(huán)境的世界模型、狀態(tài)、物體描述等事實(shí)和可行

17、操作或規(guī)則等。可行操作或規(guī)則等。（2） 控制策略：包含綜合機(jī)理，確定系統(tǒng)應(yīng)當(dāng)應(yīng)用什么控制策略：包含綜合機(jī)理，確定系統(tǒng)應(yīng)當(dāng)應(yīng)用什么規(guī)則以及采取什么方式去尋找該規(guī)則。規(guī)則以及采取什么方式去尋找該規(guī)則。（3） 推理機(jī)：用于記憶所采用的規(guī)則和控制策略及推理推理機(jī)：用于記憶所采用的規(guī)則和控制策略及推理策略。策略。（4）知識(shí)獲?。菏紫全@取某特定域的專家知識(shí)。然后用）知識(shí)獲?。菏紫全@取某特定域的專家知識(shí)。然后用程序設(shè)計(jì)語言把這些知識(shí)變換為計(jì)算機(jī)程序。最后把它們存入程序設(shè)計(jì)語言把這些知識(shí)變換為計(jì)算機(jī)程序。最后把它們存入知識(shí)庫待用。知識(shí)庫待用。18/207.5 基于專家系統(tǒng)的機(jī)器人規(guī)劃(5) 解釋與說明：通過用戶接口，在專家系統(tǒng)與用戶之間解釋與說明：通過用戶接口，在專家系統(tǒng)與用戶之間進(jìn)行對(duì)話，從而使用戶能夠輸入數(shù)據(jù)、提出問題、知道推理結(jié)進(jìn)行對(duì)話，從而使用戶能夠輸入數(shù)據(jù)、提出問題、知道推理結(jié)果以及了解推理過程等。果以及了解推理過程等。2. 任務(wù)級(jí)機(jī)器人規(guī)劃三要素任務(wù)級(jí)機(jī)器人規(guī)劃三要素（1）建立模型：世界模型。）建立模型：世界模型。（2）任務(wù)說明：定義狀態(tài)及狀態(tài)變換次序。）任務(wù)說明：定義狀態(tài)及狀態(tài)變換次