基于服務的異質作戰實體協同優化研究

宦 婧，周偉祝，陳 健，孫 媛

（海軍航空工程學院 科研部，山東 煙臺264001）

0 引 言

目前，在基于Agent的計算機生成兵力 （computer generate force，CGF）作戰仿真中，作戰實體也就是CGF開發時缺乏統一的規范，導致異質CGF的存在，使得CGF實體間難以實現信息的共享和交互，如果無法保證異質CGF協同分配的連貫性和高效性，仿真系統性能將會出現震蕩，因此如何實現異質CGF交互并高效地實現任務分配是CGF完成復雜任務的關鍵，也是CGF協同的研究熱點［1］。

目前，協同任務分配的研究方面，基于合同網的任務分配方法得到了廣泛的研究與應用，R.Zlot等人［2－3］采用面向任務樹的競價拍賣合同網法分配一類松耦合子任務取得了較好的效果，裘杭萍［4］等人從投標Agent的負載、能力和信任度3個方面進行綜合考慮和權衡，提出了一種基于多屬性評價中標策略的動態任務分配算法，對傳統的合同網協議進行了改進。但是，上述工作或多或少的存在以下幾點缺陷：未考慮異質實體間的交互問題；較少考慮系統通信開銷要求；在確定分配方案的過程中，忽略了CGF間的約束關系，從而導致問題求解難以達到全局最優。

本文旨在提高異質CGF平臺互操作和交互能力的基礎上，使作戰實體高效地完成任務分配從而協同完成上級作戰目標。Web服務技術可以較好地解決異質應用之間互操作的問題，已成為系統間功能發布和共享的重要方式［5］。本文將Web服務的思想引入到多CGF任務分配中，提出了一種基于服務的協同任務分配模型，以解決異質CGF交互過程中的兼容性問題，同時采用基于能力效用函數的任務分配策略，建立效用函數模型優化任務分配質量和效率。

1 基于服務的協同任務分配模型

作戰仿真組織內部，被分解的子任務在作戰仿真實體之間分配，接受任務的所有作戰實體組成團隊，通過內部協同完成任務。本文將作戰實體按作戰角色分為指揮實體和成員實體，按仿真角色分為資源需求型實體 （Req＿CGF）和資源提供型實體 （Sup＿CGF）。指揮實體負責任務的分配和管理，有協作需求的指揮實體的仿真角色為Req＿CGF。因此，任務分配是指Req＿CGF通過一定的方式將任務分配給愿意并有能力協作完成子任務的Sup＿CGF，將其轉化為成員實體，并組成團隊共同完成使命任務的過程。

合同網絡模型［6］下的任務分配流程是：Req＿CGF通過廣播聲明任務，系統中的Sup＿CGF根據自身能力向任務管理員投標，Req＿CGF在標書截至期限內，選擇滿意的投標者來完成任務。由于采用了廣播模式來聲明任務，因此該模型對網絡負載的要求較高，且沒有考慮異質實體間的交互通信問題。為改善原有的任務分配模型，本文引入服務機制，建立基于服務的CGF任務分配模型，各CGF將其所能提供的功能封裝為服務，向控制中心中的服務注冊中心發布服務，CGF之間的協同交互均以服務注冊中心為媒介的，該方式一方面解決了異質CGF通信交互的問題，另一方面，由于網絡傳遞的并非實際的功能，而是經過封裝的服務，所需要傳遞的數據量大大減少，因此能有效的減輕網絡負載。

1.1 基于服務的多CGF系統

傳統的仿真服務主要指為仿真運行提供服務的仿真應用系統或組件，與傳統的仿真服務不同，本文所提到的仿真服務是一種具有可持久狀態，能夠通過標準協議進行描述、發布和訪問的Web服務［5］，是把原有的仿真組件封裝為具有獨立行為邏輯或計算功能的仿真組件。

基于服務的多CGF系統結構如圖1所示，系統通過發布服務、查詢、返回服務列表、綁定控制成員的方式，滿足組織內成員實時交互并實現對組織內各CGF運行狀況的控制，主要包括兩部分：融合了服務的CGF主體模型和基于服務的控制中心。融合了服務的CGF主體模型是指，在傳統的基于Agent的CGF模型基礎上增加服務層，服務層可以根據需要將CGF功能封裝為服務向外發布，并接受來自其它CGF的服務請求，提供具體的服務，以此實現異質CGF主體間的交互；基于服務的控制中心是多CGF系統的控制單元，負責對系統中的CGF主體及其服務進行統一的控制和管理，提供系統內CGF之間交互的接口［7］，主要包括CGF注冊中心、服務注冊中心和本體。CGF注冊中心為CGF提供運行時的管理服務，包括為CGF提供注冊和注銷服務，同時也為CGF提供角色的注冊和注銷服務；服務注冊中心需要提供仿真服務管理服務，用于維護一個CGF仿真服務注冊表，它主要負責對已經注冊的CGF主體所提供的服務進行注冊管理；本體是對CGF系統的描述，主要包括：①仿真服務管理中心所提供的服務，這些服務中的操作及說明；②CGF類，以及這些CGF類所提供服務的描述；③CGF類之間的聯系、CGF類與所提供服務之間的關系、服務與操作之間的關系。

圖1 基于服務的多CGF系統模型

1.2 基于服務的任務分配流程

基于服務機制建立的任務分配模型執行步驟如圖2所示，詳細描述如下。

步驟1 服務注冊：所有參與仿真的CGF向控制中心

Service＝ ｛服務名稱，服務ID，服務鏈接地址｝

步驟2 上級下達的使命任務后，作戰實體 （Req＿CGF）產生協作需求，對分解后的子目標分別在組織中尋求協作成員，首先向服務注冊中心請求查詢服務，查詢與的CGF注冊中心注冊CGF信息，已完成注冊的CGF將其可以提供的功能資源打包成服務，上傳到控制中心，并向服務注冊中心注冊服務信息，服務注冊中心以服務列表的形式存儲為以下格式，方便為其它CGF提供查詢和調用。子目標相關的作戰實體。

步驟3 服務注冊中心將相關的服務列表返回給Req＿CGF；

步驟4 發布標書：Req＿CGF根據服務列表向各個能

圖2 基于服務的協同任務分配流程

提供相應功能的Sup＿CGF以標書的形式發送請求資源／功能請求。

標書格式：標書＝ ｛ID，Manger，Description，Restriction，Grade，ExpireTime｝，其中ID為標書標識號；Manger為發起協作的CGF標識；Description為任務的具體描述，Restriction為任務的限制條件，如：時間要求，質量要求等；Grade為任務優先級，ExpireTime為投標截止時限。

步驟5 投標：收到資源請求的Sup＿CGF，向服務注冊中心請求查詢服務和能力評估服務，根據評估結果決策是否提供協作服務，并將決策結果以標書的形式返回給Req＿CGF；

步驟6 發放標書：Req＿CGF根據所有反饋信息，請求綜合能力評估服務，根據得出的結果選擇最終愿意合作的Sup＿CGF成為成員CGF，協調制定協作計劃，形成團隊。

1.3 基于效用函數的任務分配算法優化

上述基于服務的協同分配流程雖可以有效地實現異質CGF之間的交互并實現任務分配，但由于合同網絡算法沒有考慮作戰實體之間的約束關系，因此最終的分配結果難以達到全局最優，為此，在上述分配流程的基礎上，本文提出一種基于效用的任務分配全局優化算法，該算法建立了基于能力向量的CGF效用函數，結合遺傳算法易于實現全局優化的特點對投標CGF進行全局規劃，從而在一定程度上解決動態環境下全局分配優化問題。

1.3.1 基于能力向量的效用函數

作戰仿真中，任務所要求的能力和CGF所能提供的能力隨作戰環境的變化而變化，各CGF對任務的適應程度也隨之變化。本文引入效用函數來量化CGF對子任務的勝任程度，CGFfi相對子任務tj的效用函數uj（i）可以表示為當前任務需求能力 （Ctj）和CGF能力 （）的函數，表達式表示為［8］

式中：uj（i）——CGFfi對子任務tj的效用函數值，即CGFfi對子任務tj的勝任程度。Uj（Cfi，Ctj）——與子任務tj對應的效用函數。vij——投標情況，vij∈ ｛0，1｝，vij＝1表示CGFfi向子任務tj投標，反之則表示CGFfi未向子任務tj投標。

不同的子任務對CGF的要求不同，對應的效用函數也不同，即如tk≠tj，則Uk（·）≠Uj（·）。對于某一子任務tj而言，所有CGF對其的效用函數構成效用向量Uj，Uj＝［uj（1），uj（2），…，uj（i）］T。為了使uj（i）與uk（i）具有可加性，對向量Uj進行歸一化處理

不失一般性，考慮m個CGF對n個子任務的投標情況，可得效用函數矩陣

式中uij＝珘uj（i），表明對同一個子任務而言，CGF對于子任務的執行能力隨著效用函數值的增大而增強，也就是對子任務的勝任能力越強［9］。

任務T分解為n個子任務tk（k＝1，2，…，n），應用合同網絡分配方法對m個CGF實體分配n個子任務，生成關于所有投標CGF的標書矩陣RT［10］，RT可表示為

元素rtij為bi對任務元tj進行投標的標書信息，rtij可表示為

其中：cj是表示任務tj的代碼；uij表示bi完成任務tj的效能；gij＝1表示選擇bi完成任務tj；規定任一任務僅能由一個CGF完成，即

以最大化任務完成效能為目標，建立如下任務分配目標函數

對應的 ｛θ1，θ2，…，θm｝即為任務分配方案。

1.3.2 基于遺傳算法的任務分配優化

上文所述任務分配算法的復雜度隨著子任務的數量以及參與任務的CGF實體數量的增加而劇增，為保證任務分配的時效性，通常的做法是隨機選擇若干可行解，在這些可行解中根據任務完成效能選擇最優解作為任務分配方案。這種方法雖可以實現任務分配，但獲得全局最優解的可能性較小，因此需對其進行有效地改進。遺傳算法通過模仿生物進化過程優化全局方案［11］，具有簡單通用的特性，很適合用于任務分配中對任務空間的搜索和優化。因此本文結合遺傳算法，對合同網絡任務分配方案進行優化，適應度函數選用基于能力向量的效用函數，算法具體執行步驟如下：

（1）生成標書矩陣。Sup＿CGF從所有發布的任務中選擇能夠執行的任務，計算出每個任務的執行時間和執行效用值；并對每一個投標CGF重復以上步驟，直至計算出每個投標CGF的執行時間及效用，以此形成標書矩陣RT。

（2）生成初始種群。從實現任務分解的T中依次讀取子任務tj，并在標書矩陣中找出與tj對應的投標結果集RTj＝ ［rt1j，rt2j，…，rtmj］，從中隨機提取某CGFfi的投標方案作為初始方案。對每一個子任務重復這一過程，直到它們都得到初始方案，這一方案就是種群中的個體。重復上述步驟則初始種群ρ（T）形成。

（3）計算個體適應度。依次提取ρ（T）中的個體，將其代入式 （5）中，計算個體適應度。依據此值運用賭輪選擇法，從種群中選擇（N表示種群中個體的數量）個個體對；令雜交概率為pc，變異概率為pm，首先，依據概率pc進行雜交操作產生N個個體；然后根據概率pm進行變異操作并產生新種群。

（4）任務分配方案確定，即提取最優分配方案。利用適應度函數評價最后一代種群，提取最優個體作為最終任務分配方案ρ（T′）。

（5）形成面向作戰任務的CGF團隊。根據步驟 （4）中確定的最優分配方案，Sup＿CGF將方案結果發布出去，所有受領任務的CGF形成面向任務T的CGF團隊。

2 作戰仿真驗證

本文利用Mak仿真平臺構建了一個簡單的直升機協同反潛仿真實例，驗證優化后協同任務分配模型的性能。

作戰想定：某敵對勢力在我海域進行非法偵察活動，我方兵力偵察到敵方潛艇的航跡，指揮調遣3架反潛直升機對這一海域進行反潛搜索，并進行海域劃分和任務分配。反潛直升機在受領作戰任務后迅速飛臨指定空域，搜索到敵方潛艇后迅速鎖定并通報上級指揮所，敵潛艇發現被鎖定后進行規避，我方則繼續跟蹤并在情況允許范圍內實施打擊。仿真過程截圖如圖3所示。

圖3 仿真過程截圖

從初始狀態到搜潛成功稱為一個回合，任務分配優化模型的目的是通過優化模型使得每一回合中以盡可能少的時間實現任務分配，并達到全局最優分配方案。根據待搜索海域的大小及直升機性能將其劃分為300個搜索塊，分別運用文中方法和原先方法為3架反潛直升機分配任務，試驗中遺傳算法參數設置為：種群大小為300，進化次數為100次，交叉概率取0.7，變異概率取0.2。仿真實驗共進行30次，仿真結果如圖4，圖5所示，本文以執行任務分配所需時間和完成作戰任務所需時間為指標，驗證模型優化程度。

仿真結果顯示：從完成任務分配的時間上來看，與未經優化的任務分配模型相比，優化后的模型完成任務分配所需時間略有增加，增加幅度在5%左右，這主要是由于未經優化的算法在隨機選定的部分解空間中尋求最優解，當設定的部分解空間規模較小時，耗時相對較少，而采用遺傳算法進行優化，需要對整個解空間進行隨機最優搜索，因此耗時增加；從搜潛效能上來看，采用優化后的模型所計算出的任務分配方案，搜潛成功率平均要提高50%左右，搜潛效能大大高于未經優化的算法。綜合來看，采用遺傳算法優化后的任務分配模型在基本相近的任務分配所需時間內，能有效提高任務分配方案的優劣程度，使得分配方案更逼近全局最優。

3 結束語

任務分配是作戰仿真領域的核心問題，本文為解決異質CGF任務分配問題，將服務的思想引入到任務分配中，建立了基于服務的協同任務分配模型。該模型使得CGF的功能結構不再是影響任務分配的重要因素，對異質CGF系統具有較好的通用性；在此基礎上，給出了基于效用函數的分配方案優化算法，算法充分考慮到環境因素對CGF能力、子任務要求能力的影響，采用遺傳算法對分配方案進行了全局優化。仿真實驗表明：基于遺傳算法改進的合同網絡任務分配模型可以有效地提高CGF仿真系統的作戰效能，但是對于任務間相關的任務分配策略和對任務分配效果的評估還有待進一步的研究。

［1］LI Weixiang，ZHANG Guangming，LI Bangyi.Research on multi

attributes task allocation mechanism in MAS ［J］.Systems Engineering and Electronics，2009，31 （5）：1113－1116 （in Chinese）.［李為相，張廣明，李幫義.一種多屬性的MAS任務分配機制研究 ［J］.系統工程與電子技術，2009，31 （5）：1113－1116.］

［2］Zlot R，Stentz A.Market－based multi－robot coordination for complex tasks ［J］.International Journal of Robotics Research，2006，25 （1）：73－101.

［3］MB Dias，Zlot R.Market－based multirobot coordination：A survey and analysis ［C］／／Proc of IEEE，2006：1257－1270.

［4］QIU Hangping，QIN Yao，HU Rui，et al.Study on the task allocation based on improved contract net in multi－agent system ［J］.Computer Science，2012，39 （B6）：279－282 （in Chinese）. ［裘杭萍，覃垚，胡汭，等.多Agent系統中基于改進合同網模型的任務分配研究 ［J］.計算機科學，2012，39 （B6）：279－282.］

［5］WU Zebin，WU Huizhong，LI Weiqing.Run－time infrastructure of distributed simulation based on Web services ［J］.Computer Integrated Manufacturing Systems，2009，15 （10）：2064－2068 （in Chinese）.［吳澤彬，吳慧中，李蔚清.Web服務化的分布仿真運行支撐環境 ［J］.計算機集成制造系統，2009，15 （10）：2064－2068.］

［6］DING Zhiqin，LIU Yong，WANG Kai.Bidding－based optimization of task allocation in multi－Agent system ［J］.Journal of Computer Applications，2010，30 （7）：1907－1910 （in Chinese）.［丁芝琴，劉永，王凱.多Agent系統中基于招投標的任務分配優化 ［J］.計算機應用，2010，30 （7）：1907－1910.］

［7］YAO Xifan，LIAN Zhaotong，LI Yongxiang，et al.Serviceoriented architecture and integrated development environment for cloud manufacturing ［J］.Computer Integrated Manufacturing Systems，2012，18 （10）：2312－2322 （in Chinese）.［姚錫凡，練肇通，李永湘，等.面向云制造服務架構及集成開發環境 ［J］.計算機集成制造系統，2012，18 （10）：2312－2322.］

［8］HUAN Jing，ZHOU Weizhu，LI Jiying，et al.Utility based task allocation optimized for CGF collaboration ［J］.Science Technology and Engineering，2012，12 （28）：7421－7424 （in Chinese）. ［宦婧，周偉祝，李季穎，等.基于效用函數的CGF協同任務分配優化研究 ［J］.科學技術與工程，2012，12 （28）：7421－7424.］

［9］LI Hao，DAI Jinhai.Agent－based modeling and simulation supported system effectiveness analysis for complex systems［J］.Journal of System Simulation，2008，20 （15）：3911－3914（in Chinese）.［李昊，戴金海.基于Agent的建模與仿真支持下的復雜系統效能分析法 ［J］.系統仿真學報，2008，20 （15）：3911－3914.］

［10］ZHANG Yu，LI Fanzhang.Research on multi－agent dynamic task allocation algorithm and based on dynamic fuzzy set ［J］.Acta Electronica Sinica，2009，37 （11）：2552－2555 （in Chinese）.［張瑜，李凡長.基于DFS的多Agent動態任務分配算法研究 ［J］.電子學報，2009，37 （11）：2552－2555.］

［11］LI Shujuan，LI Yan，LIU Yong，et al.A GA－based NN approach for make span estimation ［J］.Applied Mathematics and Computation，2007，185 （2）：1003－1014.