（计算机软件与理论专业论文）基于meagraph+planning的gui测试用例自动生成的研究.pdf

中山大学硕士学位论文 基于m e 母m p h 升a 嘲i 雌的乩l 测试用倒自动生成的研究 基于m e a g r a p hp l a n n i n g 的g u i 测试 用例自动生成的研究 专业：计算机软件与理论 硕士生：徐玉琼 指导教师：姜云飞教授 摘要 随着g u i 在人机交互中的广泛应用，g u i 的结构也越来越复杂了。这种日 益增加的复杂性使得软件的g u i 和软件本身的测试工作更加困难。 近些年来，许多研究人员已开始思考如何自动生成测试用例，其中人工智能 ( a r t i f i c i a l i n t e l l i g e n c e ，a i ) 的规划( p l a n n i n g ) 技术在生成系统测试用例方面表 现良好。其中在g u i 测试用例的自动生成方面，目前已有的方法是根据大多数 g u i 所具有的层次结构与层次规划之间的相似性，采用层次规划技术来解决这类 g u i 测试用例的生成这样一个规划问题。考虑到m e a - g r a p h p l a n ( m e 蛐s e n d s a n a l y s i sg r a p h p l a n ) 1 1 在初始状态和算子比较多，而目标状态相对比较集中时能 明显缩小规划图的搜索空间【m 1 1 】1 3 1 ，提高规划效率，所以本文提出采用m e a 图规 划( m e a - g r a p h p l a n ) 技术来自动生成g u i 测试用例。 规划器的输入是用规划语言描述的算子( o p e r a t o r s ) 和待求解的规划问题， 若有解则输出的是动作( a c t i o n s ，实例化后的算子) 序列。在实际的工程应用中， 获得规划器的输入文件和处理它的输出结果都是必须的，所以生成可用的测试用 例其实是一个复杂的任务，需要一个系统框架来指导。 本文在提出一套细致的具有实地可操作性的系统化g u i 领域建模方法( 包 括怎样提取和定义算子以及初始状态和目标状态的定义等) 基础上，从工程应用 的角度给出了一个基于规划器的测试用例自动生成系统框架t g m g s ( t e s tc a a u t o m a t e dg e n e r a t i o nb a s e do nm e a g r a p h p l a ns y s t e m ) ，并以微软的记事本 ( n o t e p a d ) 为例说明在t g m g s 框架上如何生成g u i 测试用例。 关键词：软件测试g u i 测试测试用例自动生成智能规划图规划 m e a - g r a p h p l a n 中山大学硕士学位论文3 ：m e a - g r a p hp i 姗j “g 的g u i 测试用例自动生成的研窒 r e s e a r c ho fg u it e s tc a s ea u t o m a t e dg e n e r a t i o n u s i n gm e a - g r a p hp l a n n i n g m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：x uy u q i o n g s u p e r v i s o r ：p r o f e s s o rj i a n gy n n f e i a b s t r a c t t h e w i d e s p r e a du s eo f g u i sf o ri n t e r a c t i n gw i t hs o f t w a r ei sl e a d i n gt ot h e c o n s t r u c t i o no f m o r ea n di l k ) r ec o m p l e xg u i s w i t ht h eg r o w i n gc o m p l e x i t yc o m e c h a l l e n g e si nt e s t i n gt h ee o r r e c t n e 站o f ag u la n di t su n d e r l y i n gs o f t w a r e r e c e n ty e a r s ，m a n yr e s e a r c h e r st e n dt oc o n s i d e rm a k i n gt e s tc a s ea u t o m a t i c a l l y g e n e r a t e d a n da ip l a n n i n gs e e m sag o o dc h o i c et od ot h i sk i n do f w o r k a tp r e s e n t ， h i e r a r c h i c a lp l a n n i n gm e t h o dh a sb e e nu s e di ng u it e s tc a s eg e n e r a t i o nb a s e do n g u i ss t r u c t u r e o nt h eo t h e rh a n d , m e a g r a p hp l a n n i n g sg o o dp , e r f o n m m ei n r e d u c i n gs t a t e s p a c eo f t h ep l a n - g r a p he n h a n c e st h ep l a n n i n ge f f i c i e n c y s ow et r yt o u s em e a - g r a p hp l a n n i n gi na u t o m a t i c a l l yg e n e r a t i n gt e s tc a s ef o rg u i s t h e i 1 1 p u to f ap l a n n e ri sas e to f o p e r a t o r sa n d ap r o b l e m ( i n c l u d ea l li n i t i a ls t a t e a n dag o a ls t a t e ) w h i c ha r ed e s c r i b e db yp l a n n i n gl a n g u a g e ，t h eo u t p u ti ss e q u e n c eo f t h eo p e r a t o r si f t h ep r o b l e mc a nh es o l v e d t h a ti st os a y , w en e e dt og e tt h ei n p u tf i l e o f t h ep l a n n e ra tf i r s ta n dp r o c e s st h eo u t p u ta tt h el a s tw h e na p p l y i n gi ti nt h er e a l w o r l d t h i si sac o m p l e xt a s ka n di ts h o u l db ei n s t r u c t e db ys y s t e ma r c h i t e c t u r ef o r p l a n n e r - h a s e dt e s tg e n e r a t i o n i nt h i sp a p e r , 、p r e s e n tam o r es y s t e m i ca n dd e t a i l e dm e t h o do nh o wt om o d e l t h eg u id o m a i nb a s e do i ls t u d i e so f f o r m e rr e s e a r c h e r s t h e nw ep r o p o s ea f r a m e w o r kt g m g s ( t e s tc a s ea u t o m a t e dg e n e r a t i o nb a s e do nm e a - g - r a p h p l a n s y s t e m ) f o ra p p l y i n ga ip l a n n i n gt e c h n i q u e s a tl a s t ，w er e p o r to n t h ep r o c e s so f g e n e r a t i n gt e s tc a s e sf o rm i c r o s o f t sn o t e p a dt h r o u g ht g m g s k e y w o r d s ：s o f t w a r et e s t i n g ，g u it e s t i n g ，t e s tc a s ea u t o m a t e dg e n e r a t i o n ，a i p l a n n i n g ，g r a p h p l a n ，m e a g r a p h p l a n n 中山大学硕士学位论文 基于m e a 如伯p l l 一枷堍的g u i 测试用例自动生成的研究 1 1 选题背景 第1 章引言 1 1 1软件测试自动化的趋势 从计算机这一庞大学科发展至今，它最根本的意义是解决人类手工劳动的复 杂性，成为替代人类某些重复性行为模式的最佳工具。在软件工程中也不例外， 到目前为止已有一些针对不同软件生产阶段的自动化工具，其中软件测试的自动 化已经成为软件工程领域中一个重要的课题。但同时要看到，目前软件测试的自 动化的研究和实旄主要体现在性能测试和回归测试中的测试执行过程中一一如 在回归测试中利用捕获回放工具协助开发测试脚本可供多次循环执行从而实现 自动化，但是关于测试用例的自动生成相对较少，相应能成熟应用的工具几乎没 有。 测试用例可以说是测试得以进行的根本，没有设计合理描述清晰的测试用例 不管是手工测试还是自动化测试都将无法进行。由此可以看出，测试用例设计编 写的自动化难度更大，所以发展相对缓慢。但是随着科学技术的进步和对提高测 试的效率和质量的更高要求，测试用例的自动生成是一个必然趋势；且这方面的 相关研究也在日益丰富。 由于测试人员的技术水平、认知和思考习惯不尽相同，再加上周围环境等其 他因素，在假设已经有了用例设计计划的前提下，部分测试人员编写的测试用例 质量要低于其他人的，就是同一名测试人员编写的测试用例其质量也可能有时好 有时差。这是与人的可靠性相关的研究范畴。人的可靠性可以提高，但是不可能 保证不出差错，除非是机器人。相比之下，自动生成的测试用例至少可以避免编 写过程中的人为失误，更大程度地保证了测试用例的整体质量。这也说明了测试 用例自动生成的研究和实施不仅是一种发展趋也是非常必要的。 中山大学硕士学位论文 墓丁f m e a g r a p hp l a n n i n g 的g u i 测试_ e j 例自动生成的研究 1 1 2 智能规划的广泛应用 在人工智能的研究中规划是其较早的研究领域之一，它的研究可以追朔到六 十年代：1 9 5 7 年n e w e l l 和s i m o n 的问题求解程序( g p s ) 、g r e e n 的q a 3 系统 ( 1 9 6 9 ) 1 4 】。1 9 7 1 年f i l ( e 和n i l s m n 的s t r i p s 系统【5 1 在智能规划领域中具有划 时代的意义，这使得规划可以非常容易地进行描述和操作，但由于受到当时客观 条件的制约，该领域一直处于较为保守的状态。但是由于其广泛的实用性，受到 研究者的高度重视，特别是近几年来，随着客观条件的改善，世界上特别是一些 发达国家在此领域获得了长足的发展，已经开发出来了获取和使用特定领域控制 信息的有效方法，并且有了一些实用的规划器( p l a n n e r ) ，它们能够在数分 钟内合成包括上百条动作的规划，并且在国防和空间技术领域中得以成功地应 用，取得了巨大的经济和社会效益，n a s a 于1 9 9 9 年在航天器“d e e ps p a c e o n e ”中运用规划技术，使得规划研究从实验室向实际应用迈出了重要的一步， 标志着规划的研究步入了实用阶段，智能规划已经成为人工智能领域研究的热 点。 一方面，规划问题包罗万象，不管是个人、机器还是组织，在做某一件事情 ( 或任务) 之前，一般都是先做一个或简单或详细的规划，而这样的事情( 或任 务) 是多种多样的。例如一位同学在考试之前他可能需要做一个规划：假定离考 试还有五天，他要考五门课，那么他复习的顺序可以与考试顺序相同，也可以与 考试顺序相反，或者根据考生的具体情况另行安排，制定这个考试复习计划的过 程就是一个规划的过程。 另一方面，智能规划是一个多领域交叉的研究领域，它涉及知识表达、知识 推理、非单调逻辑、情景演算、人机交互和知识挖掘等各个方面。在人工智能领 域，规划目前还没有一个统一的定义，m c d e r m o u 和j a m e sh e n d e l e r 认为“规划 就是设计某个( 组) 实体( e m i t y ) 的动作序列，其结果被称之为规划解( p l a n ) ” 嘲。d e e p a l 【k u m a r 更加形象地说“p m 衄m g = h o wd oig e t 丘d m h e r et ot h e r e ? ”。 直观地说，一个规划解实质上就是一个动作序列，此序列能够实现某一目标，智 能规划就是设计这个动作序列的过程，也就是说它主要解决怎么样，而不解决为 什么。 2 中山大学哩主丝论文 3 = m e a - g r a p hn 舢i n g 的g u i 测试用倒自动生成的研究 1 1 3相关的研究成果 迄今为止，人工智能技术在软件工程的各个方面几乎都有应用，但同时应该 看到在自动化的软件测试中的应用还远远不够。由于某些软件系统的测试用例与 规划过程具有相似性，故一些学者研究如何采用a i 的规划技术来自动生成软件 系统的测试用例生。在已有的研究中，作为测试对象的系统包括复杂的分布式系 统【2 】【3 1 ，也有专门针对g u i l 7 】f 8 1 1 9 1o 】系统的。 测试用例是有先后次序的算子序列。这些算子可能只在特定的上下文中或特 殊的命令中才会被运算。因此，根据测试用例所要包含的算子以及它们之间的交 互过程来自动生成测试用例是复杂而不易实现的。不过，描绘和协调算子的交互 过程正是大多数人工智能( a r t i f i c i a li n t e l l i g e n c e ，a i ) 规划系统的目的所在。 测试用例包括单元测试用例、集成测试用例和系统测试用例i n 】等，在自动化 方面都有了一定研究基础，只是由于各自的特点所运用的技术也不同。其中目前 系统测试用例的自动生成的研究所采用的方法主要集中在c a s e ( c o m p u t e r - a i d e ds o f t w a r ee n g i n e e r i n g ) 工具( 如u m l 的状态图、动作图等) f 1 2 】【13 】和智能规划【1 7 l 以及两者的结合【1 4 】等方法。 1 2本文研究思路和重点 根据实际应用中软件的图形用户界面( g u i ) 系统测试用例的特点和a l p l a n n i n g 在软件工程中的广泛应用及巨大的应用潜力，在对g u i 进行领域建模的 基础上提出了一个实用的基于m e a n s - e n d sa n a l y s i s ( m e a ) 图规划器的系统框架 t g m g s ( t e s tc a s ea u t o m a t e dg e n e r a t i o nb a s e do nm e a - g r a p h p l a ns y s t e m ) 来自动 生成g u i 的测试用例。 本文所做的主要工作： ( 1 ) 对m e a 图规划做了深入细致的介绍和分析，并举例加以说明。 ( 2 ) g u i 测试用例自动生成的规划问题的领域建模，包括动作建模和问题建模； 同时用微软的记事本作为例子作了进一步说明，并用本文所采用的规划语 言类s t r i p s 进行描述。 ( 3 ) 运用基于m e a n s - e n d sa n a l y s i s 技术的图规划解决g u i 测试用例自动生成的 - f l j l 足学硕士学位论文 基于m e a o g r a p h p l a n n i n g 酐j g u i 测试用例自动生成的研究 舰划问题，并就此提出了一个系统框架t g m g s ( t e s tc a s e a u t o m a t e d g e n e r a t i o nb a s e do nm e a - g r a p h p l a ns y s t e m ) 以指导如何从g u i 的规格说明书 生成有效可用的测试用例。 ( 4 ) 在图规划器g r a p h p l a n ( b l u m & f u r s t ) 的基础上根据m e a - g r a p h p l a n 伪算 法实现了m e a g r a p h p l a n 规划器。 ( 5 )以微软的记事本为例说明在系统框架t g m g s 的指导下生成相应g u i 测试 用例的全过程，体现了该系统框架的可用性和m e a 图规划在解决此类问题 上的有用性。 本文的创新： ( 1 ) 根据g u i 的潜在状态空间大等特点，提出基于目标分析的m e a 图规划技术 来解决g u 测试用例自动生成的规划问题，能有效提高求解效率。 ( 2 ) 在总结现有的研究成果的基础上，对现实世界中的g u i 进行了系统、细致 的领域建模。 ( 3 ) 在理论与实践相结合的基础上提出了系统框架t g m g s ( t e s tc a s ea u t o m a t e d g e n e r a t i o nb a s e do nm e a g r a p h p l a ns y s t e 岫用于指导测试用例的生成，并把 生成过程创新地分为四个数据转化的阶段，清晰地呈现了系统中数据的流 动过程，直到最终数据一测试用例一的生成。 1 3本文组织结构 本文共分为六个章节，具体结构如下： 第1 章：为引言，介绍了本课题提出的由来和意义，已有的测试用例自动生 成的相关研究，本文包括的内容要点、创新之处以及文章的组织结构。 第2 章：为本文研究基于的智能规划知识背景。重点介绍了图规划和m e a 图规划技术，以及图规划语言。 第3 章：g u i 的规划领域建模，包括对象及其属性、算子、初始状态与目标 状态的建模。并以微软的记事本为例描述如何实地建模，并用类s t r i p s 描述了 算子和规划问题( 初始状态与目标状态) 。 第4 章：提出了一个基于规划器的测试用例自动生成的系统框架t g m g s ， 并就系统的设计、结构和工作流程进行了说明，并对本文采用的m e a 图规划器 4 中山大学硕士学位论文 ：基于m e a - g r a p h p l a m i n g 的g u l 测试用例自动生成的研究 的实现进行了说明。 第5 章：在系统框架t g m g s 上，以微软的记事本为例说明如何按照 t g m g s 的指导成功生成g u i 领域的测试用例的过程。 第6 章：总结与展望，对本文所阐述的内容进行了总结，并对进一步的研究 工作进行了展望。 5 巾山塑十学位论文 基r m e a g r a p hp l a 朋i “g 的g u i 测试用例自动生成的研究 第2 章智能规划相关知识 2 1智能规划与问题求解 智能规划实质上是根据仞始状态和目标状态，在可供选择的动作集中进行逻 辑推理选择，在满足一定的时间和资源约束下求解动作序列或半序的过程。它至 少包括三个部分： 初始状态，以一阶逻辑或命题逻辑等形式化语言描述。 目标状态，以一阶逻辑或命题逻辑等形式化语言描述。 动作，也称为算子，主要包括三部分：动作名称、动作前提和动作效果。 有时还需要考虑动作的丌销( c o s t ) 或占用资源的情况等。 规划也属于一类问题求解的方法，但问题求解偏重理论研究，规划旨在解决 实际问题，因此规划的理论在很多方面都进行了扩展，例如： ( 1 ) 规划领域中不同动作问的前件后件存在复杂的依赖或冲突关系，一个动作 的选取往往对整个动作序列产生牵一发而动全身的影响，因此许多规划方 法的研究都会集中在动作和互斥依赖关系的表示上。 ( 2 ) 现实问题需要规划可以产生动作的半序，即允许动作串行和并行，不只可 以从所有问题统一出发严格线性排序动作，还可以利用问题分解，独立在 子目标上产生子规划，最后对子规划进行合并。 ( 3 ) 对于某些不确定领域，规划可以执行监控，进行条件规划或重新规划。【1 5 1 2 2经典规划与非经典规划 2 2 1经典规划 智能规划研究的主要目的是建立起高效实用的智能规划系统。该系统的主要 功能可以描述为：给定问题的状态描述、对状态描述进行变换的一组操作、初始 状态和目标状态。智能规划系统能够给出从初始状态变到目标状态的一个操作序 列，其复杂性和所处的环境以及a g e n t 的功能有关。 6 中山大学硕士学位论文 _ 基t m e a - g r a p h h a r m i n g 的g u j 测试用例自动生成的研究 为了简化规划问题，传统的规划一般都做出如下假设： ( 1 ) 环境的状态的改变完全是由a g e n t 的动作的效果造成的，排除了其他可能 的影响和干扰。 ( 2 ) a g e n t 的动作的效果是完全确定的。 ( 3 a g e n t 能够感知环境和它的动作的效果。人们把具有上述假设的规划问题叫 做经典规划问题。 人们把具有上述假设的规划问题叫做经典规划问题。1 1 5 1 最初的经典规划还有一些细节的约束，例如动作执行的时间是原子时间、瞬 间完成的。但随着智能规划研究闩益具有应用性，经典规划中添加不少实用元素， 例如动作可以有瞬间动作和持续动作之分，添加时序和资源约束，具有各种目标 优化策略等。 经典规划包括半序规划、基于逻辑的规划方法、非层次规划方法以及层次规 划方法等。 2 2 2 非经典规划 从1 9 9 5 年b l u m 和f u r s t 提出图规划算法以来，与领域无关 ( d o m a i n i n d e p e n d e n t ) 的智能规划算法的效率得到了较大的提高。f 1 5 ) 现代智能规划包括图规划、基于启发式搜索的规划方法、基于逐步细化的分 层规划方法、基于约束可满足的规划方法以及基于模型检测的规划方法等，相应 的代表性规划系统见表2 1 。下一节着重介绍图规划及其改进一m c a 图规划技 术。 表2 - 1 现代智能规始系统 现代智能规划系统分类代表性规划系统 基于图规划的 g r a p h p l a n ，b l a c k b o x ，i p p ，l g p 基于启发式搜索的h s p ，f f ，m i p s 基于逐步细化的s h o p 基于约束可满足的 b l a c k b o x 基于模型检测 m l p s 7 中山大学硕士学位论文 坫r m e a - g r a p hp l a n n i n g 的g u i 测试用例自动生成的研究 2 3 图规划( g r a p h p l a n ) 方法 2 3 1图规划基础 图规划( g r a p h p l a n ) 方法是近十年来智能规划研究中发展非常快的一种方 法，它最初是哇l a v r i ml b l u m 和m e r r i c kl f u r s t 4 】提出来，而后，很多研究者在 这个基础上提出了许多改进和优化。 几个基本概念： ( 1 ) 有效( v a l i d ) 规划解 规划问题的一个有效规划解是一个动作的集合和对每一个动作发生时问的 指定。 ( 2 ) 规划图( p l a n n i n gg r a p h ) 1 1 9 规划图是包含两类节点和三类边的有向层次图。 两类节点：动作节点和命题节点。 三类边：前提条件边( p r e c o n d i t i o n e d g e s ) 、添加边( a d d e d g e s ) 和删除边 ( d e l e t e e d g e s ) 。 动作层只包括动作节点，命题层只包括命题节点，整个规划图就是动作层和 命题层交替的序列。一个命题层和它所产生的动作层组合为一个时间步t 。t 层的 动作节点a 代表动作【a 】可以在t 时间步规划，t 层的命题节点玳表命题【目作为t 层动 作的前提或t 1 层动作的效果。规划图从初始命题层增量地扩展，直到一个不动 点层( f i x e d - p o i n tl e v e l ) ，此层再扩展的每层节点和互斥关系都维持不变。t 层的 动作节点a 以前提条件边连接t 层它的前提节点，以添加边连接t + l 层的正效果节 点，以删除边连接t + l 层的负效果节点。错误! 未找到引用源。 ( 3 ) 节点的互斥【1 5 1 第i 层两个动作实例( a c t i o ni n s t a n c e ) 满足以下三者中的任意一个时，我们 称之为具有互斥关系： 后件( 效果) 不一致( i n c o n s i s t e n t ) ：一个动作的后件是另一个动作后件 的否定。 中山大学硕士学位论文基于m e 砌p i lp i ；l m i n g i 扮g u i 测试用例自动生成的研究 冲突( i n t e r f e r e n c e ) ：一个动作删除另一个动作的：散件。 竞争所需( c o m p e t i n gn e e d s ) ：两个动作具有i 1 层互斥关系的前件。 第i 层的两个命题( p r o p o s i t i o n s ) 具有互斥关系，当： 一个命题是另一个的否定或： 不致支持( i n c o n s i s t e ms u p p o r t ) ：获得此命题的所有动作( 方法) 都 具有互斥关系。 ( 4 ) 空动作( n o o p ) f 1 9 】： 命题从一个命题层到下一个命题层都保持为真，在规划图中是通过一组空动 作来实现。 国器毳塑 芝婴确瓣蚰魄m 囱棚磐”螭守睡 到自e鼬拳bi麓畦毫+s蝎带o出 图2 - i 互斥关系 2 3 2图规划流程 图规划过程可以分为规划图扩展和规划解提取两部分，这里假设规划图层的 次序记为s ( o ) 、a ( o ) 、s ( 1 ) 、a ( 1 ) 9 中山大学顾七学位论文 3 萎t m e a - g r a p hp l a n n i n g 的g u i 测试h j 例自动生成的研究 构造只有韧蛄命题 屋的搋蟊j 雷 一 ，一 把s ( i ) 层中满足 前提且不互斥的动i 作a 插到 ( i ) 层： j 插入n o - o t , 动作到 建立a “) 动作的互 斥关系链裹 规划失败 图2 - 2 图规划流 图扩展 规划结束 4 “5 ；：掌一1 卜一1 _ 一，二j ：二： 州“_ 1 ，进功作 一一一j l 一一目i ：t 图2 - 3 图规划流程一解提取 1 0 中山大学硬士堂位论文 基于m e a - g r a p hn 蝴i n g 的g u l 测试用倒自动生成的研究 2 3 - 3图扩展 图扩展阶段分为两个步骤： ( 1 ) 假设当前层为第i 层，对于每一个算子，选取所有可能的对象将算子实例化 为动作，如果当前命题层满足该动作的前提条件且前提条件不互斥，那么 将动作插入规划图的第i + l 层即动作层，同时插入空动作结点( n o - o p ) ，该结 点表示持续效果，即命题没有旌加任何动作，状态持续不变。然后插入翦 提条件的边；检查每个动作结点，根据3 1 提到的规划图的互斥关系规则， 为每个动作创建一个互斥链表，该链表记录所有与该动作互斥的动作。这 个步骤完成了第件l 层的规划图的创建，包括结点和边。 ( 2 ) 检查第i + 1 层的动作结点的增加效果( 包括无动作结点) ，把这些增加效果命 题插入到第件2 层的命题层( 无动作结点的增加效果就是前提条件) ，然后插 入增加效果或者删除效果的边，如果所有至达第i + 2 层的两个命题的动作解 两两互斥，则标记这两个命题互斥。 2 3 4 解提取 在解提取阶段，图规划从后往前递归查找一个正确的规划，如果失败，则规 划图再向下扩展一个动作层和一个命题层，重复上述查找过程。如果相邻的两个 命题层的命题和m u t e x 完全相同，则该规划无解。 2 3 5 图规划求解举例 考虑以下闯题：给睡眠中的爱人准备一个惊喜，要求把垃圾( g a r b a g e ) 带 出去，做好正餐( d t u n e r ) ，准备好一份礼物( p r e n t ) 。 表2 - 2 动作集 动作 c o o k：前件 ( c k m d - l a n d s )c a r r y：前件 ( g a r b a g e ) ：后件 ( d i n n e r ) ：后件 ( a r l d ( n o g a r b a g e ) x n c t ( c l e a n h a n d s ) ) ) w r a p ：前件 ( q u i e t ) d o l l y ：前件 ( g a r b a g e ) ：后件 ( p r e s e n o ：后件 ( a n d ( n o t ( g a r b a g e ) x n o t ( q u i e o ) ) 巾山大学硕七学位论文 3 毒t m e a - g r a p hp l a n n i n g 雕j g u i 测试用例自动生成的研究 图2 4 是上述问题的部分规划图，我们注意到：动作c a r r y 与保持g a r b a g e 的动作具有互斥关系，因为它们的后件不一致；d o l l y 与w r a p 由于冲突而具有互 斥关系；在第二层即命题层- iq u i e t 与p r e s e n t 具有互斥关系。由于在第二层已经 获得了所有的子目标，并且它们之间没有互斥关系，因此下面可以进入图规划的 第二阶段：即解提取阶段。依次考虑目标的各个子目标，对第i 层的每一个子目 标，图规划选择第i - 1 层的获得此子目标的动作a ，此处选择是一个回溯点：如 果存在多于一个的动作能够获得此目标，那么图规划为了保证其完整性必须考虑 所有的动作，如果一个动作a 与其他的已经选择的动作是一致( c o n s i s t e m ) 的，那 么图规划就继续进行其他的予目标，否则如果没有这样的选择存在，图规划就回 溯到静一个选择。当图规划找到所有的实现第i 层目标的动作后，它再把选择的 动作的前件作为子目标，依次进行，直到第零层，即初始条件为止，否则返回第 一阶段继续进行图扩展阶段。 在上面的例子中，在第二层有三个子目标： g a r b a g e 可出动作c a r r y 或d o l l y 来获得；d i n n e r 可由c o o k 来实现；p r e s e n t 可由w r a p 来包扎好。因此图规划至少 必须考虑两个动作的集合： c a r r y , c o o k ，w r a p 和 d o l l y , c o o k ，w r a p ，但是这两个集合 都不一致，因为c a r r y 和c o o k 、d o l l y 和w r a p 是互斥的，因此解提取失败，图规 划扩展规划图到第四层如图2 5 所示，然后经过解提取阶段获得规划解如图2 - 6 。 012 g a r b d e a n q u i e t | 墨i2 4 第一层扩展 1 2 中山大学硕士学位论文= 基- y m e a - g t a p hp l a 柚i n g 的g u l 测试用例自动生成的研究 23 撩二二、( 碍 uf啦。 do l 坻 。 、二j j 嬲； 岔圃；- 。? ”j jc o o k kf d 图2 - 5 第二层扩展 23 图2 - 6 规划解 4 9 8 出、 - i g ar b l 。“h 、 1 e l e a n h ) q “融、 a u l 烈， d i n n e r p r e s e n t 目前基于图规划方法的规划系统主要有美国卡耐基一梅隆( c a r n e g i e m e l l o nu n i v e r s i t y ) 的图规划器g ，哪谓咖 ( b l u m & f u r s t ) 、德国的i p p 、英国的 s t a n 、美国华盛顿大学( u n i v e r s i t yo f w a s h i n g t o n ) 的s g p ( d a n i e ls w e l d 等) 【1 射。在这里只分析b l u m 和f u r s t 的( 却助勋玎。 4=：ll 中山本学硕士学垡堡文5 i t m e a - g r a p hp l a n n i n g 酐j g u i 测试用例自动生成的研究 2 4 。1 g r a p h p 缸h 的算法要点 ( 1 ) 规划开始时：把仞始条件( i n i t i a lc o n d i t i o n s ) 作为规划图命题层的首层， 且此时规划图仅有这一层。 2 ) 图扩展：对每一个算子( o p e r a t o r ) ，比较该算子的每一种实例化 ( i n s t a n t i a t i n g ) 的前件( p r e c o n d i t i o n s ) 与当前命题层中的命题 ( p r o p o s i t i o n s ) ，如果莳件全部被满足且没有互斥( m u t e x ) ，则将该算子实 例化了之后的动作( a c t i o n ) 添加到图中，这些动作所在的图层就为动作层。 同时这些动作的后件( e f l e e t s ) 构成了规划图的下一个命题层。并将互斥的 动作记录在一个互斥表中。以上是图扩展过程中的一个步骤( s t a g e ) 。这样 反复扩展直到所有的问题目标( p r o b l e mg o a l s ) 出现在当前命题层中并且 没有互斥，跳到( 3 ) 进行解的提取。 ( 3 ) 解提取：采用后向链接策略( b a c k w a r d c h a i n i n gs t r a t e g y ) ，从问题目标出发 逐层( 1 e v e l b y 1 e v e l ) 对规划图进行搜索。如能找到一个动作集( 包括空动 作n o o p s ) 使得目标在其增加的效果( a d de f f e c t s ) 中。同时，如果由这个 动作集的前件就构成的子目标集经过t 步能到达，则问题目标经过t + l 步 就能到达。所以以这个子目标集为目标递归地进行后向搜索，直到找到有 效的规划解，退出；否则，跳到( 2 ) 。 2 4 2 g r a p h p l a n 的优化 g r a p h p l a n 规划系统的实现运用了一些优化方法，使褥她在求解过程中表现 良好。在此简要介绍一下其中的三个优化方法：准备阶段中的有用事实集( f a c t s ) ； 图扩展阶段中的逻辑推理( r e a s o n i n g ) ；解提取阶段的记忆( m e m o r i z a t i o n ) 。 确定有用事实集 如果初始条件中包含了很多不相关的事实，则相应的规划图就被无谓的扩大 了，从而影响求解效率。一种解决办法是：在图扩展之前准备工作中，从目标开 始进行后向的回溯分析，以确定哪些事实对目标是有用的哪些是无用的。这样一 来，在图扩展阶段可以只考虑有用的事实，起到缩小规划图的目的。 1 4 中山大学硕士学位论文 基- f m e a - g r a p hp i 锄i 唱的g u i 测试用例自动生成的研究 运用逻辑推理 有推理：如果经过一个非空动作( n o n - n o o pa c t i o n ) ，当前目标集中的n 个目 标任何两个都不可能同时为真( 且任何一个目标不属于初始条件) ，那么任何一 个规划至少需要n 步。采用贪婪算法可以找出任何给定目标集中满足上述推理条 件的最大子集，进而确定当前规划图需要扩展的层数。这种推理方法在解决旅行 商贩类( t r a v e l i n g s a l e s m a n - l i k e ) 问题非常有用。 m e m o r i z a t i o n 在反向搜索解的过程中，如果在时间t 的子目标被确定为无解，贝l j g r a p h p l a n 将该子目标记录下来。如果在下一次时间t 创建了子目标，首先检查该子目标是 否己被记录为无解，如果是，则直接回溯而无需继续搜索。 2 5m e a 图规划方法 2 5 1m e a n s - e n da n a l y s i s 分析方法 m e a n s - e n d sa n a l y s i s ( m e a ) 是人工智能中最古老的思想之一。n e w e l l ，s h a w 和s i m o n 在2 0 世纪5 0 年代对其进行了命名和研究。在接下来的6 0 年代末期， f i k e s ，n i l s s o n 和r 印1 1 a e l 把这种思想引入到他们的规划器s 仃i p s 中。现在m e a 仍然很受瞩目，如在规划器p r o d i g y 中也应用了这种技术。1 2 0 1 当在规划中应用m e a 时可以这样描述： 给定一个动作规范( a c t i o ns p e c i f i c a t i o n s ) 集，一个初始状态( i n i t i a ls i t u a t i o n ) 和一个目标状态( g o a l - s i t u a t i o n ) 的描述。 找到一个动作序列，使得如果从初始状态开始执行这些动作可以到达一个满 足目标的状态。 动作规范通过对一般情况下的前件( p r e c o n d i t i o n s ) 、增加表( a d d l i s t s ) 和删 除表( d e l e t e l i s t s ) 的说明定义了动作项的含义。如我们可以这样来定义动作 t a k e _ o u t ( 协x , ? 1 2 0 1 ： 。 a c t i o l l ：t a k eo u t ( ? ) 【咖 p r e c o n d i t i o n s ：i n ( ? ) 【，? b ) e x p o s e d ( ? b ) e f f e c t s ：d e l ：i i ? ) 【，? b ) a d d ：e x p o s e d ( t x ) 中山大学颀十学位论文 基7 ：m e a - g r a p hp l a 啪i n g 的g u i 测试用例自动生成的研究 也就是说，如果? ) c 在容器? b 中，并且9 b 是“暴露”在外的( 不在任何容器 里面) ，那么执行动作t a k eo u t ( ? x ，? ”的结果就是? ) 【不再在9 b 中了，而是暴 露在外了。 m e a 图规划( m e a - g r a p h p l a n ) 是在标准图规划中应用了m e a 思想的一种图 规划算法，由p a r k e r 和k a m b h a m p a t i 在1 9 9 7 年提出这个概念【1 1 。在图规划中运 用m e a 的思想，其根本目的还是使图规划具有面向目标的特性，从而提高问题 求解的效率。m e a - g r a p h p l a n 的伪算法3 1 如图2 7 所示。 m e a g r a p h p l a n 与标准图规划算法相比有以下特点( 其中( 1 ) ( 2 ) 是 m e a g r a p h p l a n 所特有的预处理过程) ： ( 1 ) 生成回溯匹配图( g e n e r a t er e g r e s s i o n - m a t c h i n gg r a p h ) 通过对各个目标的回溯，直到初始条件全部出现在命题层中。 ( 2 ) 确定各层动作集( d e t e r m i n er e l e v a n ta c t i o n - s e t ) 根据上述回溯匹配图，记录每个动作层所对应的动作集。实现时，可以采用 二维数组来存储，一维记录层数，一维记录动作。 ( 3 ) 正向扩展规划图 从初始目标开始正向生成规划图，m e a - c j r a p h r l a n 算法仅考虑当前层所对应 的动作( 依据上述第二步的记录结果) ；g r a p h p l a n 则要考虑所有的动作。 ( 4 ) 提取解 当找不到解时，m e a - g r a p h l f l a n 算法先把当前规划图最后的命题层作为新的 初始条件，在已有的回溯匹配图的基础上继续回溯直到达到这个新的初始条件， 同时确定新增动作层的分别包含的动作，然后重新生成正向规划图；g r a p h ! ：，l a n 则是在原来规划图的基础上继续扩展。 1 6 中山大学硕士学位论文 基- t m e a - g r a p hp l a n n i n g 的g u i 测试用斜自动生成的研究 l o o p g e n e r a t er e g r e s s i o n - m a t c h i n gg r a p h ： c