（计算机软件与理论专业论文）基于mea图规划的手机软件gui自动化测试的研究.pdf

基于m e a 图规划的手机软件g u i 自动化测试的研究 摘要 论文题目： 专业： 硕士生： 指导教师： 基于m e a 图规划的手机软件g t j i 自动化测试的研究 计算机软件与理论 林义钦 姜云飞教授 摘要 手机自发明以来，行业的快速发展已经使得手机已经超出了传统通讯工具的 限制，如现在可以用手机浏览网页，收发邮件，g p s 等。手机软件的发展使得测 试变的越来越棘手，这就成为了一个值得研究的重要课题。目前工程上对手机软 件的测试还多局限于手工测试，自动化的程度非常低，耗费大量的人力和时间， 使得手机软件测试成为网络通信业的主要瓶颈之一。如今，针对手机的软件工程 理论与技术也是国内外开始着手研究的热点问题，然而手机软件g u i 自动化测 试的研究相对还比较少，资源也相对贫乏，更重要是手机软件g u i 手工测试已 经无法满足测试要求，因此，针对手机软件g u i 自动化测试进行研究具有重要 的现实意义。针对手机软件的测试来说，测试过程的自动化是保证测试质量进而 保证产品质量和可靠性的重要途径，一个专门为手机而设计的合理的自动化测试 框架对测试自动化的实现起着决定性的作用。 针对这种现状，本文在分析总结现有的研究成果的基础上，对手机软件g 的自动化测试进行研究。针对手机软件g u i 自动化测试研究比较少的现状，对 手机软件中的g u i 进行了细致的、系统的领域建模，为了简化算子建模在手机 软件上的应用，本文简化了算子的分类：将抽象算子和系统交互算子合并为逻辑 算子。逻辑算子建模即是以功能逻辑为单位来对动作进行建模。与此同时，本文 还将人工智能领域的智能规划m e a 图规划( m e ag r a p hp l a n n i n g ) 跟本文所提 出的基于手机数据线的测试框架p p t f ( p c p h o n et e s t i n gf r a m e w o r k ) 结合起来， 提出一套完整的、具有实践性特色的、带有手机领域特点的自动化测试框架。在 本文的框架p p t f 中，首先采用了基于m e a 图规划的领域建模技术对手机软件 g u i 进行建模，测试框架p p t f 便可由建模输入得到最后的测试结果的输出，也 就是说，p p t f 测试框架实现了从g u i 说明书和测试规格说明书到最后测试结果 论文题目摘要 的全部流程。与经典图规划相比，使用基于目标分析的m e a 图规划技术来解决 手机软件g u i 测试用例自动生成的规划问题，能有效提高求解效率。最后，本 文通过具体的测试案例，验证了p p t f 框架具有一定的自动化能力和可用性。 关键词：手机软件g u i 、m e a 图规划、自动化测试 基于m e a 图规划的手机软件g u i 自动化测试的研究a b s t r a c t t i t l e ：t h er e s e a r c ho na u t o m a t i o nt e s t i n go fm o b i l es o f t w a r eu s e ri n t e r f a c e s b yu 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 ：l i n y i q i n s u p e r v i s o r ：p r o f e s s o rj i a n gy u n f e i a b s t r a c t s i n c et h ei n v e n t i o no fm o b i l ep h o n e ，r a p i dd e v e l o p m e n to f t h ei n d u s t r yh a sm a d e m o b i l ep h o n e se x c e e dt h el i m i t so ft r a d i t i o n a lc o m m u n i c a t i o n st o o l s n o wm o b i l e p h o n e sc a nb r o w s et h ew e b ，s e n da n dr e c e i v ee - m a i l , d e a lw i t hg p sa n ds o o n m o b i l es o f t w a r ed e v e l o p m e n tm a k e st e s t i n gb em u c hm o r ed i f f i c u l t ，a n dt h et e s t i n g h a sb e c o m ea ni m p o r t a n ti s s u et ob es t u d i e d c u r r e n t l yt e s t i n go nm o b i l es o f t w a r ei s j u s tam a n u a lj o b b u ta sw ea l lk n o w , m a n u a lt e s t i n gi sv e r yl i m i t e d ，a l s oi st i e du pa g r e a td e a lo fm a n p o w e ra n dt i m ec o n s u m i n g a l lt h e s em a k em o b i l ep h o n et e s t i n ga s o n eo ft h em a j o rb o t t l e n e c k si nt e l e c o m m u n i c a t i o n s n o w , f o rt h em o b i l ep h o n e s o f t w a r ee n g i n e e r i n gt h e o r ya n dt e c h n o l o g yb e g i nt ob eah o ti s s u ea th o m ea n d a b r o a d b u tt h ec e l lp h o n es o f t w a r eg u ia u t o m a t e dt e s t i n gi ss t i l lr e l a t i v e l ys c a r c e ， r e l a t i v e l yl a c ko fr e s o u r c e s ，m o r ei m p o r t a n t l y , m o b i l eg u is o f b , v a r et e s t i n gi sn o w u n a b l et om e e tt h em a n u a lt e s t i n gr e q u i r e m e n t s t h e r e f o r e ，t h er e s e a r c ho fs o f t w a r e g u it e s ta u t o m a t i o nf o rm o b i l ep h o n eh a si m p o r t a n tp r a c t i c a ls i g n i f i c a n c e f o rt h e t e s t i n go fm o b i l ep h o n es o f t w a r e ，t h et e s t i n gp r o c e s si sa l li m p o r t a n tw a y t oe n s u r e p r o d u c tq u a l i t ya n dr e l i a b i l i t y s oap h o n eo r i e n t e dt e s t i n gf r a m e w o r ki sp l a y i n g ac r u c i a lr o l eo nt h et e s t i n gi s s u e c o n s i d e r i n go ft h i ss i t u a t i o n , t h i sp a p e ra n a l y z e sa n ds u m m a r i z e se x i s t i n g r e s e a r c ht o s t u d ya u t o m a t i cg u it e s t i n gp r o b l e m s i nc o g n i z a n c eo fs u c hf e w r e s e a r c h e sr e l a t i v e l yo nt h i s s u b j e c t ，t h i sp a p e rm a k e sac a r e f u l l y , s y s t e m a t i c m o d e l i n gi nt h i sd o m a i no fm o b i l es o f t w a r eg u i i no r d e rt os i m p l i f yt h eu t i l i t yo f o p e r a t o rm o d e l i n go nm o b i l ea p p l i c a t i o n , t h i sp a p e rs i m p l i f i e st h ec l a s s i f i c a t i o no f i i i 基于m e a 图规划的手机软件g u i 自动化测试的研究 a b s t r a c t o p e r a t o r s ：c o m b i n e t h ea b s t r a c to p e r a t o r sa n ds y s t e mi n t e r a c t i o no p e r a t o r si n t o l o g i c a lo p e r a t o r s t h el o g i c a lo p e r a t o r sa r eas u c ho p e r a t o r st h a tt h ew h o l el o g i c f u n c t i o n a lu n i t sa r em o d e l e di l lj u s to n eo p e r a t o r a tt h es a m et i m e ，t h i sa r t i c l e c o n n e c t sm e ag r a p hp l a n n i n gw h i c hi sab r a n c ho fa r t i f i c i a li n t e l l i g e n c ew i t ht h e d a t a l i n e b a s e dt e s t i n gf r a m e w o r kf o rm o b i l es o f t w a r et e s t i n gf r a m e w o r kp y r f ( p c - p h o n e t e s t i n gf r a m e w o r k ) t o b u i l d s y s t e m a t i c ，p r a c t i c a l a n d m o b i l e - d o m a i n - c h a r a c t e r i s t i ca u t o m a t i ct e s t i n gf r a m e w o r k i nt h e 丘a h l e w o r ko ft h e p p t f , i i lt h ef i r s tp l a c e ，t h ep a p e ru s e sm e ag r a p hp l a n n i n gm o d e l i n gt e c h n i q u e st o m o d e ls o f t w a r eo nt h em o b i l es o f t w a r eg u i s t h e na u t o m a t i ct e s t i n gf r a m e w o r k p p t fc a nf m a l l yo u t p u tt h et e s tr e s u l t sw i t ht h ei n p u to ft h em o d e l i n gr e s u l t s t h a t s t os a y , p p t ft e s t i n gf f a m e w o r kr u n sa l lt h et e s t i n gp r o c e s s e sf r o mg u ia n dt e s t i n g s p e c i f i c a t i o n st ot h ef i n a lt e s tr e s u l t s c o m p a r i n gw i t ht h ec l a s s i co fg r a p hp l a n n i n g ， i tc a nh ee f f e c t i v e l yi m p r o v es o l u t i o ne f f i c i e n c yi 1 1t e s tc a s eg e n e r a t i o nw i t ht h e g o a l - o r i e n t e da n a l y s i so ft h em e ag r a p hp l a n n i n ga n dt h er e l a t i v et e c h n o l o g y f i n a l l y , s o m es p e c i f i ct e s tc a s e ss h o ws o m eu s e f u l n e s sa n da u t o m a t i c i t yo ft h e a u t o m a t i ct e s t i n gf r a m e w o r k k e yw o r d s ：m o b i l es o f t w a r eg r a p h i cu s e ri n t e r f a c e s ，m e ag r a p hp l a n n i n g ， a u t o m a t i ct e s t i n g i v 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均己在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：盈塞圭墨 日期： 笔f 芝毒垂旦! 旦 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名：群又钦 日期：z o l o 年月夕日 基于m e a 图规划的手机软件g u i 自动化测试的研究第i 章引言 1 1 选题背景与意义 第1 章引言 手机作为移动通信行业的主要的载体，无疑是移动网络的非常重要的环节， 直到现在，手机行业的进展还一直制约着移动产业的发展。中国作为全球人口最 多的国家，移动用户的数量也已经遥遥领先于其他国家，毫无疑问，中国移动终 端市场的潜力是非常巨大的。但是，研发能力不足，运用测试技术，特别是利用 自动化测试技术来提高产品品质和竞争力的能力低下，使得终端上的高质量的软 件数量不多。在逐步步入移动互联网的今天，面对海量的手机终端软件，对软件 g u i 的测试成为了系统测试的重点之一。 软件测试贯穿了整个软件的生命周期。通俗的讲，i e e e 将软件测试定义为 使用人工或自动手段来运行或测试某个系统的过程，其目的在于检验开发的产品 是否满足需求【1 1 。具体的，i e e e 定义软件测试分为以下2 个方面【2 】： 1 ) 使用人工或自动的手段来运行或测量软件系统的过程，目的是检验软件 系统是否满足规定的要求，并找出与预期结果之间的差异。 2 ) 软件测试是- - ! 7 需要经过设计、开发和维护等完整阶段的软件工程。 测试并不仅仅是为了找出错误，通过分析错误产生的原因和错误的发生趋 势，可以帮助项目管理者发现当前软件开发过程中的缺陷，以便及时改进【3 】，因 此，测试的有效性是软件质量保证的重要手段。近几年，随着以敏捷开发模式为 代表的各种快速开发模式的日益盛行，软件的开发周期( 即分析、设计、编码、 测试) 大大缩短，导致软件测试逐渐成为影响软件生命周期长短的重要因素。很 长一段时间以来，手机软件的测试工作基本都是由手工完成的。然而手工测试中 人工干预较大，不可控因素较多( 甚至个人的疏忽会导致测试的失败) ，导致测 试效果参差不齐，测试效果不理想。测试中如果全部采用手工测试方法，则需要 付出大量的时间和人力来保证测试的有效性，会大大增长软件的生命周期，加大 软件的成本，因此，如何提高测试的效率和效果成为软件测试领域中急需解决的 问题之，自动化测试理论、方法和测试实现工具都是测试领域中研究的重点和 基于m e a 图规划的手机软件g u i 自动化测试的研究第1 章引言 热点。 手机操作系统是实时嵌入式系统，手机软件的测试也属于实时嵌入式系统的 测试范围。实时嵌入式系统是计算机操作系统的重要分支之一，它具有普通操作 系统没有具备的新特性，这些特性又决定了实时嵌入式操作系统的测试技术与传 统操作系统的测试有比较大的不同。实时嵌入式软件的测试有3 个明显的特征： 实时性、嵌入性和反应性【4 1 。 手机软件的开发和测试是一项复杂的工程，既有嵌入式的系统的规律又有手 机自身的特点，由手机运行环境的特殊性，很多测试用例是很难满足和重现的。 合理有效的测试理论技术有助于优化和改进测试过程，对产品品质和性能的提升 也有不可忽略的重要作用。与一般软件相比，手机软件的特殊性表现为以下几个 方面： 1 ) 实时性强【1 5 j 手机系统作为实时系统，要求系统对外部事件做出及时的响应，与手机 通信相关的软件一般就要求很强的实时性，比如，无论你手机现在运行 什么软件，手机都必须在一定时间内( 一般是3 0 0 m s ) 响应对方打来的 电话。 2 ) 可靠性强 排开网络的原因，假如手机通话经常断线，可以断定这样的手机肯定适 应不了当今社会的需求。 3 ) 电力要求强 手机软件应该充分考虑电力因素，很显然耗电量惊人的软件也很难取得 成功，毕竟手机是便携设备。 手机软件是实时的，可靠性要求高的，具有生命周期长，运行不问断的等特 点。由于手机具有其上特点，因此对于手机软件的测试将比一般软件进行更加严 格的测试，只有这样才能达到手机软件本身应用的要求。 2 基于m e a 图规划的手机软件g u i 自动化测试的研究第1 章引言 1 2 研究现状 随着计算机日益广泛的应用，传统的手工测试已经远远不能满足当今软件的 测试要求。软件测试的自动化已经成为软件测试发展的趋势，它能完成许多手工 测试无法实现或者是难以实现的测试要求。软件自动化测试技术所谓自动化测试 是希望通过自动化工具或其它手段，按照预定的测试要求进行自动化测试，目的 是减轻手工测试的劳动量和提高测试的有效性，从而达到提高软件质量的目的 f 5 】 o 无论是在工业部门，还是在其它各类消费品的生产线上，自动化测试技术都 有着非常广泛的应用，有着不同的运行模式【1 6 】，如感应器模型、数据库模型和 g u i 设计模型等，但总的趋势都是向通用可移植和自动化发展。由于通用性的原 因，测试人员不需要知道产品内部的细节，通用测试系统降低了测试人员的要求。 近些年来，通用自动化测试系统的开发已经成为主流。 软件的可移植性和操作的可互换性是自动化测试系统实现通用性的重要方 面。为了实现软件的上述功能，必须建立标准的软件接口。软件接口标准化的研 究是实现自动化测试通用性的关键技术，也是实现软件通用性的关键技术【6 】。 目前，关于自动化测试的研究主要集中在测试用例的自动化生成、测试用例 的自动化执行以及测试用例执行结果的自动化检验这几个方面。虽然完整的软件 测试流程还包括测试覆盖标准的选取、测试用例规范的设计等等步骤，但是这些 步骤都主要是生成一些相应的测试规范，人的主观性因素较大，自动化可行性不 高。而测试用例的生成、执行、结果的检验这些步骤上重复劳动的成分较大，且 自动化可能性比较大，故它们是自动化测试研究的重点。 图形化用户界面g u i 在8 0 年代末9 0 年代初被提出，如今已经被广泛应用 于各种类型的软件系统中，手机软件的g u i 也就是其应用之一。有学者提出给 予截图的手机软件g u i 自动化测试【3 1 1 ，还有学者利用脚本执行环境来搭建手机 测试框架f 3 2 】。一般来讲，g u i 测试作为回归测试，一般有如下几个测试阶段【1 1 ： 1 ) 确定测试目标【3 2 】。在g u i 测试的第一个阶段，首先要决定测试目标， 也就是要测试什么，即决定对哪些g u i 事件或事件序列进行测试。 2 )生成测试输入【3 2 1 。g u i 测试输入可以参照软件的规格说明数或软件的 基于m e a 图规划的手机软件g u i 自动化测试的研究第l 章引言 结构等其他软件文档，由初始条件和事件序列构成。 3 )生成预期输出【3 2 1 。对应测试输入中事件序列的每个事件，生成每个事 件执行后的预期结果。 4 ) 测试的执行及验证【3 2 1 。在测试输入的初始条件下，顺序执行事件序列 中的事件，并对比每个事件的预期输出与实际输出。当两者出现不匹配 的情况时，表示当前测试不能通过，反之则通过。 5 ) 判断测试的充分性【3 2 】。在执行了部分或全部的测试后，分析所有测试执 行情况，判断是否达到预期的要求。 6 )回归测试【3 2 1 。当程序变更后，针对g u i 的变化情况，选择部分的测试 用例或重新生成新的测试用例对更改部分进行重新测试。 目前，g u i 自动化测试，特别的，自动化测试技术中的测试用例自动生成技 术是国外自动化研究的热点，如今越来越多成熟的理论被应用到自动化测试领 域，其中包括人工智能中的智能规划( 比如图规划等) 。 1 3 课题研究内容与本文创新点 虽然手机的使用已经相当普遍，手机软件数量更是呈现爆炸式增长，但是目 前专门针对收件软件g u i 自动化测试的理论研究几乎没有。考虑到手机软件g u i 本质上是g u i 在手机上的一种应用形式，具备了g u i 的典型特征，因此，本课 题的研究思路是从g u i 自动化测试理论入手，分析目前较为常用的g u i 自动化 测试理论，从中提取出适合映射到手机软件g u i 测试领域中的测试理论作为指 导依据，来指导具有手机软件g u i 领域特色的自动化测试体系的研究。 本文提出了一套手机软件领域的自动化测试框架，框架中，首先采用了领域 建模技术对手机软件g u i 进行建模，接着，使用m e a 图规划技术自动生成测试 用例，最后，搭建基于p c 和手机的一个测试框架，来执行已经自动生成好的测 试用例，并检验测试结果。本文设计并实现了一个基于上述框架的手机软件g u i 自动化测试系统，通过试验对系统自动生成的测试用例的准确性和应用性等各方 面做出了评估。 4 基于m e a 图规划的手机软件g u i 自动化测试的研究第l 章引言 本文的创新点在于： 1 ) 在分析总结现有的研究成果的基础上，对手机软件中的g u i 进行了细致 的、系统的领域建模。针对手机领域的特点，提出了适合手机软件g u i 领域建 模的逻辑算子的概念，逻辑算子简化了对算子的分类，能有效提高手工部分( 主 要是建模阶段) 的工作效率。 2 ) 提出基于目标分析的m e a 图规划技术来解决手机软件g u i 测试用例自 动生成的规划问题，能有效提高求解效率。并使实现p c p h o n e 架构的测试框架 p p t f ，从实践应用的角度阐述了从软件的g u i 规格说明书和测试规格说明书到 生成可供自动执行的测试用例，再到执行测试用例后返回测试结果的整个过程， 具有比较强的工程实践特色。 1 4 论文组织结构 全文共分为五个章节，具体组织如下： 第1 章：介绍了课题研究的背景和研究现状，分析阐述了课题研究的意义， 并指出了本文的研究内容和创新点。 第2 章：介绍了智能规划背景知识，重点介绍了图规划和引入m e a 思想的 图规划技术，并分别用实际生活中的例子来展示它们具体的规划过程。 第3 章：介绍了手机软件g u i 领域建模技术，涉及到对象与属性的建模和 动作的建模，并通过实例详细描述建模的具体过程。 第4 章：介绍了本文提出的p p t f 测试框架，进而展示了p p t f 的工作流程， 最后详细介绍了在p p t f 上生成测试用例的步骤，并用现实中的例子来演示生成 的过程。 第5 章：对全文进行了归纳和总结，并对以后的研究方向提出展望。 5 基于m e a 图规划的手机软件g u i 自动化测试的研究第2 章m e a 图规划相关知识 第2 章m e a 图规划相关知识 图规划( g r a p h p l a n ) 方法是进十年来智能规划领域中发展最为迅速的一种 方法，它最初由a w i mb l u m ，m e r r i c kf u r s t 和j o h nl a n g f o r d f 7 】提出，而后又有许 多研究在此基础上进行了许多改进和优化。本文关于图规划的部分参考了a w i m 和m e r r i c k 所著的文献 8 】。 2 1 图规划 2 1 1s t r i p s 算子【9 1 由f i k e s 和n i l s s o n 9 1 于1 9 7 1 年开发的智能规划系统s t r i p s 中提出的一种算 子，由于该算子在表达动作方面具有很好的适用性，后来的很多规划系统都采用 了类s t r i p s 风格的算子。 一个s t r i p s 算子由3 部分组成： 1 ) 集合p ，算子的前提条件( p r e c o n d i t i o n s ) 。也就是只有当p 中的所有文 字出现在状态中时，才能执行相应动作。 2 ) 集合d ，删除列表( d e l e t el i s t ) 。 3 ) 集合a ，添加列表( a d dl i s t ) 。 2 1 2 有效( v a l i d ) 规划解【1 8 】 规划问题的一个有效规划解是一个动作的集合和对每一个动作执行时间的指 定。 2 1 3 规划图( p l a n n i n gg r a p h ) 0 8 1 3 4 】 规划图是一个具有2 类节点和3 类边的有向、分层图。规划图中命题层 ( p r o p o s i t i o nl e v e l s ) 和动作层( a c t i o nl e v e l s ) 是交替出现的，命题层包含命题节点 ( 标识为一些命题) ，动作层包含动作节点( 标识为动作) 。规划图的第一层是命 题层，第二层为动作层，以此类推，规划图的第一层包括规划问题初始条件下的 所有命题。 7 基于m e a 图规划的手机软件g u i 自动化测试的研究第2 章m e a 图规划相关知识 2 1 4 空动作( n o - o p e r a t i o n ) 命题从一个命题层到下一个命题层都保持为真，在规划图中是以一组空动作 ( n o o p e r a t i o n ) 来实现的。 2 1 5 节点的互斥【8 】【1 1 1 b l u m 和f u r s t 定义了规划图中节点的两元互斥关系，如图2 1 所示： 1 第n 层两个动作实例( a c t i o ni n s t a n c e ) 满足以下三者中的任意一个时，我们 称之为具有互斥关系： 1 ) 后件( 效果) 不一致( i n c o n s i s t e n t ) ：一个动作的后件是另一个动作后 件的否定。 2 ) 冲突( i n t e r f e r e n c e ) ：一个动作删除另一个动作的前件。 3 ) 竞争所需( c o m p e t i n gn e e d s ) ：两个动作具有n 1 层互斥关系的前件。 2 第n 层的两个命题( p r o p o s i t i o n s ) 具有互斥关系，当： 1 ) 一个命题是另一个的否定或： 2 ) 不一致支持( i n c o n s i s t e n ts u p p o r t ) ：获得此命题的所有动作( 方法) 都具 o j n e o m i s l e m 目t e c t s 有互斥关系。 o 鞫e , 菠o t ) o 蝥 g o r n p e l i n g n e e d a 图2 1 节点互斥关系图 i r e o n s i 匐e n l 5 t 印o l l 2 1 6 图规划 一个基本的规划问题是一个三元p 值( o ，s o ，g ) t 9 1 ，其中0 是所有算子的 集合，初始s o 代表着初始状态，g 代表着目标状态( 形式化来表示的目标) 。任 何规划都可以表示如下： p l a n n i n g = ，其中a i 都是算子0 的一个实例。几乎所有的人工 智能规划程序是搜索程序，不同的规划程序有不同的搜索空间。 图规划及其扩展算法【8 】【2 7 1 是两个阶段交替进行的过程，即：图扩展阶段和解 8 ) 慕 基于m e a 图规划的手机软件g u i 自动化测试的研究第2 章m e a 图规划相关知识 提取阶段。在图的扩张阶段，规划图在时间上向前延伸，直到它已取得了必要的 条件约束的解。在解提取阶段，在规划图上执行一个向后的搜索 ( b a c k w a r d s e a r c h i n g ) ，寻找一个( 当然可以根据自己的需要变为多个) 能够满 足目标的有效的规划解。如果没有找到规划解，则继续扩展规划图，然后再反向 提取规划解，直到找到规划解或达到l e v e lo f f 状态。该规划图是有两种节点的定 向分层图，节点包括命题节点和动作节点，命题层和动作层交替出现。如图2 2 所示，偶数层次的节点为命题层节点，奇数层次的节点为动作层节点，动作节点 由上一层的命题节点存在决定( 节点之间要相互一致，没有互斥) ，而在最初始 阶段的o 阶段，代表着规划的初始条件。图2 2 的实线条连接命题节点和动作节 点，两命题节点之间由动作节点连接着，代表着动作前的命题经过执行此动作后 转变为了动作后的命题。直接连接两个命题的实线代表着执行了空动作( n o o p ) 。 0i lii + l ! 。i !i 。_ - 。，。- - 。1 ：一! ：l r “8 。“。_ 。“。一三。“ 二j 1 1 ：= ：= = ：一。：”。 图2 2 图规划节点示意图 在规划图在规划过程中，将显式的在节点之间构造互斥关系。此外，一个有 效的规划在相同的动作层是不存在互斥关系的，每个动作的先决条件是规划图中 为真的命题( 也就是没有被规划解中这个层次的其他动作删除的节点) ，并且满 足了所有的目表。如果没有提取到规划解，那么该规划图及其扩展状态的终止条 件是当两个远期规划图的相邻命题水平是相同的，即它们包含同组命题，并具 有同样的排他性关系，则规划的图已趋于稳定，算法终止。 在规划空间规划( p l a n - s p a c ep l a n n i n g ) 1 2 0 2 1 】，其为偏序规划，并且有一组 限制条件。它也被称为偏序规划或至少承诺规划，它也是健全和完善。还有一些 智能规划h t n 规划f 2 2 1 【2 3 1 ，其也是健全和完善的。 在这些规划技术中，图规划及其扩展算法是一个非常合适的规划器。这是因 9 基于m e a 图规划的手机软件g u i 自动化测试的研究第2 章m e a 图规划相关知识 为规划在规划过程中，在构造规划图的过程中，使用有些限制，例如节点之间的 互斥关系。图规划的规划速度非常迅速，相比全序规划和半序规划其在速度上有 数量级的优势。下面将具体来阐述图规划的相关细节： 图规划过程可以分为图扩展阶段和解提取阶段。图规划g r a p h p l a n 与经典规 划方法相比，图规划有自己的特点：首先，图规划器并不像经典规划那样一开始 就对规划解进行搜索，而是先根据问题描述( 即初始状态s 、对象集合o 以及动 作集合a ) 进行前向扩展，并在多项式时间内逐层构造出个结构紧凑的规划图， 构造规划图具有层次性。当所有的目标命题g ( g o a l s ) 均无互斥地出现在该规划 图中当前时间步的命题层上时，图规划g r a p h p l a n 就停止图扩展阶段，然后，根 据目标集，在规划图里面进行逆向搜索，看能否找到有效解，如果找到，则输出 解并且退出规划器( 当然有些时候我们寻找的也许不止一个解，这个时候并不退 出，继续寻找其它也满足条件的解) ；如果搜索不到有效解，则继续扩展规划图， 再进行解提取。如此循环，直到规划图l e v e lo f f 或者失败退出。 图规划流程图如下图2 3 所示： ( 开始 ) n 继续扩展图i i yy 图2 3 图规划流程图 分析图2 - 3 可知，图规划( g r a p h p l a n ) 的流程其实就是一个图扩展和解提取 1 0 基于m e a 图规划的手机软件g u i 自动化测试的研究第2 章m e a 图规划相关知识 交替进行的过程，具体如下描述如下： 1 ) 扩展规划图p g ( p l a n n i n gg r a p h ) 直到所有的目标g ( g o a l s ) 都出现在 当前命题层，并且命题目标之间不互斥。如果p g 在到达此状态之前就 稳定( 1 e v e lo f f ) 了，则规划失败，退出。 2 ) 从当前命题层开始，逆向回溯提取有效解。如果有解，则执行4 ，如果 没有发现有效解，则转到3 。 3 ) 在当前命题层扩展新一层的动作层和下一层的命题层，判断是否所有目 标都非互斥的出现在新的命题层中，如果是，则转到2 ，反之，判断规 划是否l e v e lo f f , 如果是，则退出，反之，跳转回3 。 4 ) 输出有效解并退出。 其中，步骤1 ) 和3 ) 都属于图扩展阶段，步骤2 ) 为解提取阶段。 考虑到图扩展阶段状态空间爆炸问题以及接提取阶段提高逆向搜索效率等 问题，g r a p h p l a n 在图扩展阶段，加入了很多问题本身固有的互斥信息( 根据具 体的问题所提取的互斥信息) ，通过这些一层一层的节点保存这些互斥信息， g r a p h p l a n 在回溯提取解的时候，能够快速判断出当前时间步上是否仍需要继续 回溯下去，提高了搜索的效率。 2 1 6 1 图扩展步骤 图扩展算法如下： 1 ) 将初始状态命题集s o 作为规划图中的第一层命题层p o ，并令标记i = 0 。 2 ) 判断目标集命题g 是否无互斥的出现在命题层p i 中，如果是则跳到步骤 5 ) 。 3 ) 判断规划图是否已经l e v e lo f f , 如果是则跳到步骤5 ) 。 4 ) 生成动作层和命题层，具体如下： 4 1 ) 将空动作r i op p 插入到动作集o p 中，也即将命题层p i 中的命题复 制到命题层p i + l 中。 4 2 ) 依次遍历动作集o p 中的动作o p ，对于其中每一个o p ，该o p 所有 的前件是否均无互斥的出现在p i 层中，如果是，则插入该o p 到动 作层a i 中，并将o p 的增加效果插入到命题层p 件l 中；如果否，则 继续遍历动作集o p 中的下一个动作。 基于m e a 图规划的手机软件g u i 自动化测试的研究 第2 章m e a 图规划相关知识 4 3 ) 分别标记动作层a i 和命题层p i + 1 的所有互斥节点。 4 4 ) 令i 十+ ，跳到步骤2 ) 。 5 ) 结束图扩展。 图扩展之后，就是解提取阶段。 2 1 6 2 规划图解提取 解提取阶段，图规划算法充分利用划图上的互斥动作和互斥命题的相应信 息，采用逐层反向搜索规划解的策略来进行解提取。具体流程如下： 1 ) 当前目标集s = g ，当前命题层层数k = i 。 2 ) 如果k = 0 ，则规划成功，退出。如果k 0 ，则执行3 ) 。 3 ) 选取k - 1 层动作层中不互斥动作集的一个子集( 该动作子集能实现当前第k 层命题层的目标集) ，设该动作集合为彳： 3 1 ) a = 空，剩余目标集合l = s 。 3 2 ) 如果s 空，则从当前目标集s 中选取一个目标g 。如果g = 空，即成功 找到动作集合岔，则执行4 ) 。 3 3 ) 如果能在k - l 层动作层上找到一个动作a 实现目标g ，则l = l u g ) ， a = a u a ，然后执行3 2 ) 。如果k 1 层上不存在满足条件的动 作口，则执行3 4 ) 。 3 4 ) 回溯到l 集合中最后一次考虑的目标g ，并令g = g ，然后执行3 3 ) 。 如果l 集合为空，则执行5 ) 。 4 ) 将实现a ，的所有前件命题s 作为第k - 1 层命题层的目标集，即当前目标集 s = s 。同时，当前命题层层数k = k - 1 。然后转向2 ) 。 5 ) 如果k = n ，则规划失败退出。如果k n ，则回溯到第k + l 层命题层，假设第 k + l 层命题层上的目标集为空，则令当前目标集s = 空，同时，k - - k + l ，然后 转向2 ) ，重新生成新的满足条件的动作子集a 。 2 1 7 图规划求解举例 图规划求解的例子很多，在此我们以男朋友买礼物送女朋友为例示范下图规 划的求解过程。举个生活中的例子，男朋友首先要去商店买礼物，买好礼物便带 礼物回家，最后将礼物献给女朋友。下为动作集图2 1 ： 1 2 基于m e a 图规划的手机软件g u i 自动化测试的研究第2 章m e a 图规划相关知识 表2 1 动作集 动作o p 参数前件与效果 p r e s e n t 前件： a t ( b o y f r i e n d ，p l a c e ) b u y b f a t ( o b j e c t ，p l a c e ) o n ( o b j e c t ，b o y f r i e n d ) s h o p 效果： d e l e t ea t ( o b j e c t ，p l a c e ) a t ( b o y f r i e n d ，p l a c e ) p r e s e n t 前件： a t ( g i r l f r i e n d ，p l a c e ) b f g i v e o n ( o b j e c t ，b o y f r i e n d ) g f h o m e 效果： o n ( o b j e c t ，g i r l f r i e n d ) d e l e t eo n ( o b j e c t ，b o y f r i e n d ) b f 前件： a t ( b o y f r i e n d ，f r o m ) w a l l 【 s h o p o n ( o b j e c t ，b o y f r i e n d ) a t ( b o y f r i e n d ，t o ) h o m e 效果： d e l e t ea t ( b o y f r i e n d ，f r o m ) 状态描述如下： 表2 - 2 问题的状态描述 对象o b ： ( s h o p ，p l a c e ) ( h o m e ，p l a c e ) ( 对象名称，对象属性) ( b f b o y f r i e n d ) ( g f , g i r l f r i e n d ) ( p r e s e n t ，o b j e c t ) s o ：初始命题 a t ( b f , s h o p ) a n da t ( g f , h o m e ) a n da t ( p r e s e n t ，s h o p ) s g ：目标命题o n ( p r e s e n t ，g f ) 按照图规划算法，首先进行图扩展。( 注：曲线代表互斥，虚线代表删除， 实直线代表生成。) 图2 - 4 第一层扩展的规划图 基于m e a 图规划的手机软件g u i 自动化测试的研究第2 章m e a 图规划相关知识 规划图第一次扩展，目标命题没有出现在当前命题层中，所以还需要继续扩 展。下图进行第二层扩展： 图2 5 第二层扩展的规划图 同样的，在第二层扩展的规划图中还是没有出现目标命题，因此，继续扩展， 得到第三层扩展图： 图2 - 6 第三层扩展的规划图 在第三层扩展的时候，发现目标命题( o n ( p r e s e n t ，g f ) ) 已经无互斥的出现 在了当前命题中，此时，进行解提取阶段。解提取结果如下： 1 4 基于m e a 图规划的手机软件g u i 自动化测试的研究第2 章m e a 图规划相关知识 图2 7 解提取( 解为加粗部分) 2 2 引入m e a 方法的图规划 在基本图规划及其扩展算法，在规划图扩展阶段，在规划图n 层次扩展中， 包括了那些在初始状态基础上直接扩展或可以由初始状态所能到达的扩展节点。 但是也许存在这样一个事实：在规划中，大量的动作( t g 就是算子)