智能規(guī)劃分解的發(fā)展與應用研究*

李 麗，王大勇

遼寧大學創(chuàng)新創(chuàng)業(yè)學院，沈陽110036

1 引言

智能規(guī)劃是人工智能的一個重要分支。將復雜問題分解為可管理的子問題是許多智能規(guī)劃問題解決的首選方式。早在20世紀70年代末，Corkhill就在分布式環(huán)境下開始了規(guī)劃問題分解工作的研究[1]。1987年，Korf提出利用前向鏈全序規(guī)劃器分解一個具有復合目標的規(guī)劃問題，并討論了計算的復雜度[2]。2006年Sebastia等人從宏觀角度對規(guī)劃分解問題進行了深入的研究和探討，并借助基于標記的分解技術，提出利用不同子目標之間的內在交互作用來分解問題[3]。2010年Biba?等人提出一種基于進化元啟發(fā)式的算法，優(yōu)化了規(guī)劃任務分解的中間過程[4]。2019年Hu等人通過將認知公式推理委托給外部求解器來分解認知規(guī)劃，避免了認知公式的指數(shù)爆炸[5]。

研究者們經(jīng)過長期的探索，已研究出多種有效的分解方法，并在很多領域都有所應用。

2 規(guī)劃分解問題

2.1 問題描述

對于經(jīng)典規(guī)劃和類經(jīng)典規(guī)劃，規(guī)劃分解的一般方法是將目標集合G分解為多個子目標Gi，使得G=∪Gi。針對每個子目標Gi求解出其對應的子規(guī)劃Pi=＜A,I,Gi＞，然后將所有的子規(guī)劃Pi組合成一個可以處理目標G的整體規(guī)劃[3]，如圖1所示。該方法是將規(guī)劃問題分解為多個子問題，然后分別對每個子問題求得規(guī)劃解，最后將子問題的規(guī)劃解合并作為規(guī)劃問題的規(guī)劃解。分解后的規(guī)劃問題會面臨最優(yōu)性缺失、前期工作效率降低等問題。但對于復雜規(guī)劃問題而言，經(jīng)過規(guī)劃分解后的子問題更易于處理，規(guī)劃方法也具有一定的可重用性。

Fig.1 General method of AI planning decomposition圖1 智能規(guī)劃分解的一般方法

規(guī)劃分解有三個要素，即分解問題的原則、求解子問題的過程以及合并子規(guī)劃的技術。分解問題的原則決定了求解每個子問題的效率，以及合并子規(guī)劃技術的復雜度。

2.2 問題分類

規(guī)劃分解問題根據(jù)情況不同可以分成多個種類。

根據(jù)分解過程是否自動化可以將規(guī)劃分解分成自動分解和手動分解兩類。自動分解通過分析域和問題結構來完成問題的分解。手動分解是在自動分解難以實現(xiàn)時由領域工程師完成分解操作。例如Hybrid STAN規(guī)劃器方法[6]屬于自動分解，REALPLAN規(guī)劃器方法[7]屬于手動分解。

根據(jù)規(guī)劃解的類型可以將規(guī)劃分解分成相關分解和無關分解兩類。相關分解是指如果一個子問題的解依賴于其他子問題的解，則需等待其所依賴的子規(guī)劃均求解完成后才會被求解。無關分解是指分解后的子問題間是足夠獨立的，可以同時求解。例如SGPlan規(guī)劃器方法[8]屬于相關分解，分布式NOAH（nets of action hierarchies）規(guī)劃器方法[1]屬于無關分解。

根據(jù)規(guī)劃分解的目的可以將規(guī)劃分解分成效率型分解和問題求解型分解。效率型分解旨在快速高效地完成規(guī)劃問題的求解。而問題求解型分解，主要是解決普通規(guī)劃器無法解決大型復雜問題或求解效率極其低下時，為了使規(guī)劃問題能夠順利完成，對規(guī)劃問題進行的分解工作，以降低搜索空間的快速擴張，使其能夠在多項式時間內完成規(guī)劃任務。例如Iwen等人提出的分解方法主要針對求解效率[9]，而Yang提出的WATPLAN規(guī)劃則注重問題求解[10]。

根據(jù)規(guī)劃問題的工作需要，可以將規(guī)劃分解分為多智能體需求分解和單智能體需求分解。多智能體需求分解是將規(guī)劃任務分解后，由多個規(guī)劃器分別求解，即將由一個規(guī)劃器完成的任務分配到多個規(guī)劃器共同完成，以此來提高求解效率。單智能體需求分解是將規(guī)劃問題分解后，仍由原有的規(guī)劃器來解決分解后的子問題。例如Xie等人提出的任務規(guī)劃方法基于多智能體系統(tǒng)[11]，而Hu等人分解認知規(guī)劃的過程基于單智能體系統(tǒng)[5]。

規(guī)劃分解后的子問題之間的關系主要有兩種，分別為相關子問題和無關子問題。相關子問題又分為消極關聯(lián)子問題和積極關聯(lián)子問題。

消極關聯(lián)是指兩個動作互斥，即一個動作的效果否定了另一個動作的效果，或一個動作刪除了另一個動作的前提。

積極關聯(lián)是指兩個動作同源，即兩個動作需要相同的前提并且至少一個動作的執(zhí)行不會刪除該前提。

規(guī)劃分解中較難處理的就是子問題間的關系。一方面，合并兩個子規(guī)劃時，消極關聯(lián)的子問題可能引起沖突，這些沖突可以通過在干擾動作間添加新的排序約束或者通過添加新的動作來彌補被刪除的事實；另一方面，合并兩個子規(guī)劃時，積極關聯(lián)的動作可能會產(chǎn)生相同的效果，因此造成冗余動作的出現(xiàn)。

3 規(guī)劃分解方法

通用且有效的規(guī)劃分解方法能夠提升規(guī)劃器的性能，促進智能規(guī)劃的發(fā)展。

3.1 基于傳統(tǒng)方法的規(guī)劃分解

基于傳統(tǒng)方法的規(guī)劃分解方法一般先對目標進行分解，然后再對子規(guī)劃整合。許多分解方法都是在此基礎上進行的改進。

Korf基于傳統(tǒng)方法討論了采用前向鏈全序規(guī)劃器分解一個復合目標的計算復雜度問題[2]。他指出，在所有子目標都完全獨立的情況下，分解會減少分支因子和搜索深度，從而防止規(guī)劃時間指數(shù)級增長。但是該方法也同樣存在缺點，在合并規(guī)劃的過程中，由于共享相同資源，子規(guī)劃可能會發(fā)生較為嚴重的沖突。

Iwen等人依據(jù)傳統(tǒng)的方法，研究出了一種可以通過構建交互圖來劃分目標集合的方法[9]。該方法的區(qū)別在于規(guī)劃問題總是被劃分為兩個子問題。其主要思想是：初始條件I與目標集合G如果指向相同的對象，則將其連接，從而繪制出一個二分圖，并稱其為交互圖；然后G被劃分為兩個集合，其中每個集合與交互圖中的一組連接組件對應。得到的兩個子問題可以由FF（fast-forward）等規(guī)劃器解決；最后將獲得的子規(guī)劃合并，并解決可能出現(xiàn)的沖突以獲得原始問題的解決方案。Iwen等人在blockworld域和logistics域，分別對HSP（heuristic search planner）、FF、GraphPlan等經(jīng)典規(guī)劃器以及它們的分布式版本D-HSP、D-FF、D-GraphPlan進行了對比實驗，結果表明該方法在執(zhí)行時間方面具有明顯的優(yōu)勢。

3.2 基于抽象層次結構的規(guī)劃分解

基于抽象層次結構的規(guī)劃分解是將一個域分解為層次結構的若干個層。該方法的關鍵部分在最頂層，規(guī)劃問題的解在最底層或某一個具體層。ABSTRIPS（abstraction STRIPS）規(guī)劃器[12]中第一次采用了抽象層次分解，之后Knoblock的ALPINE規(guī)劃器[13]以及Bacchus和Yang的HIPOINT規(guī)劃器[14]中也都采用了該方法。盡管抽象層次結構和傳統(tǒng)問題域分解存在相似性，但二者之間仍然存在很大的差異。第一，在傳統(tǒng)分解規(guī)劃中，規(guī)劃過程是同時發(fā)生的，而不是按照抽象層次結構的順序發(fā)生；第二，ALPINE和HIPOINT要求不同層的操作之間沒有沖突。而在傳統(tǒng)分解規(guī)劃中放寬了這一要求，允許各目標組之間有交互。

3.3 基于約束可滿足問題的規(guī)劃分解

由于規(guī)劃解合并時可能存在沖突，基于約束的方法可以有效地解決沖突。針對這一問題，Yang在規(guī)劃中實踐了分而治之的思想[10]。該思想首先分析目標之間的內在交互作用，討論如何自動分解規(guī)劃域。其次將大規(guī)模的目標劃分為不相交的子集，每個子集都具有自身的操作和初始條件，從而使得每個子集中的目標可以并行處理，并利用子規(guī)劃解之間的重疊功能合并子規(guī)劃解。該方法在執(zhí)行分解時需要控制復雜性，限制解決每個子問題所需機制的數(shù)量和種類。算法中包含了五個組成部分：第一部分將域分解為多個子域；第二部分求解子域；第三部分選取每個子域的規(guī)劃解；第四部分解決子規(guī)劃沖突；第五部分合并規(guī)劃并刪除冗余。

該方法將問題構建為約束可滿足問題，并將每一個分解目標集gi表示為變量，將每個gi對應的可選規(guī)劃πij表示為gi領域內的值。在兩個值A=πij和B=πl(wèi)k之間定義了一致性關系Cπ，使得Cπ(A,B)=TRUE當且僅當COMBINE({πij,πl(wèi)k})≠Fail，其中COMBINE()表示解決規(guī)劃沖突的方法過程。此功能需要一個通用的基于回溯的方法，在搜索的每個步驟中，根據(jù)全局一致性關系檢查累積的所有子規(guī)劃，以保證最終的全局規(guī)劃沒有沖突。與其他許多約束可滿足問題一樣，該方法將規(guī)劃選擇問題的解決方案分為兩個階段，即局部一致性方法階段和基于智能回溯的方法階段。Yang將這些方法應用在了WATPLAN規(guī)劃系統(tǒng)中。

3.4 基于專用求解器的規(guī)劃分解

對于大型復雜的規(guī)劃問題，可以針對子問題類型采用專用的求解器。例如，REALPLAN規(guī)劃分解的資源調度子問題是由專門的求解器完成的[7]。這種情況要求識別子問題的任務由域工程師完成，域工程師必須理解子問題的特征，并能夠合并子規(guī)劃。

與REALPLAN不同，Hybrid STAN（hybrid state analysis）根據(jù)子問題類型自動分解問題[6]，包括子問題的自動識別以及專用求解器的集成。可以采用領域分析工具來分解問題并識別這些子問題的存在。每個已識別的子問題對應一個求解器，并在整個問題的求解過程中僅使用一個規(guī)劃器。

該方法的主要優(yōu)勢在于能夠更快速地求解每一個子問題。然而，針對一些特定的情況，子問題的識別是復雜的，因為域中的微小變化可能會阻礙子問題的檢測。另外，規(guī)劃器和特定集合求解器之間的集成也較為復雜。

3.5 基于子目標排序的規(guī)劃分解

子目標排序是目標分解的一種常用方法。子目標排序是規(guī)劃過程的一部分，它有助于確定哪個子目標更容易實現(xiàn)。此外，子目標間的排序允許將一組文字分組在一起，由此產(chǎn)生問題分區(qū)。

比較典型的基于子目標排序的分解方法是Porteous和Hoffmann等人開發(fā)的一種基于標記概念的分解技術[15]。首先找到標記并加以實現(xiàn)，其次根據(jù)必要排序、合理排序和服從排序三種排序規(guī)則分別對子目標進行排序。預處理結束后生成LGG（landmarks generation graph)圖，每個子問題位于當前LGG圖的葉子結點。當一個子任務解決時，從LGG圖中刪除掉已完成的葉子結點。通過連接從子問題中獲取的子規(guī)劃形成解規(guī)劃。

GRT規(guī)劃系統(tǒng)將原始問題分解為嚴格按順序求解的子問題[16]。該分解基于定義了文字之間關系的XOR約束，這種類型的約束在分析域系統(tǒng)（如DISCOPlan（discovering state constraints plan））中稱為不變量。例如，在包裹運輸邏輯域中，可以定義以下XOR關系：xor（at（x*））（package x）。也就是說，包裹x同一時間只能在一個地方。一旦計算了XOR約束，就可以在滿足問題頂層目標之前必須達到的子目標之間建立順序。這些子目標被劃分為有序的中間目標，這些中間目標構成了按順序求解的子問題。

SGPlan方法將一個規(guī)劃問題分解為若干個子問題，按照子目標的解決順序對這些子問題進行排序，并為每個目標找到可行的規(guī)劃[8]。SGPlan采用了一種改進的Metric-FF規(guī)劃器作為基本的規(guī)劃器，當且僅當規(guī)劃失敗時觸發(fā)LPG（local planning graph）規(guī)劃器。在Metric-FF規(guī)劃器中添加了新的算法和改進的啟發(fā)式函數(shù)，使得規(guī)劃器能夠支持衍生謂詞、時序規(guī)劃和時間初始條件。SGPlan利用子目標劃分方法，使得問題的目標狀態(tài)不再是一個目標事實，而是與其他子問題具有松散耦合約束的任何事實。該方法包括子目標排序的策略，每一個層次分解子問題的中間目標分析策略，消除子問題中不相關行為的搜索空間縮減算法，以及調用最佳規(guī)劃器求解每個底層子問題的策略。該方法為分解技術在AI規(guī)劃中起到越來越重要的角色奠定了基礎。

3.6 基于子目標交互的規(guī)劃分解

在高度交互性的領域中，子問題分解是較難解決的。Sebastia等人提出了一種基于STRIPS（Stanford Research Institute Problem Solver）域的STeLLa分解技術[3]。STeLLa技術利用不同子目標之間的內在交互作用來分解問題。該技術基于標記的概念。標記是有序的，并被組合成不同的有序中間目標，用于對應新問題的目標集。STeLLa應用時間分解法，分解后的子問題可以順序或并發(fā)地求解，所得到的子規(guī)劃解能夠輕松合并。為了達到這一效果，關鍵問題是將目標間的相互作用用于問題分解，而不是在問題分解后再加以解決。研究者認為這種方法對于其他分解方法和規(guī)劃器都是非常有益的。

分解方案描述如下：第一個子問題的初始狀態(tài)I是原始問題的初始狀態(tài)，目標集IG1是中間目標IG的第一個集合，利用STRIPS規(guī)劃器求解第一個子問題并返回規(guī)劃P1。后續(xù)初始狀態(tài)IS1是規(guī)劃P1執(zhí)行后的結果。第二個子問題的初始狀態(tài)是IS1，目標狀態(tài)是IG的下一個集合IG2。同樣，利用規(guī)劃器求得規(guī)劃解P2，并產(chǎn)生規(guī)劃結果IS2。如此循環(huán)往復，直到完成IG的最后一個集合IGn。

在這種順序分解方案下，實驗得出了兩個重要結論：（1）復雜問題在應用了分解技術后變得容易求解了。（2）分解后的規(guī)劃解質量沒有降低，在許多問題實例中，規(guī)劃解的質量甚至得到了改進。

3.7 基于啟發(fā)式算法的規(guī)劃分解

Biba?等人提出基于進化元啟發(fā)式算法DAEX，該算法旨在提高封裝規(guī)劃系統(tǒng)的規(guī)劃質量和處理復雜規(guī)劃問題的可擴展性[4]。DAEX優(yōu)化了將規(guī)劃任務分解為一系列中間狀態(tài)的過程。DAEX的組件包括：（1）用于將復雜規(guī)劃任務分解為簡單子任務的分解原則；（2）用于解決每個子任務的封裝式可滿足規(guī)劃器；（3）用于提高底層規(guī)劃器解質量的優(yōu)化算法。DAEX采用了基于狀態(tài)的分解策略，分解原理依賴于經(jīng)典的可達性規(guī)劃啟發(fā)式算法。規(guī)劃任務被分割成一系列的中間狀態(tài)，即子目標，這些中間狀態(tài)在滿足最終目標前完成。該方法只花費較少的成本來計算分解，并嘗試使用專門的優(yōu)化算法求解最佳組合。DAEX是在DAE1和DAE2基礎上構建的。DAE1的分解原則是基于規(guī)劃對象層面的，通過完全盲目的方式組合謂詞和常量符號來構建中間狀態(tài)。DAE2雖然引入了基于原子層面的中間狀態(tài)計算方式，但仍然是盲目的。DAEX采用了基于時間的原子選擇方法，該方法依賴于標準規(guī)劃可達性啟發(fā)式和原子之間的成對互斥關系。其次，由于認為最優(yōu)規(guī)劃解是由最優(yōu)規(guī)劃器得到的，因此DAE1和DAE2采用的規(guī)劃器為CPT。這種方式的確可以得到好的規(guī)劃解，但是成本很大。DAEX采用了YAHSP（yet another heuristic search planner）規(guī)劃器，可以大大地降低成本。同時，DAEX還可以將搜索空間擴大到DAE1和DAE2搜索不到的大部分區(qū)域。分別在Costs域、Temporal域和STRIPS域進行實驗，探討了YAHSP、LAMA、DAEX、LPG、TFD規(guī)劃器的相關性能。實驗證明，DAEX在覆蓋率和質量方面都可以同最先進的規(guī)劃器相媲美。

4 規(guī)劃分解的應用

規(guī)劃分解的一個重要應用就在于為規(guī)劃算法的改進提供了重要的理論支撐。規(guī)劃分解方法在提高規(guī)劃器的問題求解能力，提升規(guī)劃問題的求解效率等方面都有著良好的表現(xiàn)。

除此之外，規(guī)劃分解在很多領域也都有著廣泛的應用。

4.1 多智能體系統(tǒng)的應用

為了有效地解決多智能體動態(tài)任務規(guī)劃問題，Xie等人提出了加權與/或樹與AOE（activity on edge）網(wǎng)絡相結合的任務規(guī)劃方法[11]。并在此基礎上提出了一種基于任務分包和動態(tài)重分解的動態(tài)任務規(guī)劃方法。通過加權與/或樹和AOE網(wǎng)絡對任務分解和一致性規(guī)劃協(xié)調進行處理，形成任務規(guī)劃，然后通過動態(tài)分解和任務分包進行沖突消除協(xié)調和動態(tài)調整協(xié)調，使總任務能夠繼續(xù)保持規(guī)劃的一致性，滿足任務規(guī)劃的動態(tài)實時性要求。在任務分包開始之前，任務操作代理發(fā)現(xiàn)沒有合適的代理接受此任務，因此可以進一步對任務進行分解，即動態(tài)任務分解過程。仿真結果表明，動態(tài)任務規(guī)劃方法能夠得到每個子任務的具體執(zhí)行時間，使整個任務在最短的時間內完成，或者在指定的時間內完成多個子任務。

4.2 認知規(guī)劃的應用

認知規(guī)劃在許多多智能體與人交互的領域都是必不可少的。大多數(shù)先進的認知規(guī)劃器通過將問題預編譯為經(jīng)典規(guī)劃問題來解決，并由已有的經(jīng)典規(guī)劃器求解，或者將認知公式預編譯為特定的范式，以便在搜索過程中獲得更好的性能。這種方法規(guī)劃速度快，但編譯計算成本高，并且隨著問題規(guī)模的增長，在計算上變得不可行。Hu等人通過將認知公式的推理過程委托給外部求解器來分解認知規(guī)劃[5]。研究者提出了一種無需預編譯步驟就可以表示，并且能夠靈活地解決大多數(shù)認知規(guī)劃問題的方法。該項工作第一次將認知推理委托給外部求解器。這一委托有效地分解了搜索中的認知推理，并允許在任何支持外部功能的STRIPS規(guī)劃器中實現(xiàn)。結果表明，該模型不僅能有效地解決認知基準問題，而且能處理多種類型的認知關系。研究者將分解算法分別應用在了Corridor、Graevine、Big Brother Logic和Socialmedia Network等問題中。Corridor和Graevine是認知規(guī)劃問題，用于和最先進的規(guī)劃器進行性能比較。Big Brother Logic問題用于證明模型的表達能力。Social-media Network問題用于證明模型對群體知識的推理能力。嵌套的深度和代理的數(shù)量不影響規(guī)劃性能，且由于采用了惰性的評價認知公式，避免了指數(shù)爆炸。

4.3 軟件測試用例生成

智能規(guī)劃方法在軟件測試中也有著很好的應用，特別是應用在測試用例生成問題中。MF-IPP（multifact IPP）規(guī)劃器在IPP（interference progression planner）規(guī)劃器基礎上添加了目標分解法和多事實文件處理算法，對事實文件進行劃分，并擴展了規(guī)劃器的功能，使其能夠處理多個事實文檔[17]。該方法將目標狀態(tài)是否相關作為事實文件分解的主要依據(jù)，有效地減緩了狀態(tài)數(shù)量的指數(shù)級增長，使狀態(tài)的擴張控制在可處理的范圍內，避免了組合爆炸問題的發(fā)生。MF-IPP規(guī)劃器應用于主控軟件圖形用戶界面測試用例自動生成。主要過程為：首先將分解后的事實文件輸入到規(guī)劃器中，并由規(guī)劃器求解出初始規(guī)劃。由于該規(guī)劃沒有附帶參數(shù)，因此需要進一步利用解擴展的方法對規(guī)劃進行進一步的完善，完善后的規(guī)劃可作為測試用例用于測試軟件功能。在blockworld域的實驗結果顯示，MF-IPP規(guī)劃器可以有效地避免由狀態(tài)個數(shù)指數(shù)級增長導致的組合爆炸問題；MF-IPP規(guī)劃器生成的測試用例生成速度快，覆蓋率高，能夠有效地解決基于規(guī)格說明的測試用例自動生成問題。

4.4 大型馬爾可夫決策過程的求解

由于維度的原因，精確求解一個大型馬爾可夫決策過程通常會比較困難。這一問題可以借助在線算法或層次分解的方法來加以解決。Barry等人提出了一種基于DetH*的在線算法，該方法通過在大型馬爾可夫決策過程（Markov decision process，MDP）中構造一個層次模型來尋找近似最優(yōu)策略，然后對其應用近似求解算法，并利用分解表示來實現(xiàn)域的緊湊性和效率，發(fā)現(xiàn)域的關聯(lián)性。實驗結果表明，創(chuàng)建和解決層次結構的總運行時間明顯少于最優(yōu)分解MDP求解器的總運行時間[18]。

與Barry等人的工作類似，Bai等人將基于MAXQ值函數(shù)分解的通用層次結構的優(yōu)點與啟發(fā)式和近似技術的能力相結合，提出了一種用于開發(fā)在線規(guī)劃框架的方法MAXQ-OP（MAXQ online planning）[19]。該框架為大型隨機域中規(guī)劃自主智能體提供了分層的解決方法。該方法應用在RoboCup足球模擬等二維領域中。研究表明，用該框架開發(fā)的智能體及其相關技術性能優(yōu)異，對大型領域具有高可擴展性。與Barry等人的工作不同，Bai等人根據(jù)實際情況假設每個子任務的終端狀態(tài)上存在一個先驗分布，根據(jù)先驗分布，MAXQ-OP可以在線評估根任務，而無需實際計算每個子任務的策略。MAXQ-OP能夠解決決策理論規(guī)劃文獻中難以解決的RoboCup 2C等大型問題，因此對于密集任務層次結構的大型馬爾可夫決策問題MAXQ-OP是可靠且穩(wěn)定的。

4.5 規(guī)劃質量優(yōu)化

一般情況下，規(guī)劃速度和規(guī)劃質量很難兼得。沒有時間限定的規(guī)劃研究者更注重規(guī)劃的質量，但目前的研究并沒有在所增加的時間內獲得等效的質量提升。Siddiqui等人提出了一種基于STRIPS域的持續(xù)改進規(guī)劃的新方法，該方法分析初始規(guī)劃的結構，通過邊界值搜索來劃分子規(guī)劃[20]。利用規(guī)劃亂序和塊分解技術反復進行規(guī)劃分解并局部優(yōu)化每一個子規(guī)劃，以保證規(guī)劃的正確劃分。該方法將一個規(guī)劃分解成“塊”，“塊”是封裝了一些交互動作的規(guī)劃步驟的子集，塊內的規(guī)劃步驟與塊外的規(guī)劃步驟不能交叉，而塊內步驟仍然是偏序關系的。塊分解將規(guī)劃步驟分解為多個不重疊的塊，分解中允許一些塊無序，這種無序性使得尋找子規(guī)劃的策略更有效，應用更廣泛。塊分解規(guī)劃優(yōu)化將一個有效的規(guī)劃優(yōu)化為一個新的更有效的規(guī)劃。這種方法可以在任何時間范圍內提供持續(xù)的規(guī)劃質量改進。

4.6 機器人規(guī)劃

機器人必須在不確定的大規(guī)模的狀態(tài)-動作空間進行規(guī)劃，并隨著需求和目標的變化不斷改變功能。Gopalan等人提出了一種抽象馬爾可夫決策過程（abstract Markov decision process，AMDP）層次結構的子目標網(wǎng)絡推理方法[21]。AMDP提供了一種基于模型的層次化表示，它封裝了層次結構中每一層抽象任務的知識，使得自頂向下的規(guī)劃比以前的方法更快、更靈活。AMDP是一個馬爾可夫決策過程（MDP），其狀態(tài)是底層環(huán)境狀態(tài)的抽象表示。AMDP將問題分解為一系列子任務，以此來簡化決策問題。方法中智能體不是在動作之間選擇，而是在遞歸求解的子目標之間進行選擇，用以降低搜索深度。該方法還可以將世界狀態(tài)表示壓縮為僅包含與當前決策問題相關的信息。每個子問題的規(guī)劃算法可以定制，允許盡可能高效地解決每個目標。該層次結構只需要對有助于完成主要任務的子目標進行規(guī)劃，而不求解無關子目標的規(guī)劃，因此該方法只需普通MDP規(guī)劃復雜決策所需的少量時間就可以完成任務。所得到的分層規(guī)劃方法在每個抽象層次上都是獨立最優(yōu)的，并且在局部獎勵函數(shù)和轉移函數(shù)正確的情況下是遞歸最優(yōu)的。研究者利用“出租車”和“清理世界”域進行實驗研究，結果證明，在保持解決方案質量的同時，規(guī)劃速度顯著提高。該方法為Turtlebot智能體上的移動操作問題提供了決策模型，這種統(tǒng)一的模型可以利用低層的控制動作有效地規(guī)劃高層抽象目標。

基于線性時序邏輯（linear-time temporal logic，LTL）規(guī)范的高層規(guī)劃為復雜場景中機器人的部署提供了正確和最優(yōu)的執(zhí)行策略，避免了手工設計機器人行為的需要。然而，當處理一組機器人時，這個問題就變得格外復雜。針對一個有限的LTL任務和一組機器人，Schillinger等人給出了有限LTL規(guī)范分解的形式化定義，討論了有限LTL規(guī)范分解的屬性；研究了如何在LTL規(guī)范的自動機表示中有效地識別這種分解；提出了一種基于團隊規(guī)模構建處理復雜性團隊模型的方法，該模型可用于高效的多智能體規(guī)劃。Schillinger等人認為該方法直接導致團隊模型的構建，其復雜度明顯低于傳統(tǒng)方法構建的其他模型。因此，它能夠有效地搜索最優(yōu)分解，并將任務分配給機器人代理。該方法可以用于評估團隊模型的狀態(tài)空間復雜度和規(guī)劃時間[22]。

5 分析和展望

5.1 分析

智能規(guī)劃可以基于多種方法，針對不同類型的規(guī)劃問題也可以輔助不同的技術。但無論采用哪種技術，面對復雜的規(guī)劃問題，規(guī)劃分解都是解決問題的一個重要手段，是智能規(guī)劃發(fā)展的一個必經(jīng)之路。規(guī)劃分解將伴隨著智能規(guī)劃技術的發(fā)展而不斷發(fā)展。本文闡述了規(guī)劃分解的發(fā)展歷史、規(guī)劃分解問題的一般描述、規(guī)劃分解的分類，以及規(guī)劃分解的一些重要方法和熱門應用。

文中涉及的各種分解方法的基本情況如表1所示。

目前規(guī)劃分解存在著一些問題，這些問題也影響著其未來的發(fā)展方向。

從整體上來說，規(guī)劃分解方法種類較多，但很多方法只是針對某一問題的獨立研究，方法間的交互較少。很多方法的延續(xù)性較弱，缺乏進一步的深入研究。因此，規(guī)劃分解工作需要加強理論與應用的體系化、結構化、系統(tǒng)化的研究。

從具體問題來說，目前規(guī)劃分解中存在的問題主要有以下幾個方面：

（1）動作間仍然存在大量未知的關聯(lián)關系，這會使得規(guī)劃處理變得繁瑣復雜，也會嚴重影響規(guī)劃分解的有效性。

（2）規(guī)劃的速度和規(guī)劃的質量仍需進一步協(xié)調。

（3）針對規(guī)劃分解的效果目前還沒有統(tǒng)一的評估標準。

（4）形式化語言還需要進一步完善。

（5）對于解決復雜情況的規(guī)劃問題，可以加強多種技術的深入融合。

5.2 展望

規(guī)劃分解是求解一些復雜規(guī)劃問題的一個有效方法，但目前也有一些交叉方法推動著智能規(guī)劃的發(fā)展。主要體現(xiàn)在智能規(guī)劃與其他人工智能方法的結合，特別是神經(jīng)網(wǎng)絡[23]、強化學習[24]、遺傳算法[25]、深度學習[26]、自動推理技術[27]等。

其中一些方法與智能規(guī)劃相結合突破了經(jīng)典規(guī)劃的求解方式，取得了顯著的效果，值得進一步探索。例如Milani等人利用神經(jīng)網(wǎng)絡求解規(guī)劃問題[23]，求解過程改變了原有已知動作模型的求解方式，規(guī)劃的推導過程不是基于傳統(tǒng)的四元組＜P,I,G,A＞（其中P表示前提，I表示初始條件，G表示目標，A表示動作的集合），取而代之的是利用神經(jīng)網(wǎng)絡的方式進行求解，具體操作時用三元組＜s1,s2,a＞表示訓練實例（其中s1表示動作a執(zhí)行的前提，s2表示動作a執(zhí)行的效果），每一個前提和效果對應一個二進制位的向量長度|P|，并假設其在0～1.0的實數(shù)區(qū)間內。通過這種方式將規(guī)劃問題轉換為一個神經(jīng)網(wǎng)絡的回歸任務，訓練階段的損失函數(shù)采用均方誤差來實施。

Leonetti等人利用規(guī)劃與強化學習的互補特性研究了二者相結合的方法[25]。它們的互補性主要體現(xiàn)在規(guī)劃依賴于先前的知識和計算，強調模型的準確性；而強化學習依賴于與世界的互動和經(jīng)驗，不需要先前的知識，更能適應環(huán)境，但要求具備一定的經(jīng)驗知識。根據(jù)兩種方法的不同特點，利用規(guī)劃來約束智能體的行為，同時利用強化學習來適應環(huán)境，使智能體可以快速學習，構建執(zhí)行所有任務的動作模型，并隨著時間推移而改進，不斷適應環(huán)境的變化。賴志鋒等人將智能規(guī)劃與遺傳算法相結合[24]，研究基于遺傳算法的智能規(guī)劃動作模型的學習過程，所提出的算法能夠在較短的時間內，學習到一個逼近專家描述的動作模型。這種方法解決了不完全觀察問題中，事物前后狀態(tài)不完整導致規(guī)劃無法進行的問題。

各種方法交叉融合，不僅能夠解決智能規(guī)劃研究中出現(xiàn)的難題，推動智能規(guī)劃的發(fā)展，同時也必將促進各領域的推陳出新、不斷演化。

6 結束語

規(guī)劃分解是智能規(guī)劃研究的一個不可或缺的組成部分，是求解規(guī)劃復雜問題的一個有效解決方法。本文從規(guī)劃分解的發(fā)展、一般形式、分類等基礎問題進行闡述，并著重介紹了規(guī)劃分解的一些關鍵技術和熱門應用。歸納總結了現(xiàn)有規(guī)劃分解存在的突出問題，并分析了規(guī)劃分解未來的發(fā)展方向，以及其他人工智能方法對規(guī)劃求解的影響。