機(jī)械工業(yè)出版社2020《人工智能導(dǎo)論》課程同步PPT課件第12章 自動規(guī)劃

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

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

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