1
| 本文作者： 李尊 | 2016-07-12 19:33 |
導(dǎo)讀：2016國際人工智能聯(lián)合會議（IJCAI2016）于7月9日至7月15日舉行，今年會議聚焦于人類意識的人工智能，本文是IJCAI2016杰出論文（Distinguished Papers），除了論文詳解之外，我們另外邀請到哈爾濱工業(yè)大學(xué)李衍杰副教授進(jìn)行點(diǎn)評。
聯(lián)合編譯：Blake、章敏
1.引言
有限狀態(tài)控制器（FSCs）作為一種緊湊且有效的表達(dá)方式在AI領(lǐng)域中經(jīng)常使用，比較突出的應(yīng)用例子包括：機(jī)器人、視頻游戲。在規(guī)劃上，F(xiàn)SCs主要有兩個(gè)優(yōu)勢：
1）緊湊的解決方案
2）能夠代表一般規(guī)劃解決一系列的相似計(jì)劃問題
這種普遍適用性允許FSCs代表大型問題的解決方案，包括局部問題和非確定行為等。
然而，即便是FSCs也存在局限性?？紤]到所有的二元樹的穿越節(jié)點(diǎn)如圖1所示。針對這個(gè)任務(wù)一個(gè)典型的處理辦法包括一個(gè)行動序列（在節(jié)點(diǎn)的數(shù)量長度上是線性的），在樹的深度上是指數(shù)型的。相反，深度優(yōu)先搜索（DFS）的遞歸定義僅僅只要求一小部分代碼。然而，一個(gè)標(biāo)準(zhǔn)的FSC不能執(zhí)行遞歸，DFS的迭代定義更加復(fù)雜，包括一個(gè)內(nèi)部的數(shù)據(jù)結(jié)構(gòu)。
圖1 擁有7個(gè)節(jié)點(diǎn)的二元樹示例
在本文中我們介紹了分層有效狀態(tài)控制器，它是一種創(chuàng)新性的表征、計(jì)算緊湊和一般規(guī)劃的解決辦法。我們在三個(gè)方面將標(biāo)準(zhǔn)的FSCs進(jìn)行了擴(kuò)展。
1． 分層FSCs能夠包含多重獨(dú)立的FSCs。
2． 每個(gè)FSC能夠調(diào)用其他的FSCs。
3． 每個(gè)FSC都由個(gè)參數(shù)表，當(dāng)一個(gè)FSC被調(diào)用時(shí)，必須調(diào)整指派給參數(shù)的變量。
作為一個(gè)特例，我們的改進(jìn)通過允許一個(gè)FSC用不同的變量調(diào)用它自身來實(shí)現(xiàn)遞歸。
為了進(jìn)一步解釋，圖2展示了分層FSC C[n]使用遞歸方法實(shí)現(xiàn)了二元樹的DFS反復(fù)運(yùn)動。
這里，n是控制器的單獨(dú)參數(shù)和表示該二元樹的當(dāng)前節(jié)點(diǎn)。條件leaf(n)的測試n是否是leaf節(jié)點(diǎn)，而連字符“ - ”表示該過渡。動作visit(n)訪問節(jié)點(diǎn)n，而copyL（n，m）和copyR（n，m）將左側(cè)和右側(cè)的子節(jié)點(diǎn)從n移到m。動作call（m）為向FSC本身的遞歸調(diào)用，指派控制器的唯一參數(shù)m并重新從初始節(jié)點(diǎn)Q0開始啟動。
圖2
直觀地說，通過重復(fù)分配n的右子到n本身（使用操作copyR（n，n））和以下控制器狀態(tài)Q0,Q1,Q2,Q3,Q0,...，F(xiàn)SC的C [n的周期]具有前往樹的最右邊的分支的所有節(jié)點(diǎn)，直至到達(dá)節(jié)點(diǎn)的效果。此外，通過分配n的子（使用動作copyL（n，子）），使遞歸調(diào)用調(diào)用時(shí)，F(xiàn)SC C [n]被遞歸所有左子執(zhí)行?？刂破鳡顟B(tài)Q4是最終狀態(tài)，動作訪問（子）在過渡到Q4其實(shí)沒有必要和可能被刪除。然而，我們的做法是自動生成FSC，所以目前是完全按照條件和行動來。
與之前有關(guān)規(guī)劃的FSCs自動生成的工作對比，本文的主要貢獻(xiàn)有：
1.對FSCS的過渡功能的重構(gòu)，允許二進(jìn)制分支只為了減少可能控制器的空間。
2.規(guī)劃分層FSCS一個(gè)正式的定義，允許控制器調(diào)用其他控制器，特殊情況下包括遞歸。
3.新的匯編方法，針對一般規(guī)劃任務(wù)能夠自動生成分層FSCS。匯編作為輸入的一組從一個(gè)給定域規(guī)劃問題，并輸出單個(gè)經(jīng)典規(guī)劃問題，其解決方案對應(yīng)于一個(gè)分層的FSC。這個(gè)輸出在PDDL被表達(dá)，從而關(guān)斷的，現(xiàn)成的經(jīng)典籌辦可以用來生成分級FSCS。匯編還使得可以摻入現(xiàn)有FSCS的形式先驗(yàn)知識來自動完成余下FSCS的定義。
2.背景
本節(jié)中主要定義了我們針對經(jīng)典規(guī)劃的模型，展示了我們過去常常定義FSCs規(guī)劃的改進(jìn)。
2.1 有條件結(jié)果下的典型規(guī)劃
我們用文字來描述狀態(tài)和動作。
形式上，給定一組狀態(tài)（fluents）F，文字l是狀態(tài)F中的一個(gè)賦值，即l = f 或者l = ?f 因?yàn)?f ∈ F。一組文字L代表一些狀態(tài)的部分賦值（WLOG我們假設(shè)L不能分配沖突的值賦值給任何一個(gè)狀態(tài)）。至于 L, 讓 ?L = {?l : l ∈ L}作為L的補(bǔ)充，使得| s | =| F |，即對狀態(tài)的整體賦值。
一個(gè)經(jīng)典的規(guī)劃問題是數(shù)組P = <F,A,I,G>，其中F是一個(gè)狀態(tài)（fluents）集的，A是一組動作，I是一個(gè)初始狀態(tài)，G為目標(biāo)的條件，即一組文字。每個(gè)動作a∈A具有一組文字pre(a)被稱為前提條件，和一組條件結(jié)果cond(a)。每個(gè)條件結(jié)果C B E ∈ cond(a)由文字組C（條件）和E（結(jié)果）組成。我們常常形容初始狀態(tài)I ? F是賦值（fluents）的子集是真的。
只有在pre(a) ? s的情況下，行動a能夠應(yīng)用在狀態(tài)s中，特定集的觸發(fā)結(jié)果是：
即結(jié)果狀態(tài)保存在s中. 將 a 應(yīng)用到 s 的新結(jié)果狀態(tài)即θ(s,a) = (s \ ?eff(s,a)) ∪ eff(s,a).
計(jì)劃P是一個(gè)行動序列 π = <a1,...,ani>,它包括一個(gè)狀態(tài)序列<s0,s1,...,sn>。這樣s0 = I, 針對每個(gè) 1 ≤ i ≤ n中的i，ai能夠應(yīng)用到si?1 中并且能夠生成成功態(tài)si = θ(si?1,ai)。有且僅有 G ? sn的情況下，計(jì)劃 π 能夠解答P, 即如果目標(biāo)狀態(tài)在應(yīng)用π能夠運(yùn)用到 I中。
2.2 有限狀態(tài)控制器
給定一個(gè)規(guī)劃問題P = <F,A,I,G>， FSC被定義為一個(gè)數(shù)組C =< Q,T,q0,q⊥>，Q是一組控制器狀態(tài)，T : Q × 2F → Q × A是假定能全面觀測的局部轉(zhuǎn)移函數(shù)，q0 ∈ Q和q⊥ ∈ Q分別為初始和終端控制器的狀態(tài)。這個(gè)針對FSCS在一般規(guī)劃與以前的工作相關(guān)定義如下：
?就像以前的方法（不像Mealy machines），轉(zhuǎn)移不依賴于明顯的輸入序列，而是基于當(dāng)前的規(guī)劃狀態(tài)。
?以前的方法采用當(dāng)下規(guī)劃狀態(tài)的部分可觀測性，定義轉(zhuǎn)移函數(shù)T在Q × O，其中O是觀察組。相反，我們定義T在 Q × 2F，即整個(gè)狀態(tài)集。
?我們定義一個(gè)明確的中止?fàn)顟B(tài)q⊥，而以前的辦法是在到達(dá)目標(biāo)狀態(tài)G終止。原因在于我們將我們將定義擴(kuò)展到分層有限狀態(tài)控制器，因?yàn)槟繕?biāo)G為不一定滿足終止FSCS的中止執(zhí)行條件。
我們簡要地描述關(guān)于規(guī)劃問題P的FSC C的執(zhí)行語義問題。
當(dāng)前的狀態(tài)是一對(q,s) ∈ Q × 2F控制態(tài)和規(guī)劃態(tài)。因?yàn)?q,s)，系統(tǒng)轉(zhuǎn)移到了(q0,s0)，其中(q0,a) = T(q,s)是在將轉(zhuǎn)移函數(shù)應(yīng)用到(q,s)的結(jié)果， s0 = θ(s,a)是將a應(yīng)用到s中的結(jié)果。執(zhí)行開始于(q0,I)并重復(fù)轉(zhuǎn)移，直到達(dá)到包含終端控制器狀態(tài)q⊥的(q⊥,s⊥)。
一般規(guī)劃問題P = {P1,...,PT}是一組共享狀態(tài)和動作的多個(gè)單體規(guī)劃問題。因此每個(gè)獨(dú)立規(guī)劃問題Pt ∈ P被定義為Pt = <F,A,I,G>，僅有初始狀態(tài)It和目標(biāo)狀態(tài)Gt 與P中其他規(guī)劃問題不同。當(dāng)且僅只有當(dāng)它解決Pt ∈ P.的所有問題時(shí)，F(xiàn)SC C才能夠解決規(guī)劃問題。
3．生成有限狀態(tài)控制器
本節(jié)匯編了一個(gè)需要輸入的經(jīng)典規(guī)劃問題P = <F,A,I,G>，Gi和控制器狀態(tài)的最大數(shù)量的約束n，并且產(chǎn)生作為輸出一個(gè)經(jīng)典規(guī)劃問題的Pn。在光合操作定義，這樣可以解決任何的Pn有計(jì)劃，既產(chǎn)生FSC C和模擬P上C的執(zhí)行，從而驗(yàn)證了?解決P.我們后來此編譯擴(kuò)展到廣義的規(guī)劃問題，F(xiàn)SCS的層次結(jié)構(gòu)。
為了生成 FSC C = <Q,T,q0,q⊥> ，我們首先定義 Q = {q0,...,qn} 和數(shù)據(jù)集 q⊥ ≡ qn，剩下的就是構(gòu)筑轉(zhuǎn)移函數(shù) T。我們的方法是減少可能存在的控制器用過定義T : Q × 2F → Q × A，并使用下面三個(gè)函數(shù) Γ, Λ and Φ:
? Γ : Q → F associates a fluent f = Γ(q) to each q ∈ Q.
? Λ : Q × {0,1} → Q returns a successor state in Q.
? Φ : Q × {0,1} → A returns an action in A.
轉(zhuǎn)移從狀態(tài) (q,s) 依靠在s中的每個(gè)真實(shí)賦值Γ(q)，因此只允許二進(jìn)制分支。設(shè)Γ(q) ∈ s是測試，其結(jié)果被解釋為一個(gè)布爾值{0,1}。過渡函數(shù)被定義為
T(q,s) = (Λ(q,Γ(q) ∈ s),Φ(q,Γ(q) ∈ s)).
我們繼續(xù)定義Pn = {Fn,An,In,Gn}。編譯背后的思想是定義兩種類型的動作：對于每個(gè)控制器狀態(tài)C的每個(gè)控制器狀態(tài)進(jìn)行編程的三個(gè)函數(shù)Γ，Λ和Φ以及設(shè)計(jì)動作，通過在當(dāng)前計(jì)劃狀態(tài)評估模擬執(zhí)行P上C的執(zhí)行規(guī)劃動作。
狀態(tài)集是Fn = F ∪ FT ∪ Faux，其中 FT con包含轉(zhuǎn)移函數(shù)中需要編碼的狀態(tài)：
?For each q ∈ Q and f ∈ F, a fluent condfq that holds iff f is the condition of q, i.e. if Γ(q) = f.
?For each q,q0 ∈ Q and b ∈ {0,1}, a fluent succbq,q0 that holds iff Λ(q,b) = q0.
?For each q ∈ Q, b ∈ {0,1} and a ∈ A, a fluent actbq,a that holds iff Φ(q,b) = a.
?For each q ∈ Q and b ∈ {0,1}, fluents nocondq, nosuccbq and noactbq that hold iff we have yet to program the functions Γ, Λ and Φ, respectively.
另外， Faux包含以下狀態(tài)：
?For each q ∈ Q, a fluent csq that holds iff q is the current controller state.
?Fluents evl and app that hold iff we are done evaluating the condition or applying the action corresponding to the current controller state, and fluents o0 and o1 representing the outcome of the evaluation.
初始狀態(tài)和目標(biāo)條件定義為In =I ∪{csq0}∪{nocondq,noactbq,nosuccqb : q ∈ Q,b ∈ {0,1}} 以及 Gn = G∪{csqn}. 最后，動作集An 通過以下動作替換動作A：
動作pcondfq, pactbq,a 以及psuccbq,q0 組成了三個(gè)函數(shù) Γ, Φ 與 Λ， 與此同時(shí) econdfq, eactbq,a 和esuccbq,q0 執(zhí)行了相應(yīng)的函數(shù)。Fluents EVL和應(yīng)用控制了執(zhí)行順序，使得?？偸窍葓?zhí)行，然后是Φ，最后是Λ。
原理 1. 任何解決了Pn 的規(guī)劃π 包括一個(gè)解決P的FSC C
證明簡析
改變當(dāng)前控制器狀態(tài)的唯一方法是將動作應(yīng)用到esuccbq,q0中，這首先需要編程和順序執(zhí)行功能Γ，Φ和Λ。一旦程序編輯完成，計(jì)劃π就不能再改變，因?yàn)橛幸恍┲虚g不能再nocondq, noactbq 和nosuccbq添加狀態(tài)。一旦程序編輯完成為所有狀態(tài)和布爾值B∈{0,1}，三大功能Γ，Φ和Λ就共同定義了一個(gè)FSC C.
最后，行動esuccbq,q0 過渡到控制器狀態(tài)q0。這種確定性將繼續(xù)執(zhí)行，直到我們達(dá)到最終狀態(tài)(qn,sn)，或者重新審視整體的狀態(tài)。如果π解決了Pn，在執(zhí)行(qn,sn)和目標(biāo)狀態(tài)的sn中的G，這也是C解決P的定義。
我們延長了編譯，以解決一般規(guī)劃問題P = {P1,...,PT}。在這種情況下，以光合速率的解決方案構(gòu)建了一個(gè)FSC C和模擬上的所有個(gè)人規(guī)劃問題鉑∈P.的擴(kuò)展引入動作結(jié)束噸碳的執(zhí)行。此外，初始狀態(tài)和目標(biāo)狀態(tài)被重新定義為在= I1此外，初始狀態(tài)和目標(biāo)條件被重新定義為： In = I1 ∪{csq0} ∪ {nocondq,noactbq,nosucc and Gn = GT ∪ {csqn}.
4.分層最終狀態(tài)控制器
本節(jié)中，我們允許FSCs命令其它的FSCs，從而拓展關(guān)于分層FSCs的FSCs公式。因此現(xiàn)在的FSC C是有參數(shù)的，并且可以調(diào)用C指定傳遞給參數(shù)C的參數(shù)。同樣，我們首先描述，如何利用分層FSCs解決單一的規(guī)劃問題P = <F,A,I,G>，并將這個(gè)概念推廣到普遍的規(guī)劃問題。
在PDDL方面，我們假設(shè)F中的流體是斷言中的實(shí)例，此外，假設(shè)存在一系列的“可變對象?v”和一系列的“價(jià)值對象?x”，并且對于每一個(gè) v ∈ ?v 和 x ∈ ?x，F(xiàn)都包含流體assignv,x ——模擬v = x類型的任務(wù)。令Fa ? F 是任務(wù)流體的集，并令Fr = F \Fa是剩余的流體。
給定一個(gè)規(guī)劃問題F——有著流體 Fa ? F且包括一系列?v和 ?x，那么分層FSC就是一個(gè)數(shù)組H = <C,C1>，其中C = {C1,...,Cm} 是FSCs在分層中的集，且C1 ∈ C 是原本的FSC。我們假設(shè)所有在FSCs中的C共享相同的控制器狀態(tài)Q集，并且每一個(gè)Ci ∈ C 都有著相關(guān)的參數(shù)表——它由?v中變量對象ki 組成。那么可能的FSC指令集給出如下。例如所有從C中選擇FSC Ci的方法和它參數(shù)所指定的參數(shù)。每一個(gè)FSC Ci的轉(zhuǎn)換函數(shù)Ti定義為： Ti : Q × 2F → Q × (A ∪ Z)以便包括給C中FSCs可能下達(dá)的指令。如以前一樣，我們使用函數(shù) Γi, Λi 和 Φ代表Ti。
為了定義分層FSCH的執(zhí)行語句，我們引入了一個(gè)調(diào)用棧。在原始FSC的開始執(zhí)行，在狀態(tài) (q0,I)和一個(gè)0級的堆棧中，大體來說，對于FSC Ci，世界規(guī)定的(q, s) 和給定Ti(q,s) = (q’，a) 返還一個(gè)行為 a ∈ A，執(zhí)行語句的解釋如第2節(jié)中單體FSCs一樣的。然而，當(dāng) Ti(q,s) = (q’,Cj[p])將一個(gè)指令返還給控制器Cj[p] ∈ Z時(shí)，我們將下一個(gè)等級的堆棧設(shè)置為 (q0,s[p])，其中s[p]是從s中獲得的——通過復(fù)制每個(gè)p中的變量對象到 Cj中相應(yīng)的對象。在下一個(gè)等級的堆棧中語句的執(zhí)行伴隨著轉(zhuǎn)換函數(shù)Tj，，其中包括其它需要更高堆棧等級的FSC指令。如果 Tj 到達(dá)終端狀態(tài)(q⊥,s⊥)，控制就會返回到根控制器Ci。具體來說，Ci的狀態(tài)變成(q’,s’)，其中s’是從s⊥中獲得的，通過取代在以前的堆棧級別上原來分配變量值。當(dāng)在堆棧等級0達(dá)到語句狀態(tài)(q⊥,s⊥)，且H 解決了P iff G ? s⊥時(shí)，執(zhí)行分層FSC H語句。
4.1分層最終狀態(tài)控制器的擴(kuò)展編譯
我們從P到典型的規(guī)劃問題方面，介紹了一個(gè)編譯。例如解出的總數(shù)用于編程一個(gè)分層FSCH=<C，C1>，并在P上模擬執(zhí)行。同樣，n限制控制器狀態(tài)的數(shù)量，m是C中FSC的最大數(shù)，且l限制指令堆棧的大小。流體集是其中等，對于每一個(gè)堆棧等級l，都有每一個(gè)類型流體assignv,x 的復(fù)制品。
? FTm = {fi : f ∈ FT,1 ≤ i ≤ m}，等，對于每一個(gè)FSCCi ∈ C ， FT中每一個(gè)流體都有復(fù)制品，確定其相應(yīng)的轉(zhuǎn)換函數(shù)體Ti，等，對于每一個(gè)堆棧等級l，F(xiàn)aux 中的流體都有復(fù)制品。
此外， FH包含如下額外的流體
?對于每個(gè) l, 0 ≤ l ≤ L，包含iffl的流體lvl l是當(dāng)前的堆棧等級 。
?對于每個(gè)Ci ∈ C 和 l, 0 ≤ l ≤ L，包含iff Ci 的流體fsci,l，是在堆棧等級l上正被執(zhí)行的FSC。
?對于每個(gè)，流體包含iff Φi(q,b) = Cj[p]。
初始狀態(tài)和目標(biāo)控制轉(zhuǎn)變?yōu)椋?/p>
{nocondq,noactq ,nosuccq : q ∈ Q,b ∈ {0,1},Ci ∈ C} 且。換句話說，assignv,x ∈ Fa 類型的流體是堆棧等級0最初的標(biāo)志，在等級0控制器狀態(tài)是q0，當(dāng)前堆棧等級是0，在等級0的FSC是C1，并且函數(shù) Γi, Λi and Φi 沒有被任何的 FSC Ci ∈ C執(zhí)行。為了滿足該目標(biāo)，我們必須在堆棧等級0上達(dá)到終端狀態(tài)qn。
為了在集A`n,m建立行動，我們首先適應(yīng)了An 中所有的行動——通過FSC Ci ∈ C 和堆棧等級l，0 ≤ l ≤ L的參數(shù)，加入前提條件 lvll 和 fsci,l，并且修改剩余的先決條件和影響。作為一個(gè)例子，我們給出了最終行動pcondf,i,lq的定義：
pre(pcondf,i,lq ) = {lvll,fsci,l,cslq,nocond,
eff(pcond{?nocondiq,cond.
相比于以前的pcondfq，現(xiàn)在的控制器狀態(tài)是指堆棧級L，并且FTm 中的流體nocondiq condf,iq是指FSC Ci 。先決條件模型的事實(shí)——我們只能在堆棧等級l的控制器狀態(tài)q下編程函數(shù)Γi 的 Ci，，l是當(dāng)前堆棧等級，Ci 正在等級l執(zhí)行，等級l的當(dāng)前控制器是q，Γi原先沒有在q中編程。
除了適應(yīng)An的行動，同樣包含如下的新行動：
作為 pactb,i,lq,a的選擇，行動pcallb,i,lq,j (p)編程了一個(gè)FSC稱為Cj[p]，等，定義函數(shù)如Φi(q,b) = Cj[p]。行為ecall執(zhí)行該FSC命令——通過遞增當(dāng)前的堆等級到l+1，并且設(shè)置控制器狀態(tài)等級為l+1到q0?？刂朴绊憑assignlpk,x} B {assign有效的復(fù)制等級l上的價(jià)值參數(shù)pk 以便對應(yīng)參數(shù)等級l+1上Cj的參數(shù)。在終端狀態(tài) qn時(shí)，終端行動termi,l 遞減堆棧等級到l-1，并刪除所有關(guān)于堆棧等級l時(shí)的所有信息。
定理2
任何解決的方法 π都可以引出一個(gè)可以解決P的分層FSCH。
證據(jù)簡述。與證明定理1的論據(jù)相似，方法π需要編寫每一個(gè) FSC Ci ∈ C的函數(shù) Γi, Λi 和 Φi 。
由于新的行動pcall（p），包括了制造FSC指令的概率，所以π隱式定義了一個(gè)分層FSCH。
此外，π在P（開始于堆棧等級0的(q0,I)）上模擬執(zhí)行H。作任何情況下(q, s)在堆棧等級l執(zhí)行FSC Ci 時(shí)，無論該計(jì)劃何時(shí)包含一個(gè)部分動序列<econd,esucc,——包含F(xiàn)SC指令。ecall的影響都是增加堆棧等級，導(dǎo)致執(zhí)行進(jìn)展到FSCCj的堆棧等級l+1。唯一減少堆棧等級的行動是termj,l+1，一旦termj,l+1被應(yīng)用，我們便可以應(yīng)用行動esuccb,i,lq,q0轉(zhuǎn)換到新的控制器狀態(tài)q’。
如果π解決了，執(zhí)行則在等級0上終止于狀態(tài)(qn,sn) ，并且目標(biāo)控制包含在sn內(nèi)，以滿足控制H解決P。
我們注意到行動pcallb,i,lq,j (p) 可以通過設(shè)置i=j用于實(shí)現(xiàn)遞歸，使FSC Ci 命令自己。我們同樣可以通過在初始狀態(tài)增加condf,iq , actb,iq,a, succ and callb,iq,j(p)類型的流體 ，局部具體化FSC Ci 的函數(shù) Γi, Λi 和Φi。通過這種方法，我們可以結(jié)合先前的知識觀察一些原先存在于C中的FSCs的結(jié)構(gòu)。
編譯可以擴(kuò)展到一個(gè)普遍的規(guī)劃問題P = {P1,...,PT}類似于 Pn，具體來說endt, 1 ≤ t < T,應(yīng)該有前提并且復(fù)位狀態(tài)到，系統(tǒng)應(yīng)該達(dá)到在堆棧等級0的最終狀態(tài)qn ，并且在執(zhí)行下一個(gè)問題Pt+1 ∈ P之前，滿足Pt的目標(biāo)控制Gt 。為了解決，方案需要在所有的規(guī)劃問題P中模擬執(zhí)行H。
5.評估
我們在一系列普遍規(guī)劃基準(zhǔn)和Bonet等人進(jìn)行的編程任務(wù)中評估了我們的方法。在所有的實(shí)驗(yàn)中，我們都用LAMA-2011設(shè)置一個(gè)處理器Intel Core i5 3.10GHz x 4（有著4GB運(yùn)行內(nèi)存和3600秒的時(shí)間限制）運(yùn)行古典的設(shè)計(jì)者FastDownward。
我們簡要地描述了在實(shí)驗(yàn)中使用的每個(gè)域。在模塊方面，其目標(biāo)是從一個(gè)單獨(dú)的塔中出棧模塊，直到直到綠色的模塊。在夾持器方面，目標(biāo)是將一組球從一個(gè)房間運(yùn)輸?shù)搅硪粋€(gè)房間。在目錄方面，其目標(biāo)是訪問鏈表中所有的點(diǎn)。在反轉(zhuǎn)方面，其目的是反轉(zhuǎn)目錄中的元素。在總計(jì)方面，其目標(biāo)是計(jì)算的和并給輸入n。在數(shù)/DFS方面，其目標(biāo)是訪問二進(jìn)制樹中所有的點(diǎn)，，最后，在訪問方面，其目標(biāo)是訪問正方形網(wǎng)格中所有的單元。
表1總結(jié)了所得到的實(shí)驗(yàn)結(jié)果。除了兩個(gè)區(qū)域之外，我們的所有編譯都可以找到一個(gè)單獨(dú)的FSC（OC=one Controller），解決輸入中所有的規(guī)劃實(shí)例。此外，我們從相同的區(qū)域手動驗(yàn)證了FSC解決其他所有實(shí)例的結(jié)果。結(jié)果反映了早期的方法，但在Sgovia-Aguas區(qū)域，F(xiàn)SC能夠跟簡潔的儲存普遍的計(jì)劃，并且生成的FSC的速度更快。
在樹/DFS中，如簡介中所提到的，生成一個(gè)單獨(dú)的FSC——不使用遞歸細(xì)胞迭代解決問題是非常困難的。在對比中，由于編程模擬了一個(gè)調(diào)用堆棧，所以我們可以自動生成圖2中的FSC。一些編譯方面的差異如下：
? 編譯規(guī)劃問題Pn,m`的方法必須給每一個(gè)控制器狀態(tài)編譯一個(gè)場景，而圖2中的FSC包括確定性轉(zhuǎn)換。但由于f中所有的流體都是潛在條件，所以在一個(gè)靜止的流體上編譯場景等效于編程一個(gè)確定性的轉(zhuǎn)換，因此這些流體得評估結(jié)果總是一樣。
? 設(shè)計(jì)者生成的方法中，條件 leaf(n)實(shí)際上通過條件equals(n,n)進(jìn)行模仿，其中equals是衍生述語用于測試兩個(gè)變量的值是否相等。進(jìn)行該項(xiàng)工作的原因是：當(dāng)應(yīng)用到葉節(jié)點(diǎn)n時(shí)，行為copyR(n,n)在沒有增加任何其它值時(shí)刪除了當(dāng)前n的值，所以n沒有正確的分支。所以評估equals(n,n)時(shí)返回一個(gè)錯(cuò)誤，因?yàn)?，n沒有當(dāng)前值去進(jìn)行統(tǒng)一。
? 如前面所提到的，最終狀態(tài)Q4 的轉(zhuǎn)換包括多余的行為visit(child) ；設(shè)計(jì)者產(chǎn)生該行為的原因是：當(dāng)在問題中執(zhí)行FSC行為無效時(shí)，沒有有效的選項(xiàng)離開行為“blank”。
表1：控制器使用的數(shù)字，解法類型（OC=One Controller, HC=Hierarchical Controller, RP=Recursivity with Parameters），以及每一個(gè)控制器的，狀態(tài)數(shù)量，P中實(shí)例數(shù)量，規(guī)劃時(shí)間和計(jì)劃長度。
最后，在訪問時(shí)，試圖生成一個(gè)單獨(dú)的控制器用于解決所有失敗的輸入實(shí)例。進(jìn)一步說，盡管我們設(shè)置了m>1且試圖從抓取部分生成一個(gè)分層控制器，但設(shè)計(jì)者沒有在給定的時(shí)間界限中找到解決方法。相反，我們的方法逐漸的生成了一個(gè)分層FSC。我們首先生成了兩個(gè)單獨(dú)FSCs，其中第一個(gè)方法解決了子問題（通過單獨(dú)行進(jìn)行迭代），訪問了所有的細(xì)胞，而第二個(gè)方法解決了返回第一列這一子問題。我們隨后通過編程生成了一個(gè)規(guī)劃問題，其中兩個(gè)FSCs早已被編程，所以古典的計(jì)劃只需要自動生成根控制器。
6.相關(guān)工作
在自動生成FSCs方面，與以前的工作最大的不同之處是：他們利用部分觀測規(guī)劃模型，生成了單獨(dú)的FSCs。相反，我們的編程生成了分層FSCs，它能在我們認(rèn)為所有的流體可觀測時(shí)分支任何流體。我們的方法同樣使得遞歸解法變得可能，而且將原先的知識納入現(xiàn)存的FSCs，并自動完成剩余分層FSC的定義也可能行得通。
分層FSCs類似于規(guī)劃問題。程序是FSCs一個(gè)具體化的情況，通常來說，F(xiàn)SCs能夠更加完整的代表一個(gè)計(jì)劃。另一個(gè)相關(guān)的形式是自動計(jì)劃（automaton plans），同樣通過使用分層有限狀態(tài)自動機(jī)最簡單化的儲存時(shí)序計(jì)劃。然而，自動計(jì)劃是Mealy機(jī)，它的轉(zhuǎn)換取決于明確的輸入字符串 。因此自動計(jì)劃無法儲存生成計(jì)劃，并且它們的焦點(diǎn)并非簡化時(shí)序計(jì)劃。
FSCs同樣可以在規(guī)劃中代表其它的對象。Hickmott[2007]和LaValle [2006] 等人，使用FSCs代表整個(gè)規(guī)劃實(shí)例。相反，Toropila 和Bartak [2010] 使用FSCs代表實(shí)例單變量部分。Baier 和McIlraith [2006]展示了如何轉(zhuǎn)換LTL代表時(shí)間擴(kuò)展目標(biāo)，例如，在非確定性FSc中，必須堅(jiān)持一個(gè)計(jì)劃的中間狀態(tài)時(shí)。
7.總結(jié)
本文中，我們在規(guī)劃中提出了一種新形式的分層FSCs（控制器遞歸命令自己或者其它控制器），以便更簡潔的代表普遍的計(jì)劃。我們還在經(jīng)典的規(guī)劃方面介紹了一個(gè)匯編，它使得利用off-the-shelf設(shè)計(jì)者生成分層FSCs變得可能。最后我們展示了可以用漸進(jìn)的方式生成分層FSCs，以便解決更多具有挑戰(zhàn)性的普遍的規(guī)問題。
正如前期自動生成FSCs的工作一樣，當(dāng)輸入控制器狀態(tài)一個(gè)有邊界的數(shù)字時(shí)，我們就進(jìn)行匯編。進(jìn)一步說，對于分層FSCs我們指定了FSCs數(shù)字的范圍和堆棧等級。迭代深化的方法可以實(shí)現(xiàn)自動獲得這些界限。另一個(gè)問題是：以漸進(jìn)的方式，代表子問題生成分層FSCs的規(guī)范。受到“Test Driven Development”的啟發(fā)，我們相信定義子問題是是邁向自動化的一步。
最后（但同樣重要），我們遵循了歸納的方法進(jìn)行一般化，因此我們只能保證：解決方案推廣到普遍規(guī)劃問題的實(shí)例，大部分如前期計(jì)算FSCs的工作一樣。所以說，我們文章中報(bào)告的所有的控制器都是普及化的。在機(jī)器學(xué)習(xí)中，驗(yàn)證普及化問題一般都是通過統(tǒng)計(jì)和驗(yàn)證集的方式進(jìn)行的。在規(guī)劃中這是一個(gè)開放性的情況，也正是這一代相關(guān)的例子衍生了普及化的解決方法。
點(diǎn)評：
該文給出了一種新的規(guī)劃問題中分層有限狀態(tài)控制機(jī)（FSCs）的描述，這種新的FSC可以遞歸地調(diào)用它本身和其他的控制器，從而可以更加緊湊地描述更一般性的規(guī)劃問題。該方法在經(jīng)典的規(guī)劃問題中引入了一種編譯方法，使得它可以使用現(xiàn)成的規(guī)劃器來產(chǎn)生分層FSCs。最后該文還證明了分層FSC可以通過一種增量式的方式生成，這可以用來解決更具挑戰(zhàn)性的一般性規(guī)劃問題。這個(gè)方法有待完善的地方包括：這個(gè)方法還像以前的方法一樣需要指定FSC的狀態(tài)數(shù)量的界，以及分層FSC中FSC的數(shù)量界和層級的界，進(jìn)一步的研究應(yīng)該可以實(shí)現(xiàn)這些界的自動獲??；另一問題是典型子問題的的確定，這是分層FSC自動生成的重要一步。
via IJCAI2016
PS : 本文由雷鋒網(wǎng)獨(dú)家編譯，未經(jīng)許可拒絕轉(zhuǎn)載！
雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
