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

李 麗，王大勇

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

1 引言

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

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

2 規(guī)劃分解問題

2.1 問題描述

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

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

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

2.2 問題分類

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

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

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

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

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

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

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

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

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

3 規(guī)劃分解方法

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

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

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

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

Iwen等人依據(jù)傳統(tǒng)的方法，研究出了一種可以通過構(gòu)建交互圖來劃分目標(biāo)集合的方法[9]。該方法的區(qū)別在于規(guī)劃問題總是被劃分為兩個子問題。其主要思想是：初始條件I與目標(biāo)集合G如果指向相同的對象，則將其連接，從而繪制出一個二分圖，并稱其為交互圖；然后G被劃分為兩個集合，其中每個集合與交互圖中的一組連接組件對應(yīng)。得到的兩個子問題可以由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進(jìn)行了對比實驗，結(jié)果表明該方法在執(zhí)行時間方面具有明顯的優(yōu)勢。

3.2 基于抽象層次結(jié)構(gòu)的規(guī)劃分解

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2 認(rèn)知規(guī)劃的應(yīng)用

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

4.3 軟件測試用例生成

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

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

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

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

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

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

4.6 機(jī)器人規(guī)劃

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

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

5 分析和展望

5.1 分析

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

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

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

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

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

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

（2）規(guī)劃的速度和規(guī)劃的質(zhì)量仍需進(jìn)一步協(xié)調(diào)。

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

（4）形式化語言還需要進(jìn)一步完善。

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

5.2 展望

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

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

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

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

6 結(jié)束語

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