分层有限状态控制器也能用于一般规划了 IJCAI2016杰出论文详解

  导读：2016国际人工智能联合会议（IJCAI2016）于7月9日至7月15日举行，今年会议聚焦于人类意识的人工智能，本文是IJCAI2016杰出论文（Distinguished Papers），除了论文详解之外，我们另外邀请到哈尔滨工业大学李衍杰副教授进行点评。

  有限状态控制器（FSC）是一种紧凑地表征顺序规划的有效方式。通过在过渡上施加适当的条件，FSC 也能表征解决给定领域内的一系列的规划问题。这篇论文介绍了分层 FSC的概念，它通过允许控制器调用其它控制器来进行规划。其中证明分层 FSC 可以比个体 FSC更紧凑地表征一般规划。此外，其调用机制允许以模块化的方式生成分层 FSC，甚至应用递归方式。论文还介绍了能让经典规划者生成分层 FSC 的汇编，这能解决很有挑战性的一般规划问题。该汇编以来自特定领域的规划问题集合作为输入，然后输出一个单一经典规划问题，这种解决方案对应一个分层 FSC。

  有限状态控制器（FSCs）作为一种紧凑且有效的表达方式在AI领域中常常使用，比较突出的应用例子包括：机器人、视频游戏。在规划上，FSCs主要有两个优势：

  这种普遍适用性允许FSCs代表大型问题的解决方案，包括局部问题和非确定行为等。

  然而，即便是FSCs也存在局限性。考虑到所有的二元树的穿越节点如图1所示。针对这个任务一个典型的解决的方法包括一个行动序列（在节点的数量长度上是线性的），在树的深度上是指数型的。相反，深度优先搜索（DFS）的递归定义仅仅只要求一小部分代码。然而，一个标准的FSC不能执行递归，DFS的迭代定义更为复杂，包括一个内部的数据结构。

  在本文中我们介绍了分层有效状态控制器，它是一种创新性的表征、计算紧凑和一般规划的处理方法。我们在三个方面将标准的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开始启动。

  直观地说，通过重复分配n的右子到n本身（使用操作copyR（n，n））和以下控制器状态Q0,Q1,Q2,Q3,Q0,...，FSC的C [n的周期]具有前往树的最右边的分支的所有节点，直至到达节点的效果。此外，通过分配n的子（使用动作copyL（n，子）），使递归调用调用时，FSC C [n]被递归所有左子执行。控制器状态Q4是最终状态，动作访问（子）在过渡到Q4其实没有必要和可能被删除。然而，我们的做法是自动生成FSC，所以目前是完全按照条件和行动来。

  1.对FSCS的过渡功能的重构，允许二进制分支只为减少可能控制器的空间。

  2.规划分层FSCS一个正式的定义，允许控制器调用其他控制器，特殊情况下包括递归。

  3.新的汇编方法，针对一般规划任务能自动生成分层FSCS。汇编作为输入的一组从一个给定域规划问题，并输出单个经典规划问题，其解决方案对应于一个分层的FSC。这个输出在PDDL被表达，从而关断的，现成的经典筹办可拿来生成分级FSCS。汇编还使得可以掺入现有FSCS的形式先验知识来自动完成余下FSCS的定义。

  本节中主要定义了我们针对经典规划的模型，展示了我们过去常常定义FSCs规划的改进。

  形式上，给定一组状态（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中，特定集的触发结果是：

  给定一个规划问题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的中止执行条件。

  当前的状态是一对(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才能够解决规划问题。

  本节汇编了一个要输入的经典规划问题P = F,A,I,G，Gi和控制器状态的最大数量的约束n，并且产生作为输出一个经典规划问题的Pn。在光合操作定义，这样做才能够解决任何的Pn有计划，既产生FSC C和模拟P上C的执行，从而验证了Ç解决P.我们后来此编译扩展到广义的规划问题，FSCS的层次结构。

  转移从状态 (q,s) 依靠在s中的每个真实赋值Γ(q)，因此只允许二进制分支。设Γ(q) ∈ s是测试，其结果被解释为一个布尔值{0,1}。过渡函数被定义为

  我们继续定义Pn = {Fn,An,In,Gn}。编译背后的思想是定义两种类型的动作：对于每个控制器状态C的每个控制器状态进行编程的三个函数Γ，Λ和Φ以及设计动作，通过在当前计划状态评估模拟执行P上C的执行规划动作。

  状态集是Fn = F ∪ FT ∪ Faux，其中 FT con包含转移函数中需要编码的状态：

  改变当前控制器状态的唯一方法是将动作应用到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,nosuccand Gn = GT ∪ {csqn}.

  本节中，我们允许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语句。

  我们从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 中的流体都有复制品。

  为了在集A`n,m建立行动，我们第一步适应了An 中所有的行动——通过FSC Ci ∈ C 和堆栈等级l，0 ≤ l ≤ L的参数，加入前提 lvll 和 fsci,l，并且修改剩余的先决条件和影响。作为一个例子，我们给出了最终行动pcondf,i,lq的定义：

  相比于以前的pcondfq，现在的控制器状态是指堆栈级L，并且FTm 中的流体nocondiq condf,iq是指FSC Ci 。先决条件模型的事实——我们只可以在堆栈等级l的控制器状态q下编程函数Γi 的 Ci，，l是当前堆栈等级，Ci 正在等级l执行，等级l的当前控制器是q，Γi原先没有在q中编程。

  作为 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时的所有信息。

  证据简述。与证明定理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, succand 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。

  我们在一系列普遍规划基准和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”。

  最后，在访问时，试图生成一个单独的控制器用于解决所有失败的输入实例。进一步说，尽管我们设置了m1且试图从抓取部分生成一个分层控制器，但设计者没有在给定的时间界限中找到解决方法。相反，我们的方法逐渐的生成了一个分层FSC。我们首先生成了两个单独FSCs，其中第一个方法解决了子问题（通过单独行进行迭代），访问了所有的细胞，而第二个方法解决了返回第一列这一子问题。我们随后通过编程生成了一个规划问题，其中两个FSCs早已被编程，所以古典的计划只需要自动生成根控制器。

  在自动生成FSCs方面，与以前的工作最大的不同之处是：他们利用部分观测规划模型，生成了单独的FSCs。相反，我们的编程生成了分层FSCs，它能在我们认为所有的流体可观测时分支任何流体。我们的方法同样使得递归解法变得可能，而且将原先的知识纳入现存的FSCs，并自动完成剩余分层FSC的定义也可能行得通。

  分层FSCs类似于规划问题。程序是FSCs一个具体化的情况，通常来说，FSCs能够更加完整的代表一个计划。另一个相关的形式是自动计划（automaton plans），同样通过使用分层有限状态自动机最简单化的储存时序计划。然而，自动计划是Mealy机，它的转换取决于明确的输入字符串 。因此自动计划无法储存生成计划，并且它们的焦点并非简化时序计划。

  本文中，我们在规划中提出了一种新形式的分层FSCs（控制器递归命令自己或者其它控制器），以便更简洁的代表普遍的计划。我们还在经典的规划方面介绍了一个汇编，它使得利用off-the-shelf设计者生成分层FSCs变得可能。最后我们展示了可以用渐进的方式生成分层FSCs，以便解决更多具有挑战性的普遍的规问题。

  正如前期自动生成FSCs的工作一样，当输入控制器状态一个有边界的数字时，我们就进行汇编。进一步说，对于分层FSCs我们指定了FSCs数字的范围和堆栈等级。迭代深化的方法可以实现自动获得这些界限。另一个问题是：以渐进的方式，代表子问题生成分层FSCs的规范。受到“Test Driven Development”的启发，我们相信定义子问题是是迈向自动化的一步。

  最后（但同样重要），我们遵循了归纳的方法进行一般化，因此我们只能保证：解决方案推广到普遍规划问题的实例，大部分如前期计算FSCs的工作一样。所以说，我们文章中报告的所有的控制器都是普及化的。在机器学习中，验证普及化问题一般都是通过统计和验证集的方式进行的。在规划中这是一个开放性的情况，也正是这一代相关的例子衍生了普及化的解决方法。

  该文给出了一种新的规划问题中分层有限状态控制机（FSCs）的描述，这种新的FSC可以递归地调用它本身和其他的控制器，从而可以更加紧凑地描述更一般性的规划问题。该方法在经典的规划问题中引入了一种编译方法，使得它可以使用现成的规划器来产生分层FSCs。最后该文还证明了分层FSC能够最终靠一种增量式的方式生成，这可以用来解决更具挑战性的一般性规划问题。这个方法有待完善的地方包括：这个方法还像以前的方法一样需要指定FSC的状态数量的界，以及分层FSC中FSC的数量界和层级的界，进一步的研究应该能轻松实现这些界的自动获取；另一问题是典型子问题的的确定，这是分层FSC自动生成的重要一步。