1、目錄,第八章自動規(guī)劃 課程：人工智能 專業(yè)：物流工程,8.1 自動規(guī)劃概述,8.1.1 規(guī)劃的概念及作用 1. 規(guī)劃的概念 定義8.1 從某個特定的問題狀態(tài)出發(fā)，尋求一系列行為動作，并建立一個操作序列，直到求得目標狀態(tài)為止。這個求解過程就稱為規(guī)劃。 定義8.2 規(guī)劃是對某個待求解問題給出求解過程的步驟。規(guī)劃涉及如何將問題分解為若干相應的子問題，以及如何記錄和處理問題求解過程中發(fā)現(xiàn)的各子問題間的關系。 定義8.3 規(guī)劃系統(tǒng)是一個涉及有關問題求解過程步驟的系統(tǒng)。如計算機或飛機設計、火車或汽車運輸路徑、財政和軍事規(guī)劃等問題。,8.1 自動規(guī)劃概述,8.1.1 規(guī)劃的概念及作用 例： 救援仿真機器人系

2、統(tǒng) （RoboCup Rescue Simulation System，RCRSS） 消防智能體 醫(yī)療智能體 警察智能體 普通市民 中心智能體 路障 避難所 著火建筑物 普通建筑物）,8.1 自動規(guī)劃概述,8.1.1 規(guī)劃的概念及作用 2. 規(guī)劃的作用 規(guī)劃可用來監(jiān)控問題求解過程，并能夠在造成較大的危害之前發(fā)現(xiàn)差錯。規(guī)劃的好處可歸納為簡化搜索、解決目標矛盾以及為差錯補償提供基礎。 “十二五”規(guī)劃、城市規(guī)劃、企業(yè)發(fā)展規(guī)劃,8.1 自動規(guī)劃概述,8.1.2 規(guī)劃的分類和問題分解途徑 1. 規(guī)劃的分類 （1）按規(guī)劃內容分 國家、地方、重大項目、企業(yè)、交通、城市、環(huán)境 （2）按規(guī)劃方法分 非遞階（非分

3、層）規(guī)劃與遞階（分層）規(guī)劃；線性規(guī)劃與非線性規(guī)劃；同步規(guī)劃與異步規(guī)劃；基于腳本、框架和本體的規(guī)劃；基于專家系統(tǒng)的規(guī)劃；基于競爭機制的規(guī)劃； （3）按規(guī)劃實質分 任務規(guī)劃、路徑規(guī)劃、軌跡規(guī)劃,8.1 自動規(guī)劃概述,8.1.2 規(guī)劃的分類和問題分解途徑 2. 問題分解途徑 把某些較復雜的問題分解為一些較小的子問題。有兩條實現(xiàn)這種分解的重要途徑。 第一條重要途徑是當從一個問題狀態(tài)移動到下一個狀態(tài)時，無需計算整個新的狀態(tài)，而只要考慮狀態(tài)中可能變化了的那些部分。 第二條重要途徑是把單一的困難問題分割為幾個有希望的較為容易解決的子問題。,8.1 自動規(guī)劃概述,8.1.2 規(guī)劃的分類和問題分解途徑 3. 域

4、的預測和規(guī)劃的修正 （1）域的預測 問題論域的預測。對于不可預測的論域，考慮可能的結果集合，按照它們出現(xiàn)的可能性以某個次序排列。然后，產生一個規(guī)劃、并試圖去執(zhí)行這個規(guī)劃。 （2）規(guī)劃的修正 規(guī)劃執(zhí)行失敗導致對規(guī)劃的修正。 在規(guī)劃過程中不僅要記錄規(guī)劃的執(zhí)行步驟，而且要記錄每一步必須要執(zhí)行的理由。,8.1 自動規(guī)劃概述,8.1.3 執(zhí)行規(guī)劃系統(tǒng)任務的一般方法 （1）選擇和應用原則 （2）檢驗解答與空端 （3）修正殆正確解,8.2任務規(guī)劃,8.2.1 積木世界的機器人規(guī)劃,B,A,C,C,B,A,機械手,機械手,(a),(b),8.2任務規(guī)劃,8.2.1 積木世界的機器人規(guī)劃 1. 積木世界的機器人

5、問題 機器人能夠執(zhí)行的動作舉例如下： unstack(a,b)：把堆放在積木b上的積木a拾起。在進行這個動作之前，要求機器人的手為空手，且積木a的頂上是空的。 stack(a,b)： 把積木a堆放在積木b上。動作之前要求機械手必須已抓住積木a，而且積木b頂上必須是空的。 pickup(a)： 從桌面上拾起積木a，并抓住它不放。在動作之前要求機械手為空手，而且積木a頂上沒有任何東西。 putdown(a)： 把積木a放置到桌面上。要求動作之前機械手已抓住積木a。,8.2任務規(guī)劃,8.2.1 積木世界的機器人規(guī)劃 1. 積木世界的機器人問題 狀態(tài)描述謂詞： ON(a,b)： 積木a在積木b之上。

6、ONTABLE(a)： 積木a在桌面上。 CLEAR(a)： 積木a頂上沒有任何東西。 HOLDING(a)： 機械手正抓住積木a。 HANDEMPTY： 機械手為空手。,8.2任務規(guī)劃,8.2.1 積木世界的機器人規(guī)劃 2.用F規(guī)則求解規(guī)劃序列 采用F規(guī)則表示機器人的動作，這是一個叫做STRIPS規(guī)劃系統(tǒng)的規(guī)則，它由3部分組成： 第一部分是先決條件。為了使F規(guī)則能夠應用到狀態(tài)描述中去。 第二部分是一個叫做刪除表的謂詞。當一條規(guī)則被應用于某個狀態(tài)描述或數(shù)據(jù)庫時，就從該數(shù)據(jù)庫刪去刪除表的內容。 第三部分叫做添加表。當把某條規(guī)則應用于某數(shù)據(jù)庫時，就把該添加表的內容添進該數(shù)據(jù)庫。,8.2任務規(guī)劃,8

7、.2.1 積木世界的機器人規(guī)劃 2.用F規(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),8.2任務規(guī)劃,8.2.2 STRIPS規(guī)劃系統(tǒng) STanford Research Institute Problem SolverSTRIPS STRIPS系統(tǒng)的組成如下： (1) 世界模型。為一階謂詞演算公式。 (2) 操作符(F規(guī)則)。包括先決條件、刪除表和添加表。 (3) 操作方法。應用狀態(tài)空間表示

8、和中間-結局分析。 規(guī)劃過程 每個STRIPS問題的解答為某個實現(xiàn)目標的操作符序列，即達到目標的規(guī)劃。,8.2任務規(guī)劃,8.2.3 具有學習能力的規(guī)劃系統(tǒng) 1.PULP-I的結構與操作方式 PULP-I 機器人規(guī)劃系統(tǒng)是一種具有學習能力的系統(tǒng)，它采用管理式學習，其作用原理是建立在類比的基礎上的。 2.PULP-I的世界模型和規(guī)劃結果 PULP-I系統(tǒng)能夠完成一系列規(guī)劃任務。具有學習能力的機器人問題求解與規(guī)劃系統(tǒng)PULP-I已經(jīng)成功地顯示出規(guī)劃性能的改善。,8.2任務規(guī)劃,8.2.4 分層規(guī)劃 1.長度優(yōu)先搜索 探索規(guī)劃時首先只考慮一層的細節(jié)，然后再注意規(guī)劃中比這一層低一層的細節(jié)， 2.NOAH

9、規(guī)劃系統(tǒng) （1）. 應用最小約束策略 一個尋找非線性規(guī)劃而不必考慮操作符序列的所有排列的方法是把最少約束策略應用來選擇操作符執(zhí)行次序的問題。 問題求解系統(tǒng)NOAH采用一種網(wǎng)絡結構來記錄它所選取的操作符之間所需要的排序。它也分層進行操作運算，即首先建立起規(guī)劃的抽象輪廓，然后在后續(xù)的各步中，填入越來越多的細節(jié)。,8.2任務規(guī)劃,（2）. 檢驗準則 準則法已被應用于各種規(guī)劃生成系統(tǒng)。對于早期的系統(tǒng)，如HACKER系統(tǒng)，準則只用于舍棄不滿足的規(guī)劃。在NOAH系統(tǒng)中，準則被用來提出推定的方法以便修正所產生的規(guī)劃。第一個涉及的準則是歸結矛盾準則。 第二個準則叫做消除多余先決條件準則，包括除去對子目標的多余說明。 可以把分層規(guī)劃和最少約定策略十分直接地結合起來，以求得非線性規(guī)劃而不產生一個龐大的搜索樹。,8.2任務規(guī)劃,8.2.5 基于專家系統(tǒng)的機器人規(guī)劃 1. 系統(tǒng)結構及規(guī)劃機理 （1）知識庫：用于存儲某些特定領域的專家知識和經(jīng)驗，包括機器人工作環(huán)境的世界模型、狀態(tài)、物體描述等事實和可行操作或規(guī)則等。 （2） 控制策略：包含綜合機理，確定系統(tǒng)應當應用什么規(guī)則以及采取什么方式去尋找該規(guī)則。 （3） 推理機：用于記憶所采用的規(guī)則和控制策略及推理策略。 （4）知識獲取：首先獲取某特定域的專家知識。然后用程序設計語言把這些知識變換為計算機程序。最后把它們存入知識庫待用。,8.2任務規(guī)劃,(5)解釋