《武汉工程大学学报》
2013年10期
74-80
出版日期：
2013-11-10
ISSN:
1674-2869
CN:
42-1779/TQ
界标知识及其应用研究进展
0引言 “问题的结构”是人工智能研究者面对复杂问题时希望发现并利用的一类信息.这些信息通常有助于研究者设计更高效的问题求解方法.如，在命题可满足（SAT）研究领域，研究者发现了Backbone和Backdoor这两种问题结构信息［1］并设计了由该类信息引导的SAT求解算法［2］；最近，北京大学苏开乐教授和蔡少伟博士等人利用命题变量的邻域信息（Neighborhood），提出了Configuration Checking（CC）策略，并开发了基于CC策略的一系列高效算法［3\|5］，在国际上将SAT求解器的效率推到了更高的层次. 智能规划研究者近年来发现了对应于SAT中“Backbone”的问题结构信息：界标命题（Landmark Facts）和界标动作（Landmark Actions）［6\|7］，统称为界标知识（Landmark）.Landmark不仅包含一系列命题和动作，而且包含它们之间的先后顺序，它对于寻找“动作序列”的智能规划问题具有重要的研究价值，激发了研究者的深入研究.在基于搜索思想的规划方法方面，Hoffmann等人首先利用Landmark进行规划问题的子目标分解，用以提高规划算法的求解效率［7］.Helmert等人利用Landmark设计STRIPS规划问题的启发函数，开发了相应的规划系统LAMA［8］，获得了2008年“智能规划系统国际竞赛”（International Planning Competition，IPC）的冠军，随后，LAMA的改进版本LAMA\|2011又获得了2011年IPC竞赛的冠军.在基于SAT技术的规划方法方面，将Landmark编码为子句形式的约束，加速冲突信息的传播，在较大规模的问题实例上表现出了效率优势［9］.随着Landmark计算方法的不断涌现［10］，它在“动作代价不等的规划”、“时态规划”和“Conformant规划”等建模能力强于STRIPS规划的问题上产生了研究成果［11\|13］，涌现了一批求解效率更高的规划系统，值得国内外学者继续深入地研究与应用. 首先介绍Landmark的相关概念及其计算方法，之后分别介绍此类信息在STRIPS规划、动作代价不等的规划和时态规划上的应用研究成果，最后进行总结与展望.1Landmark及其计算方法 首先介绍智能规划基本概念，之后介绍Landmark及其顺序的概念，最后介绍Landmark的基本计算方法.1.1智能规划的基本概念 本文将依次介绍STRIPS规划、动作代价不等的规划和时态规划的基本概念. 定义1.规划任务（Planning Task）为四元组Π=
，其中，V是命题变量的有限集，O是动作的有限集，I是V的子集、表示初始状态，G是V的子集、表示目标条件.O中每个动作o为三元组
，其中pre(o),add(o),del(o)均为V的子集，分别表示动作o的前提、添加效果和删除效果，cost(o)为实数，表示o的代价. 状态s为V的子集，因此，状态空间为S={s|sV}.对于给定的s和o，如果动作o满足pre(o)s则称o在s上“可用”. 定义2.如果o在s上可用，则o在s上的执行结果为s/del(o)∪add(o)，记为o(s). 动作序列π的形式为
，该序列在动作s上的执行结果为on(…o1(s)…)，记为π(s). 定义3.对于规划任务Π=
，如果动作序列π满足π(I)G则称π为Π的规划解（Plan）. 为了方便论述后续内容，定义“相对于状态的规划解”. 定义4.对于规划任务Π=
，状态sV，如果动作序列π满足π(s)G则称π为“s的规划解”（s\|plan），I\|plan即为Π的规划解. 定义5.动作序列
的代价为∑ni=1cost(oi). 定义6. 意规划问题（Satisfactory Planning）要求对于给定的规划任务Π，找到一个I\|plan，或者证明不存在I\|plan. 定义7. 最优规划问题（Optimal Planning）要求为规划任务Π找到代价最小的I\|plan，或者证明I\|plan不存在. 如果在规划任务中，动作的代价都为1，则称该类规划问题为STRIPS规划问题，否则，称之为“动作代价不等的规划问题”.第10期蔡敦波，等：界标知识及其应用研究进展武汉工程大学学报第35卷1.2Landmark与Landmark顺序的基本定义 Landmark由“Landmark命题”和“Landmark动作”组成［6\|7］. 定义8. 在Π=
中，若命题f∈V在每个I\|plan执行过程中的某个时刻上为真，则称f为“Landmark命题”；如果动作o∈O存在于每个I\|plan中，则称o为“Landmark动作”. 根据定义，规划任务中I和G中的命题都是Landmark命题.此外，还存在其他的Landmark命题. 例1.设规划任务Π=
仅有两个I\|plan：π1=
，π2=
，则add(o1)中的命题都是Landmark命题，因为这些命题在两个规划执行过程中都有成立的时刻.o1为Landmark动作.此外，假如存在f∈(add(o2)∩add(o3))则f也是Landmark命题. 除了单个命题（动作）符合Landmark的含义外，命题集（动作集）也符合Landmark的含义，这些集称之为“析取型Landmark”（Disjunctive Landmark）［7］. 定义9.在Π=
中，如果命题集V′V在每个I\|plan执行过程中的某个时刻都使V′中的某个命题为真，则称V′为“析取型Landmark”命题集；如果每个I\|plan均包含动作集O′O中的至少一个动作，则称O′为“析取型Landmark”动作集. Landmark命题和Landmark动作之间存在着一些顺序关系.下面首先介绍几个基本概念，之后介绍“Landmark命题”之间的三种顺序关系［8］. 定义10. 对于Π=
，i∈{0,…,n}，给定动作序列π=
，如果命题则f∈(
(I))称f在π的第i步为真；如果f在π的第i \| 1步为假，但“在π第i步为真”，则称“f在π的第i步被添加”；如果对于j≤i-1：f在π的第j步均为假”，但f在第i步为真，则称“f在π的第i步被首次添加”. 定义11. 设f和f′为Π=
中两个命题，称f与f′具有“自然顺序”（Natural Ordering），记为f→f′，当且仅当：对于每个在I上“可用”的动作序列π，当“f′在π的第i步为真”时均有“f在π的某个第j（j < i）步为真”；称f与f′具有“必然顺序”（Necessary Ordering），记为f→nf′，当且仅当：对于每个在I上“可用”的动作序列π，当“f′在π的第i步被添加”时均有“f在π的第i\|1步为真”；称f与f′具有“首次必然顺序”（Greedy\|necessary Ordering），记为f→gnf′,当且仅当：对于每个在I上“可用”的动作序列π，当“f′在π的第i步被首次添加”时均有“f在π的第i\|1步为真”. 根据定义10，若两个命题具有“必然顺序”或者“首次必然顺序”，则它们具有“自然顺序”；如果两个命题具有“必然顺序”，则它们具有“首次必然顺序”.但反过来则不然，因此，“必然顺序”是最严格的顺序.此外，对于Landmark顺序的理解，应避免将其理解为数学中的“关系”，主要原因在于Landmark顺序不具有传递性. 例2．设规划Π=
中，O={o1,o2}，o1的具体形式为<{f},{f′},{f}>，o2的具体形式为<{f′},{f″},>，I={f}，G={f″}.显然，在I上“可用”的动作序列为π1=
和π2=
，因此，f→nf′和f′→nf″这两个顺序均存在.但是，f→nf″不存在，因为，当“f″在π2的第2步被添加”时“f在π2的第1步为真”不成立.1.3Landmark的计算方法 Landmark命题的计算问题为：给定规划任务Π=
，判定f∈V是否为“Landmark命题”.Porteous等人证明了该问题为PSPACE\|hard难题［6\|7］.因此，计算Landmark命题的实用算法均为近似算法.总体上，计算Landmark的方法主要有两种思想，一种是根据已知的Landmark通过逆向分析发现新的Landmark；另一种是基于反驳的方法：将某个命题（动作）从规划任务中暂时移除，如果该规划任务无解，则该命题（动作）必然是Landmark.下面分别介绍计算Landmark命题和Landmark动作的基本方法.1.3.1Landmark命题的计算方法Porteous等人最早提出了通过构建“松弛规划图”（Relaxed Planning Graph，RPG）和“Landmark生成树”（Landmark Generation Tree，LGT）来计算Landmark命题的方法［6］.针对具体的规划任务Π=
，该方法首先构造松弛规划图，直到目标集G中的命题均在该图中出现，然后通过LGT记录得到“候选Landmark”.LGT中的节点为“候选Landmark命题”，节点之间有向弧表示它们的“首次必然顺序”关系.“候选Landmark命题”通过如下的命题进行判定，该判定过程能由规划图算法在以动作和命题数量为参数的多项式时间内完成［6］.称此方法为LMRPG，它本质上根据命题1计算Landmark命题. 命题1［6］. 对于规划任务Π，对于f∈V，定义松弛规划问题Πf=
，其中Of={
|o∈O,fadd(o)}；如果Πf无解，则f为Landmark命题. 但是，LMRPG在某一层考察的动作集可能是全部可能动作的某个子集，因而该算法可能计算出一部分错误的Landmark顺序.Porteous等人随后提出了“首次必然顺序”的一种正确计算方法［14］.该方法的主要思想是：为了收集所有在命题f′之前可能执行的动作，将任务中以f′为添加效果的动作全部移除，之后构造规划图G直到G不发生变化.显然，G的最后一层包含所有在f′之前能成立的命题，将该集记为pb(f′)；在pb(f′)上“可用”的动作集pba(f)={o|pre(o)∈pb(f′),o∈O}必然为在f′之前实际上“可用”的动作的超集.因此，pba(f′)中动作前提的交集为正确的Landmark命题，它们与f′之间的“首次必然顺序”也正确. 为了发现更多的Landmark命题，Richter等人根据“域转移图”（Domain Transition Graph）的结构特征，提出了一种能够计算更多Landmark的方法［8］.其主要思想为：对于变量v的域转移图DTGv，如果从v在初始状态中的取值d0到Landmark命题v=d的所有路径都经过d′，则v=d′是Landmark命题.为进行此判断，该方法在DTGv中依次去除d′，之后判断从d0到d′的连通性，如果不连通，则判定v=d′为Landmark命题，并且v=d′与v=d存在“自然顺序”.1.3.2Landmark动作的计算方法Landmark动作的计算方法通常是受启发函数设计思想的引导.根据“析取型Landmark动作集”设计的启发函数的思想为［15］：假设规划任务Π有m个“析取型Landmark动作集”LA={LA1,…,LAm}，其中LA1O，则根据Landmark的定义，每个I\|plan π都至少包含LAi中的动作，即，必然有∧la∈LA(π∩la≠)，换句话说，π是LA的碰集（Hitting Set）.因此，当每个动作均具有不等代价时，LA的代价最小的碰集即为初始状态I与目标的距离的可纳估计（Admissible Estimation）［15］.为计算此类启发函数，Haslum等人提出了计算“析取型Landmark动作集”的方法［15］.2Landmark在STRIPS规划上的应用 由于Landmark及其顺序刻画了规划问题实例的结构，研究者最初利用Landmark命题顺序对规划任务的目标进行分解来降低规划问题的求解难度；近来的研究主要集中于利用Landmark设计启发函数；本文作者探索了在基于SAT的规划框架下使用Landmark的方法.2.1基于Landmark的任务分解 Hoffmann等人研究了基于Landmark将规划任务分解为规模较小的规划任务的方法［7］，用该方法引导FF规划系统［16］和LPG规划系统进行规划求解.在测试的Blocksworld域、Grid域、Logistics域和Rovers域实现了较大的效率提升，但是在FreeCell域和Depots域的性能相比FF和LPG均有下降［7］. 该分解方法的主要思想为：用LGT存储Landmark及其顺序，不断迭代地调用“底层规划器”（FF或者LPG）来实现LGT的叶子节点，直到LGT为空.在每次迭代中，首先将LGT中叶子节点对应的命题以析取目标（Disjunctive Goal）的形式输入“底层规划器”，将“底层规划器”输出的规划与上一次迭代产生的规划拼接，根据拼接后实现的命题集s′去除LGT的叶子节点，并将s′作为下一次迭代的初始状态. 在该方法中，由于每次求解的问题相当于仅包含一个目标命题的规划问题，而且上一次迭代的初始状态通常需要较少的动作即可实现LGT的叶子节点，因此“底层规划器”每次求解的规划任务较小，求解的速度较快.使用该方法后，出现整体性能下降的原因主要有两方面：1）LGT中存在不正确的Landmark顺序；2）对于结构复杂的问题，如FreeCell域，Landmark不足以反映出问题的全部结构信息.2.2基于Landmark计数的启发函数 Richter和Helmert等人使用从状态s到目标G的过程中所需要实现的Landmark的数目估计状态s与目标的距离［8］，该启发函数通常记为hLM.具体而言，对于规划任务Π中的状态s，有hLM(s,π)=|L(s,π)|=|(L\\Accepted(s,π))∪ReqAgain(s,π)| (1)其中π为从初始状态I到当前状态s的动作序列，L为该规划任务的Landmark命题集.Accepted(s,π)为从I到s过程中“已接受”的Landmark命题集，ReqAgain(s,π)为从s向目标前进过程中“仍需要”的Landmark命题集. 启发函数hLM将L(s,π)中包含的Landmark命题的数目作为状态s的目标距离估计.与以往的启发函数根据“动作数目”估计目标距离的思想不同，hLM首次使用了“命题数目”来估计目标距离.在设计思路上，hLM不仅考虑了“未接受”的Landmark命题，而且考虑了“已接受”但“还需要”的Landmark命题，包含了较丰富的信息量.在实际性能方面，以hLM为关键技术的规划系统LAMA获得了2008年IPC竞赛“满意规划”竞赛组的冠军.hLM的成功引起了智能规划领域研究者的广泛关注，随之出现了多个根据Landmark提高启发函数精度的新方法.2.3基于Landmark顺序的启发函数 在分析Landmark及其顺序与规划问题结构的基础上，改进了Helmert和Geffner等人提出的“上下文信息增强的和代价启发函数”（Context\|enhanced Additive Heuristic）hcea，提出了考虑动作前提“优先顺序约束”（Precedence Constraints）和上下文信息的启发函数hpcc［12］. 启发函数hcea是建立在“因果图”（Causal Graph）和“域转移图”（Domain Transition Graph）上的启发函数［12］.hcea在评估状态的目标距离过程中，将动作前提中的一个前提假定为“核心前提”（Pivot Condition）.动作的代价估计由“核心前提”的代价估计和其他前提相对于“核心前提”的代价估计组成.可见，对于任一动作，hcea假定“核心前提”优先于其他前提成立、其他前提之间无优先顺序.显然，hcea的假定与实际不符.在实际问题中，一个动作可以包含多个前提，其中每两个前提之间都可能存在优先顺序.但是，“如何确定这些优先顺序”是一个难题. 根据Landmark命题的顺序以及对Landmark命题的支持动作的分析，探索了“确定动作前提优先顺序”的方法.如方法中的一个规则为：对于动作o的两个前提p和q，如果q和p之间不存在Landmark顺序，但是，存在Landmark顺序f→gnq，并且添加f的所有动作都使p为假，则“先计算实现q的代价再根据该计算过程结束时变量的取值情况计算p的代价”.根据此类规则，我们为每个动作前提的代价评估确定计算顺序，定义了启发函数hpcc.实验结果表明，在许多问题上由hpcc引导的搜索算法的求解效率明显优于hcea.2.4基于Landmark顺序改进SatPlan 探索了Landmark在基于SAT的规划方法中的应用.将Landmark命题和Landmark顺序转化为子句的形式，称这些子句为“Landmark子句”.分析并证明了“Landmark子句”不能全部由常用的预处理推理过程，如“单元传播”（Unit Propagation）、“二元归结”（Binary Resolution）、或者“超归结”（Hyper Resolution）推导出，说明了“Landmark子句”相对于常用的预处理过程在逻辑上“不是”冗余的子句，进而表明了“Landmark子句”对SAT求解器的有用性［9］.根据Landmark命题及其顺序生成“Landmark子句”的方法见文献［9］.如，其中的一条规则为：若Landmark命题p和q存在顺序p→q，则对于每个时间步i∈{1...k}生成子句：qi∨pi-1∨…∨p1. “Landmark子句”对SAT求解算法的主要影响包括以下两点：1）相对于其他命题，Landmark命题受到的约束较多，在变量选择过程中或许被更早选择；2）由于“Landmark子句”的加入，约束传播的深度增加，使求解器在约束传播过程中发现冲突的频率增加，进而减少进入无用搜索区域的次数.我们在SatPlan、MiniSat和LAMA等推理工具的基础上，实现了使用Landmark子句的规划系统SatPlanLM.实验结果表明，SatPlanLM在Blocks域、OpenStacks域、Pipesworld\|notankage域、Pipesworld\|tankage域和TPP域的困难问题上，相对SatPlan有成倍的效率提高.3Landmark在动作代价不等规划上的应用针对动作代价不等的规划问题，Karpas等人首先在2009年的“人工智能国际联合大会”（IJCAI）上发表了使用Landmark设计可纳启发函数（Admissible Heuristic Function）的工作［11］.他们将动作a的代价“划分”到a能添加的Landmark命题上，使用类似LAMA的方法记录从当前状态s到目标的路径上所需要成立的Landmark命题，定义了如下的启发函数： hL(s,π)=cost(L(s,π))=∑p∈L(s,π)cost(p)(2) 将动作代价“划分”给Landmark命题的思想如下：设动作a的代价为cost(a)，记Landmark命题p的代价为cost(p)，用cost(a, p)表示a“划分”给p的代价；Landmark命题的代价通过满足如下约束条件的动作代价划分得出：a∈O:{∑p∈L(a|s,π)cost(a,p)}≤cost(a) (3)p∈L(s,π):cost(p)≤mina∈ach(p|s,π)cost(a,p) (4)其中，ach(p|s,π)是在从I执行π后的结果状态上能添加p的动作集.L(a|s,π)={p|p∈L(s,π),a∈ach(p|s,π)}表示在π的基础上执行a后能添加的Landmark命题集.hL函数通过多个代价划分函数cost(a, p)将动作的代价传播给动作可能添加的Landmark命题，从而得出Landmark命题的代价.在满足约束（3）和（4）的情况下，hL是可纳的［11］.制定代价划分函数的最简单方法是“代价均分”（Uniform Cost Sharing），令cost(a,p)=cost(a)/|L(a|s,π)|.在此基础上，使每个Landmark命题p的cost(p)取值为mina∈ach(p|s,π).除了“代价均分”方法，Karpas等人也探讨了“最优的代价划分”（Optimal Cost Sharing）以及基于“Landmark动作”信息提高划分精度所形成的hLA启发函数.实验结果表明，hLA在Logistics域、Satellite域、Blocks域、Depot域上对初始状态目标距离的估计明显优于当时精确度最好的可纳启发函数“Flexible Abstraction”；在hLA引导下，搜索算法在限定时间内成功求解的问题数目增加了22个. 在hLA提出之后，出现了许多基于Landmark设计可纳启发函数的工作.Helmert等人提出了结合图论中“切”概念和Landmark的启发函数hLM\|cut［17\|18］，Helmert和Haslum等人提出了结合图论中“碰集”概念和Landmark的启发函数.这些工作极大缩小了当前的启发函数与理想的启发函数h+的差距，Bonet等人在总结可纳启发函数相对误差时指出：未利用Landmark的可纳启发函数hmax和additive hmax相对h+的误差分别为68.5%和25.2%，而结合了Landmark的可纳启发函数hLA和hLM\|cut相对h+的误差分别提高到9.5%和2.5%.可见，Landmark对于提高可纳启发函数信息量的重要作用.4Landmark在时态规划上的应用 在时态规划问题上，探索了使用Landmark设计启发函数的方法［12］，通过扩展STRIPS规划上的启发函数hpcc，定义了适用于时态规划的启发函数htpcc.该函数在估算动作前提的实现代价过程中使用Landmark顺序预测动作前提的合理实现顺序.htpcc的计算不仅涉及预测布尔变量的合理顺序，而且需要预测布尔变量和数值变量的合理实现顺序.使用htpcc扩展了时态规划系统Temporal FastDownward（TFD），实现了“LMTD”的时态规划系统.在IPC竞赛的时态规划标准测试用例上比较了LMTD和TFD的性能，结果表明LMTD比TFD能多求解11个问题实例［19］.5总结与展望 国内研究者已经重视了对界标知识的研究，取得了一些成果.如，北京大学金芝教授指导的研究组开发了计算界标命题顺序的新方法［20］，中山大学姜云飞教授指导的课题组提出了基于目标顺序设计信息量较大启发函数的新方法［21］. 介绍了界标知识的基本概念与成果.然而，随着界标知识的相关概念与方法的发展，将能对规划问题进行更丰富的刻画，从而激发更多的应视角.如，界标命题间在时态上的距离可用于设计时态规划问题上的启发函数；界标动作的顺序结构可在基于动作序列空间的规划方法上用于构造初始节点、引导相邻节点的选择；界标知识在机器人规划［22\|23］中的应用。目前，还未发现此类方面的工作. 鉴于界标知识在“STRIPS规划”、“动作代价不等的规划”和“时态规划”上的研究成果，随着界标知识计算方法的发展、应用领域和应用角度不断扩展，其应用将取得更多、更大的成功. 致谢 衷心感谢国家自然科学基金委的资助！