1
| 本文作者：李尊 | 2016-07-12 19:33 |
导读：2016国际人工智能联合会议（IJCAI2016）于7月9日至7月15日举行，今年会议聚焦于人类意识的人工智能，本文是IJCAI2016杰出论文（Distinguished Papers），除了论文详解之外，我们另外邀请到哈尔滨工业大学李衍杰副教授进行点评。
联合编译：Blake、章敏
1.引言
有限状态控制器（FSCs）作为一种紧凑且有效的表达方式在AI领域中经常使用，比较突出的应用例子包括：机器人、视频游戏。在规划上，FSCs主要有两个优势：
1）紧凑的解决方案
2）能够代表一般规划解决一系列的相似计划问题
这种普遍适用性允许FSCs代表大型问题的解决方案，包括局部问题和非确定行为等。
然而，即便是FSCs也存在局限性。考虑到所有的二元树的穿越节点如图1所示。针对这个任务一个典型的处理办法包括一个行动序列（在节点的数量长度上是线性的），在树的深度上是指数型的。相反，深度优先搜索（DFS）的递归定义仅仅只要求一小部分代码。然而，一个标准的FSC不能执行递归，DFS的迭代定义更加复杂，包括一个内部的数据结构。
图1 拥有7个节点的二元树示例
在本文中我们介绍了分层有效状态控制器，它是一种创新性的表征、计算紧凑和一般规划的解决办法。我们在三个方面将标准的FSCs进行了扩展。
1． 分层FSCs能够包含多重独立的FSCs。
2． 每个FSC能够调用其他的FSCs。
3． 每个FSC都由个参数表，当一个FSC被调用时，必须调整指派给参数的变量。
作为一个特例，我们的改进通过允许一个FSC用不同的变量调用它自身来实现递归。
为了进一步解释，图2展示了分层FSC C[n]使用递归方法实现了二元树的DFS反复运动。
这里，n是控制器的单独参数和表示该二元树的当前节点。条件leaf(n)的测试n是否是leaf节点，而连字符“ - ”表示该过渡。动作visit(n)访问节点n，而copyL（n，m）和copyR（n，m）将左侧和右侧的子节点从n移到m。动作call（m）为向FSC本身的递归调用，指派控制器的唯一参数m并重新从初始节点Q0开始启动。
图2
直观地说，通过重复分配n的右子到n本身（使用操作copyR（n，n））和以下控制器状态Q0,Q1,Q2,Q3,Q0,...，FSC的C [n的周期]具有前往树的最右边的分支的所有节点，直至到达节点的效果。此外，通过分配n的子（使用动作copyL（n，子）），使递归调用调用时，FSC C [n]被递归所有左子执行。控制器状态Q4是最终状态，动作访问（子）在过渡到Q4其实没有必要和可能被删除。然而，我们的做法是自动生成FSC，所以目前是完全按照条件和行动来。
与之前有关规划的FSCs自动生成的工作对比，本文的主要贡献有：
1.对FSCS的过渡功能的重构，允许二进制分支只为了减少可能控制器的空间。
2.规划分层FSCS一个正式的定义，允许控制器调用其他控制器，特殊情况下包括递归。
3.新的汇编方法，针对一般规划任务能够自动生成分层FSCS。汇编作为输入的一组从一个给定域规划问题，并输出单个经典规划问题，其解决方案对应于一个分层的FSC。这个输出在PDDL被表达，从而关断的，现成的经典筹办可以用来生成分级FSCS。汇编还使得可以掺入现有FSCS的形式先验知识来自动完成余下FSCS的定义。
2.背景
本节中主要定义了我们针对经典规划的模型，展示了我们过去常常定义FSCs规划的改进。
2.1 有条件结果下的典型规划
我们用文字来描述状态和动作。
形式上，给定一组状态（fluents）F，文字l是状态F中的一个赋值，即l = f 或者l = ¬f 因为 f ∈ F。一组文字L代表一些状态的部分赋值（WLOG我们假设L不能分配冲突的值赋值给任何一个状态）。至于 L, 让 ¬L = {¬l : l ∈ L}作为L的补充，使得| s | =| F |，即对状态的整体赋值。
一个经典的规划问题是数组P = <F,A,I,G>，其中F是一个状态（fluents）集的，A是一组动作，I是一个初始状态，G为目标的条件，即一组文字。每个动作a∈A具有一组文字pre(a)被称为前提条件，和一组条件结果cond(a)。每个条件结果C B E ∈ cond(a)由文字组C（条件）和E（结果）组成。我们常常形容初始状态I ⊆ F是赋值（fluents）的子集是真的。
只有在pre(a) ⊆ s的情况下，行动a能够应用在状态s中，特定集的触发结果是：
即结果状态保存在s中. 将 a 应用到 s 的新结果状态即θ(s,a) = (s \ ¬eff(s,a)) ∪ eff(s,a).
计划P是一个行动序列 π = <a1,...,ani>,它包括一个状态序列<s0,s1,...,sn>。这样s0 = I, 针对每个 1 ≤ i ≤ n中的i，ai能够应用到si−1 中并且能够生成成功态si = θ(si−1,ai)。有且仅有 G ⊆ sn的情况下，计划 π 能够解答P, 即如果目标状态在应用π能够运用到 I中。
2.2 有限状态控制器
给定一个规划问题P = <F,A,I,G>， FSC被定义为一个数组C =< Q,T,q0,q⊥>，Q是一组控制器状态，T : Q × 2F → Q × A是假定能全面观测的局部转移函数，q0 ∈ Q和q⊥ ∈ Q分别为初始和终端控制器的状态。这个针对FSCS在一般规划与以前的工作相关定义如下：
•就像以前的方法（不像Mealy machines），转移不依赖于明显的输入序列，而是基于当前的规划状态。
•以前的方法采用当下规划状态的部分可观测性，定义转移函数T在Q × O，其中O是观察组。相反，我们定义T在 Q × 2F，即整个状态集。
•我们定义一个明确的中止状态q⊥，而以前的办法是在到达目标状态G终止。原因在于我们将我们将定义扩展到分层有限状态控制器，因为目标G为不一定满足终止FSCS的中止执行条件。
我们简要地描述关于规划问题P的FSC C的执行语义问题。
当前的状态是一对(q,s) ∈ Q × 2F控制态和规划态。因为(q,s)，系统转移到了(q0,s0)，其中(q0,a) = T(q,s)是在将转移函数应用到(q,s)的结果， s0 = θ(s,a)是将a应用到s中的结果。执行开始于(q0,I)并重复转移，直到达到包含终端控制器状态q⊥的(q⊥,s⊥)。
一般规划问题P = {P1,...,PT}是一组共享状态和动作的多个单体规划问题。因此每个独立规划问题Pt ∈ P被定义为Pt = <F,A,I,G>，仅有初始状态It和目标状态Gt 与P中其他规划问题不同。当且仅只有当它解决Pt ∈ P.的所有问题时，FSC C才能够解决规划问题。
3．生成有限状态控制器
本节汇编了一个需要输入的经典规划问题P = <F,A,I,G>，Gi和控制器状态的最大数量的约束n，并且产生作为输出一个经典规划问题的Pn。在光合操作定义，这样可以解决任何的Pn有计划，既产生FSC C和模拟P上C的执行，从而验证了Ç解决P.我们后来此编译扩展到广义的规划问题，FSCS的层次结构。
为了生成 FSC C = <Q,T,q0,q⊥> ，我们首先定义 Q = {q0,...,qn} 和数据集 q⊥ ≡ qn，剩下的就是构筑转移函数 T。我们的方法是减少可能存在的控制器用过定义T : Q × 2F → Q × A，并使用下面三个函数 Γ, Λ 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.
转移从状态 (q,s) 依靠在s中的每个真实赋值Γ(q)，因此只允许二进制分支。设Γ(q) ∈ s是测试，其结果被解释为一个布尔值{0,1}。过渡函数被定义为
T(q,s) = (Λ(q,Γ(q) ∈ s),Φ(q,Γ(q) ∈ s)).
我们继续定义Pn = {Fn,An,In,Gn}。编译背后的思想是定义两种类型的动作：对于每个控制器状态C的每个控制器状态进行编程的三个函数Γ，Λ和Φ以及设计动作，通过在当前计划状态评估模拟执行P上C的执行规划动作。
状态集是Fn = F ∪ FT ∪ Faux，其中 FT con包含转移函数中需要编码的状态：
•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包含以下状态：
•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.
初始状态和目标条件定义为In =I ∪{csq0}∪{nocondq,noactbq,nosuccqb : q ∈ Q,b ∈ {0,1}} 以及 Gn = G∪{csqn}. 最后，动作集An 通过以下动作替换动作A：
动作pcondfq, pactbq,a 以及psuccbq,q0 组成了三个函数 Γ, Φ 与 Λ， 与此同时 econdfq, eactbq,a 和esuccbq,q0 执行了相应的函数。Fluents EVL和应用控制了执行顺序，使得Γ总是先执行，然后是Φ，最后是Λ。
原理 1. 任何解决了Pn 的规划π 包括一个解决P的FSC C
证明简析
改变当前控制器状态的唯一方法是将动作应用到esuccbq,q0中，这首先需要编程和顺序执行功能Γ，Φ和Λ。一旦程序编辑完成，计划π就不能再改变，因为有一些中间不能再nocondq, noactbq 和nosuccbq添加状态。一旦程序编辑完成为所有状态和布尔值B∈{0,1}，三大功能Γ，Φ和Λ就共同定义了一个FSC C.
最后，行动esuccbq,q0 过渡到控制器状态q0。这种确定性将继续执行，直到我们达到最终状态(qn,sn)，或者重新审视整体的状态。如果π解决了Pn，在执行(qn,sn)和目标状态的sn中的G，这也是C解决P的定义。
我们延长了编译，以解决一般规划问题P = {P1,...,PT}。在这种情况下，以光合速率的解决方案构建了一个FSC C和模拟上的所有个人规划问题铂∈P.的扩展引入动作结束吨碳的执行。此外，初始状态和目标状态被重新定义为在= I1此外，初始状态和目标条件被重新定义为： In = I1 ∪{csq0} ∪ {nocondq,noactbq,nosucc and Gn = GT ∪ {csqn}.
4.分层最终状态控制器
本节中，我们允许FSCs命令其它的FSCs，从而拓展关于分层FSCs的FSCs公式。因此现在的FSC C是有参数的，并且可以调用C指定传递给参数C的参数。同样，我们首先描述，如何利用分层FSCs解决单一的规划问题P = <F,A,I,G>，并将这个概念推广到普遍的规划问题。
在PDDL方面，我们假设F中的流体是断言中的实例，此外，假设存在一系列的“可变对象Ωv”和一系列的“价值对象Ωx”，并且对于每一个 v ∈ Ωv 和 x ∈ Ωx，F都包含流体assignv,x ——模拟v = x类型的任务。令Fa ⊆ F 是任务流体的集，并令Fr = F \Fa是剩余的流体。
给定一个规划问题F——有着流体 Fa ⊆ F且包括一系列Ωv和 Ωx，那么分层FSC就是一个数组H = <C,C1>，其中C = {C1,...,Cm} 是FSCs在分层中的集，且C1 ∈ C 是原本的FSC。我们假设所有在FSCs中的C共享相同的控制器状态Q集，并且每一个Ci ∈ C 都有着相关的参数表——它由Ωv中变量对象ki 组成。那么可能的FSC指令集给出如下。例如所有从C中选择FSC Ci的方法和它参数所指定的参数。每一个FSC Ci的转换函数Ti定义为： Ti : Q × 2F → Q × (A ∪ Z)以便包括给C中FSCs可能下达的指令。如以前一样，我们使用函数 Γi, Λi 和 Φ代表Ti。
为了定义分层FSCH的执行语句，我们引入了一个调用栈。在原始FSC的开始执行，在状态 (q0,I)和一个0级的堆栈中，大体来说，对于FSC Ci，世界规定的(q, s) 和给定Ti(q,s) = (q’，a) 返还一个行为 a ∈ A，执行语句的解释如第2节中单体FSCs一样的。然而，当 Ti(q,s) = (q’,Cj[p])将一个指令返还给控制器Cj[p] ∈ Z时，我们将下一个等级的堆栈设置为 (q0,s[p])，其中s[p]是从s中获得的——通过复制每个p中的变量对象到 Cj中相应的对象。在下一个等级的堆栈中语句的执行伴随着转换函数Tj，，其中包括其它需要更高堆栈等级的FSC指令。如果 Tj 到达终端状态(q⊥,s⊥)，控制就会返回到根控制器Ci。具体来说，Ci的状态变成(q’,s’)，其中s’是从s⊥中获得的，通过取代在以前的堆栈级别上原来分配变量值。当在堆栈等级0达到语句状态(q⊥,s⊥)，且H 解决了P iff G ⊆ s⊥时，执行分层FSC H语句。
4.1分层最终状态控制器的扩展编译
我们从P到典型的规划问题方面，介绍了一个编译。例如解出的总数用于编程一个分层FSCH=<C，C1>，并在P上模拟执行。同样，n限制控制器状态的数量，m是C中FSC的最大数，且l限制指令堆栈的大小。流体集是其中等，对于每一个堆栈等级l，都有每一个类型流体assignv,x 的复制品。
• FTm = {fi : f ∈ FT,1 ≤ i ≤ m}，等，对于每一个FSCCi ∈ C ， FT中每一个流体都有复制品，确定其相应的转换函数体Ti，等，对于每一个堆栈等级l，Faux 中的流体都有复制品。
此外， FH包含如下额外的流体
•对于每个 l, 0 ≤ l ≤ L，包含iffl的流体lvl l是当前的堆栈等级 。
•对于每个Ci ∈ C 和 l, 0 ≤ l ≤ L，包含iff Ci 的流体fsci,l，是在堆栈等级l上正被执行的FSC。
•对于每个，流体包含iff Φi(q,b) = Cj[p]。
初始状态和目标控制转变为：
{nocondq,noactq ,nosuccq : q ∈ Q,b ∈ {0,1},Ci ∈ C} 且。换句话说，assignv,x ∈ Fa 类型的流体是堆栈等级0最初的标志，在等级0控制器状态是q0，当前堆栈等级是0，在等级0的FSC是C1，并且函数 Γi, Λi and Φi 没有被任何的 FSC Ci ∈ C执行。为了满足该目标，我们必须在堆栈等级0上达到终端状态qn。
为了在集A`n,m建立行动，我们首先适应了An 中所有的行动——通过FSC Ci ∈ C 和堆栈等级l，0 ≤ l ≤ L的参数，加入前提条件 lvll 和 fsci,l，并且修改剩余的先决条件和影响。作为一个例子，我们给出了最终行动pcondf,i,lq的定义：
pre(pcondf,i,lq ) = {lvll,fsci,l,cslq,nocond,
eff(pcond{¬nocondiq,cond.
相比于以前的pcondfq，现在的控制器状态是指堆栈级L，并且FTm 中的流体nocondiq condf,iq是指FSC Ci 。先决条件模型的事实——我们只能在堆栈等级l的控制器状态q下编程函数Γi 的 Ci，，l是当前堆栈等级，Ci 正在等级l执行，等级l的当前控制器是q，Γi原先没有在q中编程。
除了适应An的行动，同样包含如下的新行动：
作为 pactb,i,lq,a的选择，行动pcallb,i,lq,j (p)编程了一个FSC称为Cj[p]，等，定义函数如Φi(q,b) = Cj[p]。行为ecall执行该FSC命令——通过递增当前的堆等级到l+1，并且设置控制器状态等级为l+1到q0。控制影响{assignlpk,x} B {assign有效的复制等级l上的价值参数pk 以便对应参数等级l+1上Cj的参数。在终端状态 qn时，终端行动termi,l 递减堆栈等级到l-1，并删除所有关于堆栈等级l时的所有信息。
定理2
任何解决的方法 π都可以引出一个可以解决P的分层FSCH。
证据简述。与证明定理1的论据相似，方法π需要编写每一个 FSC Ci ∈ C的函数 Γi, Λi 和 Φi 。
由于新的行动pcall（p），包括了制造FSC指令的概率，所以π隐式定义了一个分层FSCH。
此外，π在P（开始于堆栈等级0的(q0,I)）上模拟执行H。作任何情况下(q, s)在堆栈等级l执行FSC Ci 时，无论该计划何时包含一个部分动序列<econd,esucc,——包含FSC指令。ecall的影响都是增加堆栈等级，导致执行进展到FSCCj的堆栈等级l+1。唯一减少堆栈等级的行动是termj,l+1，一旦termj,l+1被应用，我们便可以应用行动esuccb,i,lq,q0转换到新的控制器状态q’。
如果π解决了，执行则在等级0上终止于状态(qn,sn) ，并且目标控制包含在sn内，以满足控制H解决P。
我们注意到行动pcallb,i,lq,j (p) 可以通过设置i=j用于实现递归，使FSC Ci 命令自己。我们同样可以通过在初始状态增加condf,iq , actb,iq,a, succ and callb,iq,j(p)类型的流体 ，局部具体化FSC Ci 的函数 Γi, Λi 和Φi。通过这种方法，我们可以结合先前的知识观察一些原先存在于C中的FSCs的结构。
编译可以扩展到一个普遍的规划问题P = {P1,...,PT}类似于 Pn，具体来说endt, 1 ≤ t < T,应该有前提并且复位状态到，系统应该达到在堆栈等级0的最终状态qn ，并且在执行下一个问题Pt+1 ∈ P之前，满足Pt的目标控制Gt 。为了解决，方案需要在所有的规划问题P中模拟执行H。
5.评估
我们在一系列普遍规划基准和Bonet等人进行的编程任务中评估了我们的方法。在所有的实验中，我们都用LAMA-2011设置一个处理器Intel Core i5 3.10GHz x 4（有着4GB运行内存和3600秒的时间限制）运行古典的设计者FastDownward。
我们简要地描述了在实验中使用的每个域。在模块方面，其目标是从一个单独的塔中出栈模块，直到直到绿色的模块。在夹持器方面，目标是将一组球从一个房间运输到另一个房间。在目录方面，其目标是访问链表中所有的点。在反转方面，其目的是反转目录中的元素。在总计方面，其目标是计算的和并给输入n。在数/DFS方面，其目标是访问二进制树中所有的点，，最后，在访问方面，其目标是访问正方形网格中所有的单元。
表1总结了所得到的实验结果。除了两个区域之外，我们的所有编译都可以找到一个单独的FSC（OC=one Controller），解决输入中所有的规划实例。此外，我们从相同的区域手动验证了FSC解决其他所有实例的结果。结果反映了早期的方法，但在Sgovia-Aguas区域，FSC能够跟简洁的储存普遍的计划，并且生成的FSC的速度更快。
在树/DFS中，如简介中所提到的，生成一个单独的FSC——不使用递归细胞迭代解决问题是非常困难的。在对比中，由于编程模拟了一个调用堆栈，所以我们可以自动生成图2中的FSC。一些编译方面的差异如下：
• 编译规划问题Pn,m`的方法必须给每一个控制器状态编译一个场景，而图2中的FSC包括确定性转换。但由于f中所有的流体都是潜在条件，所以在一个静止的流体上编译场景等效于编程一个确定性的转换，因此这些流体得评估结果总是一样。
• 设计者生成的方法中，条件 leaf(n)实际上通过条件equals(n,n)进行模仿，其中equals是衍生述语用于测试两个变量的值是否相等。进行该项工作的原因是：当应用到叶节点n时，行为copyR(n,n)在没有增加任何其它值时删除了当前n的值，所以n没有正确的分支。所以评估equals(n,n)时返回一个错误，因为，n没有当前值去进行统一。
• 如前面所提到的，最终状态Q4 的转换包括多余的行为visit(child) ；设计者产生该行为的原因是：当在问题中执行FSC行为无效时，没有有效的选项离开行为“blank”。
表1：控制器使用的数字，解法类型（OC=One Controller, HC=Hierarchical Controller, RP=Recursivity with Parameters），以及每一个控制器的，状态数量，P中实例数量，规划时间和计划长度。
最后，在访问时，试图生成一个单独的控制器用于解决所有失败的输入实例。进一步说，尽管我们设置了m>1且试图从抓取部分生成一个分层控制器，但设计者没有在给定的时间界限中找到解决方法。相反，我们的方法逐渐的生成了一个分层FSC。我们首先生成了两个单独FSCs，其中第一个方法解决了子问题（通过单独行进行迭代），访问了所有的细胞，而第二个方法解决了返回第一列这一子问题。我们随后通过编程生成了一个规划问题，其中两个FSCs早已被编程，所以古典的计划只需要自动生成根控制器。
6.相关工作
在自动生成FSCs方面，与以前的工作最大的不同之处是：他们利用部分观测规划模型，生成了单独的FSCs。相反，我们的编程生成了分层FSCs，它能在我们认为所有的流体可观测时分支任何流体。我们的方法同样使得递归解法变得可能，而且将原先的知识纳入现存的FSCs，并自动完成剩余分层FSC的定义也可能行得通。
分层FSCs类似于规划问题。程序是FSCs一个具体化的情况，通常来说，FSCs能够更加完整的代表一个计划。另一个相关的形式是自动计划（automaton plans），同样通过使用分层有限状态自动机最简单化的储存时序计划。然而，自动计划是Mealy机，它的转换取决于明确的输入字符串 。因此自动计划无法储存生成计划，并且它们的焦点并非简化时序计划。
FSCs同样可以在规划中代表其它的对象。Hickmott[2007]和LaValle [2006] 等人，使用FSCs代表整个规划实例。相反，Toropila 和Bartak [2010] 使用FSCs代表实例单变量部分。Baier 和McIlraith [2006]展示了如何转换LTL代表时间扩展目标，例如，在非确定性FSc中，必须坚持一个计划的中间状态时。
7.总结
本文中，我们在规划中提出了一种新形式的分层FSCs（控制器递归命令自己或者其它控制器），以便更简洁的代表普遍的计划。我们还在经典的规划方面介绍了一个汇编，它使得利用off-the-shelf设计者生成分层FSCs变得可能。最后我们展示了可以用渐进的方式生成分层FSCs，以便解决更多具有挑战性的普遍的规问题。
正如前期自动生成FSCs的工作一样，当输入控制器状态一个有边界的数字时，我们就进行汇编。进一步说，对于分层FSCs我们指定了FSCs数字的范围和堆栈等级。迭代深化的方法可以实现自动获得这些界限。另一个问题是：以渐进的方式，代表子问题生成分层FSCs的规范。受到“Test Driven Development”的启发，我们相信定义子问题是是迈向自动化的一步。
最后（但同样重要），我们遵循了归纳的方法进行一般化，因此我们只能保证：解决方案推广到普遍规划问题的实例，大部分如前期计算FSCs的工作一样。所以说，我们文章中报告的所有的控制器都是普及化的。在机器学习中，验证普及化问题一般都是通过统计和验证集的方式进行的。在规划中这是一个开放性的情况，也正是这一代相关的例子衍生了普及化的解决方法。
点评：
该文给出了一种新的规划问题中分层有限状态控制机（FSCs）的描述，这种新的FSC可以递归地调用它本身和其他的控制器，从而可以更加紧凑地描述更一般性的规划问题。该方法在经典的规划问题中引入了一种编译方法，使得它可以使用现成的规划器来产生分层FSCs。最后该文还证明了分层FSC可以通过一种增量式的方式生成，这可以用来解决更具挑战性的一般性规划问题。这个方法有待完善的地方包括：这个方法还像以前的方法一样需要指定FSC的状态数量的界，以及分层FSC中FSC的数量界和层级的界，进一步的研究应该可以实现这些界的自动获取；另一问题是典型子问题的的确定，这是分层FSC自动生成的重要一步。
via IJCAI2016
PS : 本文由雷锋网独家编译，未经许可拒绝转载！
雷峰网原创文章，未经授权禁止转载。详情见转载须知。
