基于DFA復(fù)合式Agent模型的設(shè)計與實現(xiàn)

盧薇薇，蔡自興，文志強，陳愛斌

(中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙，410083)

多移動體的多目標協(xié)作跟蹤一直是計算機視覺中極富挑戰(zhàn)性的問題，隨著機器人硬件設(shè)施、計算機網(wǎng)絡(luò)技術(shù)的快速發(fā)展，機器人團隊完成復(fù)雜任務(wù)的能力也越來越強。目前，人們對多目標協(xié)作跟蹤的研究著重于多Agent系統(tǒng)的體系結(jié)構(gòu)、任務(wù)分配、運動協(xié)調(diào)及控制、可重構(gòu)機器人等方面[1-2]。要解決在未知環(huán)境中協(xié)作檢測與跟蹤動態(tài)多目標問題，要求多Agent系統(tǒng)和單個Agent模型均具有合理和先進的體系結(jié)構(gòu)，即保證異步的通過多機器人上的Agent模型對環(huán)境進行實時觀察，并解決局部問題，又通過同步整個多Agent系統(tǒng)之間的信息，保證信息的實時性和準確性，進而根據(jù)全局信息進行決策。多移動機器人協(xié)同的體系結(jié)構(gòu)主要有集中式、分布式和復(fù)合式。近年來，在多目標協(xié)作檢測及跟蹤方面所牽涉的多Agent系統(tǒng)的體系結(jié)構(gòu)，大多是采用分布式或復(fù)合式來進行調(diào)控，比較典型的有 GOFER[3]，MURDOCH[4]，KAMARA和ALLIANCE等[5]。ALLIANCE體系結(jié)構(gòu)可使機器人實現(xiàn)基于區(qū)域進行協(xié)同檢測和跟蹤。Ukita等[6]使用一種Active Vision Agents (AVAs)的三層交互結(jié)構(gòu)，研究了室內(nèi)環(huán)境下固定底座可轉(zhuǎn)動攝像頭檢測跟蹤動態(tài)多目標的情況。相對而言，多Agent 系統(tǒng)中的主要組成部分即Agent模型主要集中在單Agent的理論與體系結(jié)構(gòu)上。例如：BDI(Belief, Desire, Intention)結(jié)構(gòu)的實用推理Agent[7-8]；歸類式結(jié)構(gòu)的反應(yīng)式Agent等[9]。在多移動體的多目標協(xié)作跟蹤中，由于目標和 Agent均是動態(tài)的，實時性高，且個體性能有限等，因而，這些Agent模型存在一定的局限性：在大量Agent需要進行信息交互的情況下，它們不能通過思維狀態(tài)獲取環(huán)境信息指導(dǎo)動作，并且不能與當前其他Agent群體進行信息交互的團隊協(xié)作，從而不能計算出精確性更高的結(jié)果[10-11]。由于意圖在實用推理中的重要性以及它在邏輯上并不能歸結(jié)為信念和愿望，因此，在具體應(yīng)用時，應(yīng)針對實際需求舍棄BDI框架的部分描述能力，并進行改進[12-13]。為了較好地解決多移動體的多目標協(xié)作跟蹤中信息和決策的同步與異步問題，本文作者以從BDI理論模型發(fā)展而來的復(fù)合式Agent模型為原型，提出了1個基于有限狀態(tài)自動機的Agent模型，可適用于集中式、分布式和復(fù)合式的多 Agent多目標協(xié)作跟蹤系統(tǒng)。

1 基于有限狀態(tài)自動機的Agent模型結(jié)構(gòu)設(shè)計

1.1 復(fù)合式Agent

復(fù)合式Agent是以BDI為理論模型在Agent內(nèi)組合多種相對獨立和并行執(zhí)行的智能形態(tài)，其結(jié)構(gòu)包括感知、動作、反射、建模、規(guī)劃、通信和決策等模塊，改進前后的復(fù)合式Agent模型結(jié)構(gòu)如圖1所示。Agent通過感知模塊來反映現(xiàn)實世界，并對環(huán)境信息進行抽象，再送到不同的處理模塊。若感知到簡單或緊急情形，信息就被送入反射模塊，做出決定，并把動作命令送到行動模塊，產(chǎn)生相應(yīng)的動作[14]。從1個Agent的社會性來看，這樣的Agent個體之間是沒有差異的，它們通過自身的智能形態(tài)，改變環(huán)境，而在大量需要合作的情形下，環(huán)境希望Agent相互之間通過某種形態(tài)體現(xiàn)出合作的主動性和可靠性[15-16]。而BDI理論支持的Agent模型更偏重于個體思維狀態(tài)所指引的動作與環(huán)境信息的混合[17]。因此，采用一定的方法使Agent模型自身提供1個抽象的整體形象負責和對外的進行信息交互，對內(nèi)處理問題的分解和局部問題的優(yōu)化有重要的意義。

1.2 結(jié)合有限狀態(tài)自動機(DFA)對復(fù)合式 Agent的改進

有限狀態(tài)自動機是計算理論中計算模型的一種，可以自動識別符合定義的任何一種語言，表示為其中，Q是1個有窮集，它的每個元素均表示當前系統(tǒng)的1個狀態(tài)，這些狀態(tài)在接收到可接受的輸入符號Σ時，將會按照轉(zhuǎn)移函數(shù)δ從一個狀態(tài)準確地轉(zhuǎn)移到下一個后繼狀態(tài)。當集中為F 終態(tài)時，表示可以結(jié)束輸入[18]。本文對Agent模型的討論以基于1個黑板模型[19]的服務(wù)器端為上層監(jiān)控，可接受Agent個體信息交互控制的客戶端/服務(wù)器模式復(fù)合式多Agent系統(tǒng)。改進后的復(fù)合式Agent模型主要包括如下部分：用DFA所維持的行為狀態(tài)模型、建模部分、意外處理、決策生成、模塊庫、通信模塊和動作執(zhí)行器與感知器。其中，意外處理和決策生成組成了行為決策層的實現(xiàn)實體，體現(xiàn)了對Agent自身愿望和意圖的維護。

圖1 改進前后的復(fù)合式Agent模型結(jié)構(gòu)Fig.1 Structure of complex agent without and using DFA

基于有限狀態(tài)自動機的 Agent模型對復(fù)合式Agent模型的改進主要在如下2個方面：

(1) 設(shè)計了 1個以有限狀態(tài)自動機為基礎(chǔ)的行為狀態(tài)模型。在該模型中，感知器從外界環(huán)境獲取信息后，通過行為狀態(tài)模型的不同狀態(tài)，進行選擇性建模。狀態(tài)轉(zhuǎn)移條件可以定義為其他Agent發(fā)送的請求或自身根據(jù)環(huán)境信息做出的決策。通過行為狀態(tài)模型，可將個體思維狀態(tài)所指引的動作與環(huán)境信息的混合進行了有效的分離，增加了Agent模型設(shè)計的可擴展性。

(2) 通過行為狀態(tài)的體現(xiàn)，對 Agent模型的表現(xiàn)形式進行抽象，使Agent模型之間的社會性和協(xié)作性得到了提高。以行為狀態(tài)為指標從社會的角度對Agent群體進行團體的劃分，直觀的區(qū)分可實時靈活調(diào)度的Agent個體，可分簇進行團隊任務(wù)的Agent個體和處于不同優(yōu)先級的任務(wù)中的Agent個體等。服務(wù)器端和不同的Agent群體以團隊為單位來進行交流。團隊中以選定的領(lǐng)隊為中心，該領(lǐng)隊對上負責獲取服務(wù)器端和其他Agent團隊的信息，對下獲取目前該團隊中其他Agent個體的信息，并根據(jù)所獲取的團隊信息進行融合與重建，以一個整體的形式對外提供有效信息。每個Agent個體則負責與團隊中其他Agent個體進行信息交流并負責管理自己內(nèi)部各個傳感器獲取的信息。Agent個體通過各個模塊對獲取的各種信息進行處理與整合，并根據(jù)歷史信息與其他Agent協(xié)商且做出相應(yīng)決策。

2 行為狀態(tài)模型的設(shè)計

2.1 Agent個體行為分析

有限狀態(tài)自動機維持的行為狀態(tài)模型定義如下。

定義1 全自動狀態(tài)：在Agent行為過程中，在沒有其他Agent和服務(wù)器端黑板模型的信息支持的情況下，能夠自主地完成目標發(fā)現(xiàn)和跟蹤的任務(wù)，并能自主搜尋其他Agent個體的狀態(tài)，被稱為全自動狀態(tài)。

定義2 半自動狀態(tài)：在Agent行為過程中，在指定協(xié)作的情形下，Agent接受特定指令，跟蹤搜尋指定目標，與已知的Agent進行通信，協(xié)作完成任務(wù)，不能隨意放棄現(xiàn)有任務(wù)，進行其他非授權(quán)的自主行為，被稱為半自動狀態(tài)。

1個社會性的群體在需要協(xié)作的團隊精神時，會希望對Agent的權(quán)限有所限制和區(qū)分。在半自動狀態(tài)中，服務(wù)器上層監(jiān)控首先針對任務(wù)和Agent個體狀態(tài)劃分Agent群體，然后，該群體中的Agent個體針對群體分配任務(wù)和權(quán)限，通過與服務(wù)器及群體中其他成員聯(lián)系獲取詳細的目標信息，有針對性地等待和搜尋丟失的目標。而全自動狀態(tài)下的Agent個體，可以自主獨立運行，獨立決策，也可以與其他Agent群體協(xié)商決策，或根據(jù)服務(wù)器端黑板模型的信息進行決策，并且對任務(wù)的完成沒有強制性，如果能力不夠，就不去進一步進行搜尋來強制完成任務(wù)。

2.2 DFA設(shè)計

由于Agent個體行為表現(xiàn)的固定性，全自動狀態(tài)和半自動狀態(tài)下的有限狀態(tài)自動機的狀態(tài)集是一致的，2個狀態(tài)可以根據(jù)現(xiàn)實環(huán)境和任務(wù)需求自由轉(zhuǎn)換。復(fù)合式Agent上維持行為狀態(tài)模型的有限狀態(tài)自動機可以通過探測的環(huán)境信息 I、需要完成的任務(wù)信息 M和人為的指定信息H，以N=f (I, M, H)為選擇指標來選擇。

為了在1個實時性強、交互性強的多Agent系統(tǒng)中保證每個Agent模型與其他Agent能夠協(xié)作自主地完成動態(tài)多目標協(xié)作檢測跟蹤的任務(wù)，構(gòu)建了1個有限狀態(tài)自動機來描述Agent個體在現(xiàn)實環(huán)境中的行為狀態(tài)，表示成數(shù)學(xué)模型為，其詳細介紹如下。

(1) 1個狀態(tài)的有窮集合：

其中：Wait為等待狀態(tài)；Detect為檢測狀態(tài)；Track為跟蹤狀態(tài)；Lost為目標丟失狀態(tài)；Busy為忙碌狀態(tài)。當多Agent協(xié)作完成任務(wù)時，為了資源最優(yōu)分配，協(xié)作的部分Agent會接收命令后處于Busy狀態(tài)，其優(yōu)先級最高，不可被中斷，所接收的命令處于命令列表中，按照時序完成。協(xié)作的Agent接收的命令來自服務(wù)器端或協(xié)作的Agent群體的管理者，服務(wù)器端會根據(jù)實時環(huán)境或任務(wù)情形對Agent分布進行干擾。而Agent群體的管理者針對當前任務(wù)管理協(xié)作的Agent群體，通過對 Agent個體發(fā)送指令保證資源利用最大化。Agent個體接受指令后會保存當前被中斷的狀態(tài)信息，進入Busy狀態(tài)完成任務(wù)。Wait狀態(tài)為Agent準備狀態(tài)，而其他3個狀態(tài)管理與實現(xiàn)了Agent個體對目標的有效跟蹤。

(2) 可接受的輸入集合Σ，它指明了所有允許輸入的符號，有限狀態(tài)自動機根據(jù)該集合中的符號進行狀態(tài)的變化。這個集合中包括7個可輸入的符號，它們代表在實際中相應(yīng)的物理事件的發(fā)生：

其中：connect和unconnect表示Agent個體視頻設(shè)備連接或斷開；findobj和lostobj表示Agent個體在現(xiàn)有狀態(tài)下，通過當前獲取的視頻圖像和已知信息在視野可及的范圍內(nèi)搜尋到1個運動目標或在此情況下無法找到1個和歷史信息吻合的目標；work和finishwork表示Agent個體接受服務(wù)器指定任務(wù)或已完成指令隊列中所有的任務(wù)。接收到work指令時，對Agent個體當前狀態(tài)和相關(guān)信息進行保存，再去進行相應(yīng)任務(wù)。執(zhí)行finishwork指令時，從所保存的數(shù)據(jù)中獲取任務(wù)完成前的狀態(tài)信息，恢復(fù)到任務(wù)執(zhí)行之前的狀態(tài)。order表示Agent個體接受服務(wù)器的指令，轉(zhuǎn)換到新的狀態(tài)，完成指定的任務(wù)。

(3) 起始狀態(tài)q0={Wait}和結(jié)束狀態(tài)F={Wait}。

(4) 轉(zhuǎn)移函數(shù)δ是Q×Σ→Q的一個映射，被有限狀態(tài)自動機所識別。有限狀態(tài)自動機轉(zhuǎn)移函數(shù)如圖 2所示，其中：實線為有限狀態(tài)自動機各種狀態(tài)下通用的轉(zhuǎn)移函數(shù)，短虛線為半自動狀態(tài)下有限狀態(tài)自動機特有的轉(zhuǎn)移函數(shù)，長虛線為全自動狀態(tài)下有限狀態(tài)自動機特有的轉(zhuǎn)移函數(shù)。

2.3 建模部分

由于半自動狀態(tài)下的DFA不具有較強的自主性，權(quán)限被大量限制，因此，主要通過全自動狀態(tài)下的DFA來對建模部分進行說明。建模部分的功能是通過外界信息的獲取、Agent自身有限狀態(tài)自動機中提供的狀態(tài)和模塊庫內(nèi)的功能模塊的選擇建立觀測到的目標模型和當前 Agent的抽象模型。為了保證當部分Agent個體檢測到目標后，能夠使得其他尚未檢測到目標的Agent個體準確地搜尋到目標，目標模型的描述應(yīng)具有可重建性。在設(shè)計中，對于目標的描述采用了2個不變量(顏色信息與輪廓信息)和1個可變量(區(qū)域信息)來表示，它們通過大量的信息保證了對目標重建的可靠性[20]。HSV色彩空間中顏色不變量和完整輪廓信息的選取既可在檢測中減少由光線、陰影、遮擋和旋轉(zhuǎn)等帶來的干擾，又可在信息傳輸后，迅速地表述所描述的目標，因此，跟蹤采用的算法主要通過基于顏色的 Meanshift算法來實現(xiàn)。為了實現(xiàn)對動態(tài)目標檢測跟蹤，在不同的狀態(tài)下將調(diào)用不同的功能模塊。整個有限狀態(tài)自動機結(jié)合所需的功能模塊對Agent的自主行為規(guī)劃進行了完整的覆蓋，狀態(tài)集中的 Detect狀態(tài)、Track狀態(tài)和Lost狀態(tài)這3種狀態(tài)的模塊調(diào)用方案如圖3所示。

2.3.1 Detect狀態(tài)

圖2 結(jié)合DFA的復(fù)合式Agent模型中有限狀態(tài)自動機轉(zhuǎn)移函數(shù)示意圖Fig.2 Transfer functions in complex Agent using DFA

Detect狀態(tài)有3個出度，其中：1個到Track狀態(tài)，1個到Busy狀態(tài)，1個到自身的循環(huán)。Detect狀態(tài)到Track狀態(tài)的轉(zhuǎn)換有findobj和order 2種方法。Findobj法是通過調(diào)用模塊庫中的基于三幀差的目標檢測，形態(tài)學(xué)去噪聲、目標分割、合并與提取等模塊完成對目標的查找；order法是與服務(wù)器端進行通信，接收跟蹤指定目標的指令，完成相應(yīng)的任務(wù)。Detect狀態(tài)到Busy狀態(tài)的轉(zhuǎn)換是由于接收到服務(wù)器端產(chǎn)生的指令 order而實現(xiàn)的強制轉(zhuǎn)換，而 Detect到自身狀態(tài)的循環(huán)的lostobj是和Detect到Track狀態(tài)的findobj所對應(yīng)的互補行為。

圖3 建模模塊調(diào)用方案Fig.3 Methods of combining modules through DFA

在全自動狀態(tài)下計算檢測運動目標，若可以計算出有效目標信息，則是findobj，它以滿足先到先得、跟蹤可視面積最大、目標與Agent個體距離最近為標準，選取最優(yōu)目標并進行動作轉(zhuǎn)換到Track狀態(tài)進行跟蹤，其他目標可進行基本的視覺跟蹤。若沒有跟蹤到目標，則是lostobj，回到Detect狀態(tài)繼續(xù)檢測。

2.3.2 Track和Lost狀態(tài)

Track狀態(tài)的出度有 2種狀態(tài)轉(zhuǎn)換：一種是findobj，若一直有效地跟蹤著當前目標，則維持跟蹤狀態(tài)；另一種是lostobj，丟失目標之后，轉(zhuǎn)入Lost狀態(tài)。進入跟蹤狀態(tài)的findobj動作有3種，但與Detect狀態(tài)的findobj和Track狀態(tài)相比，Lost狀態(tài)的findobj有所不同。Detect狀態(tài)的findobj找到的目標是預(yù)先未知的，而Track狀態(tài)和Lost狀態(tài)的findobj都是根據(jù)Detect狀態(tài)獲取的或者根據(jù)服務(wù)器端發(fā)送的已知目標信息來查找與跟蹤。

2.3.3 意外處理

在光線、物理慣性等各種不可預(yù)知的條件影響下，目標的意外丟失是很有可能出現(xiàn)的。因此，為了處理這種意外，為Agent個體設(shè)計了記憶和預(yù)測功能。它們在對 Track與 Lost狀態(tài)進行轉(zhuǎn)換的過程中起輔助作用。

記憶是Agent個體在Track狀態(tài)的同時，將已知信息在容器中進行保存的過程，它可分為短期記憶和長期記憶。短期記憶會記住Agent個體和目標最近所做的動作，而長期記憶會記住在跟蹤目標的整個過程中，所得到的Agent個體和目標移動的路徑。在獲取到一定量信息后，可以使用曲線擬合對Agent個體和目標移動的路徑的信息進行歸納。在Agent個體的客戶端上，由于性能限制、圖像數(shù)據(jù)處理和通信等大量任務(wù)，只需要考慮對部分數(shù)據(jù)進行直線或簡單的曲線擬合。服務(wù)器端會對總體的數(shù)據(jù)進行計算。

預(yù)測是根據(jù)歷史信息計算與分析目標下個時刻將出現(xiàn)的位置的過程。當計算目標的面積小于某個閾值時，可認為目標丟失，則進入Lost狀態(tài)。短期記憶中最近所做的動作影響最大，其他的起輔助檢驗工作。根據(jù)短期記憶完成的1～2個動作來查找目標，若失敗，則通過獲取長期記憶的多項式曲線擬合出的目標軌跡找到目標接下來的角度，轉(zhuǎn)到預(yù)測到的角度來進行觀測。若在一定時限內(nèi)都無法找到目標，則認為目標確實丟失，發(fā)送信息到服務(wù)器端，并根據(jù)情況進行狀態(tài)轉(zhuǎn)換。

3 實驗結(jié)果

本文用2個不同實驗來測試提出模型的有效性。硬件實驗平臺為：AmigoBot改造后的MORCS-2及其團隊，最大運動速度 750 mm/s，處理器速度為 677 MHz，內(nèi)存為 512 Mb，攝像頭為長城攝像頭GWS-1320，130萬像素，無線網(wǎng)卡TL-WN321G，最大傳輸速度 54 Mb/s；軟件實驗平臺為：操作系統(tǒng)Windows XP，編程環(huán)境為Microsoft Visual Studio .NET 2003，編程語言為C++，服務(wù)器端采用黑板模型，支持以人作為監(jiān)督者的遙操作和全自主協(xié)作2種工作模式，客戶端為AmigoBot平臺上設(shè)計改進后的結(jié)合DFA的復(fù)合式Agent模型；網(wǎng)絡(luò)環(huán)境為基于簇的按需路由通信方式的Ad-hoc網(wǎng)絡(luò)，通信遵循IEEE802.11b/g無線通信標準。實驗環(huán)境為室內(nèi)，均勻自然光照。

3.1 固定路線的目標跟蹤實驗

在1個區(qū)域內(nèi)，1個獨立的Agent在使用結(jié)合DFA的復(fù)合式Agent和使用不帶DFA的復(fù)合式Agent模型2種情形下，跟蹤1個固定路線的目標，對其跟蹤定位，并分析誤差。跟蹤路線如圖4(a)所示。

3.1.1 理論路線的確定方法

在理論路線計算時，可認為Agent啟動與運動過程中的速度變化是瞬時完成的，Agent在運行過程中能維持勻速運動，每次Agent旋轉(zhuǎn)的偏移角度為θ。當目標和Agent在1條直線上時，理論路線為直線段，當目標和Agent不處于1條直線上時，但θ≥45?時，Agent的路線也為直線段；當θ＜45?時，Agent的路線為由|90?/θ|-1段直線組成的折線段，具體計算方法如下：

獲取理論路線的示意圖如圖4(b)所示?？梢姡寒斈?--標-→到達S1點時，Agent到達S0點，目標改變方向沿方向行走，則Agent行走路線為 。設(shè) S0與 S1之間距離為s，目標運動速度為v1，Agent速度為v2(已知v2略大于v1)。當目標從S1出發(fā)，到達b1點時，Agent從S0出發(fā)，到達a0點。由于目標已經(jīng)到達Agent視野的臨界點，因此，Agent以轉(zhuǎn)動θ為單位調(diào)整方向繼續(xù)跟蹤，行走路徑將沿著a0到b1方向進行。當目標從 b1點行進到 b2點時，Agent也從 a0點行進到 a1點。設(shè)從 S0到 a0的時間為t0，a0到a1的時間為t1…an到S2的時間為tn+1。s與θ為已知，要得知Agent的路徑，即求解出t0, t1, …, tn+1。其中：當θ≥45?時，只需要計算r=0的情況，便可得出直線路徑。

從式(1)和式(2)可計算 t0, t1, …, tn+1，并可得到Agent行走的理論路線。從圖4可得：帶DFA的Agent行走 路線比不帶DFA的Agent行走的路線具有更優(yōu)效果。

圖4 帶DFA模型的Agent個體和不帶DFA模型的Agent個體對固定路線目標的跟蹤Fig.4 Path data generated by agent using DFA and without DFA

3.1.2 目標跟蹤實驗結(jié)果比較

結(jié)合DFA的復(fù)合式Agent個體和使用不帶DFA的復(fù)合式 Agent個體在跟蹤同一個固定路線的目標時，將它們的跟蹤實際路線與式(1)和式(2)計算的Agent個體跟蹤理論路線進行比較，可見：結(jié)合DFA的復(fù)合式Agent個體有較明顯的性能優(yōu)勢。其主要原因在于：使用不帶DFA的復(fù)合式Agent個體將直接調(diào)用模塊庫中的模塊進行建模，且和服務(wù)器交流的信息中不帶狀態(tài)信息。所獲取的外界信息和與服務(wù)器交流的信息中，只能帶有當前是否找到目標、是否在跟蹤目標等標志位信息。如果目標丟失后，通過意外處理進行搜索，搜索不到則自動繼續(xù)檢測。但是檢測狀態(tài)下傳回的Agent個體信息將和丟失狀態(tài)傳回的Agent個體信息將不會被加以區(qū)分，因此，意外處理性能將下降，跟蹤效果變差。

選擇在相同時間點的Agent個體實際路徑上的位置(',')x y 與理論路徑上的位置(x, y)之間的偏差作為標準來衡量Agent個體的目標跟蹤效果。對于改進前后的方法分別均勻取30個時間點，并分別計算實際路線與理論路線偏差，結(jié)果如圖5所示。帶DFA模型的Agent個體行走路線相對與不帶DFA模型的Agent個體行走路線偏差較小，主要是3個直角處偏差較大，第1個直角處，目標與Agent個體之間有一段初始距離，因此，Agent個體的拐彎較大，偏差也最大。而由于Agent個體速度略大于目標，因此，在第1個拐彎之后，Agent個體已經(jīng)和目標保持了一個穩(wěn)定的跟蹤距離，后2個拐彎的偏差相對較小，但還是比直線距離跟蹤偏差大。通過計算所取的樣本均值，可得偏差的期望信息，結(jié)果如表1所示。可見，帶DFA模型的Agent個體行走路線偏差期望值約為不帶DFA模型的Agent個體行走路線偏差期望值的一半。再通過樣本方差來計算2種路線的樣本波動大小，可知帶DFA模型的Agent個體行走路線中樣本波動較小，約為不帶DFA模型的Agent個體行走路線樣本方差的一半。

圖5 實際位置與理論位置的偏差比較Fig.5 Errors generated by agent using DFA and without DFA

表1 不同Agent個體行走路線的平均偏差與樣本方差Table 1 Expected values of error and sample variant generated by agent using DFA and without DFA

3.2 基于區(qū)域的目標跟蹤實驗

基于區(qū)域的目標跟蹤實驗[21]是多目標動態(tài)檢測與跟蹤研究中經(jīng)常使用的一種實驗手段，可通過這種實驗驗證所設(shè)計的結(jié)合DFA的復(fù)合式Agent個體的可行性。由于使用不帶DFA的復(fù)合式Agent個體的跟蹤性能較為自主，在協(xié)作跟蹤時可調(diào)度性較差，在協(xié)同檢測自由路線多目標并實時進行協(xié)同跟蹤時難以完成任務(wù)，因此，可以通過使用多個具有結(jié)合DFA的復(fù)合式Agent個體模型的機器人在該實驗中完成多目標跟蹤任務(wù)，由此驗證結(jié)合DFA的復(fù)合式Agent模型的可行性和其在協(xié)同上的優(yōu)越性。在設(shè)計的實驗中，2個獨立的機器人各負責觀測一塊區(qū)域，它們需要保證當前被觀測的區(qū)域中所出現(xiàn)的動態(tài)目標均能被跟蹤，并記錄相關(guān)信息。跟蹤基本規(guī)則為：當1個自由路線的目標進入觀測區(qū)域時，若當前被觀測到的目標沒有被其他機器人跟蹤，則對其進行跟蹤；若當前目標已有機器人對其跟蹤，則根據(jù)機器人當前處于的跟蹤狀態(tài)、機器人負責觀測區(qū)域的目標出現(xiàn)概率、機器人和觀測點的距離等因素計算2個機器人之間的競爭成本，成本較低者將獲得該目標的跟蹤權(quán)限，而競爭失敗者，將回到自己負責的區(qū)域觀測點繼續(xù)進行觀測。實驗結(jié)果如圖6所示。實驗步驟如下：

(1) 實驗開始時，機器人1和機器人2并行排列，各負責一塊區(qū)域進行觀測，自由路線目標A進入機器人1的觀測區(qū)域。

(2) 機器人1在觀測區(qū)域觀測到目標A后，和機器人2通信得知尚未有機器人跟蹤目標A，機器人1獲得權(quán)限對目標A進行跟蹤，如圖6 (a)所示。

(3) 目標A進入機器人2的觀測區(qū)域，機器人1和機器人2通信確認它們觀測著同一個目標，2個機器人進行成本計算。根據(jù)競爭成本計算的假設(shè)，相對于機器人2，機器人1具有較高的疲勞度，并距離區(qū)域觀測點更遠，計算出的競爭成本比機器人2的高，如圖6 (b)所示。

(4) 目標A繼續(xù)前進，機器人1放棄目標A的跟蹤，將回到區(qū)域觀測點繼續(xù)觀測，機器人2獲得目標A的跟蹤權(quán)限，對其進行跟蹤，如圖6 (c)所示。

(5) 目標A繼續(xù)前進，機器人2繼續(xù)跟蹤目標A，目標B出現(xiàn)在機器人1的觀測區(qū)域，機器人1觀測到目標B后，與機器人2通信后，確認目標B的狀態(tài)和信息，并獲得權(quán)限跟蹤目標B，如圖6 (d)所示。

圖6 基于區(qū)域的目標跟蹤實驗(箭頭表示機器人和目標運動的方向)Fig.6 Region based multi-object tracking experiment (arrows indicate robots and objects moving directions)

4 結(jié)論

(1) 在復(fù)合式 Agent模型的基礎(chǔ)上，引入有限狀態(tài)自動機作為行為狀態(tài)模型進行擴展，并針對多機器人團隊多目標協(xié)作檢測與協(xié)作跟蹤的環(huán)境進行了設(shè)計。

(2) 在實際環(huán)境下通過單機器人承載改進前后的Agent模型進行固定路線目標的跟蹤，對模型性能進行分析，證明改進后的模型能明顯改善目標跟蹤的性能，跟蹤偏差的期望值與樣本方差均降為改進前的一半。

(3) 改進后的模型通過可自由轉(zhuǎn)換的 2種有限狀態(tài)自動機進行協(xié)作，為多機器人協(xié)作檢測和跟蹤動態(tài)多目標提供了有效途徑，實現(xiàn)了基于區(qū)域的目標跟蹤。

(4) 多 Agent群體分配算法優(yōu)化等方面有待進一步研究。

[1] 蔡自興, 陳白帆, 王璐, 等. 異質(zhì)多移動機器人協(xié)同技術(shù)研究的進展[J]. 智能系統(tǒng)學(xué)報, 2007, 2(3): 1-7.CAI Zi-xing, CHEN Bai-fan, WANG Lu, et al. The progress of cooperative technology for heterogeneous multiple mobile robots[J]. CAAI Transactions on Intelligent Systems, 2007, 2(3):1-7.

[2] Sukhatme G S, Montgomery J F, Mataric M J. Design and implementation of a mechanically heterogeneous robot group[C]//Proc of SPIE Conference on Sensor Fusion and Decentralized Control in Robotic Systems 2. Boston, 1999:122-133.

[3] Caloud P, Choi W, Lacombe J C. Indoor automation with many mobile robots[C]//Proceedings IEEE International Workshop on Intelligent Robotics and Systems’90. Tokyo, 1990: 67-72.

[4] Gerky B, Mataric M. Auction methods for multi robot control[J].IEEE Transactions on Robotics and Automation, 2002, 18(5):758-768.

[5] Parker L E. ALLIANCE: An architecture for fault tolerant multi-robot cooperation[J]. IEEE Transactions on Robotics and Automation, 1998, 14(2): 220-240.

[6] Ukita N, Matsuyama T. Real-time cooperative multi-target tracking by communicating active vision agents[J]. Computer Vision and Image Understanding, 2005, 97(2): 137-179.

[7] Rao A S, Georgeff M P. Modeling rational agents within a BDI-Architecture[C]//Proceedings of the Second International Conference on Principles of Knowledge Representation and Reasoning. San Mateo: Morgan Kaufmann Publishers, 1991:473-484.

[8] Brooks R. Intelligence without representation[J]. Artificial Intelligence, 1991, 47: 139-159.

[9] 黎建興, 毛新軍, 束堯. 軟件 Agent 的一種面向?qū)ο笤O(shè)計模型[J]. 軟件學(xué)報, 2007, 18(3): 582-591.LI Jian-xing, MAO Xin-jun, SU Rao. An object-oriented design model of software Agent[J]. Journal of Software, 2007, 18(3):582-591.

[10] 譚顯東, 胡兆光, 張克虎, 等. 構(gòu)造多 Agent模型研究差別電價對行業(yè)影響[J]. 中南大學(xué)學(xué)報: 自然科學(xué)版, 2008, 39(1):172-177.TAN Xian-dong, HU Zhao-guang, ZHANG Ke-hu, et al.Constitution of multi-agent to study influence of discriminating power price on sectors[J]. Journal of Central South University:Science and Technology, 2008, 39(1): 172-177.

[11] GAO Jian-hua, HU Xu-dong, WU Chuan-yu. Design and simulation of multi-robot logistic system[C]//Mechatronic and Embedded Systems and Applications, Proceedings of the 2nd IEEE/ASME International Conference. Beijing, 2006: 106-111.

[12] 龔濤, 蔡自興, 夏潔, 等. 分布式人工免疫系統(tǒng)的魯棒性歸約模型[J]. 中南大學(xué)學(xué)報: 自然科學(xué)版, 2007, 38(5): 956-961.GONG Tao, CAI Zi-xing, XIA Jie, et al. Reduction model of robustness for distributed artificial immune system[J]. Journal of Central South University: Science and Technology, 2007, 38(5):956-961.

[13] 蔡自興, 徐光祐. 人工智能及其應(yīng)用[M]. 北京: 清華大學(xué)出版社, 2004.CAI Zi-xing, XU Guang-you. Artificial intelligence: Principles and applications[M]. Beijing: Tsinghua University Press, 2004.

[14] Sipser M. 計算理論導(dǎo)引[M]. 張立昂, 譯. 北京: 機械工業(yè)出版社, 2000.Sipser M. Introduction to the theory of computation[M].ZHANG Li-ang, trans. Beijing: China Machine Press, 2000.

[15] Kanda A, Sato M, Ishii K. Environment recognition system based on multiple classification analyses for mobile robots[J].Journal of Bionic Engineering, 2008(5): 113-120.

[16] DeLoach S A, Valenzuela J L. An agent-environment interaction model[J]. Lecture Notes in Computer Science, 2007, 4405:1-18.

[17] Guerra-Hernandez A, Fallah-Seghrouchni A E, Soldano H.Learning in BDI multi-agent systems[C]//Proceedings of CLIMA IV: Computational Logic in Multi-Agent Systems. Berlin:Springer-Verlag, 2004: 39-44.

[18] 劉群, 夏虹. 多源信息融合系統(tǒng)的主動式黑板結(jié)構(gòu)與模型[J].哈爾濱工程大學(xué)學(xué)報, 2007, 28(5): 910-916.LIU Qun, XIA Hong. Active blackboard model and construction of multi-source information fusion system[J]. Journal of Harbin Engineering University, 2007, 28(5): 910-916.

[19] Gonzalez R C, Woods R E. Digital image processing[M]. 阮秋琦, 阮宇智, 譯. 北京: 電子工業(yè)出版社, 2003.Gonzalez R C, Woods R E. Digital Image Processing[M]. RUAN Qiu-qi, QUAN Yu-zhi, trans. Beijing: Electronics Industry Press,2003.

[20] Jung B, Sukhatme G S. Generalized region-based approach for multi-target tracking in outdoor environments[C]//Proceedings of 2004 IEEE International Conference on Robotics and Automation. New Orleans, LA, 2004: 2189-2195.

[21] Oswald N, Levi P. Cooperative vision in a multi-agent architecture[J]. Lecture Notes in Computer Science, 1997, 1310:709-716.