基于AUML的BDI Agent软件测试用例生成算法

宫大鹏，王黎明，夏 静

（郑州大学 信息工程学院，河南 郑州450001）

0 引 言

目前，有关Agent软件测试的研究工作主要有［1］：①基于模型的测试 （model based testing－MBT）。文献 ［2］在文献 ［3］的基础上扩展了3种面向对象的测试方法对A－gent软件进行了随机测试、行为测试、等价类测试的研究，但是，由于没有考虑Agent与object的区别，所以测试用例的完备性有待商榷。文献 ［4］利用嵌入了BDI特性的扩展状态机 （extended state machine－ESM）对Agent软件进行了需求与实现的一致性测试，该方法使用ESM并结合BDI的特点，运用基于状态覆盖的方法对Agent软件进行测试。但由于ESM表达能力有限，Agent复杂的行为空间规模并不能很好的在有限状态的ESM中表示出来，所以测试用例的生成也具有局限性。文献 ［5］基于Prometheus模型对Agent软件进行单元测试，将Agent看作是由规划、事件和信念集封装而成并具有感知能力的计算实体。主要对规划进行测试，针对规划依赖、规划循环进行研究，生成测试用例序列，但并未考虑测试用例的自动生成。②针对MAS系统中各个Agent间交互进行的研究。文献 ［6］利用Petri网对Agent的建模语言AUML的语义进行了形式化地分析，对软件设计人员分析软件有所益处，但并不适合以测试为目的的分析。文献 ［7］针对 MAS系统中Agent可能发生的交互定义了诸如，消息覆盖、规划覆盖、规划路径覆盖等用来衡量测试用例质量的标准，但是也没有考虑Agent软件测试用例的生成。

在以上文献的基础上，本文首先介绍BDI Agent的工作原理，在此基础上分析出Agent的行为空间，进一步描述在MAS系统中，何时会触发Agent的BDI决策过程，并使用AUML模型来对该触发过程进行详细描述，将MBT测试与Agent结合起来，进行测试用例的自动生成。

1 相关概念

定义1 信念 （belief）：信念是Agent对外部环境的一个认识集合，Agent的信念集与知识集是一个概念即AgentbeliefAgentKnowledge。

定义2 目的 （Desire）：目的是一个目标集合即AgentDesire≌AgentGoal。Goal＝＜ID，Type＞其中ID是目标编号，每个目标有一个唯一的ID，Type表示目标的类型，目标有2种类型S和L，S表示Agent的近期目标，Agent依据现有的信念认识可以完成，L表示Agent的远期目标集合，Agent依据现有的信念或许暂时不能完成。

定义3 意图 （Intention）：Intention＝ ｛goal｜goal∈GoalAgent且goal.Type＝S｝，即意图是目的中Agent近期可以实现的目标所构成的集合，是目的的一个子集。

定义4 动作 （Action）：Action＝＜guard，content＞其中guard为动作的限制条件，content为动作所要做的内容。动作是Agent行为的最小单位，也是Agent行为的最小执行单元，任何目的的实现都需要Agent依据Agentbelief将目的分解为Agent可以实现的动作即Agent的行为序列必须以动作作为终结。

定义5 行为 （Behavior）：Agent的行为是一个序列S＝＜as，a1…ae＞，其中as表示行为的起点，as可以是一个目标或一个动作，ae表示行为的终止，ae必须是一个动作。

定义6 规划 （Plan）：Plan＝＜name，e，con，Body＞其中name是规划名，e是调用条件，用来说明规划处理哪类事件，con是环境条件，用来说明规划的使用环境，Body是规划体。规划是用来实现一个目标的动作序列。

定义7 序列图 （SD）：SD＝＜A，M，Conn＞其中A＝ ｛A1，A2，…，An｝是Agent的集合；M＝M1，M2，…，Mn是消息序列，其中 M＝＜mName，fAgent，to Agent，mType＞，mName为消息名，fAgent为消息发送方，toAgent为消息请求方，mType为消息类型，用于标识哪些消息是Agent需要回复，哪些是仅仅接收而不做处理；Conn是连接器，Conn＝ ｛And，Or，Xor｝分别表示‘与’连接、‘或’连接和 ‘异或’连接。

定义8 测试用例 （TC）：TC＝＜ID，In，Out＞ID表示用例编号，In表示用例输入数据，Out表示期望用例输出。

2 目标规划树遍历与MAS交互表示

2.1 BDI运行原理

BDI的执行过程就是BDI Agent的行为轨迹，但信念、目的和意图在系统功能中被分配的角色以及表示和控制他们的形式各不相同。有一些理论旨在从观察者的角度（Ferguson，1995）来解释和预测Agent的行为，有一些则是用于设计Agent的体系结构 （d’Inverno等，2004），还有的是用于支持从事集体活动的Agent进行推理 （Jennings，1993）［8］。

本文将BDI Agent运行理解为如下过程：

（1）Agent接受或感知外部环境事件。

（2）Search （Agentbelief）来生成一个 AgentDesire。

（3）Watch （Environment）并 Search （Agentbelief）依据资源、环境条件等因素推算每个目的的实现难易度。

（4）选择当前较容易完成的目的放入意图集中准备实现。

（5）对意图集中的目标依据Agentbelief进行分析，选择合适的规划完成目标。

Agent构造目标规划树的过程如图1所示。

如上所述，Agent在Agentbelief的认知下对目标进行建立和选择，确定目标后需要考虑目标的实现。本文将目标的实现看作是当目的确定时，Agent如何选择规划并执行动作的过程。为了能够可视化这个实现过程，本文将目标的实现过程抽象为一棵目标规划树。

由于AgentDesire≌AgentGoal，本文剩余部分将使用Goal来替代Desire进行表述。一个典型的目标规划树如图2所示。

图2 的目标规划树中，Goal有2个孩子结点分别是Plan1与Plan2，表明Agent有2种方式实现根结点的Goal。2个孩子节点之间是 “或”关系，而为了实现Plan1，需要分别实现动作a、子目标、动作b，这三者之间是一个“与”关系。Plan2与Plan1的分解关系相同。Agent的目标规划树中如果父结点是一个目标，则父、子节点的关系为“或”关系，如果父结点是一个规划，则父、子节点为“与”关系。

本文在遍历的过程中，将每个分支都遍历并保存在字符型的容器Vector＜String＞中，依据父子结点的关系并结合Vector容器的值进行组合来确定Agent的行为。上述目标规划树中Goal有2个子结点，用Vector＜String＞Path－Vc［2］存放结果。

此时需分情况处理：

（1）当目标没有孙结点时，根据目标的与或关系进行相应容器运算。

（2）如果有孙结点，开始递归直到遍历到以叶子结点为子结点的子树时，依据 （1）的处理方法处理。

以图2中目标左子树为例，plan3返回的容器中存放e，plan4返回的容器中存放f，subGoal为 “或”关系，返回的容器r中存放 （e，f）；plan1为 “与”关系，容器内容为（aeb，afb）。

算法1：确定Agent行为

输入：目标规划树

输出：Agent行为集合

步骤1 令GCFlag为布尔型用来判断一个树的根结点是否有孙结点，初始为false；容器vs用于返回一棵子树的活动路径集合，容器数组vec［］用于记录以各孩子结点为根结点的树的活动路径集合。

步骤2 从树的根结点开始分层遍历树，确定Agent的行为。如果根结点只有子结点而没有孙结点，可直接求出活动路径。根结点的 “与或”标识变量为flag。若flag＝0为 “与”，此时活动路径只有一条，为各孩子结点的值序列；若flag＝1为 “或”，此时各子结点的值为活动路径，活动路径的条数为子结点的个数。

步骤3 若根结点有孙结点，采用递归方法返回以子结点为根结点的子树的活动路径集合。递归找到目标树的叶子结点，以叶子结点为子结点的子树通过步骤2处理，返回子树的行为集合vs。

步骤4 若原树根结点有多个子结点，重复步骤3得到各子树的活动路径集合vec［d］。

步骤5 若根结点flag标识为 “或”，求vec［d］的并集；若flag标识为 “与”，求vec［d］的组合。

步骤6 步骤5的结果赋给vs并返回即为Agent的行为集合，算法终止。

算法1对目标规划树进行遍历，假设每个结点遍历的时间复杂度为O（1），则算法的时间复杂度为O（n），其中n为结点数。

2.2 MAS中BDI的触发过程

下面讨论MAS系统中，不同Agent间如何进行协作。MAS系统的行为本质上是各分布的Agent的行为以及不同Agent之间交互的行为。一个Agent的能力等同于这个Agent可以实现目标的能力，即capabilitiesAgent≌solvesAgent。但是有些目标可能需要别的Agent协助才能实现。Agent间进行目标委托规则如下：

若MAS＝ ｛A1，A2，…，An｝是由n个Agent所构成的多系统，A、B∈ MAS，g：GAg，slovesB（g）则AgentA.Substitute（GA，B）。

上述规则表明，若Agent A有一个目标g需要完成，但Agent由于信念发生变化或规划环境不满足导致目标不能实现，则Agent B会代替Agent A来实现该目标。

当Agent位于MAS中时，它就处在了一个与其它A－gent不断交互的过程中。Agent可以感知环境的变化并接收其它Agent发送过来的消息，将消息作为一个事件，事件会驱动BDI机制的运行，进而导致目标建立。即外部的消息事件驱动Agent建立一个目标。

2.3 Agent交互的表示

AUML作为FIPA规范中阐述Agent交互协议的符号，其序列图成为使用最多的模型［8］。序列图可以很好的描述消息交互的过程。如图3所示的一个Agent交互过程。

图3 显示2个BookingAgent的样本协议交互图，它们分别扮演不同的角色：ExploringTeacherAgent和OccupyingTeacherAgent。黑色圆形表示Agent在接受消息后触发BDI的时间点。这里用到了FIPA的AUML标记，AUML中描述角色特征的一般形式为：

实例1、…实例n／角色特征1、…角色特征m：类

上式表示满足Agent角色特征的一系列Agent实例和类组成。FIPA规定的具体组合规则见表1。

近年来，教育部针对课后服务及规范校外培训机构发展等问题曾多次发文，强调各地要积极探索，尝试建立课后服务的体制机制，鼓励学校主动承担起课后服务的职责，并将政府、民间企业、社会团体、社区志愿者等社会资源纳入课后服务中来，合力解决中小学生的课后服务难题。

表1 AUML序列图中Agent名称的不同组合

3 测试过程

3.1 测试覆盖规则

首先给出一些本文方法所需要用到的相关覆盖标准。文献 ［7］中给出了2种度量测试用例质量的标准：①基于消息的覆盖；②基于规划的覆盖。其中，基于消息的覆盖用于衡量交互测试用例的质量，基于规划的覆盖用于衡量单个Agent模块的测试用例的质量。两者结合可以很好的筛选出一些高效的测试用例，即：用尽量少的用例来发现尽量多的错误。

对于MBC标准来说我们不用关注消息内容，也不关注消息的发送时间，只关注消息的相对顺序。关注相对顺序是为了避免出现文献 ［9］中提到的资源、环境等冲突导致的Agent进程挂起或死锁现象。这种情况下的测试用例就是无效用例。

对于PBC标准，因为规划是解决问题的有效步骤，当覆盖了Agent内部所有规划集合后，也就完备的测试了Agent的所有可能出现的行为。即标准是具备完备性的。

3.2 序列图信息提取

由于BDI Agent是目标驱动型智能体，消息事件通常是Agent建立目标的外在动力。因此，首先必须从SD中，提取出引起Agent触发BDI并建立目标的相关消息。

算法2：提取SD图消息

输入：顺序图

输出：需要Agent处理的消息集

步骤1 用Vector＜message＞ 类型的变量MVector存放SD图中每个Agenti需要处理的消息集，初始为NULL。

步骤3 If Conn.type＝＝And则使用 MVector.push＿back（m）方法将Conn输出端所列出的每条消息加入m.toAgent所列出的Agent的消息集中；If Conn.type＝＝Or则依据Conn中给出的限制条件选择Conn输出端的一条或多条消息调用 MVector.push＿back（m）方法将消息加入m.toAgent所列出的Agent的消息中；If Conn.type＝＝Xor则依据Conn中所给出的限制条件选择Conn输出端的一条消息，使用 MVector.push＿back（m）方法将消息加入m.toAgent所列出的Agent的消息集中。

步骤4 若SD图中没有可解析的消息m，算法终止。

算法2对SD图中的消息依序逐个进行处理，算法时间复杂度为O（n），其中n为消息个数。

3.3 测试路径的生成

在给出生成路径算法前，先给出几个函数定义：①CreateGT（m）建立消息m对应的目标规划树；②AddGS（t）将目标规划树t放入 AgentGoal集合中；③isExist（m.type）判定Agent是否处理过同类问题。

算法3：生成测试路径

输入：消息集合

输出：测试路径

步骤1 对任一消息m∈MessageSet，使用isExist（m.type）判定Agent是否实现过同类型的目标，if（isExist（m.type）＝＝true）当环境条件没有改变时，直接用已有的目标规划树解决该问题。否则转到步骤2.

步骤2 调用CreateGT（m）建立消息m对应的目标规划树t，并调用AddGS（t）将目标规划树t放入Agent－Goal集合中，当消息集合中仍有消息m未被处理时转到步骤1，否则转到步骤3。

步骤3 对任一t∈AgentGoal调用算法1来确定Agent实现每棵目标规划树的行为轨迹，如果所有t都处理完成，算法终止。

算法3需要处理消息集合中的所有消息，每个消息对应一个目标规划树需要进行遍历处理，算法的时间复杂度为O（n2），消息个数为n遍历目标规划树的复杂度为n。

3.4 测试用例的生成

依据算法2提取SD中的所有消息并结合算法3构造目标规划树，使用算法1判定所有可能的规划所生成的测试路径同时结合MBC和PBC标准可以生成完备的测试用例。

算法4：测试用例生成算法

输入：测试路径

输出：测试用例

步骤1 令pNode为指针型变量指向TP中的每个结点，变量InData为Vector＜Pair＜String，Sting＞ ＞型用于存放动作的前置条件和具体内容，OutData为Vector＜Pair＜InDateType，OutDateType＞ ＞型用来存放测试用例的输入与期望的输出。

步骤2 对每条测试路径TPi（TPi∈TP）遍历TPi中的每个结点，令pNode指向起始结点，while（pNode！＝EndNode）将每个动作结点的限制条件和动作信息存入容器中，即 InData.push ＿back （make＿Pair＜pNode－＞guard，pNode－＞content＞），然后将pNode＋＋，指向下一个动作结点，从while循环退出后，将终止结点的信息进行处理存入容器InData中；

步骤3 对InData容器中的每个内容IntData［i］进行处理，分析InData［i］.second的内容，使用OutData.push＿back （make＿pair （In，out））将InData ［i］.second对应的测试数据存入容器OutData中。当容器中所有消息处理完后，算法终止。

算法4：主要依据算法3生成的测试用例进行测试用例的生成，算法的时间复杂度为O（n），n为测试路径TP的数目。

4 实 验

为了对本文测试方法进行检验，设计了3组实验。第一组实验用来验证通过目标规划树生成Agent行为轨迹的有效性；第二组实验用来验证测试路径生成方法的有效性；第三组实验用来验证生成测试用例的有效性。

本文选择文献 ［11］经典实例来展示所给出算法的正确性。Agent的信念集中存放的是关于环境的信息，使用位置表格L＝ ｛0…MAX｝× ｛0…MAX｝，l∈L表示环境中具体的一个位置，对于一个给定位置l所含的垃圾数目为m（l），还有关于垃圾箱位置的集合b∈l，h表示Robot所携带的垃圾数量，c表示Robot最多可携带的垃圾数。Robot的Goal是清除所有的垃圾，即任何一个l∈L，使得v（l）＝0。Robot可用的动作见表2。

表2 Robot可用的动作列表

4.1 目标规划树生成BDI Agent行为轨迹有效性验证

Agent程序可以处理如下情况：

若robot没有携带垃圾且当前位置没有垃圾，就explore；

若robot没有携带垃圾且当前位置有垃圾，就Pick；

若robot携带垃圾但当前位置没有垃圾箱b，就movetobin；

若robot携带垃圾且当前位置有垃圾箱，就drop；

上述情况有些plan中含有相应子目标要实现，如movetobin需要知道b的具体位置，也需要别的plan处理。实例中Agent程序的目标规划树如图4所示。

图4 Robot的目标规划树

使用算法1处理上图目标规划树，可以得出5条行为序列，即：S1＝＜CleanGoal，Plan1，Action1＞，S2＝＜CleanGoal，plan2，FindWp，Action2＞，S3＝ ＜Clean－Goal，Plan2，CallHelpP，Action3＞，S4＝＜CleanGoal，Plan3，FindBP，Action4＞，S5＝ ＜CleanGoal，Plan3，CallHelpP，Action5＞。

使用算法4处理上述5条行为序列，可分别得到相应的测试序列。如S2行为序列对应的测试用例为＜t＞0，belief.l！＝b，belief.b＝0，Pick（）；v（p）＝0＞表示当位置p有垃圾且robot不知道垃圾箱b的位置，自己寻找垃圾箱，最后执行pick（）操作，作用的结果为v（p）＝0；

4.2 测试路径生成方法有效性验证

选择文献 ［12］中的网上购物系统、E－Learning系统、机票预订系统、E－Novel系统和电子拍卖系统，并选取文献［3，4］的方法与本文所提基于AUML生成测试路径的方法进行对比。

文献 ［3］完全采用OO的方法对UML序列图的模型进行处理，并未考虑BDI的特性。文献 ［4］使用ESM单纯考虑Agent的频繁出现的状态，将BDI的运行嵌入到ESM的状态转换中，在同等条件下，基于ESM的方法生成的测试路径具有局限性。由表3中可以看出，本文的方法较文献［3，4］相比，结点数比文献 ［3］多、比文献 ［4］少，但边数比两者都多。这是因为文献 ［3，4］并没有完全考虑BDI和MAS的交互，因此它们进行的测试是不完备的。

表3 文献 ［3，4］方法与本文基于AUML方法对比

4.3 测试用例生成有效性验证

本文以文献 ［12］的系统为测试对象，图5至图7为文献 ［12］与本文的测试用例数目、检测错误数与检测错误率的情况。

由图5可知，本文的测试用例数目要多于文献 ［12］，这是因为文献 ［12］采用的角色模型对BDI的特性没有完备的考虑，本文基于目标规划树考虑Agent的行为，增加了问题的规模，所需要考虑的测试场景也多于文献 ［12］，所以测试用例有所增加。

由图6可知本文所检测的错误数不低于文献 ［12］所检测的错误数，图7很好的说明了本文与文献 ［12］相比，检测错误率也有一定程度的提高。虽然随着系统规模的增大，错误的检测率会有所下降，同时目标规划树的规模也会指数级的增长，对硬件的负荷也相应增大，这也是本方法的一个需要改进的不足之处。但总体来说，本文所提方法还是能够很好的处理基于BDI Agent所开发的软件。

5 结束语

本文主要研究BDI型Agent软件的测试用例自动生成方法。该方法直观的刻画出了BDI的运行轨迹，确定了单个Agent的运行轨迹，解决了AUML序列图SD到Agent执行目标规划树之间的转换，对AUML模型的分类器进行了不同的处理，从目标规划树的结点提取出测试用例生成所需要的输入、输出、前置条件等信息，该方法不需要的SD图做任何的修改同时不需要人工干预测试过程，很好的实现了BDI型Agent的自动化测试。

下一步的研究工作是在保证测试用例有效性的前提下，考虑BDI的动态更新以及Agent所处环境的动态变化对测试过程的影响，并同时简化测试步骤，得到一个基于AUML模型更加高效、实用的测试方法。

［1］MAO Xinjun，HU Cuiyun，SUN Yuesheng，et al.The research of Agent－oriented program design ［J］.Journal of Software，2012，23 （11）：2885－2904 （in Chinese）.［毛新军，胡翠云，孙跃坤，等.面向Agent的程序设计的研究 ［J］.软件学报，2012，23 （11）：2885－2904.］

［2］Srivastava P R，K A V.Extension of object－oriented software testing techniques to Agent oriented software testing ［J］.Journal of Object Technology，2008，7 （8）：155－163.

［3］Bauer，Bernhard Odell，James.UML2.0and Agents：How to build Agent－based systems with the new UML standard ［J］.Engineering Applications of Artificial Intelligence，2005，18（2）：141－157.

［4］Zheng M，Alagar V S.Conformance testing of BDI properties in Agent－based software systems ［C］／／12th Asia－Pacific Software Engineering Conference.IEEE，2005：130－138.

［5］Zhang Z.Automated unit testing for Agent systems ［D］.Melbourne：Melbourne University，2011.

［6］Lawrence Cabac，Daniel Moldt.Formal semantics for AUML Agent interaction protocol diagrams ［M］.Berlin：Springer，2005：47－61.

［7］Tim Miller，Lin Padgham，John Thangarajah.Test coverage criteria for Agent interaction testing ［M］.Berlin：Springer，2011：91－105.

［8］XUE Xiao.Agent－oriented software design and development methods ［M］.Beijing：Mechanical Industry Press，2009：200－215（in Chinese）.［薛宵.面向Agent的软件设计开发方法 ［M］.北京：机械工业出版社，2009：200－215.］

［9］Thangarajah J，Harland J.Suspending and resuming tasks in BDI Agents［C］／／IFAAMAS，2008：405－412.

［10］Hong－han Z，Rui－zhong M.A modeling methodology for MAS based on AUML ［C］／／IEEE，2011：185－188.

［11］Lars Braubach，Alexander Pokahr，Daniel Moldt，et a1.Programming multi－Agent systems ［M］.Berlin：Springer，2005：44－45.

［12］Sivakumar N，Vivekanandan K.Agent oriented software testing－role oriented approach ［J］.International Journal，2012，33 （4）：100－110.