人工智能導論Introductiontoartificialintelligence機械工業出版社2020第12章自動規劃【導讀案例】“雙馬”激辯AI討論：1什么是自動規劃2規劃方法3著名的規劃系統1規劃是特殊的智力指標2策劃的概念分析3自動規劃的定義4規劃應用示例第1節12.1什么是自動規劃與一些求解技術相比，自動規劃（AutomaticPlanning）與專家系統都屬于高級的求解系統與技術。由于自動規劃系統具有廣泛的應用場合和應用前景，因而引起人們的濃厚研究興趣，并取得了許多研究成果。12.1.1規劃是特殊的智力指標人們通常認為規劃是一種與人類密切相關的活動。由于規劃代表了一種非常特殊的智力指標，即為了實現目標而對活動進行調整的能力，因此，它是人類所獨有的。在日常生活中，規劃意味著在行動之前決定其進程，或者說，規劃一詞指的是在執行一個問題求解程序中任何一步之前，計算該程序幾步的過程。一個規劃是一個行動過程的描述。它可以是像百貨清單一樣的沒有次序的目標表列，但一般來說，規劃具有某個規劃目標的蘊含排序。12.1.1規劃是特殊的智力指標例如，對于大多數人來說，吃早飯之前要先洗臉和刷牙。又如，一個機器人要搬動某工件，必須先移動到該工件附近，再抓住該工件，然后帶著工件移動。許多規劃所包含的步驟是含糊的，需要進一步說明。大多數規劃都具有子規劃結構，規劃中的每個目標可以由達到此目標的比較詳細的子規劃所代替。盡管最終得到的規劃是某個問題求解算符的線性或分部排序，但是由算符來實現的目標常常具有分層結構。12.1.2規劃的概念分析規劃的概念很多，具體可以整理成如下幾點：（1）從某個特定的問題狀態出發，尋求一系列行為動作，并建立一個操作序列，直到求得目標狀態為止，這個求解過程就是規劃；（2）規劃是關于動作的推理，它是一種抽象的和清晰的深思熟慮的過程，該過程通過預期動作的期望效果，選擇和組織一組動作，其目的是盡可能好地實現一個預先給定的目標；（3）規劃是對某個待求解問題給出求解過程的步驟，規劃設計將問題分解為若干相應的子問題，以及記錄和處理問題求解過程中發現的子問題間的關系；（4）規劃系統是一個涉及有關問題求解過程的步驟的系統。12.1.2規劃的概念分析規劃有以下兩個非常突出的特點。（1）為了完成任務，可能需要完成一系列確定的步驟。（2）定義問題解決方案的步驟順序可能是有條件的。也就是說，構成規劃的步驟可能會根據條件進行修改（這稱為條件規劃）。因此，規劃的能力代表了某種意識，代表了使我們成為人類的自我意識。12.1.2規劃的概念分析泰特（1999）指出：“規劃是在使用此類規劃約束或控制行為之前，為未來行為（可能部分地）生成表示的過程。結果通常是具有時間和其他限制的一組動作，這些動作可以由一些智能體或某個智能體來執行。”12.1.2規劃的概念分析規劃一直是人工智能研究的活躍領域。規劃算法和技術已經應用到了諸多領域，包括機器人技術、流程規劃、基于Web的信息收集、自主智能體、動畫和多智能體規劃。人工智能中一些典型的規劃問題包括：（1）對時間、因果關系和目的的表示和推理。（2）在可接受的解決方案中，物理和其他類型的約束。（3）規劃執行中的不確定性。（4）如何感覺和感知“現實世界”。（5）可能合作或互相干涉的多個智能體。12.1.3自動規劃的定義自動規劃是一種重要的問題求解技術。與一般問題求解相比，自動規劃更注重于問題的求解過程，而不是求解結果。此外，自動規劃要解決的問題，如機器人世界問題，往往是真實世界問題，而不是比較抽象的數學模型問題。圖12-3規劃自動化立體庫12.1.3自動規劃的定義在研究自動規劃時，往往以機器人規劃與問題求解作為典型例子加以討論。這是因為機器人規劃能夠得到形象的和直覺的檢驗。因此，自動規劃也稱為機器人規劃（robotplanning），是機器人學的一個重要研究領域，也是人工智能與機器人學一個令人感興趣的結合點。機器人規劃的原理、方法和技術可以推廣應用到其他規劃對象或系統。雖然通常我們會將規劃和調度視為共同的問題類型，但是它們之間有一個相當明確的區別：規劃關注“找出需要執行哪些操作”，而調度關注“計算出何時執行動作”。規劃側重于為實現目標選擇適當的行動序列，而調度側重于資源約束（包括時間）。我們把調度問題作為規劃問題的一個特例。12.1.3自動規劃的定義在人工智能領域，所有規劃問題的本質就是將當前狀態（可能是初始狀態）轉變為所需目標狀態。所生成的規劃就是在某個領域中執行這種轉換的一系列步驟。求解規劃問題所遵循的步驟順序稱為操作符模式。操作符模式表征動作或事件（可互換使用的術語）。操作符模式表征一類可能的變量，這些變量可以用值（常數）代替，構成描述特定動作的操作符實例。“操作符”這個術語可以用作“操作符模式”或“操作符實例”的同義詞。12.1.4規劃應用示例在魔方的離散拼圖和15拼圖的移動方塊拼圖示例中，我們可以找到很熟悉的規劃應用，其中包括國際象棋、橋牌以及調度問題。由于運動部件的規律性和對稱性，這些領域非常適合開發和應用

規劃算法。魔方拼圖15拼圖12.1.4規劃應用示例同樣常見的問題是試圖讓機器人識別墻壁和障礙物，在迷宮中移動，成功地到達其目標。這是計算機和機器人視覺領域的典型問題。圖12-5所示的是機器人多年來一直在求解的迷宮問題類型。機器人不僅需要從A移動到B，還需要能夠識別墻壁并進行妥善處理。

圖12-5一個典型的迷宮問題12.1.4規劃應用示例在設計和制造應用中，人們應用規劃來解決組裝、可維護性和機械部件拆卸問題。人們使用運動規劃，自動計算從組裝中移除零件的無碰撞路徑。視頻游戲程序員和人工智能規劃社區有許多潛在的機會，結合各種人們努力得到的成果，生成精彩、獨特、類似人類的角色。人們將規劃應用到開發虛擬人類和計算機生成動畫也有著廣泛的興趣。動畫師的目標是開發具有人類演員特征的角色，同時能夠設計高層次的運動描述，使得這些運動可以由智能體執行。這仍然是一個非常詳細、費力的逐幀過程。動畫師希望通過規劃算法的發展來減少這些過程。12.1.4規劃應用示例將自動操作規劃應用到計算機動畫中，根據任務規格計算場景中人物的動畫，這使得動畫師可以專注于場景的整體設計，而不是專注于如何在逼真、無碰撞的路徑中移動人物的細節。一個具體的例子是為執行如操縱物體之類的任務，生成人類和機器人手臂的最佳運動，這不但與計算機動畫相關，而且與人體工程學和產品的可用性評估相關。科加等人開發了一個執行多臂操作的規劃器：給定一個待完成的目標或任務，這個規劃器將會生成必要的動畫，使得在人與機器人手臂在棋盤上進行協同操作。12.1.4規劃應用示例圖12-6所示的是一個機器人手臂規劃器，這個規劃器執行了多臂任務，在汽車裝配線上協助制造。圖12-6在汽車裝配線上協助制造的機器人手臂12.1.4規劃應用示例娛樂和游戲行業關注生產高愿量的動畫角色，希望角色動作盡可能逼真，還希望角色有能力自動適應出現挑戰和障礙的動態環境。行為規劃可為動畫角色生成這些逼真的動作。勞和庫夫納通過創建高層次動作的有限狀態機，捕捉、利用真實的人體動作，然后執行全局搜索，計算動作序列，將動畫角色帶到目標位置。12.1.4規劃應用示例示例12-1說明制訂規劃過程和執行規劃過程之間的區別。讓我們思考一下：規劃你離開家去工作的過程。你必須出席上午10:00的會議。早上上班通常需要40分鐘。在準備上班的過程中，你還可以做一些自己喜歡做的任務——一些任務是非常重要的，一些任務是可有可無的，這取決于你可用的時間。12.1.4規劃應用示例下面所列出的是在工作前你認為要完成的一些任務。（1）將幾件襯衫送至干洗店。（2）將瓶子送去回收。（3）把垃圾拿出去。（4）在銀行的自動提款機上取現金。（5）以本地最便宜的價格購買汽油。（6）為自行車輪胎充氣。（7）清理汽車——整理和吸塵。（8）為汽車輪胎充氣。12.1.4規劃應用示例作為一個聰明的人，你可能立刻會問這些問題（或任務）的限制時間。也就是說，在保證你能夠準時參加會議的情況下，這些任務有多少可用的時間？你于上午8:00起床，認為兩個小時已經足夠執行上述許多任務，并能及時參加上午10:00的會議。在上述8項可能的任務中，你很快就會確定只有兩項是非常重要的：第4項（獲得現金）和第8項（為汽車輪胎充氣）。第4項很重要，因為從經驗來看，如果現金不足，那么你這一天會寸步難行。你需要購買餐點、小吃和其他可能的物品。第8項可能比第4項更重要，這取決于輪胎中有多少氣。在極端情況下，這可能使你無法駕駛或無法安全駕駛。12.1.4規劃應用示例在大多數情況下，如果輪胎氣不足，至少在駕駛舒適度和汽車每加侖英里方面效率不高。現在，你確定第4項和第8項很重要、不能避免。這是一個分級規劃的例子，也就是對必須完成的任務進行分級或賦值。換句話說，并不是所有的任務都是同等重要的，你可以相應地對它們進行排序。12.1.4規劃應用示例你想是否有靠近銀行/ATM的加油站。所得出的結論是最近的加油站距離銀行約三個街區。你也在想：“如果我已經去加油站充氣，那么我也可以買汽油。”現在你在思考：“在銀行附近的哪個加油站還有一個氣泵？”這是一個機會規劃的例子。也就是說，你正在嘗試利用在規劃形成和規劃執行過程中的某個狀態所提供的條件和機會。在這種情況下，你實際上不需要購買汽油，但是你試圖節省一些時間，在這個意義上，如果你花費了時間和精力開車去加油站充氣，那么去一個加油站充氣，再到另一個加油站殉買汽油，就變得不太高效了（無論是在時間上還是在金錢上）。12.1.4規劃應用示例在這一點上，第1~3項看起來完全不重要；第6~7項看起來同樣不重要，并且這些任務更適合周末進行，因為周末可以有更多時間執行這樣的任務。當然，除非你正在規劃駕駛和騎自行車的某個組合，否則為自行車輪胎充氣通常與開車不相關。讓我們考慮一些情況，在這些情況中，第1~3可能非常相關。第1項：將幾件襯衫送至干洗店在繁忙的工作日上午，這看起來似乎是一項無關緊要的多余任務，但是，也許第二天你要接受新工作的面試，或者你想在做演講時穿得得體一些，或者這是你期待已久的一個約會。在這些情況下，你要正確思考（規劃），做正確的事情，獲得最佳機會，讓自己變得成功和快樂。12.1.4規劃應用示例第2項：丟棄瓶子進行回收同樣，這通常是一個“周末”型的活動。會不會有這樣一種情形：在這種情況中，這是必需的行動？有的，不過，這代表你遇到了一種非常遺憾的情況：你剛剛丟了錢包，而錢包里有你所有的現金、信用卡和身份證。你需要將100個空瓶送到超市回收，每個瓶子5美分，這樣才能獲得現金。這是一件非常遺憾的事情，我們希望永遠不會發生在你身上。除此之外，如果你丟了錢包，你就不應該在沒有駕駛證的情況下駕駛。盡管如此，這聽起來像是我們應該做好準備的一種情況。如果這確實發生了，你也許有足夠的理由不參加那次活動。12.1.4規劃應用示例第3項：把垃圾拿出去在一些相當現實的條件下，這個任務在重要性方面可以得到很大程度上的重視。下面是一些例子。（l）垃圾散發出可怕的惡臭。（2）人們聲稱你的公寓都是廢棄物，你有責任清理它。（3）這是星期一早上，如果現在不收拾，那么直到星期四才會有人來收拾垃圾。12.1.4規劃應用示例基于某些可能發生的事件或某些緊急情況做出的規劃，稱為條件規劃。作為一種“防御性”措施，這種規劃通常是有用的，或者你必須考慮一些可能發生的事件。例如，如果你計劃在9月初在佛羅里達州舉辦大型活動，那么考慮颶風保險可能不是一個壞主意。有時候，我們只能規劃事件（操作符）的某些子集，這些事件的子集可能會影響到我們達成目標，而無須特別關注這些步驟執行的順序。我們將此稱為部分有序規劃。在示例12-1的情況下，如果輪胎的情況不是很糟糕，那么我們可以先去加油站充氣，也可以先到銀行取現金。但是，如果輪胎確實癟了，那么執行該規劃的順序是先修理輪胎，然后進行其他任務。12.1.4規劃應用示例通過注意一些更多的現實，我們就可以結束這個例子了。即使兩個小時看起像是花了大量的時間來處理一些差事，我們依然需要40分鐘的上班時間，但是人們很快就意識到，即使在這個簡單的情況下，也有許多未知數。例如，在加油站、在氣泵處或在銀行可以有很多條線路；在高速公路上可能會發生事故，拖延了上班時間；或者可能會有警察、火警或校車，這些也會導致延遲。換句話說，有許多未知事件可能會干擾最佳規劃。1規劃即搜索2部分有序規劃3分級規劃4基于案例的規劃第2節12.2規劃方法規劃可用來監控問題求解過程，并能夠在造成較大的危害之前發現差錯。規劃的好處可歸納為簡化搜索、解決目標矛盾以及為差錯補償提供基礎，把某些較復雜的問題分解為一些較小的子問題。12.2.1規劃即搜索規劃本質上是一個搜索問題，就計算步驟數、存儲空間、正確性和最優性而言，這些涉及搜索技術的效率。找到一個有效的規劃，從初始狀態開始，并在目標狀態處結束，一般要涉及探索潛在大規模的搜索空間。如果有不同的狀態或部分規劃相互作用，事情會變得更加困難。因此，查普曼（1987）證明了，即使是簡單的規劃問題在大小方面也可能是指數級的。12.2.1規劃即搜索1.狀態空間搜索早期的規劃工作集中在游戲和拼圖的“合法移動”方面，觀察是否可以發現一系列的移動將初始狀態轉換到目標狀態，然后應用啟發式評估來評估到達目標狀態的“接近度”——這些技術己經應用到規劃領域了。12.2.1規劃即搜索2.中間結局分析最早的人工智能系統之一是Newell和Simon的一般問題求解器（GPS），GPS使用了一種稱為“中間結局分析”的問題求解和規劃技術，在中間結局分析背后的主要思想是減少當前狀態和目標狀態之間的距離。也就是說，如果要測量兩個城市之間的距離，算法將選擇能夠在最大程度上減少到目標城市距離的“移動”，而不考慮是否存在機會從中間城市達到目標城市。這是一個貪心算法，它對所到過的位置沒有任何記憶，對其任務環境沒有特定的知識。12.2.1規劃即搜索例如，你想從紐約市到加拿大的渥太華，距離是682千米，估計需要約9小時的車程。飛機只需要1小時，但由于這是一次國際航班，費用是600美元，這個費用高得嚇人。12.2.1規劃即搜索對于這個問題，中間結局分析自然偏向飛行，但這是非常昂貴的。一個有趣的可替代方法是結合了時間和金錢的成本效率，同時允許充分的自由，即飛往紐約州錫拉丘茲（最接近渥太華的美國大城市），然后租一輛車開車到渥太華。注意到就推薦的解決方案而言，可能會有一些壓倒性因素。例如，你必須考慮租車的實際成本，你將在渥太華度過的天數，以及你是否真的需要在渥太華開車。根據這些問題的答案，你可以選擇公共汽車或火車來滿足部分或全部的交通需求。12.2.1規劃即搜索3.規劃中的各種啟發式搜索方法狀態空間（非智能、窮盡）的搜索技術可能會導致必須探索太多的可能性，為了彌補這種情況，我們簡要介紹為此開發的各種啟發式搜索技術。（1）最小承諾搜索。是指“規劃器的任何方面，只有在受到某些約束迫使的情況下，才承諾特定的選擇”。比如說，你打算搬到一所新的公寓。首先，你根據自己特定的收入水平選定合適的城鎮和社區，不需要決定將要居住的區塊、建筑和具體的公寓。這些決定可以推遲到更晚、更適合的時間做出。12.2.1規劃即搜索（2）選擇并承諾。這是一種獨特的規劃搜索技術，這種方法并不能激發太多的信心。它是指基于局部信息（類似于中間結局分析），遵循一條解決路徑的新技術，這項新技術通過做出的決策（承諾）得到測試。使用這種方式測試的其他規劃器可以集成到稍后的規劃器中，這些稍后的規劃器可以搜索替代方案。當然，如果對一條路徑的承諾沒有產生解，那么就出現問題了。12.2.1規劃即搜索（3）深度優先回溯。是考慮替代方案的一種簡單方法，特別是當只有少數解決方案可供選擇時。這種方法涉及在有替代解決方案的位置保存解決方案路徑的狀態，選中第一個替代路徑，備份搜索；如果沒有找到解決方案，則選擇下一個替代路徑。通過部分實例化操作符來查看是否已經找到解決方案，測試這些分支的過程，我們稱之為“舉起”。（4）集束搜索。它與其他啟發式方法一起實現，選擇“最佳”解決方案，也許是由集束搜索建議子問題的“最佳”解決方案。12.2.1規劃即搜索（5）主因最佳回溯。通過搜索空間的回溯，雖然可能得到解決方案，但是在多個層次中所需要探索的節點數量龐大，所以這可能非常昂貴。主因最佳回溯花費更多的努力，確定了在特定節點所備份的局部選擇是最佳選擇。12.2.1規劃即搜索作為一個類比，讓我們回到選擇某個城鎮來生活的問題。考慮候選地區的兩個主要因素是距離和價格。根據這些因素，我們找到最理想的區域。但是現在，我們必須在可能的5~10個合理候選城鎮中做出決定。現在，我們必須考慮更多的因素。①學校系統怎么樣（為了小孩）？②在這個地區，購物如何？③這個城鎮有多安全？④它距離中心位置有多遠（運輸）？⑤在這個地區還有哪些景點？12.2.1規劃即搜索當你能夠進行評估時，基于公寓的價格和每個候選城鎮到你工作地點的距離，再加上上述5個附加因素，你應該可以選擇一個城鎮，然后繼續進行搜索，進而選擇一處適當的公寓。一旦選擇了一個城鎮，你可以查看這個城鎮某些公寓的可用性和適用性。如有必要，稱可以重新評估其他城鎮的可能性，并選擇另―個城鎮（基于兩個主要因素和5個次要因素）作為主要選擇。這就是主因最佳回溯算法的工作原理。12.2.1規劃即搜索（6）依賴導向式搜索。回溯到保存狀態并恢復搜索可能帶來極大的浪費。雖然存儲在選擇點能找到解的所保存狀態可能有用，但是實踐證明，存儲決策之間的依賴關系所做出的假設和可以做出選擇的替代方案可能更有用、更有效。通過重建解決方案中的所有依賴部分，系統就避免了失敗，同時不相關的部分也可以保持不變。（7）機會式搜索。基于“可執行的最受約束的操作”。所有問題求解組件都可以將其對解決方案的要求歸結為對解決方案的約束，或對表示被操作對象的變量值的限制。操作可以暫停，直到有進一步可用信息。12.2.1規劃即搜索（8）元級規劃。是從各種規劃選項中進行推理和選擇的過程。一些規劃系統具有類似操作符表示的規劃轉換可供規劃器使用。系統執行獨立的搜索，在任何點上，確定最適合應用哪個操作符。這些動作發生在做出任何關于規劃應用的決策之前。（9）分布式規劃。系統在一群專家中分配子問題，讓他們求解這些問題，在通過黑板進行溝通的專家之間傳遞子問題并執行子問題。這里總結回顧了在規劃中使用的搜索方法。人工智能規劃社區已經開發了一些技術來限制所需要的搜索量。12.2.2部分有序規劃部分有序規劃（POP）被定義為“事件（操作符）的某個子集可以實現、達到目標，而無須特別關注執行步驟的順序。”在部分有序規劃器中，可以使用操作符的部分有序網絡表示規劃。在制訂規劃過程中，只有當問題請求操作符之間的有序鏈時，才引進有序鏈，在這個意義上，部分有序規劃器表現為最小承諾。相比之下，完全有序規劃器使用操作符序列表示其搜索空間中的規劃。12.2.2部分有序規劃部分有序規劃通常有以下3個組成部分。（1）動作集。{開車上班，穿衣服，吃早餐，洗澡}（2）順序約束集。{洗澡，穿衣服，吃早餐，開車去上班}（3）因果關系鏈集。穿衣服——著裝→開車去上班12.2.2部分有序規劃這里的因果關系鏈是，如果你不想沒穿衣服就開車，那么請在開車上班前穿好衣服！在不斷完善和實現部分規劃時，這種鏈有助于撿測和防止不一致。回顧一下，在前幾章討論的標準搜索中，節點等于具體世界（或狀態空間）中的狀態。在規劃世界中，節點是部分規劃。因此，部分規劃包括以下內容。操作符應用程序集Si。部分（時間）順序約束Si<Sj。因果關系鏈Si——→Sj。12.2.2部分有序規劃這意味著，Si實現了c，c是Sj的前提條件。因此，操作符是在因果關系條件上的動作，可以用來獲得開始條件。開始條件是未被因果關系鏈接的動作的前提條件。這些步驟組合形成一個部分規劃：為獲得開始條件，使用因果關系鏈描述動作。從現有動作到開始條件過程中，做出因果關系鏈。在上述步驟之間做出順序約束。12.2.2部分有序規劃圖12-7描繪了一個簡單的部分有序規劃。這個規劃在家開始，在家結束。在部分有序規劃中，不同的路徑（如首先選擇去加油站還是銀行）不是可選規劃，而是可選動作。如果每個前提條件都能達成（我們到銀行和加油站，然后安全回家），我們就說規劃完成了。當動作順序完全確定后，部分有序規劃成了完全有序規劃。一個示例是，如果發現汽車的油箱幾乎是空的，當且僅當達成每個前提條件時，規劃才能算完成。當一些動作Sk發生時，這阻止我們實現規劃中所有前提條件，阻礙了規劃的執行，我們就說發生了對規劃的威脅。威脅是一個潛在的干擾步驟，阻礙因果關系達成條件。12.2.2部分有序規劃圖12-7部分有序規劃12.2.2部分有序規劃在上面的例子中，如果車子沒有啟動，那么這個威脅就可能會推翻“最好的規劃”。總之，部分有序規劃是一種健全、完整的規劃方法。如果失敗，它可以回溯到選擇點。它可以使用析取、全稱量化、否定和條件的擴展。總體來說，當與良好的問題描述結合時，這是一項有效的規劃技術。但是，它對子目標的順序非常敏感。12.2.3分級規劃規劃適用層次結構，也就是說，并不是所有的任務都處于同一個重要級別，一些任務必須在進行其他任務之前完成，而其他任務可能會交錯進行。此外，層次結構（有時為了滿足任務前提條件而需要）有助于降低復雜性。分級規劃通常由動作描述庫組成，而動作描述由執行組成規劃的一些前提條件的操作符組成。其中一些動作描述將“分解”成多個子動作，這些子動作在更詳細（較低）級別上操作。因此，一些子動作被定義為“原語″，即不能進一步分為更簡單任務。12.2.3分級規劃分級任務網絡（HTN）規劃適用于細化規劃模型。初步規劃納入任務規范假設，這個任務規范假設是關于待執行的規劃（或可能是部分解決方案）所處的局面。然后，這可以通過層次結構提煉到更高級別的細節，同時也解決了在規劃中出現的問題和缺陷。在實際應用中，分級規劃已經得到廣泛部署，如物流、軍事運行規劃、危機應對（漏油）、生產線調度、施工規劃，又如任務排序、衛星控制的空間應用和軟件開發。12.2.4基于案例的規劃基于案例的推理是一種經典的人工智能技術，它與描述某個世界中狀態的先前實例并確定在當前世界中新情況與先前情況相符程度的能力密切相關。在法律與醫學界，它與識別先例密切聯系。如果能夠這樣做，那就對此先例進行匹配，然后選擇基于靜態的動作過程。在基于案例的規劃中，學習的過程是通過規劃重演以及通過在類似情況下工作過的先前規劃進行“派生類比”。基于案例的規劃側重于應用過去的成功規劃以及從先前失敗的規劃中恢復。12.2.4基于案例的規劃基于案例的規劃器設計用于尋找以下問題的解決方案：規劃內存表示是指決定存儲的內容以及如何組織內存的問題，以便有效并高效地檢索和重用舊規劃。規劃檢索處理檢索一個或多個解決過類似當前問題的規劃問題。規劃重用解決為滿足新問題而能夠重新利用（適應）已檢索的規劃的問題。規劃修訂是指成功測試新規劃，如果規劃失敗了，則修復規劃的問題。規劃保留處理存儲新規劃的問題，以便對將來的規劃有用。通常情況下，如果新規劃失敗了，則此規劃與一些導致其失敗的原因一起被存儲。12.2.4基于案例的規劃根據這5個參數，斯巴拉吉研究了一些系統。基于案例的規劃器，使用合理的局部選擇，積累和協商成功的規劃。重復使用部分匹配所學習到的經驗，新問題只需要相似就可以重新使用規劃。所謂“Prodigy/Analogy”的系統執行“懶惰”歸納，這樣所學的片斷就不需要為其正確性做解釋，因此也就不需要完整的領域理論。在局部決策中的學習可以增加所學知識的轉移（但是也增加了匹配成本），因此還需要定義在規劃情況之間相似性度量。為了完成此類任務，現代規劃系統通常與機器學習方法相關聯。1STRIPS2NOAH3NONLIN4O-PLAN第3節5Graphplan12.3著名的規劃系統下面，我們來了解規劃研究開發歷史上早期的3個重要系統，即STRIPS、NOAH和NONLIN。最早是STRIPS；之后斯坦福大學研究所的NOAH系統總結了STRIPS背后的規劃思想；接著是NONLIN，它繼承了NOAH的想法并更進了一步。后來，又陸續開發了一些較新的現代規劃系統，例如有O-Plan和Graphplan系統。12.3.1STRIPSSTRIPS也稱斯坦福大學研究所問題求解器，是最早、最基礎的規劃系統之一。STRIPS語言已經成了一個標準，例如Grasp(x)、Puton(x,y)、ClearTop(y)等。它能夠使用一階邏輯表示領域狀態的應用，也可以表示領域狀態的改變。它還可以使用中間結局分析法確定需要實現的目標和子目標。這些目標和子目標是先決條件，需要先獲得才能得到解。STRIPS操作符提供了一個簡單而有效的框架，這個框架可以表示在領域中的搜索和動作。正如我們所看到的，在規劃領域，它們構成了未來工作的基礎。12.3.1STRIPS在STRIPS世界中，我們要確定其帶來的另外兩個問題。其中的一個是分支問題，即由于采取了動作，世界發生變化的結果是什么？例如，如果機器人從A點到B點，積木塊A是否依然在積木塊B上？機器人的輪子上是否仍然有輪胎？它是否仍然使用相同的電量來操作？12.3.1STRIPS有關積木塊狀態的問題很容易回答，但是，一旦遇到涉及自我狀態意識（知覺）和常識知識問題，分支問題就變得更加嚴重起來。STRIPS提出的另一個問題被稱為合格問題。也就是說，當執行某些動作（例如將鑰匙放在鎖孔中）時，定義成功的必要合格條件是什么？如果鑰匙沒有打開門，可能是什么錯了（例如鑰匙錯了、鑰匙壞了等等）。STRIPS在自動規劃系統的歷史、思考和開發方面是一個非常重要的系統。12.3.2NOAH厄爾·薩爾多提（1975）描述了程序NOAH（NetsofActionHierarchies，動作層次網絡）背后的概念。具體體現在3個方面：（1）對開發分級規劃（而不是開發單一級別的規劃）在技術上做出了重大貢獻。（2）引入和利用將規劃表示為部分有序序列的思想，部分有序序列僅僅是對步驟的時間順序做出了必需的承諾。（3）開發了機制，使得規劃系統能夠檢查自己的規劃，這樣就可以改進這些規劃，也因此可以智能地監測規劃執行。12.3.2NOAH這些對于僅限于單一級別動作的GPS、STRIPS和MIT積木世界而言，都是突出的進展。NOAH帶來3種類型的知識：①問題求解；②在動作程序規范中的領域特定性；③處理具體情況的符號知識數據庫。12.3.2NOAHNOAH對自動規劃做出的貢獻特別表現在以下幾個方面：（1）使用命令式語義來生成類似框架的結構。（2）考慮了規劃的非線性性質，規劃被視為相對于時間的部分排序。這也避免了由線性引起的深度回溯的必要性。（3）規劃可以在很多抽象層次上完成。（4）使用分級規劃，提供執行監測和簡易的錯誤恢復。（5）提供了迭代的抽象表示。（6）鼓勵結構的重要性，幫助處理在不同細節層次中的大量知識。12.3.3NONLIN為了生成部分有序動作網絡的規劃，AustinTate（1977）開發了NONLIN系統，這是一個規劃空間的規劃器（而不是―個狀態空間規劃器），NONLIN向后搜索問題空間，找到目標解決方案規劃。它使用功能性的、狀態可變的規劃生成表示，其目標是基于結構的規劃開發，基于規劃基本原理，考慮替代方法。12.3.3NONLINNONLIN可以執行問答模態真值標準條件。也就是說，它可以響應兩種查詢：（1）在當前網絡中的節點N處，語句P是否具有值V（V值的選擇為“絕對是V，絕對不是V，或不可判定”）？（2）如果在給定網絡中P沒有某個值，那么在網絡中必須添加哪些鏈才能使P在N節點處具有這個值？為了回答第一種問題，NONLIN將在網絡中找到可用于提供正確結果的“關鍵”節點。12.3.3NONLINNONLIN一個最重要的特征就是，在規劃期間維持了一個目標結構表，記錄網絡中某點必須為真的事實，以及使其為真的可能的“貢獻者”。使用這種方式，系統可以在不選擇其中一個（也可能是多個）貢獻者的情況下進行規劃，直到如上所述的交互檢測強制執行選擇“貢獻者”。12.3.4O-PLAN1983-1999年，愛丁堡大學的AustinTate開發了著名的NONLN系統的繼任者O-PLAN。O-PLAN是用CommonLisp編寫的，可用于網絡規劃服務（自1994年起）。O-PLAN擴展了泰特在NONLIN的早期工作（分級規劃系統）。這個系統能夠將規劃作為部分有序活動網絡生成，這些網絡可以檢查時間、資源、搜索等方面的各種限制。12.3.4O-PLANO-PLAN是一個實用的規劃器，可以用于各種人工智能規劃，它包括以下特征。領域知識引導和建模工具。豐富的規劃表示和使用。分級任務網絡規劃。詳細的約束管理。基于目標結構的規劃監測。動態問題處理。在低高節奏下的規劃維修。具有不同角色的用戶接口。規劃和執行工作