HTN規(guī)劃方法的性能研究

HTN規(guī)劃方法的性能研究摘要人工智能作為一門對從環(huán)境接收感知信息并執(zhí)行行動的智能體的研究的學科，近年來越來越受到各個領域研究人員的關注與重視，而自動規(guī)劃是人工智能中一個十分重要的研究子領域，專門從計算上研究規(guī)劃這種抽象的、清晰的深思熟慮過程，這個過程通過預期動作的期望效果，選擇和組織一組動作，其目的是盡可能地實現一些預先給定的目標。自動規(guī)劃的方法眾多，但近年來HTN（分層任務網絡）規(guī)劃則是學界最熱門的研究方向之一，同時在對HTN規(guī)劃的研究中也產生了許多新的規(guī)劃方法，例如規(guī)劃空間規(guī)劃的搜索空間節(jié)點部分規(guī)劃的結構是從對HTN做出貢獻的規(guī)劃器NONLIN中逐步發(fā)展來的。本課題將選取HTN規(guī)劃中由UniversityofMaryland的DanaNau等人開發(fā)的具有良好性能的開源規(guī)劃器SHOP為例，通過編寫領域知識對一個電梯載人問題進行求解并引入啟發(fā)式的方法，同時用簡單調度規(guī)則對此問題求解，在不同的問題規(guī)模下對求解的結果進行比較。最后，本課題對此標桿問題引入時態(tài)約束，在SHOP2規(guī)劃器中用MTP（多時間軸預處理）技術對問題進行求解。關鍵詞：人工智能；自動規(guī)劃；HTN規(guī)劃；時態(tài)約束

ResearchonPerformanceofHTNPlanningMethodsAbstractArtificialintelligence,adisciplinestudyingonreceptionofsensoryinformationfromenvironmentandaction,hasbeenpaidincreasinglyattentioninrecentyears.Asanimportantsubfieldofartificialintelligence,automaticplanningmainlyfocusesontheprocessofabstract,clearthoughtbycomputing.Byexpectingeffectofexpectedoperation,theprocessselectsandorganizesasetofactionstoachievegivengoals.Althoughmanymethodsinautomaticplanninghavebeenwellestablished,HierarchicalTaskNetwork(HTN)isbecomingpopularinthoseyearsandnovelplanningmethodshavebeendevelopedfromthestudyonHTNplanning.Forexample,thestructureofspatialplanning,thatisthenodeinthesearchspaceofplanningspaceplanning,hasbeendevelopedgraduallyfromtheNONLINplanner,whichhascontributedalottotheHTNplanning.ThispaperwillselecttheHTNopensourceplannerSHOP2withgoodperformancewhichisdevelopedbyDanaNauwhoisfromUniversityofMaryland,andsolveanelevatormannedproblembywritingthedomaindescriptionintheSHOP2plannerwithintroducingaheuristicapproach.Meanwhile,wewillusethesimpleschedulingrulestosolvetheproblem,andcomparetheresultsofthesimpleschedulingrulesandSHOP2plannerindifferentproblemscale.Finally,weintroducetemporalconstraintsintothisbenchmarkproblem,whilesolvethisproblembyusingtheMTP(multi-timelinepreprocessing)technologyinSHOP2planner.Keywords：ArtificialIntelligence;automaticplanning;HTNplanning;temporalconstraints

目錄摘要 1Abstract 21. 選題背景 51.1. 課題來源及背景 51.2. 課題目的及意義 61.3. 課題內容及研究方法 61.4. 國內外基本研究概況 71.5. 指導思想與文章結構說明 102. 關鍵理論與技術 122.1. 規(guī)劃問題的經典表示方法 122.2. HTN規(guī)劃 142.3. MTP技術 163. 電梯載人問題HTN建模及求解 183.1. 電梯載人問題 183.2. 利用JSHOP2進行建模求解 194. HTN規(guī)劃與簡單調度規(guī)則的比較 304.1. 幾種常用的簡單調度規(guī)則 304.2. 調度規(guī)則求解及與規(guī)劃器比較 304.3. 擴大問題規(guī)模并求解比較 325. 時態(tài)約束下的HTN規(guī)劃 375.1. 引入時態(tài)約束后的問題 375.2. 對領域及問題描述所做的修改 375.3. 時態(tài)規(guī)劃求解過程與結果 425.4. MTP處理時態(tài)約束的小結與存在問題 436. 總結與今后研究方向 456.1. 總結 456.2. 今后研究方向 46致謝 47參考文獻 48附錄代碼清單 51附錄一電梯載人問題代碼 51附錄二擴大規(guī)模后的電梯載人問題代碼 55附錄三引入時態(tài)約束后的電梯載人問題代碼 58

選題背景課題來源及背景規(guī)劃是關于動作的推理。它是一種抽象的、清晰的深思熟慮過程，這個過程通過預期動作的期望效果，選擇和組織一組動作，其目的是盡可能好地實現一些預先給定的目標。而智能規(guī)劃則是人工智能（AI）中專門從計算上研究這個深思熟慮過程的一個領域[1]。規(guī)劃的形式由于動作的種類繁多而多種多樣，例如運動規(guī)劃是在移動系統(tǒng)所在的參數配置空間中尋找一條軌跡，感知規(guī)劃是解決類似于需要何種信息及合適需要這些信息的問題，等等。由于對于自動規(guī)劃的研究始于工程實踐中對于快速經濟且有效地解決規(guī)劃問題的需求，早期的自動規(guī)劃實踐都集中在領域相關規(guī)劃，即對每種問題都根據問題的特點使用專門的表示并設計開發(fā)與之相適應的技術，這種規(guī)劃方法的好處在于能夠很好的利用領域知識解決問題，但也存在著不可回避的缺陷，對于每種規(guī)劃問題都需要分別進行處理而不是使用一般化的工具，其費用較高?；诖?，自動規(guī)劃研究的更主要是與領域無關的通用方法，這種規(guī)劃是基于抽象的、通用的動作模型。這類模型主要有以下一些形式的模型與規(guī)劃能力：項目規(guī)劃，所用的模型動作已簡化為時代和次序約束；調度與資源分配，所用動作模型包括項目規(guī)劃中的約束，還增加了動作的資源約束；規(guī)劃合成，所用模型的動作比前面兩種模型更豐富，增加了動作運用的條件和動作對世界狀態(tài)的效果。盡管自動規(guī)劃在理論上的研究還處于早期階段，但實際應用中已經發(fā)展到可以滿足許多需求的程度了，而在這方面的成功例子非常多，例如在自動化立體倉庫中AGV小車的路徑與動作規(guī)劃。通過自動規(guī)劃技術，可以讓智能體通過感知周邊的環(huán)境為實現給定的目標自動的規(guī)劃出一套行動方案。課題目的及意義到目前為止，國內外學者提出了各種各樣思路完全不同的規(guī)劃方法，不同的規(guī)劃方法能夠處理的問題的特征也不盡相同。在過去的15年內，大部分在人工智能規(guī)劃系統(tǒng)上的實用工作都基于分層任務網絡（HTN）規(guī)劃[2]，這是繼STRIPS規(guī)劃后最為重要的規(guī)劃方法。同時，針對于某一種具體的規(guī)劃方法，也有許多有著差別的規(guī)劃器被提出，例如HTN規(guī)劃中比較有影響力的規(guī)劃器有UMCP[3]、NONLIN[4]、SHOP2[5]、SIPE-2[6]、O-PLAN[7][8]等。本課題將選取HTN規(guī)劃中由UniversityofMaryland的DanaNau等人開發(fā)的具有良好性能的開源規(guī)劃器SHOP為例，通過編寫領域知識對一個電梯載人問題進行求解并引入啟發(fā)式的方法對其進行改進，同時用簡單調度規(guī)則對此問題求解，在不同的問題規(guī)模下對求解的結果進行比較。最后，本課題對此標桿問題引入時態(tài)約束，在SHOP2規(guī)劃器中用MTP（多時間軸預處理）技術對問題進行求解。通過對本課題的研究，能夠使得自己對HTN規(guī)劃有更為清晰與全面的了解，同時也對規(guī)劃空間規(guī)劃做一定的了解，通過與簡單調度規(guī)則對問題求解的結果進行比較，對自動規(guī)劃技術的優(yōu)勢產生一定的感性認識，并學習MTP技術為今后的研究奠定基礎。此外，從學習規(guī)劃器語法、編寫領域知識、到求解等這一系列過程，通過自己的切實參與，會使自己基本了解研究問題、解決問題包括哪些基本步驟。對模型的求解過程會使自己在算法設計方面積累一定的經驗。課題內容及研究方法本課題由一個電梯載人問題展開，在使用HTN方法解決此問題的過程中對HTN進行多方面的探究。課題首先使用在2002年國際規(guī)劃大賽上獲得了前四名的好成績的高效規(guī)劃系統(tǒng)——SHOP2規(guī)劃器對此問題進行建模求解，在此過程中逐步加入啟發(fā)式規(guī)則引導搜索，以期得到更高的規(guī)劃解。并設計一個問題，對此領域進行測試，以確保領域的可靠性與完備性。之后課題提出幾種常用在電梯調度領域的調度規(guī)則對問題進行手動求解，并對求解的結果進行比較。擴大問題規(guī)模后，再次用SHOP2規(guī)劃器與調度規(guī)則求解比較。同時，鑒于規(guī)劃空間規(guī)劃的搜索空間節(jié)點部分規(guī)劃的結構是從對HTN做出貢獻的規(guī)劃器NONLIN中逐步發(fā)展來的，課題也試圖在規(guī)劃空間規(guī)劃中最具代表性的開放源代碼的UCPOP的Lisp執(zhí)行程序中對此問題的求解進行了一定的探索。最后，由于時態(tài)約束是最重要的一類約束，課題也對此做了一定的工作，課題為之前所提到的電梯問題增添時態(tài)約束，并使用MTP（多時間軸預處理）技術在SHOP2規(guī)劃器中進行求解。國內外基本研究概況到目前為止，國內外學者提出了各種各樣思路完全不同的規(guī)劃方法，不同的規(guī)劃方法能夠處理的問題的特征也不盡相同。同時，針對于某一種具體的規(guī)劃方法，也有許多有著差別的規(guī)劃器被提出，例如HTN規(guī)劃中比較有影響力的規(guī)劃器有UMCP[3]、NONLIN[4]、SHOP2[5]、SIPE-2[6]、O-PLAN[7][8]等。本課題主要是對一個電梯載人問題進行研究，通過標準化的方法將規(guī)劃問題進行表達，所涉及到的規(guī)劃方法主要有HTN規(guī)劃、規(guī)劃空間規(guī)劃，并在本文最后的部分對時態(tài)約束規(guī)劃有一定的涉及。因此本章節(jié)將從四個方面進行綜述：(1)智能規(guī)劃的模型及規(guī)劃問題的表示。(2)HTN規(guī)劃。(3)時態(tài)規(guī)劃。智能規(guī)劃的模型及規(guī)劃問題的表示自動規(guī)劃的早期研究工作收到了自動推理證明的很大影響。首批自動規(guī)劃闡述的一種形式[9]使用了對初始狀態(tài)、目標狀態(tài)和規(guī)劃操作的公理化描述，使用歸結定理證明產生對存在規(guī)劃的構造性證明，然后使用答案抽出過程找出實際規(guī)劃。然而，這種方法在處理眾所周知的框架問題[10]時遇到了困難，建立經典規(guī)劃描述的目的之一就是這種描述為框架問題提供了一個簡單的解法：在經典規(guī)劃中，在操作效果中沒有提到的原子在動作過程中保持不變。經典規(guī)劃與早期的規(guī)劃系統(tǒng)STRIPS聯(lián)系在一起，每個操作有前提條件、增加表、刪除表，這些表允許包含任何的一階邏輯合式公式。在后來的工作中，研究者對表示做了限制，使用前提條件、增加表、刪除表只能包含原子。Nilssiom在他1980年的教科書中用這種方式闡述了STRIPS[11]。從此以后，操作和表示方法分別變成了眾所周知的STRIPS型操作和STRIPS型規(guī)劃。在UCPOP[12]規(guī)劃器中，Penberthy和Weld對STRIPS型操作做了句法修改，操作不再具有增加表和刪除表，而是寫成正效果和負效果。這種表示是我們經典規(guī)劃操作表示的基礎。Pednault[13,14]引進了動作描述語言表示（ActionDescriptionLanguage，ADL），值金額中語言權衡了一般邏輯表示的表達能力和利用表示推理的復雜性。從UCPOP[9]開始，各種規(guī)劃器對ADL或者是接近于ADL的表示做了推廣，使之能處理經典規(guī)劃中大多數的擴展。這些擴展都已經在PDDL規(guī)劃語言中實現，PDDL語言用于國際人工智能規(guī)劃和調度會議（InternationalConferenceonAIPlanningandScheduling，AIPS）的規(guī)劃大賽中。HTN規(guī)劃在過去的15年內，大部分在人工智能規(guī)劃系統(tǒng)上的實用工作都基于分層任務網絡（HTN）規(guī)劃[2]，這是繼STRIPS規(guī)劃后最為重要的規(guī)劃方法。HTN規(guī)劃用狀態(tài)原子集合來表達世界的狀態(tài)，并在一定的前提下，動作將通過增加和/或刪除狀態(tài)原子改變世界。在這一點上，HTN與經典規(guī)劃十分相似，但不同的是規(guī)劃問題的類型及對問題進行規(guī)劃的方法。HTN規(guī)劃的基本思想最初是Sacerdoit[15]在25年前的研究中提出并發(fā)展而來的，Tate的Nonlin規(guī)劃器[4]也是最早使用HTN規(guī)劃基本思想的規(guī)劃器。Yang[16]、Kambhampati和Hendler[17]等人首次對HTN規(guī)劃的理論模型進行了研究。Erol[3]等人提出了一種完備的模型，該模型的提出為復雜性分析[18]奠定了基礎，并且給出了第一個可被證明為正確的HTN規(guī)劃程序，即UMCP[3]。下面列出了一些最為著名的領域無關的HTN規(guī)劃系統(tǒng)：Nonlin[4]是最早的HTN規(guī)劃系統(tǒng)之一。SIPE-2[6]已被應用于許多領域。O-plan[7][8]也在許多應用領域得到應用。UMCP[3]是第一個使用被證明是可靠且完備的規(guī)劃算法的系統(tǒng)。SHOP2[3]是一個高效的規(guī)劃系統(tǒng)，該系統(tǒng)在2002年國際規(guī)劃大賽上獲得了前四名的好成績。需要說明的是，Lifted-PFD程序是簡化版本的SHOP2，Lifted-TFD程序是SHOP2的前身SHOP的簡化版本，而我們的Abstract-HTN程序是簡化版本的UMCP。NONLIN和SIPE-2系統(tǒng)使用了外部前提條件，不過其外部前提條件實在領域描述中聲明的。而UMCP系統(tǒng)則采用了能自動發(fā)現外部前提條件的算法。O-Plan、SIPE-2和SHOP2各自都能處理某類時態(tài)規(guī)劃問題。綜上所述，與經典規(guī)劃相比，HTN規(guī)劃器主要的有點在于其推理能力以及它們能對經驗知識進行有效表示。HTN規(guī)劃器能表示并求解多種非經典規(guī)劃問題。如果有好的HTN方法集合引導搜索的話，HTN規(guī)劃器求解經典規(guī)劃問題的速度能比那些經典的或新經典規(guī)劃器快好幾個數量級。HTN規(guī)劃器的主要缺點是不僅需要領域專家給出規(guī)劃動作集合，還要給出方法集合。時態(tài)規(guī)劃對于時態(tài)規(guī)劃問題，既可以從面向狀態(tài)的角度處理，也可以從面向時間的角度處理。正如大多數近期出現的規(guī)劃器一樣，早期的關于時態(tài)規(guī)劃的工作采用的是面向狀態(tài)的角度。這主要是由于這種面向狀態(tài)的處理方法更接近于經典規(guī)劃的處理方法，因此可以更容易地與經典規(guī)劃技術相結合，也更容易地從這些經典規(guī)劃技術的最新進展中獲益。使用面向狀態(tài)的處理技術的規(guī)劃器有：在狀態(tài)空間規(guī)劃器中，根據Deviser[19]早期的工作，最近已經出現了幾個能處理時間的采用啟發(fā)式引導技術的規(guī)劃器，例如TLplan及其后續(xù)規(guī)劃器[20,21]、ALplanner[22,23,24]和HS[25]規(guī)劃器。在規(guī)劃空間規(guī)劃中，ZENO[26]系統(tǒng)能表示可變的持續(xù)時間和線性約束。在規(guī)劃圖方法中個，TGP[27]、SAPA[28]和TPSYS[29]能處理持續(xù)時間和其他時態(tài)結構。在HTN規(guī)劃中，幾個規(guī)劃器如O-plan[7][8]、SIPE[30]和SHOP2[2]在各自的表示和搜索過程中整合了時間窗口和約束的技術。在這些規(guī)劃方法中，最近幾個規(guī)劃器顯示了非常高的求解效率，并且允許進行合理的調節(jié)。然而，通常這些方法都會導致并發(fā)動作的受限模型。通常的假定是，動作帶有一持續(xù)時間，但不考慮在該持續(xù)時間內的中間時間點的情況。動作的前提條件和效果均在持續(xù)時間區(qū)間的端點處被聲明，并且這些前提條件和效果的取值情況將在持續(xù)時間區(qū)間內保持不變。面向時間角度的規(guī)劃觀點來自Allen[31]的開創(chuàng)性工作。該規(guī)劃器正是采用Allen的區(qū)間代數處理動作的條件和效果命題間的定性時序約束，這些約束可以出現在動作持續(xù)時間內的任何位置。該規(guī)劃器在規(guī)劃空間中進行搜索，它是通過IA約束來處理因果鏈的。面向時間角度的規(guī)劃方面，另外一個重要的成果是Dean和McDermott[32]的時間映射管理器以及基于它的幾個規(guī)劃器。這些規(guī)劃期處理我們所表示的時態(tài)數據庫。指導思想與文章結構說明本課題以小見大，通過對一個電梯載人問題進行研究，試圖理清不同規(guī)劃方法的異同，以及規(guī)劃與調度之間的聯(lián)系與區(qū)別，并在此過程中加深對于自動規(guī)劃理解，為今后進一步的研究打下基礎。同時，在此對后面的幾個章節(jié)主要內容進行一個大致的說明。第二章是關鍵理論與技術。主要對規(guī)劃問題的經典表示方法、HTN規(guī)劃、規(guī)劃空間規(guī)劃及MTP等理論及技術進行闡釋。第三章是電梯載人問題HTN建模及求解。主要對電梯載人問題用SHOP2進行建模，引入啟發(fā)式規(guī)則引導搜索并求解，同時設計一個問題，對此領域進行測試，以確保領域的可靠性與完備性。第四章是HTN規(guī)劃與簡單調度規(guī)則的比較。主要使用幾種常用在電梯調度領域的調度規(guī)則對問題進行手動求解，并對求解的結果進行比較。擴大問題規(guī)模后，再次用SHOP2規(guī)劃器與調度規(guī)則求解比較。第五章是時態(tài)約束下的HTN規(guī)劃。主要使用MTP技術對引入時態(tài)約束后的電梯載人問題進行規(guī)劃求解。第六章是對總結與今后研究方向。分析課題研究中有待進一步完善的地方，并給出本課題之后研究方向。

關鍵理論與技術本章節(jié)將分為3個子章節(jié)分別對對規(guī)劃問題的經典表示方法、HTN規(guī)劃及MTP技術等理論及技術進行闡釋。規(guī)劃問題的經典表示方法概念模型是描述一個問題的主要因素的簡單的理論方法。它的意義在于可以把描述同計算和算法分隔開來。多數的規(guī)劃方法使用了狀態(tài)轉移系統(tǒng)的模型，又稱為離散事件系統(tǒng)。一個狀態(tài)轉移系統(tǒng)是一個四元組Σ=S,A,E,γS=sA=aE=e1γ:S×A×E→2一個狀態(tài)轉移系統(tǒng)也可以用有向圖表示，其中節(jié)點表示S中的狀態(tài)。如果s'∈γs,u，其中u是一個偶對a,e，a∈A且e∈E，那么途中包含一條從s到s對概念模型施加以下各種限定假設，從而得到受限的概念模型。：假設A0（有限的Σ），假設A1（完全可觀察的Σ），假設A2（確定的Σ），假設A3（靜態(tài)的Σ），假設A4（受限的目標），假設A5（序列式計劃），假設A6（隱去時間），假設A5（脫機規(guī)劃）。經典規(guī)劃一般是指對受限的狀態(tài)轉移系統(tǒng)進行規(guī)劃[1]，常用的表示方法有三種，它們具有同等的表示能力：在規(guī)劃的集合論表示中，世界的狀態(tài)是一組命題集合，動作是一種句法構造表示，說明當狀態(tài)具有哪些命題時才可以使用該動作，在應用了動作后所得到的新的狀態(tài)里，哪些命題是動作加上去的，哪些命題是動作刪去的。在經典表示中，狀態(tài)和動作的描述類似于集合論表示，但是使用一階文字和邏輯連接符，而不是使用命題。在狀態(tài)變量的表示中，每一個狀態(tài)都表示成狀態(tài)變量的n元組，而每一個動作都用一個狀態(tài)變量的n元組到另外一個n元組的部分映射函數表示。這種方法常用于表示特征集合在某一有限范圍而特征的值隨時間改變的領域。其中，經典表示是受限狀態(tài)轉移系統(tǒng)中最常用的。所以下面詳細闡述經典表示[1]：經典規(guī)劃表示中，一個狀態(tài)是一階邏輯語言L的一個基原子集。因為L中沒有函數，可能狀態(tài)集S必定是有限集。并規(guī)定，一個原子p在s中成立當且僅當p∈s。一個規(guī)劃操作就是一個三元組o=(nameoname(o)，操作的名字，是形如n(x1,…,xk)的語法表示，其中precondo和effects(o)分別是o一個經典規(guī)劃領域是一個受限的狀態(tài)轉移系統(tǒng)Σ=S,A,γS?2A={O中操作的所有基例}，其中γs,a=(s-effects-(a))∪effect+S對γ是封閉的，即，如果s∈S，則對每一個可應用于s的動作a，γs,a一個經典規(guī)劃問題是一個三元組P=(Σ,初始狀態(tài)s0是S目標g是任意一個基文字集；Sg一個規(guī)劃問題P=(Σ,s0HTN規(guī)劃如同其他經典的AI規(guī)劃，HTN規(guī)劃將現實世界的狀態(tài)用一組原子表示，而每一個動作都意味著一個確定性的狀態(tài)轉換。但HTN規(guī)劃與其他經典的AI規(guī)劃區(qū)別在于它們規(guī)劃什么與它們如何規(guī)劃。HTN規(guī)劃器的目標是產生一序列的動作以表示一些活動或工作。規(guī)劃領域知識的表述包括和其他經典規(guī)劃器一樣的一組操作，以及表示如何將一個任務分解為子任務的方法。給定一個規(guī)劃領域知識，規(guī)劃問題的表述將同其他經典規(guī)劃器一樣包括一系列初始狀態(tài)，但問題規(guī)范還包括一組部分有序的需要完成的任務。求解過程中，通過使用方法遞歸地將任務分解為越來越小的子任務，直到達到能夠直接用規(guī)劃操作來表達的原始任務。對于每個非原始任務，規(guī)劃器選擇一個可應用的方法，實例化并將其分解為子任務，然后選擇并實例化方法進一步對子任務進行分解。如果規(guī)劃隨后被證明是不可行的，規(guī)劃器會滾回并嘗試其他方法。HTN方式通常描述了標準操作過程，這通常在一些領域中用來表達任務。HTN規(guī)劃能夠以較快的速度求解規(guī)劃問題，且規(guī)劃解的質量取決于領域知識的編寫。大多數HTN的實踐者認為這樣的表達對于現實世界中的很多領域比經典的規(guī)劃操作更加適合，因為他們更好地描繪了用戶思考問題的方式。任務網絡是形如w=(U,C)的序對，其中U為任務節(jié)點集合，C為約束集合。規(guī)劃問題的所有解規(guī)劃必須滿足CHTN方法是一個4元組：m其中各成員的含義分別是：namem為方法的名稱，是形如n(x1,…,xk)的表達式，這里n是唯一的方法符號（也就是說，規(guī)劃領域中不存在兩種具有相同名稱的方法）taskm為(subtasksm,假定w=(U,C)為一任務網絡，u∈U為一任務節(jié)點，u對應的任務為tu，m為方法M的一個實例，并且taskm=tuδ 其中，C’是對C做下列修改后得到的：對所有含u的先后約束，用含subtasks(m’)的節(jié)點的先后約束代替。對前置約束、效果約束或中間約束，如果這些約束中的任務節(jié)點集合U‘含有u，則以U-u∪subtasksm'HTN規(guī)劃領域是一序對：D=(并且一個HTN規(guī)劃問題是一4元組：P=其中，s0是初始狀態(tài)，w是初始任務網絡，O是動作集合，M為HTN如果w=U,C為原子任務網絡，并且存在(U,C)的一個基例(U‘,C’)以及U‘節(jié)點集上規(guī)劃π中的動作由節(jié)點u1,…,uk命名，也就是說對于i=1,…,k，規(guī)劃π在狀態(tài)s0下全序u1,…,uk滿足C‘中的先后約束，也就是說，C’中不存在u對于C‘中的每一前提條件before(U’,l)，l在動作ai的直前驅狀態(tài)si-1下成立，這里ai為對于C‘中的每一效果約束after(U’,l)，l在動作aj所產生的狀態(tài)sj下成立，其中ai為U‘對于C‘中的每一中間約束between(U’,U'',l)，l在動作ai和aj的所有中間狀態(tài)下保持成立，其中ai為U’中最后一個節(jié)點命名的動作，a如果w=U,C為非原子任務網絡，若此時存在一個可以作用于w并將其分解成原子任務網絡w’的任務分解序列，則π為w’的解，則π即為w的解。在此情況下，π的MTP技術SHOP2操作的表達力至少在PDDL第二層，但SHOP2不支持在PDDL第三層中的持續(xù)時間動作，SHOP2也沒有明確的機制來對持續(xù)時間動作與并發(fā)動作進行推理。但SHOP2仍然有足夠的表達力來表示持續(xù)時間動作與并發(fā)動作，因為規(guī)劃過程每一步的當前狀態(tài)是明確的，且它的操作可以給變量賦值同時進行數值計算。這使得我們可以開發(fā)一種叫MTP（Multi-TimelinePreprocessing，多時間軸預處理）的技術，將PDDL操作轉化為SHOP2操作，同時保持現在狀態(tài)中暫時信息的追蹤。圖2-1中的偽代碼對MTP的機制做了一個算法上的描述。為了使MTP的表達簡潔，假設在每個狀態(tài)s，每個原子(pc1…cn)表達了單值屬性。如果操作可以改變cn的值則為動態(tài)屬性。對于每個隨著時間改變的屬性p，MTP修改操作以保持對現在狀態(tài)下屬性變化時的時間及取決于屬性的各種前提條件的時間的追蹤。對于每個動態(tài)屬性p，當前狀態(tài)將會包含兩個時間標記：read-time(p)（最后一個讀取p的值的時間）和write-time(p)（最后一個修改p的值的時間）。MTP修改操作在動作讀取動態(tài)屬性這種情況下，操作會更新屬性的讀時間，如果操作修改了動態(tài)屬性則還會更新些時間。因此，不同于一個單獨的全局時間，當前狀態(tài)會包含很多局部時間，即每個動態(tài)屬性的讀時間和寫時間。foreveryoperatorointheplanningdomainaddtwoparameters?startand?durationtooino’spreconditionaddanassignment?duration←dwheredisaformulaforcalculatingo’sdurationaddanassignment?start←swheresisaformulathattakesthemaximumofthewritetimesofalldynamicpropertiesino’spreconditionandthereadtimesofalldynamicpropertiesino’seffectsforeachdynamicpropertypino’seffectsaddeffectstochangethevalueofwrite-time(p)to?start+?durationforeachdynamicpropertythatappearsinoaddeffectstochangeread-time(p)tothemaximumofread-time(p)and?start+?duration圖foreveryoperatorointheplanningdomainaddtwoparameters?startand?durationtooino’spreconditionaddanassignment?duration←dwheredisaformulaforcalculatingo’sdurationaddanassignment?start←swheresisaformulathattakesthemaximumofthewritetimesofalldynamicpropertiesino’spreconditionandthereadtimesofalldynamicpropertiesino’seffectsforeachdynamicpropertypino’seffectsaddeffectstochangethevalueofwrite-time(p)to?start+?durationforeachdynamicpropertythatappearsinoaddeffectstochangeread-time(p)tothemaximumofread-time(p)and?start+?duration圖STYLEREF1\s2SEQ圖\*ARABIC\s11MTP機制

電梯載人問題HTN建模及求解本章主要是對電梯載人問題用SHOP2進行建模并求解，同時介紹對使用UCPOP解決此問題所做的探究。電梯載人問題課題以電梯載人問題為例對HTN規(guī)劃性能進行研究。電梯載人問題如下：一棟大樓從低到高有n0到n8共9層，該大樓有快速電梯一部(fast0)，慢速電梯兩部(slow1和slow2)?？焖匐娞輋ast0最初停留在n0處，fast0可達到各個樓層，在n1、n2、n3層只允許乘客進入電梯，在n4、n6、n8層只允許乘客出電梯。慢速電梯slow1可到達的樓層為n0、n1、n2、n3、n4，最初停留在n4層，在n0和n4層只允許乘客進入電梯，在n2層只允許乘客出電梯；慢速電梯slow2可到達的樓層有n4、n5、n6、n7和n8，最初停留在n4層，在n4和n6層只允許乘客進入電梯，在n7層只允許乘客出電梯?，F有乘客4人，分別記為p0、p1、p2、p3，其中p0在n5層，p1在n7層，p2在n1層，p3在n8層。這四個乘客要乘坐電梯各自達到自己希望的樓層，即：p0要去n4層，p1要去n3層，p2要去n2層，p3要去n6層?？紤]每個電梯容量為一個人，設計相應的規(guī)劃方案，以此解決電梯載人問題。利用JSHOP2進行建模求解JSHOP作為SHOP2規(guī)劃器的JAVA版本可以在Eclipse-Java中運行，作為一種HTN規(guī)劃器，對問題建模應分為兩個部分：領域與問題。這兩個部分又可以繼續(xù)分解為幾個子部分，其從屬關系及所包含的內容如圖3-1所示。 圖STYLEREF1\s3SEQFigure\*ARABIC\s11HTN規(guī)劃問題建模以下分操作、方法、初始狀態(tài)、初始任務網絡四個子章節(jié)詳細闡述建模的過程。最后2個子章節(jié)，將分別介紹測試問題與規(guī)劃求解的過程及結果。完整的代碼參見附錄。操作在電梯載人領域中，操作一共有3個，分別完成乘客搭乘電梯、乘客離開電梯、電梯移動三個動作。操作：乘客搭乘電梯。(:operator(!lift-in?p?n?lift) ( (or(in?lift?n)(both?lift?n)) (un-occupy?lift) (lift-at?lift?n) (at-floor?p?n) ) ( (:protection(lift-at?lift?n)) (un-occupy?lift) (at-floor?p?n) ) ( (occupy?lift) (at-lift?p?lift) ))代碼如圖3-2所示。操作名為!lift-in，前面添加!表明操作為實際操作。如果一個操作為虛擬操作則在名稱前添加!!，則在最后的規(guī)劃解的動作序列中將不出現此虛擬操作。操作的參數有乘客?p、電梯?lift、樓層?n。前提條件有四項，分別為樓層?n允許乘客搭乘電梯、電梯?lift未被占用，電梯?lift在樓層?n，乘客?p在樓層?n。操作刪除的狀態(tài)有保護狀態(tài)（在后面的章節(jié)會對此進行解釋）——電梯?lift在樓層?n(:operator(!lift-in?p?n?lift) ( (or(in?lift?n)(both?lift?n)) (un-occupy?lift) (lift-at?lift?n) (at-floor?p?n) ) ( (:protection(lift-at?lift?n)) (un-occupy?lift) (at-floor?p?n) ) ( (occupy?lift) (at-lift?p?lift) ))圖STYLEREF1\s3SEQFigure\*ARABIC\s12乘客搭乘電梯操作操作：乘客離開電梯。代碼如圖3-3所示。操作名為!lift-out。操作的參數有乘客?p、電梯?lift、樓層?n。前提條件有四項，分別為樓層?n允許乘客離開電梯、電梯?lift被占用，電梯?lift在樓層?n，乘客?p在電梯?lift里。操作刪除的狀態(tài)有保護狀態(tài)（在后面的章節(jié)會對此進行解釋）——電梯?lift在樓層?n、電梯?lift被占用、乘客?p在電梯?lift里。同時操作增加的狀態(tài)有電梯?lift未被占用、乘客?p在樓層?n。圖STYLEREF1\s3圖STYLEREF1\s3SEQFigure\*ARABIC\s13乘客離開電梯操作(:operator(!lift-out?p?n?lift) ( (or(out?lift?n)(both?lift?n)) (occupy?lift) (lift-at?lift?n) (at-lift?p?lift) ) ( (:protection(lift-at?lift?n)) (occupy?lift) (at-lift?p?lift) ) ( (un-occupy?lift) (at-floor?p?n) ))代碼如圖3-4所示。操作名為!lift-move。操作的參數有電梯?lift、所在樓層?n-from、目標樓層?n-to。前提條件有三項，分別為電梯?lift在樓層?n-from、?n-to允許乘客搭乘或離開，電梯?lift在樓層?n-from。操作刪除的狀態(tài)有電梯?lift在樓層?n-from。同時操作增加的狀態(tài)有保護狀態(tài)——電梯?lift在樓層?n-to、電梯?lift在樓層?n-to。圖STYLEREF1\s3SEQFigure\*ARABIC\s14電梯移動操作(:operator(!lift-move?lift?n-from?n-to) ( (lift-at?lift?n-from) (or(in?lift?n-to)(both?lift?n-to)(out?lift?n-to)) (or(in?lift?n-from)(both?lift?n-from)(out?lift?n-from)) ) ( (lift-at?lift?n-from) ) ( (lift-at?lift?n-to) (:protection(lift-at?lift?n-to)) ))添加保護狀態(tài)用于告訴規(guī)劃系統(tǒng)不允許執(zhí)行任何刪除此被保護的狀態(tài)的圖STYLEREF1\s3SEQFigure\*ARABIC\s14電梯移動操作(:operator(!lift-move?lift?n-from?n-to) ( (lift-at?lift?n-from) (or(in?lift?n-to)(both?lift?n-to)(out?lift?n-to)) (or(in?lift?n-from)(both?lift?n-from)(out?lift?n-from)) ) ( (lift-at?lift?n-from) ) ( (lift-at?lift?n-to) (:protection(lift-at?lift?n-to)) ))方法在電梯載人領域中，方法一共有3個，分別為選擇一個可用的電梯并確定移動的樓層、將電梯運送到乘客所在樓層、將乘客移動到要去的樓層。方法：選擇一個可用的電梯并確定移動的樓層。(:method(move?p?n) ;branch0: ( (un-occupy?lift) (or(out?lift?n)(both?lift?n)) (at-floor?p?n-now) (or(in?lift?n-now)(both?lift?n-now)) ) ( (lift-move?p?n?lift) ) ;branch1: ( (at-floor?p?n-now)(:method(move?p?n) ;branch0: ( (un-occupy?lift) (or(out?lift?n)(both?lift?n)) (at-floor?p?n-now) (or(in?lift?n-now)(both?lift?n-now)) ) ( (lift-move?p?n?lift) ) ;branch1: ( (at-floor?p?n-now) (or(in?lift?n-now)(both?lift?n-now)) (or(out?lift?n-to)(both?lift?n-to)) (or(out?lift-other?n)(both?lift-other?n)) (or(in?lift-other?n-to)(both?lift-other?n-to)) (un-occupy?lift) ) ( (lift-move?p?n-to?lift) (move?p?n) ) ;branch2: ( (at-floor?p?n-now) (lift-at?lift?n-now) (un-occupy?lift) (or(in?lift?n-now)(both?lift?n-now)) (or(out?lift?n-to)(both?lift?n-to)) ) ( (lift-move?p?n-to?lift) (move?p?n) ) ;branch3: ( (at-floor?p?n-now) (or(in?lift?n-now)(both?lift?n-now)) (un-occupy?lift) (or(out?lift?n-to)(both?lift?n-to)) ) ( (lift-move?p?n-to?lift) (move?p?n) ) )圖STYLEREF1\s3SEQFigure\*ARABIC\s15方法：選擇一個可用的電梯并確定移動的樓層方法的名字和參數為(move?p?n)，為初始任務網絡在規(guī)劃搜索中最先進行分解的所用的方法，需要將任務（將乘客?p移動到樓層?n）分解為(lift-move?p?n-to?lift)（將乘客?p用電梯?lift移動到樓層?n-to）與(move?p?n)（如果有電梯可以直接將乘客移動到目標樓層?n，則此任務略去）。為此，為此方法設計了4個分支，對應于不同的情況設置了相應的啟發(fā)式規(guī)則以引導搜索。以下分別具體解釋4個分支：Branch0：在此分支里，首先檢驗是否有未被占用的電梯可以將乘客?p直接移動到目標樓層?n，并且乘客所在樓層搭乘電梯與目標樓層離開電梯都滿足此電梯的約束，如果是則分解為(lift-move?p?n?lift)（將乘客?p用電梯?lift移動到樓層?n），目標任務完成。Branch1：如果不滿足Branch0的前提條件，則需要將乘客移動至其他樓層以便換乘其他電梯。為了減少換乘次數，檢驗乘客能否通過換乘一次電梯到達目標樓層，如果存在這樣的途徑就優(yōu)先選擇這樣這方式先移動到換乘樓層，分解為(lift-move?p?n-to?lift)與(move?p?n)。而在下一次對(move?p?n)分解時就會進入Branch0完成任務。如此，方法的前提條件會搜索是否有電梯?lift滿足在乘客?p所在樓層?n-now允許乘客搭乘且在某一樓層?n-to允許乘客離開，同時另外有一部電梯?lift-other在樓層?n-to允許乘客搭乘且在目標樓層?n允許乘客離開，如果滿足條件就說明存在這樣的一次換乘途徑可以到達目標樓層。Branch2：如果都不滿足以上兩個分支的前提條件，且有電梯停留在乘客所在的樓層，則乘客優(yōu)先搭乘這部電梯隨機的前往電梯停留規(guī)則允許的某樓層。同上一分支分解成(lift-move?p?n-to?lift)與(move?p?n)兩個任務。Branch3：如果以上分支的前提條件都不滿足，則隨機選擇一部電梯，并隨機確認一個對應電梯停留規(guī)則允許的某樓層。同上一分支分解成(lift-move?p?n-to?lift)與(move?p?n)兩個任務。將Branch1放在Branch2之前進行判斷則是考慮應優(yōu)先尋找可以通過一次換乘到達目標樓層的方案，而不是先考慮哪個電梯在本樓層，因為如果電梯不在本樓層也只需多執(zhí)行一個將電梯移動至本樓層的動作，而如果舍棄了一次換乘就能到達目標樓層的方案可能需要通過3到4個動作在能夠完成到達目標樓層的任務。方法：將電梯運送到乘客所在樓層。(:method(lift-move?p?n-to?lift) ;branch0: ( (at-floor?p?n-now) (lift-at?lift?n-now) ) ( (move-to-floor?p?n-to?lift) ) ;branch1: ( (at-floor?p?n-now) (lift-at?lift?n-other) ) ( (!lift-move?lift?n-other?n-now) (:method(lift-move?p?n-to?lift) ;branch0: ( (at-floor?p?n-now) (lift-at?lift?n-now) ) ( (move-to-floor?p?n-to?lift) ) ;branch1: ( (at-floor?p?n-now) (lift-at?lift?n-other) ) ( (!lift-move?lift?n-other?n-now) (move-to-floor?p?n-to?lift) ))圖STYLEREF1\s3SEQFigure\*ARABIC\s16方法：將電梯運送到乘客所在樓層此方法處理方式較為簡單，共有兩個分支：Branch0：如果電梯在乘客所在的樓層，則此方法什么也不做。直接分解為(move-to-floor?p?n-to?lift)。Branch1：如果乘客搭乘的電梯不在乘客所在的樓層，此方法將電梯移動到乘客所在的樓層。分解為操作(!lift-move?lift?n-other?n-now)與(move-to-floor?p?n-to?lift)。方法：將乘客移動到要去的樓層。代碼如圖3-7所示。方法名稱及參數為(move-to-floor?p?n-to?lift)。任務分解到此，需要做的只有將乘客移動到目標樓層，故此方法將任務分解為3個操作：(!lift-in?p?n-now?lift)、(!lift-(:method(move-to-floor?p?n-to?lift)( (lift-at?lift?n-now) )(:method(move-to-floor?p?n-to?lift)( (lift-at?lift?n-now) ) ( (!lift-in?p?n-now?lift) (!lift-move?lift?n-now?n-to) (!lift-out?p?n-to?lift) ))圖STYLEREF1\s3SEQFigure\*ARABIC\s17方法：將乘客移動到要去的樓層初始狀態(tài);快速電梯停留樓層(bothfast0n0)(infast0n1)(infast0n2)(infast0n3)(outfast0n4)(bothfast0n5)(outfast0n6)(bothfast0n7)(outfast0n8);慢速電梯1停留樓層(inslow1n0)(bothslow1n1)(outslow1n2)(bothslow1n3)(inslow1n4);慢速電梯2停留樓層(inslow2n4)(bothslow2n5)(inslow2n6)(outslow2n7)(bothslow2n8);電梯初始位置(lift-atfast0n0)(lift-atslow1n4)(lift-atslow2n4);;快速電梯停留樓層(bothfast0n0)(infast0n1)(infast0n2)(infast0n3)(outfast0n4)(bothfast0n5)(outfast0n6)(bothfast0n7)(outfast0n8);慢速電梯1停留樓層(inslow1n0)(bothslow1n1)(outslow1n2)(bothslow1n3)(inslow1n4);慢速電梯2停留樓層(inslow2n4)(bothslow2n5)(inslow2n6)(outslow2n7)(bothslow2n8);電梯初始位置(lift-atfast0n0)(lift-atslow1n4)(lift-atslow2n4);人初始位置(at-floorp0n5)(at-floorp1n7)(at-floorp2n1)(at-floorp3n8);電梯是否占用(un-occupyfast0)(un-occupyslow1)(un-occupyslow2)圖STYLEREF1\s3SEQFigure\*ARABIC\s18初始狀態(tài)其中，(in?lift?n)表示電梯?lift允許乘客在樓層?n搭乘，(out?lift?n)表示電梯?lift允許乘客在樓層?n離開，(both?lift?n)表示電梯?lift允許乘客在樓層?n搭乘或離開。初始任務網絡 (movep0n4) (movep1n3) (movep2n2) (movep0n4) (movep1n3) (movep2n2) (movep3n6)圖STYLEREF1\s3SEQFigure\*ARABIC\s19初始任務網絡測試問題(defproblemproblemelevator(;快速電梯停留樓層(infast0n2)(outfast0n6);慢速電梯1停留樓層(inslow1n0)(outslow1n2)(bothslow1n4);慢速電梯2停留樓層(inslow2n6)(outslow2n5)(defproblemproblemelevator(;快速電梯停留樓層(infast0n2)(outfast0n6);慢速電梯1停留樓層(inslow1n0)(outslow1n2)(bothslow1n4);慢速電梯2停留樓層(inslow2n6)(outslow2n5);慢速電梯3停留樓層(inslow3n5)(outslow3n8);電梯初始位置(lift-atfast0n2)(lift-atslow1n4)(lift-atslow2n5)(lift-atslow3n8);人初始位置(at-floorp0n0);電梯是否占用(un-occupyfast0)(un-occupyslow1)(un-occupyslow2)(un-occupyslow3) )( (movep0n8) ))圖STYLEREF1\s3SEQFigure\*ARABIC\s110測試問題代碼對此測試領域進行求解，得到任務分解過程如圖3-11所示。其中第一次調用圖STYLEREF1\s3SEQFigure\*ARABIC\s111測試問題任務分解過程方法(movep0n8)進入的是Branch3，第二次調用進入的是Branch2，第三次調用進入的是Branch1，第四次調用進入的是Branch0。方法(lift-move?p?n-to?lift)的4次調用中進入Branch1的次數為3次，進入Branch2的次數為圖STYLEREF1\s3SEQFigure\*ARABIC\s111測試問題任務分解過程以此，可以認為，領域是可靠且完備的，可以用來求解類似的電梯載人問題。測試問題求解的結果如圖3-12所示。圖STYLEREF1\s3SEQFigure\*ARABIC\s112測試問題規(guī)劃解規(guī)劃求解的過程及結果圖STYLEREF1\s3SEQFigure\*ARABIC\s113電梯載人問題任務分解過程將領域文件elevator與問題文件problem輸入到JSHOP2中，編譯后即可打開GUI圖形規(guī)劃界面進行規(guī)劃求解，規(guī)劃的過程如圖3-13所示。由于篇幅所限，其中方法(move-to-floor?p?n-to?lift)分解結果的三個動作圖STYLEREF1\s3SEQFigure\*ARABIC\s113電梯載人問題任務分解過程可以看到每個乘客都在一次以內的換乘到達目標樓層。規(guī)劃解如圖3-14所示。整個規(guī)劃搜索過程共84步，得到的規(guī)劃解長度為23。四個目標任務中，乘客p0通過4個動作，直接搭乘電梯fast0到達目標樓層n4；乘客p1通過7個動作，搭乘電梯fast0在樓層n4換乘電梯slow1到達目標樓層n3；乘客p2通過4個動作，直接搭乘電梯slow0到達目標樓層n2；乘客p3通過8個動作，搭乘電梯slow2在樓層n7換乘電梯fast0到達目標樓層n6。圖圖STYLEREF1\s3SEQFigure\*ARABIC\s114電梯載人問題規(guī)劃解

HTN規(guī)劃與簡單調度規(guī)則的比較本章首先介紹幾種在電梯中常用的簡單調度規(guī)則，用其進行求解電梯載人問題，并與SHOP2規(guī)劃器求解的結果進行比較，而后，擴大問題的規(guī)模再進行求解，比較結果。故本章分為以下3個小結進行闡述：幾種常用的簡單調度規(guī)則、依據調度規(guī)則求解并與規(guī)劃器比較、擴大問題規(guī)模并求解比較。幾種常用的簡單調度規(guī)則電梯領域的調度規(guī)則有許多，這里僅提出2種適用于此電梯載人問題調度規(guī)則。規(guī)則1：優(yōu)先選擇離乘客最近且允許進入的電梯到達離目標樓層最近且允許離開的樓層，直到到達目標樓層為止。規(guī)則2：優(yōu)先選擇允許進入的快速電梯到達離目標樓層最近且允許離開的樓層，再換乘慢速電梯到達目標樓層。在下一章節(jié)中將分別利用這2條規(guī)則對電梯載人問題進行求解。調度規(guī)則求解及與規(guī)劃器比較使用規(guī)則1對電梯載人問題進行求解，得到的結果如圖4-1所示。所需進行的動作數為23個。使用規(guī)則2對電梯載人問題進行求解，得到的結果如圖4-2所示。所需進行的動作數為27個。而根據上一節(jié)求解的結果，使用SHOP2規(guī)劃器對電梯載人問題進行求解，得到的結果中，所需進行的動作數為23個?？梢钥吹?，在電梯載人問題上，SHOP2規(guī)劃器求解的結果在解的質量上與規(guī)則1一樣，比規(guī)則2要優(yōu)，則可認為SHOP2規(guī)劃器求解的結果在解的質量上至少不會劣于簡單調度規(guī)則。而在求解的速度上，如果采用手動方式依據簡單調度規(guī)則調度效率比較低下，而采用計算機程序依據簡單調度規(guī)則進行調度效率與規(guī)劃器效率相仿，但當對規(guī)劃問題做適當修改后，SHOP規(guī)劃領域知識通過少量的修改便可用于求解新的規(guī)劃問題，而依靠簡單調度規(guī)則的計算機程序則需做較為[1](!lift-movefast0n0n5) [2](!lift-inp0n5fast0)[3](!lift-movefast0n5n4) [4](!lift-outp0n4fast0)[1](!lift-movefast0n0n5) [2](!lift-inp0n5fast0)[3](!lift-movefast0n5n4) [4](!lift-outp0n4fast0)[5](!lift-movefast0n4n7) [6](!lift-inp1n7fast0)[7](!lift-movefast0n7n4) [8](!lift-outp1n4fast0)[9](!lift-inp1n4slow1) [10](!lift-moveslow1n4n3)[11](!lift-outp1n3slow1) [12](!lift-moveslow1n3n1)[13](!lift-inp2n1slow1) [14](!lift-moveslow1n1n2)[15](!lift-outp2n2slow1) [16](!lift-moveslow2n4n8)[17](!lift-inp3n8slow2) [18](!lift-moveslow2n8n7)[19](!lift-outp3n7slow2) [20](!lift-movefast0n4n7)[21](!lift-inp3n7fast0) [22](!lift-movefast0n7n6)[23](!lift-outp3n6fast0)圖STYLEREF1\s4SEQFigure\*ARABIC\s11規(guī)則1對電梯規(guī)劃問題求解結果[1](!lift-movefast0n0n5) [2](!lift-inp0n5fast0)[3](!lift-movefast0n5n4) [4](!lift-outp0n4fast0)[5](!lift-movefast0n4n7) [6](!lift-inp1n7fast0)[7](!lift-movefast0n7n4) [8](!lift-outp1n4fast0)[9](!lift-inp1n4slow1) [10](!lift-moveslow1n4n3)[11](!lift-outp1n3slow1) [12](!lift-movefast0n4n1)[13](!lift-inp2n1fast0) [14](!lift-movefast0n1n4)[15](!lift-outp2n4fast0) [16](!lift-moveslow1n3n4)[17](!lift-inp2n4slow1) [18](!lift-moveslow1n4n2)[19](!lift-outp2n2slow1) [20](!lift-moveslow2n4n8)[21](!lift-inp3n8slow2) [22](!lift-moveslow2n8n7)[23](!lift-outp3n7slow2)[24](!lift-movefast0n4n7)[25](!lift-inp3n7fast0) [26](!lift-movefast0n7n6)[27](!lift-outp3n6fast0)圖STYLEREF1\s4SEQFigure\*ARABIC\s12規(guī)則2對電梯規(guī)劃問題求解結果擴大問題規(guī)模并求解比較一般來說，當問題規(guī)模較小時，依據簡單調度規(guī)則進行手動或計算機程序調度與自動規(guī)劃器規(guī)劃的性能差別不大，而當問題的規(guī)模擴大，其性能上的差異可能逐漸顯現，故本節(jié)的目的在于驗證此觀點。擴大規(guī)模后的問題。對問題規(guī)模進行擴大，乘客數擴大到8人，樓層數擴大到15層，電梯數擴大到快速電梯1部、慢速電梯4部。原問題中，快速電梯可以停留所有樓層，而慢速電梯則停留大約一半的樓層，慢速電梯之間有一個樓層的都可停留，故擴大規(guī)模后的問題中，快速電梯依舊可以停留所有樓層，而慢速電梯則停留稍多于總樓層數四分之一的樓層，同時各相鄰慢速電梯之間均有移到兩個樓層都可停留，同時，為了保證所有的乘客都能通過此電梯系統(tǒng)從任意初始樓層移動到任意目標樓層，所有的樓層都至少存在電梯可以搭乘或到達。規(guī)模擴大后的問題如下：一棟大樓從低到高有n0到n14共15層，該大樓有快速電梯一部(fast0)，慢速電梯四部(slow1和slow2)?？焖匐娞輋ast0最初停留在n0，fast0可達到各個樓層，在n1、n2、n3、n10、n11層只允許乘客進入電梯，在n4、n6、n8、n12、n14層只允許乘客出電梯慢速電梯slow1可到達的樓層為n0、n1、n2、n3、n4，最初停留在n0層，在n0和n4層只允許乘客進入電梯，在n2層只允許乘客出電梯；慢速電梯slow2可到達的樓層有n3、n4、n5、n6和n7，最初停留在n3層，在n4、n6層只允許乘客進入電梯，在n3、n7層只允許乘客出電梯。慢速電梯slow3可到達的樓層有n7、n8、n9、n10和n11，最初停留在n7層，在n7、n9層只允許乘客進入電梯，在n11層只允許乘客出電梯。慢速電梯slow4可到達的樓層有n10、n11、n12、n13和n14，最初停留在n10層，在n12、n13、n14層只允許乘客進入電梯，在n10層只允許乘客出電梯。現有乘客8人，分別記為p0、p1、p2、p3、p4、p5、p6、p7，其中p0在n0層，p1在n2層，p2在n4層，p3在n5層，p4在n7層，p5在n8層，p6在n12層，p7在n13層。這八個乘客要乘坐電梯各自達到自己希望的樓層，即：p0要去n11層，p1要去n10層，p2要去n14層，p3要去n1層，p4要去n3層，p5要去n13層，p6要去n0層，p7要去n10層?？紤]每個電梯容量為一個人，設計相應的規(guī)劃方案，以此解決電梯載人問題。SHOP2規(guī)劃器求解情況擴大后的電梯規(guī)則不影響領域文件elevator，無需做任何修改，而只需對問題文件problem進行修改，因篇幅限制，修改后的代碼略去，詳見附錄的代碼清單。求解的結果如圖20所示?？梢钥吹?，規(guī)劃解動作的個數為59個。整個規(guī)劃搜索過程為210步。從結果中可以看到，乘客p0、p1、p3和p4通過乘坐快速電梯換乘慢速電梯到達目標樓層，乘客p7直接乘坐慢速電梯到達目標樓層，乘客p2、p5和p6通過搭乘慢速電梯換乘快速電梯到達目標樓層。[1](!lift-inp0n0fast0) [2](!lift-movefast0n0n8) [3](!lift-outp0n8fast0)[4](!lift-moveslow3n7n8)[1](!lift-inp0n0fast0) [2](!lift-movefast0n0n8) [3](!lift-outp0n8fast0)[4](!lift-moveslow3n7n8) [5](!lift-inp0n8slow3) [6](!lift-moveslow3n8n11)[7](!lift-outp0n11