宮大鵬，王黎明，夏 靜

（鄭州大學(xué) 信息工程學(xué)院，河南 鄭州450001）

0 引 言

目前，有關(guān)Agent軟件測(cè)試的研究工作主要有［1］：①基于模型的測(cè)試 （model based testing－MBT）。文獻(xiàn) ［2］在文獻(xiàn) ［3］的基礎(chǔ)上擴(kuò)展了3種面向?qū)ο蟮臏y(cè)試方法對(duì)A－gent軟件進(jìn)行了隨機(jī)測(cè)試、行為測(cè)試、等價(jià)類測(cè)試的研究，但是，由于沒有考慮Agent與object的區(qū)別，所以測(cè)試用例的完備性有待商榷。文獻(xiàn) ［4］利用嵌入了BDI特性的擴(kuò)展?fàn)顟B(tài)機(jī) （extended state machine－ESM）對(duì)Agent軟件進(jìn)行了需求與實(shí)現(xiàn)的一致性測(cè)試，該方法使用ESM并結(jié)合BDI的特點(diǎn)，運(yùn)用基于狀態(tài)覆蓋的方法對(duì)Agent軟件進(jìn)行測(cè)試。但由于ESM表達(dá)能力有限，Agent復(fù)雜的行為空間規(guī)模并不能很好的在有限狀態(tài)的ESM中表示出來，所以測(cè)試用例的生成也具有局限性。文獻(xiàn) ［5］基于Prometheus模型對(duì)Agent軟件進(jìn)行單元測(cè)試，將Agent看作是由規(guī)劃、事件和信念集封裝而成并具有感知能力的計(jì)算實(shí)體。主要對(duì)規(guī)劃進(jìn)行測(cè)試，針對(duì)規(guī)劃依賴、規(guī)劃循環(huán)進(jìn)行研究，生成測(cè)試用例序列，但并未考慮測(cè)試用例的自動(dòng)生成。②針對(duì)MAS系統(tǒng)中各個(gè)Agent間交互進(jìn)行的研究。文獻(xiàn) ［6］利用Petri網(wǎng)對(duì)Agent的建模語言AUML的語義進(jìn)行了形式化地分析，對(duì)軟件設(shè)計(jì)人員分析軟件有所益處，但并不適合以測(cè)試為目的的分析。文獻(xiàn) ［7］針對(duì) MAS系統(tǒng)中Agent可能發(fā)生的交互定義了諸如，消息覆蓋、規(guī)劃覆蓋、規(guī)劃路徑覆蓋等用來衡量測(cè)試用例質(zhì)量的標(biāo)準(zhǔn)，但是也沒有考慮Agent軟件測(cè)試用例的生成。

在以上文獻(xiàn)的基礎(chǔ)上，本文首先介紹BDI Agent的工作原理，在此基礎(chǔ)上分析出Agent的行為空間，進(jìn)一步描述在MAS系統(tǒng)中，何時(shí)會(huì)觸發(fā)Agent的BDI決策過程，并使用AUML模型來對(duì)該觸發(fā)過程進(jìn)行詳細(xì)描述，將MBT測(cè)試與Agent結(jié)合起來，進(jìn)行測(cè)試用例的自動(dòng)生成。

1 相關(guān)概念

定義1 信念 （belief）：信念是Agent對(duì)外部環(huán)境的一個(gè)認(rèn)識(shí)集合，Agent的信念集與知識(shí)集是一個(gè)概念即AgentbeliefAgentKnowledge。

定義2 目的 （Desire）：目的是一個(gè)目標(biāo)集合即AgentDesire≌AgentGoal。Goal＝＜ID，Type＞其中ID是目標(biāo)編號(hào)，每個(gè)目標(biāo)有一個(gè)唯一的ID，Type表示目標(biāo)的類型，目標(biāo)有2種類型S和L，S表示Agent的近期目標(biāo)，Agent依據(jù)現(xiàn)有的信念認(rèn)識(shí)可以完成，L表示Agent的遠(yuǎn)期目標(biāo)集合，Agent依據(jù)現(xiàn)有的信念或許暫時(shí)不能完成。

定義3 意圖 （Intention）：Intention＝ ｛goal｜goal∈GoalAgent且goal.Type＝S｝，即意圖是目的中Agent近期可以實(shí)現(xiàn)的目標(biāo)所構(gòu)成的集合，是目的的一個(gè)子集。

定義4 動(dòng)作 （Action）：Action＝＜guard，content＞其中g(shù)uard為動(dòng)作的限制條件，content為動(dòng)作所要做的內(nèi)容。動(dòng)作是Agent行為的最小單位，也是Agent行為的最小執(zhí)行單元，任何目的的實(shí)現(xiàn)都需要Agent依據(jù)Agentbelief將目的分解為Agent可以實(shí)現(xiàn)的動(dòng)作即Agent的行為序列必須以動(dòng)作作為終結(jié)。

定義5 行為 （Behavior）：Agent的行為是一個(gè)序列S＝＜as，a1…ae＞，其中as表示行為的起點(diǎn)，as可以是一個(gè)目標(biāo)或一個(gè)動(dòng)作，ae表示行為的終止，ae必須是一個(gè)動(dòng)作。

定義6 規(guī)劃 （Plan）：Plan＝＜name，e，con，Body＞其中name是規(guī)劃名，e是調(diào)用條件，用來說明規(guī)劃處理哪類事件，con是環(huán)境條件，用來說明規(guī)劃的使用環(huán)境，Body是規(guī)劃體。規(guī)劃是用來實(shí)現(xiàn)一個(gè)目標(biāo)的動(dòng)作序列。

定義7 序列圖 （SD）：SD＝＜A，M，Conn＞其中A＝ ｛A1，A2，…，An｝是Agent的集合；M＝M1，M2，…，Mn是消息序列，其中 M＝＜mName，fAgent，to Agent，mType＞，mName為消息名，fAgent為消息發(fā)送方，toAgent為消息請(qǐng)求方，mType為消息類型，用于標(biāo)識(shí)哪些消息是Agent需要回復(fù)，哪些是僅僅接收而不做處理；Conn是連接器，Conn＝ ｛And，Or，Xor｝分別表示‘與’連接、‘或’連接和 ‘異或’連接。

定義8 測(cè)試用例 （TC）：TC＝＜ID，In，Out＞ID表示用例編號(hào)，In表示用例輸入數(shù)據(jù)，Out表示期望用例輸出。

2 目標(biāo)規(guī)劃樹遍歷與MAS交互表示

2.1 BDI運(yùn)行原理

BDI的執(zhí)行過程就是BDI Agent的行為軌跡，但信念、目的和意圖在系統(tǒng)功能中被分配的角色以及表示和控制他們的形式各不相同。有一些理論旨在從觀察者的角度（Ferguson，1995）來解釋和預(yù)測(cè)Agent的行為，有一些則是用于設(shè)計(jì)Agent的體系結(jié)構(gòu) （d’Inverno等，2004），還有的是用于支持從事集體活動(dòng)的Agent進(jìn)行推理 （Jennings，1993）［8］。

本文將BDI Agent運(yùn)行理解為如下過程：

（1）Agent接受或感知外部環(huán)境事件。

（2）Search （Agentbelief）來生成一個(gè) AgentDesire。

（3）Watch （Environment）并 Search （Agentbelief）依據(jù)資源、環(huán)境條件等因素推算每個(gè)目的的實(shí)現(xiàn)難易度。

（4）選擇當(dāng)前較容易完成的目的放入意圖集中準(zhǔn)備實(shí)現(xiàn)。

（5）對(duì)意圖集中的目標(biāo)依據(jù)Agentbelief進(jìn)行分析，選擇合適的規(guī)劃完成目標(biāo)。

Agent構(gòu)造目標(biāo)規(guī)劃樹的過程如圖1所示。

如上所述，Agent在Agentbelief的認(rèn)知下對(duì)目標(biāo)進(jìn)行建立和選擇，確定目標(biāo)后需要考慮目標(biāo)的實(shí)現(xiàn)。本文將目標(biāo)的實(shí)現(xiàn)看作是當(dāng)目的確定時(shí)，Agent如何選擇規(guī)劃并執(zhí)行動(dòng)作的過程。為了能夠可視化這個(gè)實(shí)現(xiàn)過程，本文將目標(biāo)的實(shí)現(xiàn)過程抽象為一棵目標(biāo)規(guī)劃樹。

由于AgentDesire≌AgentGoal，本文剩余部分將使用Goal來替代Desire進(jìn)行表述。一個(gè)典型的目標(biāo)規(guī)劃樹如圖2所示。

圖2 的目標(biāo)規(guī)劃樹中，Goal有2個(gè)孩子結(jié)點(diǎn)分別是Plan1與Plan2，表明Agent有2種方式實(shí)現(xiàn)根結(jié)點(diǎn)的Goal。2個(gè)孩子節(jié)點(diǎn)之間是 “或”關(guān)系，而為了實(shí)現(xiàn)Plan1，需要分別實(shí)現(xiàn)動(dòng)作a、子目標(biāo)、動(dòng)作b，這三者之間是一個(gè)“與”關(guān)系。Plan2與Plan1的分解關(guān)系相同。Agent的目標(biāo)規(guī)劃樹中如果父結(jié)點(diǎn)是一個(gè)目標(biāo)，則父、子節(jié)點(diǎn)的關(guān)系為“或”關(guān)系，如果父結(jié)點(diǎn)是一個(gè)規(guī)劃，則父、子節(jié)點(diǎn)為“與”關(guān)系。

本文在遍歷的過程中，將每個(gè)分支都遍歷并保存在字符型的容器Vector＜String＞中，依據(jù)父子結(jié)點(diǎn)的關(guān)系并結(jié)合Vector容器的值進(jìn)行組合來確定Agent的行為。上述目標(biāo)規(guī)劃樹中Goal有2個(gè)子結(jié)點(diǎn)，用Vector＜String＞Path－Vc［2］存放結(jié)果。

此時(shí)需分情況處理：

（1）當(dāng)目標(biāo)沒有孫結(jié)點(diǎn)時(shí)，根據(jù)目標(biāo)的與或關(guān)系進(jìn)行相應(yīng)容器運(yùn)算。

（2）如果有孫結(jié)點(diǎn)，開始遞歸直到遍歷到以葉子結(jié)點(diǎn)為子結(jié)點(diǎn)的子樹時(shí)，依據(jù) （1）的處理方法處理。

以圖2中目標(biāo)左子樹為例，plan3返回的容器中存放e，plan4返回的容器中存放f，subGoal為 “或”關(guān)系，返回的容器r中存放 （e，f）；plan1為 “與”關(guān)系，容器內(nèi)容為（aeb，afb）。

算法1：確定Agent行為

輸入：目標(biāo)規(guī)劃樹

輸出：Agent行為集合

步驟1 令GCFlag為布爾型用來判斷一個(gè)樹的根結(jié)點(diǎn)是否有孫結(jié)點(diǎn)，初始為false；容器vs用于返回一棵子樹的活動(dòng)路徑集合，容器數(shù)組vec［］用于記錄以各孩子結(jié)點(diǎn)為根結(jié)點(diǎn)的樹的活動(dòng)路徑集合。

步驟2 從樹的根結(jié)點(diǎn)開始分層遍歷樹，確定Agent的行為。如果根結(jié)點(diǎn)只有子結(jié)點(diǎn)而沒有孫結(jié)點(diǎn)，可直接求出活動(dòng)路徑。根結(jié)點(diǎn)的 “與或”標(biāo)識(shí)變量為flag。若flag＝0為 “與”，此時(shí)活動(dòng)路徑只有一條，為各孩子結(jié)點(diǎn)的值序列；若flag＝1為 “或”，此時(shí)各子結(jié)點(diǎn)的值為活動(dòng)路徑，活動(dòng)路徑的條數(shù)為子結(jié)點(diǎn)的個(gè)數(shù)。

步驟3 若根結(jié)點(diǎn)有孫結(jié)點(diǎn)，采用遞歸方法返回以子結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹的活動(dòng)路徑集合。遞歸找到目標(biāo)樹的葉子結(jié)點(diǎn)，以葉子結(jié)點(diǎn)為子結(jié)點(diǎn)的子樹通過步驟2處理，返回子樹的行為集合vs。

步驟4 若原樹根結(jié)點(diǎn)有多個(gè)子結(jié)點(diǎn)，重復(fù)步驟3得到各子樹的活動(dòng)路徑集合vec［d］。

步驟5 若根結(jié)點(diǎn)flag標(biāo)識(shí)為 “或”，求vec［d］的并集；若flag標(biāo)識(shí)為 “與”，求vec［d］的組合。

步驟6 步驟5的結(jié)果賦給vs并返回即為Agent的行為集合，算法終止。

算法1對(duì)目標(biāo)規(guī)劃樹進(jìn)行遍歷，假設(shè)每個(gè)結(jié)點(diǎn)遍歷的時(shí)間復(fù)雜度為O（1），則算法的時(shí)間復(fù)雜度為O（n），其中n為結(jié)點(diǎn)數(shù)。

2.2 MAS中BDI的觸發(fā)過程

下面討論MAS系統(tǒng)中，不同Agent間如何進(jìn)行協(xié)作。MAS系統(tǒng)的行為本質(zhì)上是各分布的Agent的行為以及不同Agent之間交互的行為。一個(gè)Agent的能力等同于這個(gè)Agent可以實(shí)現(xiàn)目標(biāo)的能力，即capabilitiesAgent≌solvesAgent。但是有些目標(biāo)可能需要?jiǎng)e的Agent協(xié)助才能實(shí)現(xiàn)。Agent間進(jìn)行目標(biāo)委托規(guī)則如下：

若MAS＝ ｛A1，A2，…，An｝是由n個(gè)Agent所構(gòu)成的多系統(tǒng)，A、B∈ MAS，g：GAg，slovesB（g）則AgentA.Substitute（GA，B）。

上述規(guī)則表明，若Agent A有一個(gè)目標(biāo)g需要完成，但Agent由于信念發(fā)生變化或規(guī)劃環(huán)境不滿足導(dǎo)致目標(biāo)不能實(shí)現(xiàn)，則Agent B會(huì)代替Agent A來實(shí)現(xiàn)該目標(biāo)。

當(dāng)Agent位于MAS中時(shí)，它就處在了一個(gè)與其它A－gent不斷交互的過程中。Agent可以感知環(huán)境的變化并接收其它Agent發(fā)送過來的消息，將消息作為一個(gè)事件，事件會(huì)驅(qū)動(dòng)BDI機(jī)制的運(yùn)行，進(jìn)而導(dǎo)致目標(biāo)建立。即外部的消息事件驅(qū)動(dòng)Agent建立一個(gè)目標(biāo)。

2.3 Agent交互的表示

AUML作為FIPA規(guī)范中闡述Agent交互協(xié)議的符號(hào)，其序列圖成為使用最多的模型［8］。序列圖可以很好的描述消息交互的過程。如圖3所示的一個(gè)Agent交互過程。

圖3 顯示2個(gè)BookingAgent的樣本協(xié)議交互圖，它們分別扮演不同的角色：ExploringTeacherAgent和OccupyingTeacherAgent。黑色圓形表示Agent在接受消息后觸發(fā)BDI的時(shí)間點(diǎn)。這里用到了FIPA的AUML標(biāo)記，AUML中描述角色特征的一般形式為：

實(shí)例1、…實(shí)例n／角色特征1、…角色特征m：類

上式表示滿足Agent角色特征的一系列Agent實(shí)例和類組成。FIPA規(guī)定的具體組合規(guī)則見表1。

近年來，教育部針對(duì)課后服務(wù)及規(guī)范校外培訓(xùn)機(jī)構(gòu)發(fā)展等問題曾多次發(fā)文，強(qiáng)調(diào)各地要積極探索，嘗試建立課后服務(wù)的體制機(jī)制，鼓勵(lì)學(xué)校主動(dòng)承擔(dān)起課后服務(wù)的職責(zé)，并將政府、民間企業(yè)、社會(huì)團(tuán)體、社區(qū)志愿者等社會(huì)資源納入課后服務(wù)中來，合力解決中小學(xué)生的課后服務(wù)難題。

表1 AUML序列圖中Agent名稱的不同組合

3 測(cè)試過程

3.1 測(cè)試覆蓋規(guī)則

首先給出一些本文方法所需要用到的相關(guān)覆蓋標(biāo)準(zhǔn)。文獻(xiàn) ［7］中給出了2種度量測(cè)試用例質(zhì)量的標(biāo)準(zhǔn)：①基于消息的覆蓋；②基于規(guī)劃的覆蓋。其中，基于消息的覆蓋用于衡量交互測(cè)試用例的質(zhì)量，基于規(guī)劃的覆蓋用于衡量單個(gè)Agent模塊的測(cè)試用例的質(zhì)量。兩者結(jié)合可以很好的篩選出一些高效的測(cè)試用例，即：用盡量少的用例來發(fā)現(xiàn)盡量多的錯(cuò)誤。

對(duì)于MBC標(biāo)準(zhǔn)來說我們不用關(guān)注消息內(nèi)容，也不關(guān)注消息的發(fā)送時(shí)間，只關(guān)注消息的相對(duì)順序。關(guān)注相對(duì)順序是為了避免出現(xiàn)文獻(xiàn) ［9］中提到的資源、環(huán)境等沖突導(dǎo)致的Agent進(jìn)程掛起或死鎖現(xiàn)象。這種情況下的測(cè)試用例就是無效用例。

對(duì)于PBC標(biāo)準(zhǔn)，因?yàn)橐?guī)劃是解決問題的有效步驟，當(dāng)覆蓋了Agent內(nèi)部所有規(guī)劃集合后，也就完備的測(cè)試了Agent的所有可能出現(xiàn)的行為。即標(biāo)準(zhǔn)是具備完備性的。

3.2 序列圖信息提取

由于BDI Agent是目標(biāo)驅(qū)動(dòng)型智能體，消息事件通常是Agent建立目標(biāo)的外在動(dòng)力。因此，首先必須從SD中，提取出引起Agent觸發(fā)BDI并建立目標(biāo)的相關(guān)消息。

算法2：提取SD圖消息

輸入：順序圖

輸出：需要Agent處理的消息集

步驟1 用Vector＜message＞ 類型的變量MVector存放SD圖中每個(gè)Agenti需要處理的消息集，初始為NULL。

步驟3 If Conn.type＝＝And則使用 MVector.push＿back（m）方法將Conn輸出端所列出的每條消息加入m.toAgent所列出的Agent的消息集中；If Conn.type＝＝Or則依據(jù)Conn中給出的限制條件選擇Conn輸出端的一條或多條消息調(diào)用 MVector.push＿back（m）方法將消息加入m.toAgent所列出的Agent的消息中；If Conn.type＝＝Xor則依據(jù)Conn中所給出的限制條件選擇Conn輸出端的一條消息，使用 MVector.push＿back（m）方法將消息加入m.toAgent所列出的Agent的消息集中。

步驟4 若SD圖中沒有可解析的消息m，算法終止。

算法2對(duì)SD圖中的消息依序逐個(gè)進(jìn)行處理，算法時(shí)間復(fù)雜度為O（n），其中n為消息個(gè)數(shù)。

3.3 測(cè)試路徑的生成

在給出生成路徑算法前，先給出幾個(gè)函數(shù)定義：①CreateGT（m）建立消息m對(duì)應(yīng)的目標(biāo)規(guī)劃樹；②AddGS（t）將目標(biāo)規(guī)劃樹t放入 AgentGoal集合中；③isExist（m.type）判定Agent是否處理過同類問題。

算法3：生成測(cè)試路徑

輸入：消息集合

輸出：測(cè)試路徑

步驟1 對(duì)任一消息m∈MessageSet，使用isExist（m.type）判定Agent是否實(shí)現(xiàn)過同類型的目標(biāo)，if（isExist（m.type）＝＝true）當(dāng)環(huán)境條件沒有改變時(shí)，直接用已有的目標(biāo)規(guī)劃樹解決該問題。否則轉(zhuǎn)到步驟2.

步驟2 調(diào)用CreateGT（m）建立消息m對(duì)應(yīng)的目標(biāo)規(guī)劃樹t，并調(diào)用AddGS（t）將目標(biāo)規(guī)劃樹t放入Agent－Goal集合中，當(dāng)消息集合中仍有消息m未被處理時(shí)轉(zhuǎn)到步驟1，否則轉(zhuǎn)到步驟3。

步驟3 對(duì)任一t∈AgentGoal調(diào)用算法1來確定Agent實(shí)現(xiàn)每棵目標(biāo)規(guī)劃樹的行為軌跡，如果所有t都處理完成，算法終止。

算法3需要處理消息集合中的所有消息，每個(gè)消息對(duì)應(yīng)一個(gè)目標(biāo)規(guī)劃樹需要進(jìn)行遍歷處理，算法的時(shí)間復(fù)雜度為O（n2），消息個(gè)數(shù)為n遍歷目標(biāo)規(guī)劃樹的復(fù)雜度為n。

3.4 測(cè)試用例的生成

依據(jù)算法2提取SD中的所有消息并結(jié)合算法3構(gòu)造目標(biāo)規(guī)劃樹，使用算法1判定所有可能的規(guī)劃所生成的測(cè)試路徑同時(shí)結(jié)合MBC和PBC標(biāo)準(zhǔn)可以生成完備的測(cè)試用例。

算法4：測(cè)試用例生成算法

輸入：測(cè)試路徑

輸出：測(cè)試用例

步驟1 令pNode為指針型變量指向TP中的每個(gè)結(jié)點(diǎn)，變量InData為Vector＜Pair＜String，Sting＞ ＞型用于存放動(dòng)作的前置條件和具體內(nèi)容，OutData為Vector＜Pair＜InDateType，OutDateType＞ ＞型用來存放測(cè)試用例的輸入與期望的輸出。

步驟2 對(duì)每條測(cè)試路徑TPi（TPi∈TP）遍歷TPi中的每個(gè)結(jié)點(diǎn)，令pNode指向起始結(jié)點(diǎn)，while（pNode?。紼ndNode）將每個(gè)動(dòng)作結(jié)點(diǎn)的限制條件和動(dòng)作信息存入容器中，即 InData.push ＿back （make＿Pair＜pNode－＞guard，pNode－＞content＞），然后將pNode＋＋，指向下一個(gè)動(dòng)作結(jié)點(diǎn)，從while循環(huán)退出后，將終止結(jié)點(diǎn)的信息進(jìn)行處理存入容器InData中；

步驟3 對(duì)InData容器中的每個(gè)內(nèi)容IntData［i］進(jìn)行處理，分析InData［i］.second的內(nèi)容，使用OutData.push＿back （make＿pair （In，out））將InData ［i］.second對(duì)應(yīng)的測(cè)試數(shù)據(jù)存入容器OutData中。當(dāng)容器中所有消息處理完后，算法終止。

算法4：主要依據(jù)算法3生成的測(cè)試用例進(jìn)行測(cè)試用例的生成，算法的時(shí)間復(fù)雜度為O（n），n為測(cè)試路徑TP的數(shù)目。

4 實(shí) 驗(yàn)

為了對(duì)本文測(cè)試方法進(jìn)行檢驗(yàn)，設(shè)計(jì)了3組實(shí)驗(yàn)。第一組實(shí)驗(yàn)用來驗(yàn)證通過目標(biāo)規(guī)劃樹生成Agent行為軌跡的有效性；第二組實(shí)驗(yàn)用來驗(yàn)證測(cè)試路徑生成方法的有效性；第三組實(shí)驗(yàn)用來驗(yàn)證生成測(cè)試用例的有效性。

本文選擇文獻(xiàn) ［11］經(jīng)典實(shí)例來展示所給出算法的正確性。Agent的信念集中存放的是關(guān)于環(huán)境的信息，使用位置表格L＝ ｛0…MAX｝× ｛0…MAX｝，l∈L表示環(huán)境中具體的一個(gè)位置，對(duì)于一個(gè)給定位置l所含的垃圾數(shù)目為m（l），還有關(guān)于垃圾箱位置的集合b∈l，h表示Robot所攜帶的垃圾數(shù)量，c表示Robot最多可攜帶的垃圾數(shù)。Robot的Goal是清除所有的垃圾，即任何一個(gè)l∈L，使得v（l）＝0。Robot可用的動(dòng)作見表2。

表2 Robot可用的動(dòng)作列表

4.1 目標(biāo)規(guī)劃樹生成BDI Agent行為軌跡有效性驗(yàn)證

Agent程序可以處理如下情況：

若robot沒有攜帶垃圾且當(dāng)前位置沒有垃圾，就explore；

若robot沒有攜帶垃圾且當(dāng)前位置有垃圾，就Pick；

若robot攜帶垃圾但當(dāng)前位置沒有垃圾箱b，就movetobin；

若robot攜帶垃圾且當(dāng)前位置有垃圾箱，就drop；

上述情況有些plan中含有相應(yīng)子目標(biāo)要實(shí)現(xiàn)，如movetobin需要知道b的具體位置，也需要?jiǎng)e的plan處理。實(shí)例中Agent程序的目標(biāo)規(guī)劃樹如圖4所示。

圖4 Robot的目標(biāo)規(guī)劃樹

使用算法1處理上圖目標(biāo)規(guī)劃樹，可以得出5條行為序列，即：S1＝＜CleanGoal，Plan1，Action1＞，S2＝＜CleanGoal，plan2，F(xiàn)indWp，Action2＞，S3＝ ＜Clean－Goal，Plan2，CallHelpP，Action3＞，S4＝＜CleanGoal，Plan3，F(xiàn)indBP，Action4＞，S5＝ ＜CleanGoal，Plan3，CallHelpP，Action5＞。

使用算法4處理上述5條行為序列，可分別得到相應(yīng)的測(cè)試序列。如S2行為序列對(duì)應(yīng)的測(cè)試用例為＜t＞0，belief.l?。絙，belief.b＝0，Pick（）；v（p）＝0＞表示當(dāng)位置p有垃圾且robot不知道垃圾箱b的位置，自己尋找垃圾箱，最后執(zhí)行pick（）操作，作用的結(jié)果為v（p）＝0；

4.2 測(cè)試路徑生成方法有效性驗(yàn)證

選擇文獻(xiàn) ［12］中的網(wǎng)上購物系統(tǒng)、E－Learning系統(tǒng)、機(jī)票預(yù)訂系統(tǒng)、E－Novel系統(tǒng)和電子拍賣系統(tǒng)，并選取文獻(xiàn)［3，4］的方法與本文所提基于AUML生成測(cè)試路徑的方法進(jìn)行對(duì)比。

文獻(xiàn) ［3］完全采用OO的方法對(duì)UML序列圖的模型進(jìn)行處理，并未考慮BDI的特性。文獻(xiàn) ［4］使用ESM單純考慮Agent的頻繁出現(xiàn)的狀態(tài)，將BDI的運(yùn)行嵌入到ESM的狀態(tài)轉(zhuǎn)換中，在同等條件下，基于ESM的方法生成的測(cè)試路徑具有局限性。由表3中可以看出，本文的方法較文獻(xiàn)［3，4］相比，結(jié)點(diǎn)數(shù)比文獻(xiàn) ［3］多、比文獻(xiàn) ［4］少，但邊數(shù)比兩者都多。這是因?yàn)槲墨I(xiàn) ［3，4］并沒有完全考慮BDI和MAS的交互，因此它們進(jìn)行的測(cè)試是不完備的。

表3 文獻(xiàn) ［3，4］方法與本文基于AUML方法對(duì)比

4.3 測(cè)試用例生成有效性驗(yàn)證

本文以文獻(xiàn) ［12］的系統(tǒng)為測(cè)試對(duì)象，圖5至圖7為文獻(xiàn) ［12］與本文的測(cè)試用例數(shù)目、檢測(cè)錯(cuò)誤數(shù)與檢測(cè)錯(cuò)誤率的情況。

由圖5可知，本文的測(cè)試用例數(shù)目要多于文獻(xiàn) ［12］，這是因?yàn)槲墨I(xiàn) ［12］采用的角色模型對(duì)BDI的特性沒有完備的考慮，本文基于目標(biāo)規(guī)劃樹考慮Agent的行為，增加了問題的規(guī)模，所需要考慮的測(cè)試場(chǎng)景也多于文獻(xiàn) ［12］，所以測(cè)試用例有所增加。

由圖6可知本文所檢測(cè)的錯(cuò)誤數(shù)不低于文獻(xiàn) ［12］所檢測(cè)的錯(cuò)誤數(shù)，圖7很好的說明了本文與文獻(xiàn) ［12］相比，檢測(cè)錯(cuò)誤率也有一定程度的提高。雖然隨著系統(tǒng)規(guī)模的增大，錯(cuò)誤的檢測(cè)率會(huì)有所下降，同時(shí)目標(biāo)規(guī)劃樹的規(guī)模也會(huì)指數(shù)級(jí)的增長，對(duì)硬件的負(fù)荷也相應(yīng)增大，這也是本方法的一個(gè)需要改進(jìn)的不足之處。但總體來說，本文所提方法還是能夠很好的處理基于BDI Agent所開發(fā)的軟件。

5 結(jié)束語

本文主要研究BDI型Agent軟件的測(cè)試用例自動(dòng)生成方法。該方法直觀的刻畫出了BDI的運(yùn)行軌跡，確定了單個(gè)Agent的運(yùn)行軌跡，解決了AUML序列圖SD到Agent執(zhí)行目標(biāo)規(guī)劃樹之間的轉(zhuǎn)換，對(duì)AUML模型的分類器進(jìn)行了不同的處理，從目標(biāo)規(guī)劃樹的結(jié)點(diǎn)提取出測(cè)試用例生成所需要的輸入、輸出、前置條件等信息，該方法不需要的SD圖做任何的修改同時(shí)不需要人工干預(yù)測(cè)試過程，很好的實(shí)現(xiàn)了BDI型Agent的自動(dòng)化測(cè)試。

下一步的研究工作是在保證測(cè)試用例有效性的前提下，考慮BDI的動(dòng)態(tài)更新以及Agent所處環(huán)境的動(dòng)態(tài)變化對(duì)測(cè)試過程的影響，并同時(shí)簡化測(cè)試步驟，得到一個(gè)基于AUML模型更加高效、實(shí)用的測(cè)試方法。

［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的程序設(shè)計(jì)的研究 ［J］.軟件學(xué)報(bào)，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的軟件設(shè)計(jì)開發(fā)方法 ［M］.北京：機(jī)械工業(yè)出版社，2009：200－215.］

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

［10］Hong－h(huán)an 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.