titleGP基于规划图的遗传规划算法.docVIP

关于CTL与EAGLE两种规划扩展目标表示语言的语义比较( 黄巍1 姜云飞2 文中华3 彭宏1 （华南理工大学计算机科学与工程学院 广州 510641）1 （中山大学软件研究所 广州 510275）2 （湘潭大学信息工程学院 湘潭 411105）3 摘要 在不确定的智能规划领域中，CTL和EAGLE是两种重要的扩展目标表示语言。虽然与CTL相比EAGLE具有可以表示规划意图和失败处理机制的特点，但是有关严格比较这两种目标表示语言语义的研究工作还不多。本文在规划的执行结构这一语义层次上对这两种语言做了严格的比较，证明了对于许多包括原来曾被认为无法用CTL表示的EAGLE规划目标而言，都存在着一个与之语义等价CTL规划目标，并且进一步分析了这两种语言在表示规划目标和指导规划求解这两个层次上的优缺点。 关键词 不确定的智能规划; 扩展的规划目标; 执行结构; CTL; EAGLE 中图法分类号 TP18 １引言 与经典规划中的可达性目标不同，扩展的规划目标往往包含了对规划执行过程的时态要求，所以它们往往被表示成时态逻辑公式[1-2]。而在不确定的规划领域中，具有分支计算结构的CTL[3]和EAGLE[4]是目前两种重要的扩展目标表示语言。 CTL由于已被广泛应用于模型检测的领域，所以它也在基于模型检测的规划方法[5-7]中被用于表示扩展的规划目标；而EAGLE是一种专门描述扩展的规划目标的语言，它长于表示规划者的规划意图（如其语法中的TryReach和DoReach算子分别表示“尽量试着到达”和“必须保证到达”，而TryMaint和DoMaint算子则分别表示“尽量保持”和“必须保持”）以及失败处理机制（如其语法中的Fail算子表示“若(失败则(”）[4, 7, 8]。 如何选择合适的规划目标表示语言并将目标公式转化为用于指导有哪些信誉好的足球投注网站规划解的控制自动机是一个很重要的问题。因为目标语言的表达能力决定了对规划解的有哪些信誉好的足球投注网站是否可能，而由目标公式产生的控制自动机的状态数目部分决定了整个有哪些信誉好的足球投注网站空间的大小[4-5]。虽然在文献[4]和[7]中，一些用EAGLE公式（例如一些含有TryReach算子和Fail算子的EAGLE公式）表示的扩展目标被认为无法用CTL表示，但是至今有关CTL和EAGLE在语义层次上比较的研究还很少。本文在规划的执行结构这一语义层次上对这两种语言做了严格的比较，证明了对于许多EAGLE目标公式（包括了文献[4]和[7]所列举的所有不可被CTL表示的EAGLE目标公式）而言，都存在着一个与之语义等价CTL目标公式。并进一步分析指出了EAGLE与CTL相比在表示规划目标时更简洁、相应的控制自动机构造过程更简单，但是它无法表示一些基本的CTL语义特征。 下文内容安排如下：第2部介绍了有关不确定规划的基本概念，第3部分则是CTL和EAGLE目标公式严格的语法和语义定义，第4部分即本文的核心是CTL和EAGLE之间的语义比较，最后的第5部分则给出了结论以及下一步研究展望。 2不确定的规划领域与带有上下文信息的规划 所谓规划领域是指现实动态系统的抽象模型。在本文中，规划领域是指一个不确定的状态转换系统，它由系统的状态集合、动作集合以及状态转换函数构成。其中，各系统状态可以用命题公式描述，状态转换函数则描述了如何通过执行某个动作而使系统从一个状态不确定地转换到若干个不同的可能状态。 定义1(规划领域)：一个规划领域D是一个四元组(P, S, A, R(，其中： P是一个有限非空的原子命题集合， S (2P是系统的状态集合， A是一个有限的动作集合，而 R : S(A(2S是一个状态转换函数。 ■ 在后面的内容里，F(P)表示建立在原子命题集P上的命题公式集合。 对扩展目标作规划时，规划的目的已不再仅仅限于令系统能够从初始状态到达目标状态（即可达性目标），当中还可能包括了对系统的状态转换历史的具有时态性质和强度差别的要求。例如，要求一个可移动的机器人尽量试着到达某一指定位置并要求它永远避开那些危险的区域；又或者，要求机器人不断地在位置A与位置B（如果可能的话）之间来回移动。像上述这些扩展目标往往被表示成时态逻辑公式，特别是CTL公式或EAGLE公式。 为了满足扩展的规划目标，规划中须包含上下文信息（即应考虑系统的状态转换历史）。 定义2(规划)：对于一个规划领域D = (P, S, A, R(而言，它的一个规划(是一个四元组(C, c0, act, ctxt(，其中： C是一个上下文集合， c0(C是D的初始上下文， act: S(C(A为动作选择函数，而 ctxt: S(C(S(C为上下文更新函数。 ■ 在定义2中，act和ctxt的含义是：若D处于状态s下并且当前上下文为c，那么act(s,c)将返回此时规划(所