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