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