基于合同網的分布式動態任務分配算法

肖玉杰，李 杰，劉 方

(1.海軍工程大學 電子工程學院，湖北 武漢430033;2.海軍工程大學 動力工程學院，湖北 武漢430033;3.海軍工程大學 兵器系，湖北 武漢430033)

0 引 言

信息化技術在軍事領域的應用，使得動態任務分配問題成為提高協同作戰能力的關鍵［1］。一方面，戰場復雜多變，指揮決策系統需要對新產生的作戰任務動態分配;另一方面，各作戰平臺內部各節點作戰能力可能會發生變化，需要對未完成的任務快速有效的再分配。這就要求指揮決策系統選擇合理的分配策略，進行任務動態分配。故研究動態任務分配問題具有重要意義。

目前，用于實現多智能體系統(Multi- Agent System，MAS)智能控制的算法主要包括合同網模型、黑板模型、馬爾科夫決策過程模型、節點規劃方法、集合覆蓋理論和市場協議方法等［2］，其中合同網在動態任務分配方面取得了較好效果。合同網模型(Contract Net Protocol，CNP)是Smith R.G.和Davis R.提出的關于人物和資源分配的經典協調策略。其基本思想是節點之間通過“招標—投標—中標”這一市場機制進行任務分配，系統以較低代價、較高質量完成委托和承攬構成的合同關系。

合同網模型現已廣泛應用到機器人、編隊協同作戰、衛星和多UCAV［1-6］等領域。文獻［7］指出了任務分配的目標是代價最小，效能最大，并限制了允許分配的最大任務數以減小計算的復雜度。文獻［8］提出了利用包含價格和時間的代價時間Petri 網來模擬合同網的協商過程，完善了合同網的運行機制。文獻［9-10］在傳統合同網協議的基礎上引入信任度和懲罰機制，來限制發送標書的范圍和控制評價標書的數量來減少通信量。文獻［11］引入各種心智參數來對招標范圍進行限制，并設置緩沖池來限制投標者接收標書的數目，提出了一種自適應的投標策略，減少了合同網協議時的通信量。

本文在以上基礎上，針對傳統合同網的不足，有針對性地總結了基于聯盟、公告板及優先級的3 種合同網改進模型，解決了合同網在任務發布階段和協商階段的信息阻塞以及承諾失敗等問題，減少了系統的通信量，滿足控制系統實時性等要求，提高了協商效率，擴展了合同網模型的使用范圍，有助于MAS 在復雜大系統中的應用。最后介紹2 種常用的MAS 軟件仿真平臺-JADE和Repast 仿真平臺。

1 基本合同網任務分配算法

1.1 合同網基本思想

圖1所示為合同網的工程應用原理圖。在實際應用中，由于單個Agent 無法實現對現有任務的求解，需要多個節點之間的協作。其基本思想是“任務的解耦—任務的發布—任務的協商—任務的耦合”，最終得到復雜任務的控制決策結果，以較低消耗滿足系統在特定情況下的運行需求。

1.2 合同網運行機制

在合同網模型中，任務Agent 負責任務的解耦、發布和任務耦合，資源Agent 負責子任務的協商，保證任務的正常運行。其中，資源Agent 之間滿足對等關系，既是子任務的管理者，又是子任務的接收者，通過直接或間接的交互通信最終實現復雜任務的求解［12］。合同網的交互協商過程如圖2所示。

圖2 合同網的交互協商流程圖Fig.2 The flow chart of interaction and cooperation in CNP

1)任務Agent 發出任務信息CFP，將自己的任務或不能完成的任務用招標的信息向資源Agent 發布，等待資源Agent的反應信息，包括“投標”、“拒絕”和“不明”，直至到任務信息截止時間。

2)資源Agent 根據任務要求和自己的狀態進行投標，此時，資源Agent 等待任務Agent的反應時間，包括“拒絕”和“請求”，同時資源Agent 可以向其他任務Agent 發送任務的請求信息;

3)任務Agent 對任務的請求決策處理，選擇能夠滿足任務需求的最佳資源Agent，并發送任務執行邀請。參與者在接收到執行邀請后，如果向任務Agent 發送接收任務邀請的信息，則任務Agent 發出任務執行“接受”確認信息，向其他發送任務請求的資源Agent 發送“拒絕”信息。

4)執行任務的資源Agent 向任務Agent 提交任務的反饋信息，實現任務Agent 對任務的監督和管理。

1.3 任務分配基本描述

多Agent 任務分配問題是指各Agent 分布式的自主執行任務，由于任務類型的不同，各個Agent的能力不同，當發現新的任務時，各Agent 能夠根據當前態勢快速、合理實現任務的動態分配［3］。

下面以多無人水下潛航器 (Unmanned Underwater Vehicle，UUV)為研究對象，構建多UUV 協同作戰的動態任務分配模型。

任務效能定義［13］:AgentVi執行任務Tj的效能Ui(Tj)為完成任務的收益Rewardi(Tj)減去相應付出的代價Costi(Tj):

因為Rewardi(Tj)與Costi(Tj)具有不同的量綱，所以需要先分別對其進行歸一化處理，統一到相同的量綱后再進行相減。

設Vi執行對某目標的確認任務Tj，Vi對該類型目標的確認概率為(Tj)，Tj的任務價值為Value(Tj)，則Vi執行Tj的收益為:

設Vi執行對某目標的攻擊任務Tk，Vi對該類型目標的殺傷概率為(Tj)，則Vi執行Tk的收益為:

設Vi執行對某目標的毀傷評估任務T1，Vi對該類型目標的毀傷評估概率為(Tl)，則Vi執行T1的收益為:

得到任務效能的定義后，任務分配的目標可以描述為:

目標 3:使 UUV 完成任務所需的時間maxi∈VTimei(Si)為最小，其中Timei(Si)為Vi完成任務集Si的時間;

2 改進合同網任務分配算法

2.1 傳統合同網的不足

傳統的合同網模型可以成功解決一個任務在多個Agent 之間的分配問題，特別適合于單任務、單中標者、單回合的招標場景。MAS 利用合同網方法進行協商，雖可以實現任務分配，但隨著任務的復雜和系統環境的變化，表現出以下不足［14-15］:

1)任務發布階段，信息通信量大，資源消耗大

在傳統的合同網中，任務Agent 采用廣播的方式發送任務信息，獲取任務信息的任何Agent 都可以對任務信息作出“投標”響應，而自身不需要支付額外費用或作出某種承諾。這種不對招標范圍進行限制的運作機制，不僅浪費標書，造成系統通信的頻繁，甚至造成系統堵塞，加大任務Agent的決策負擔。

2)任務協商階段，協商次數多、計算量大，效率低

任務Agent 在任務分配和協商過程中，需要多次交互通信，并通過匹配實現系統的智能決策。這一過程，任務Agent和資源Agent 之間能力的獲取加大了系統的通信量，導致系統的相應時間變慢，協商成功率大大降低。

3)任務的耦合階段，容易出現流標現象

管理者在接收到所有投標后，經過評估，未發現合適的Agent 或者各個投標者在規定的時限內不能完成任務，則此次任務出現流標現象。

目前，對于合同網模型的改進從任務解耦階段到任務的耦合階段，最終的落腳點都是能否實現系統的智能決策和控制。合同網模型對系統智能控制的能力主要體現在系統之間的交互協商通信量和通信時間。

2.2 合同網改進模型

2.2.1 基于Agent 聯盟的改進合同網

在基于Agent 聯盟的合同網模型中，Agents 之間依據能力互補性、合作信任度和低通信代價的原則形成Agent 聯盟，不同聯盟之間存在競爭，聯盟內部即存在競爭又存在協作。這一改進模型是MAS競爭性和合作性的有效結合，充分發揮單個Agent問題求解能力，提高系統效率?；贏gent 聯盟的合同網模型以Agent 為單位進行任務的協商，如圖3所示。任務Agent 中有管理模塊和決策模塊，管理模塊實現任務在Agent 聯盟之間的交互協商，決策模塊依據最優原則實現任務在Agent 聯盟之間的分配，在管理模塊的監督和管理下實現系統智能決策;聯盟內通信能力較強的Agent 擔任盟主，負責聯盟內部任務的分配、協商和監督執行。

圖3 基于Agent 聯盟的合同網模型框圖Fig.3 The CNP based on Agent alliance

基于Agent 聯盟的合同網模型具有以下優點:

1)Agent 聯盟的形成，降低了網絡的通信量，方便任務Agent 對任務的管理和分配;

2)這一改進合同網模型合理的整合了Agents 之間的合作性和自利性，使任務完成更加合理、高效。

2.2.2 基于公告板模型的改進合同網

黑板模型是一種平行信息共享數據結構，它能解決分布式人工智能中多個計算實體的協作問題，實現異構Agent 集成，為多Agent 提供通信支持。圖4 為黑板模型結構圖［16-17］:①黑板用來儲存數據、傳遞信息和處理方法的數據庫，是系統中全局工作區。黑板根據處理知識領域的不同由上而下劃分為多個信息處理層次，對各信息處理層次進行統一管理;②控制單元是黑板模型的核心，它負責以下工作:一是對Agent 激活和工作的分配;二是對黑板上信息的更新;三是負責通知Agent 讀取黑板上的消息;③Agent 是黑板模型中被服務的主體，它們需要在控制單元中進行注冊，才能在控制單元的協調下與黑板進行信息交互，完成信息和知識的共享。

針對黑板模型本身的局限性，提出了基于公告板模型的合同網改進方案，公告板作為控制系統中Agent 協商交互的基礎，是系統的信息中心。因此，公告板的創建方便了信息的調用，有效提高了合同網的性能。如圖5所示為基于公告板的合同網改進模型工作流程。該模型通過公告板的協助實現任務的分布、協商和監督，具有以下優點:

1)管理者發送任務消息，由公告板進行任務匹配，并以公告板的反饋信息為依據，通過與部分資源Agent 交互和協商，實現對被控系統的管理和控制。因此，減少管理者與資源Agent 之間的交互和協商，提高任務的協商效率，減少控制系統的響應時間;

2)公告板為資源Agent 提高了統一的信息格式，解決了黑板模型中Agent信息格式異構的難題，為Agent信息注冊和任務匹配等提供了方便。

2.2.3 基于優先級的改進合同網

為了方便緊急任務條件和故障狀態下的智能控制，提出了基于優先級的合同網模型。在該模型中，定義了任務的優先級，優先實現優先級相對高的任務，最終實現多任務發布、協商和執行;以不同的優先級定義資源Agent 之間的主備用和并行關系，實現突發情況、故障狀態下主備用的切換和滿足不同條件下Agents的協同工作。如圖6所示為基于優先級的合同網模型的工作流程。

圖5 基于公告板的合同網模型框圖Fig.5 The CNP based on bulletin board

圖6 基于優先級的合同網模型框圖Fig.6 The priority-based CNP

任務Agent 在虛擬工作區以優先級為依據，得到系統的任務序列;資源Agent 以實物模型為基礎，得到資源Agent的并行關系。

依據優先級的高低，由管理者實現任務的發布、協商，得到資源Agent的響應。

結合協商結果和虛擬工作區上的資源Agent的并行關系，得出系統仿真結果。

3 合同網軟件仿真平臺

3.1 JADE 仿真平臺

JADE (Java Agent Development Framework)是一個完全由Java 語言編寫的多Agent 開發框架，遵循FIPA (Foundation Intelligent Physical Agents)規范，提供基本的命名服務、黃頁服務、通信機制等，能夠與多種軟件集成，兼容性較強，極大簡化了多Agent 系統在開發過程中的各個環節。

在JADE 平臺中，1個平臺可以有多個容器，1個容器可容納多個Agent。容器可以位于不同的主機上，1個JADE 平臺有且僅有1個主容器。每個Agent 在JADE 平臺中都有唯一的名字，Agents 之間在通信協議下，通過名字標識實現不同平臺之間的信息交互。

為了便于多Agent 系統的開發，JADE 提供了2個重要組成部分:遵循FIPA 規范的Agent 開發平臺和開發Agent的軟件包。前者定義了Agent 平臺提供的若干服務:其中Agent 管理系統(MAS)、黃頁服務(DF)和消息傳遞服務(MTS)為3 種最基本的服務。這一開發平臺可以實現多平臺的集成，方便多Agent控制系統的開發;后者為程序設計者提供完備的功能接口和規范的抽象性界面。在JADE 平臺中，單個Agent 滿足基于FIPA 規范的Agent 管理參考模型，提供最基本的服務，通過消息傳輸系統實現不同Agent 之間的信息交互。

JADE 智能體最重要的特征之一就是這一平臺具備通信能力［18-19］。Agents 之間的通信模式是異步消息傳遞。在JADE 平臺中，每個Agent 都有一個消息隊列，如果其他Agents 需要與其通信時，JADE就把相應的消息投遞到其隊列中。

JADE 在處理消息發送時，會根據不同情形選擇最合適的信息傳輸方法:

如果消息發送者與接收者在同一容器中時，用Java 對象代替ACL 消息，通過運行線程發送給指定Agent，不存在任何消息傳輸;

如果消息發送者與接收者位于同一JADE 平臺，但不在同一容器中時，ACL 消息通過Java RMI 發送。對于接收者而言，Agent 也只是接收到1個Java 對象;

如果消息發送者與接收者不在同一平臺時，JADE 將根據FIPA 標準，利用HOP 協議和OMG IDL界面來進行消息發送。消息發送者將ACL 消息對象翻譯為字符串，并把HOP 協議視為一個中間協議來執行遠程調用;消息接收者收到一個相應的HOP 序列，并生成一個Java的String 對象，隨后該對象被解析成一個ACL 消息對象，最終該消息對象通過Java 事件或RMI 調用發送給指定的Agent。

總之，JADE 平臺能夠實時維護Agent 地址列表，以便有效提供Agent 之間的消息傳輸，它使用標準的ACC Agent 向外界提供唯一接口，可遠程調用。JADE 這種多方式通信機制大大降低了系統通信的開銷。

3.2 Repast 仿真平臺

Repast (Recursive Porous Agent Simulation Toolkit)是芝加哥大學社會科學計算研究中心研制的Multi-Agent 建模工具。它提供了一系列用以生成、運行、顯示和收集數據的類庫，并能對運行中的模型進行“快照”，記錄某一時刻模型的當前狀態，還可以生成模型運行過程中狀態動態演化的視頻資料。Repast 從Swarm 中借鑒了不少設計結構和方法，所以常常稱Repast 為類Swarm的架構。

Repast 共有近 130個類，封裝在分析庫Analysis、引擎庫Engine、博弈庫Games、因形用戶界面庫GUI、空間庫Space、Util 類庫6個庫中。Repast 模型有批處理方式和非批處理方式(也稱圖形交互方式)2 種運行方式。批處理運行需要一個特殊格式的參數文件，在這個文件中要詳細給出模型各個參數的起始值、終止值和增量值，以及運行的次數等;有了參數文件后，模型就可無須用戶干預連續重復運行。一個非批處理的運行則需要通過圖形用戶界面來交互啟動和終止模型，用戶可以通過圖形界面來設定初始參數值，可以在運行過程中圖形化監控主體和模型的各種狀態。

由于Swarm 對建模者來說還是有些過于復雜，Repast 項目提供一系列簡化Swarm 模型開發的Java類庫。設計者通過讓模擬軟件的底層結構具備抽象性、可擴展性以及“良好”的表現能力等優點。

4 結 語

本文簡述了MAS 協作環境下的任務分配模型。描述了合同網的基本思想和運行機制，針對合同網本身的缺陷，給出了基于聯盟、基于公告板、基于優先級的3 種合同網改進模型，改進模型解決了合同網在任務發布階段和協商階段的信息阻塞和承諾失敗等問題，減少了系統的通信量，滿足控制系統實時性要求，提高了協商效率，擴展了合同網模型的使用范圍，有助于MAS 在復雜、大系統中的應用。最后介紹了2 種常用的MAS 軟件仿真平臺—JADE和Repast 仿真平臺。

［1］孫慶聲，繆旭東，陳行軍.一種基于擴展合同網視為編隊動態任務分配模型［J］.兵工自動化，2009，28(8):50-52.

［2］張陽，張睿，霍德才.遺傳進化算法在多Agent 協作通信中的應用［J］.信息化，2010(26):74-75.

［3］郝莉莉，顧浩，楊慧珍，等.多機器人系統合同網任務分配方法的改進與仿真［C］//2012年水下復雜戰場環境目標識別與對抗及仿真技術學術論文集，2012.

［4］陳華東，王航宇，王樹宗，等.基于合同網的協同作戰分布式目標分配研究［J］.系統仿真學報，2009，21(16):5116-5119.

［5］高黎，沙基昌.基于合同網的分布式威脅系統任務優化分配研究［J］.宇航學報，2007，28(2):352-357.

［6］龍濤，陳巖，沈林成.基于合同網機制的多UCAV 分布式協同任務控制［J］.航空學報，2007，28(2):352-357.

［7］FANG Tang，PARKER L E.A complete methodology for generating multi-robot task solutions using ASyMTRe-D and market-based task alloocation ［ C ］//2007IEEE International Conference on Robotics and Automation Roma，Italy，2007:3351-3358.

［8］張廣勝，蔣昌俊，沙靜，等.基于時間Petri 網的合同網模型研究［J］.系統仿真學報，2008，20(20):5438-5441.

［9］李彤，陳利，李功麗.面向對象Petri 網合同網協議模型的一種改進方案［J］.計算機應用與軟件，2008，25(10):113-115.

［10］AARTI S，DIMPLE J.Introducing trust establishment protocol in contract NET protocol［C］//2010 International Conference on Advances in Computer Engineering，2010:59-63.

［11］高飛燕.基于擴展合同網的多Agent 任務分配機制的研究［D］.大連:大連海事大學，2009.

［12］劉海龍，吳鐵軍.基于合同網的多Agent 任務分配分布式優化算法［J］.浙江大學學報，2001，35(2):550-554.

［13］龍濤，沈林成.多UCAV 協同任務控制中分布式任務分配與任務協調技術研究［D］.長沙:國防科技大學，2006.

［14］楊萍，劉穎.改進合同網協議的Agent 動態任務分配［J］.火力與指揮控制，2011，36(10):77-80.

［15］宋海剛，張堯學，陳松喬.FIPA 合同網協議的一種改進方案［J］.華中科技大學學報，2004，32(7):31-33.

［16］蔣麗娟，劉衛國.基于層次黑板模型的多Agent 系統研究［J］.計算機系統應用，2008(5):10-13.

［17］孫隅隅，黃光球.基于黑板模型的多Agent 智能決策支持系統的研究［J］.嵌入式與單片機，2007，20(25):85-88.

［18］李曉瑜，余謙.一種多Agent 系統通信框架［J］.重慶理工大學學報，2010，24(5):100-103.

［19］趙輝，譚天曉，趙宗濤.基于MAS的作戰指揮模型的通信技術實現［J］.微電子學與計算機，2007，24(11):107-109.