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

2、目標狀態為止。這個求動作，并建立一個操作序列，直到求得目標狀態為止。這個求解過程就稱為解過程就稱為規劃規劃。 定義定義7.2 規劃是對某個待求解問題給出求解過程的步驟。規劃是對某個待求解問題給出求解過程的步驟。規劃涉及如何將問題分解為若干相應的子問題，以及如何記錄規劃涉及如何將問題分解為若干相應的子問題，以及如何記錄和處理問題求解過程中發現的各子問題間的關系。和處理問題求解過程中發現的各子問題間的關系。 定義定義7.3 規劃系統是一個涉及有關問題求解過程步驟的系規劃系統是一個涉及有關問題求解過程步驟的系統。如計算機或飛機設計、火車或汽車運輸路徑、財政和軍事統。如計算機或飛機設計、火車或汽車運輸

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

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

5、階（分層）規劃；線性規劃與非線性規劃；同步規劃與異步規劃；基于腳本、框架和本體的非線性規劃；同步規劃與異步規劃；基于腳本、框架和本體的規劃；基于專家系統的規劃；基于競爭機制的規劃；規劃；基于專家系統的規劃；基于競爭機制的規劃； （3）按規劃實質分）按規劃實質分 任務規劃、路徑規劃、軌跡規劃任務規劃、路徑規劃、軌跡規劃6/207.1 自動規劃概述7.1.2 規劃的分類和問題分解途徑規劃的分類和問題分解途徑 2. 問題分解途徑問題分解途徑把某些較復雜的問題分解為一些較小的子問題。有兩條實把某些較復雜的問題分解為一些較小的子問題。有兩條實現這種分解的重要途徑。現這種分解的重要途徑。第一條重要途徑是當

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

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

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

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

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

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

12、第三部分叫做添加表。當把某條規則應用于某數據庫時，就把該添加表的內容添進該數據庫。就把該添加表的內容添進該數據庫。13/207.3 STRIPS規劃系統 7.3.1 積木世界的機器人規劃積木世界的機器人規劃 2.用用F規則求解規劃序列規則求解規劃序列例：例： 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規劃系統 7.3.2 STRI

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

14、索規劃時首先只考慮一層的細節，然后再注意規劃中比探索規劃時首先只考慮一層的細節，然后再注意規劃中比這一層低一層的細節，所以把它叫做長度優先搜索。這一層低一層的細節，所以把它叫做長度優先搜索。NOAH規劃系統規劃系統1. 應用最小約束策略應用最小約束策略一個尋找非線性規劃而不必考慮操作符序列的所有排列的一個尋找非線性規劃而不必考慮操作符序列的所有排列的方法是把最少約束策略應用來選擇操作符執行次序的問題。方法是把最少約束策略應用來選擇操作符執行次序的問題。問題求解系統問題求解系統NOAH采用一種網絡結構來記錄它所選取的采用一種網絡結構來記錄它所選取的操作符之間所需要的排序。它也分層進行操作運算，即

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

16、二個準則叫做消除多余先決條件準則，包括除去對子目第二個準則叫做消除多余先決條件準則，包括除去對子目標的多余說明。標的多余說明。可以把分層規劃和最少約定策略十分直接地結合起來，以可以把分層規劃和最少約定策略十分直接地結合起來，以求得非線性規劃而不產生一個龐大的搜索樹。求得非線性規劃而不產生一個龐大的搜索樹。 17/207.5 基于專家系統的機器人規劃1. 系統結構及規劃機理系統結構及規劃機理（1）知識庫：用于存儲某些特定領域的專家知識和經驗）知識庫：用于存儲某些特定領域的專家知識和經驗，包括機器人工作環境的世界模型、狀態、物體描述等事實和，包括機器人工作環境的世界模型、狀態、物體描述等事實和可行

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