異構多智能體系統協同任務規劃研究初探

摘要：文章探討了云環境下異構多智能體系統協同任務規劃國內外相關技術研究、共性技術和算法框架，針對云環境下異構多智能體系統協同任務規劃算法在應用效果、類型、實時響應及效率等方面的問題，展望了異構多智能體系統協同任務規劃研究中面臨的技術難題。

關鍵詞：多智能體；任務規劃；云計算

中圖分類號：TP391 文獻標識碼：A

文章編號：1009-3044（2024）31-0018-03

開放科學（資源服務）標識碼（OSID） ：

0 引言

多智能體系統已成為人工智能領域的前沿研究方向之一。多智能體系統（Multi-Agent System，MAS） 是一種全新的分布式計算技術，是由在環境中交互的多個智能體組成的計算系統。近年來，研究者廣泛深入地研究了自然界中蜂群筑巢、鳥群遷徙、蟻群搬運和獸群圍獵等生物集體行為，通過研究生物集體協作行為，為智能體和多智能體系統的模型、概念及理論提供借鑒和啟發。多智能體系統產生于20世紀70年代，由分布式人工智能演化而來。隨著信息科技的飛速發展，近年來，多智能體系統已取得長足發展，且被人工智能與計算機科學的眾多研究領域廣泛應用于求解復雜問題。多智能體系統的研究旨在將復雜的大系統構建為小型、易于管理的系統，這些小系統能夠相互通信和協調，用于解決大規模的、復雜的現實問題。由于具有較好的實用性和可擴展性強等突出特點，其廣泛應用在多機器人協作、協同決策系統、協同作戰系統、分布式控制、數據挖掘、虛擬現實等領域，已成為人工智能領域最前沿的學科研究方向之一。

1 國內外相關技術研究

多智能體協同任務規劃根據智能體的位置、環境因素及能力約束，為多智能體執行多目標任務制定最佳規劃方案和路徑，通過協同實現多智能體之間的優勢互補，提高整體效能。一般而言，多智能體協同任務規劃包括任務分配模型建立及算法求解、路徑規劃及算法求解。近年來，國內外學文獻庫中大量研究了關于多智能體協同任務規劃算法方面。

1.1 多智能體任務模型研究

任務分配的具體問題眾多，主要有多旅行商問題、機車路徑問題、混合整數線性規劃問題[1-3]。文獻[4]建立了CVRP 模型，將智能體載荷約束加入了模型。文獻[5]建立了CMTAP模型，將執行時間、時序、協同約束等加入了模型。文獻[6]基于CMTAP模型，將動態任務和智能體執行任務能力等約束加入了模型，建立了擴展分配模型。

1.2 多智能體任務分配研究

模型建立后，關鍵步驟是任務分配。主要的方式為傳統式和啟發式兩種。文獻[7]針對具有優先約束的多目標、多任務的智能體任務分配問題，提出了分支價格優化的列生成方法。文獻[8]針對防空任務中的多智能體任務分配問題，提出了混合整數線性規劃方法。文獻[9]針對智能體協同任務分配問題，采用了蟻群算法。文獻[10]針對多智能體的任務分配問題，采用了樹搜索算法。

1.3 多智能體任務動態重分配研究

多智能體任務動態重分配，即在故障或取消任務等緊急或突發狀況時，對原任務分配進行動態調整。

文獻[11]提出一種基于監督的順序拍賣機制，應用于解決多智能體任務重分配問題。文獻[12]提出了兩種動態任務再分配算法，應用于多智能體森林滅火并實踐檢驗算法效果。文獻[13]提出了初步分組與組內任務分配思路，采用了改進的K均值聚類算法和分合粒子群優化算法。文獻[14]提出了一種多智能體時間敏感任務動態分配算法，應用在智能體編隊結構下，且充分考慮了時間窗口對智能體編隊執行當前任務后續時敏目標任務的影響。

1.4 多智能體算法優化研究

任務分配完成后，設計具體算法進行求解并檢驗，檢驗效果靠算法。目前，主要算法有最優化方法和啟發式方法兩種。匈牙利算法是一種最常用的最優化算法之一，文獻[15]采用了匈牙利算法，為多智能體目標分配問題提供了解決方案。文獻[16]采用了蟻群算法，應用在求解多約束條件下的多智能體任務規劃中，文獻[17]采用了改進的蟻群算法，對蟻群信息素更新規則進行重定義，應用在多智能體任務規劃中。

2 多智能體系統協作共性技術

協同規劃已成為多智能體系統協作的三大關鍵共性技術之一。多智能體系統是用多個相對簡單的個體構建復雜系統群體進行研究，其關鍵為以下三方面：一是環境的感知與學習，二是彼此間的協調與協作，三是任務完成的能力和效率。多智能體系統是人工智能最重要的技術之一，其包含的協同協調、交互通信、協作機制等智能行為在軟件開發、智能交通管理、智能制造系統等諸多領域廣泛運用。多智能體系統協作最關鍵的三大共性技術分別是：協同感知、協同規劃和協同控制。在多智能體系統中，單個智能體在環境中分散開，它們可通過合作、競爭或部分組合等方式并行地完成目標任務。協同任務規劃是對最優決策/路線/動作的求取，其本質是對狀態空間的搜索求解。其利用分布式原理進行求解具有三大優點：一是有效提高了問題的解決效率，增強了個體隱私性。二是減少了信息的傳遞開銷，降低了系統負荷。三是增強了系統的魯棒性。協同規劃已成為多智能體系統協作最關鍵的共性技術之一。

3 多智能體協同任務規劃算法框架

云環境下的異構多智能體協同任務規劃算法已成為多智能體研究的熱點。近年來，云計算迅速發展成為IT領域技術熱點，集并行計算、分布式計算、網格計算及虛擬化等技術的優點于一身，已被公認為是下一代計算的基礎設施。隨著智能設備的發展進步和技術需求，加之云計算服務的類型更豐富，應用更廣泛，功能也更強大，其有著非常巨大的未來發展空間。云計算有低成本、靈活性、可伸縮性、安全性、可靠性、多租戶、自適應性和提供服務等諸多特點，為滿足多智能體系統的日益增長的計算需求，是解決多智能體系統日益增長的計算需求的現實途徑。同時，通過云中的多智能體的資源共享與協作，使得系統在資源配置、任務協作及服務質效等方面獲得有效的管理和性能優化，可以進行協同任務規劃來完成復雜功能，多智能體系統的云計算框架如圖1所示。

多智能體系統可分為同構多智能體系統和異構多智能體系統，其具備分布式、自主性強、協調性好、效率高、開發成本低、魯棒性強等優勢。多智能體系統主要研究多智能體的協作，實質是每個智能體在協作過程中的交互學習過程。通常使用貝葉斯學習和強化學習方法對智能體數量、結構、類型、協同策略等內容進行學習。智能體協作問題求解的目的是使得每個智能體之間能夠合理有效地合作，通過協調保證效率和公平。多智能體系統的基本結構如圖2所示。

云環境下異構多智能體協同任務規劃算法研究具有重要意義。協同任務規劃算法，使智能體系統的任務規劃更加合理且高效。協同任務規劃算法，是多智能體系統完成任務的關鍵。通過對智能體協同任務規劃問題建模將任務規劃問題轉化為一個優化問題。在綜合考慮智能體資源能力和任務要求的基礎上，對多智能體系統資源進行有效地分配與調度，制訂合理的任務計劃，充分利用有限的系統資源，最大限度地完成系統的目標任務。多智能體協同任務規劃問題本質上仍是NP問題的求解。因此，其模型的建立和算法的使用則是求解關鍵。智能體任務規劃模型具有眾多約束條件，使用算法求解智能體系統任務規劃模型是一個具有挑戰性的課題，也是學術界的研究熱點。

協同任務規劃算法，使智能體之間的溝通機制更加健全且有效。隨著多智能體系統場景的日益增多，單智能體向多智能體發展面臨通信技術及溝通機制等問題。多智能體系統有大量的信息，研究減少智能體之間的資源消耗和信息交互，增加多智能體系統的自適應能力，是當前的技術熱點。近年來研究人員將關注的焦點投入多智能體的算法研究，達到使智能體之間的相互協同配合的策略，解決通信機制建立方法所面臨泛化性能的挑戰。尤其是在多智能體環境中，狀態信息是部分可觀測的，智能體數量是動態變化的，要解決這些難題的有效方法之一就是通過協同任務規劃算法在智能體之間互相建立溝通機制。

協同任務規劃算法，使智能體系統的決策能力更加科學且智效。未來，推理系統將從“面向信息”到“智能自主”，以探索新的思想和方法進行智能自主行為、滲透和實現預定的目標。但是，多智能體系統研究以及目前的知識框架仍然存在著不夠精細、應用粗糙等問題，這就為協同任務規劃算法理論及應用帶來深度研究空間。任務類型、時序約束、智能體執行任務類型和能力差異等因素，須在任務分配過程中充分考慮，合理地將任務分配給智能體，目標為滿足整體任務完成及效率達到最優。關鍵是任務分配模型的建立和分配算法的使用。由此，將多智能體系統與分布式約束優化問題進行融合，依據多智能體建立系統模型進行研究，采用分布式約束優化算法進行計算，即可在滿足實時性需要的前提下，獲得相對完備的最優化方案以供智能體系統決策。多智能體系統在軍事、生產和生活的各個方面，都取得了極大的效益并解決了很多以前難以有效解決的復雜問題。行業的迅速發展，使得協同任務規劃算法在多智能體系統中的應用具有很重要的應用價值和廣闊的發展前景。

4 展望

針對多智能體協同任務規劃問題，研究人員在多智能體系統建模和算法應用等主要研究方向上取得了大量研究成果。但是，從應用效果改進和技術發展的角度看，仍然存在以下4個方面的問題：1） 算法中簡約化處理的目標任務和約束條件，使實際應用效果欠佳。2） 智能體和規劃任務相對單一，對異構體和多任務考量不多，降低了復雜度。3） 現有的某些任務規劃算法計算結果準確但是時間代價過大，實時性不強，不具備對突發情況的響應能力。4） 大多算法在面對動態環境變化增加的系統不確定性時，算法的實時性不足。如何在云環境中實現不同類型、不同能力智能體的協同任務規劃，最大限度地利用多智能體系統資源，成為其中的核心和關鍵問題。

隨著人工智能的發展，深度強化學習的決策能力和深度卷積神經的感知能力為許多懸而未決的問題提供新的視角和優異的解決方案。特別是，深度強化學習算法已被證明能夠解決以前具有高維狀態和動作空間的棘手的決策問題。

參考文獻：

[1] 楊杰，席建祥，王成，等.多無人機協同巡視任務規劃方法綜述[J].飛行力學，2018，36（5）：1-6.

[2] 高揚.基于智能優化算法的無人機任務規劃[D].南京：南京郵電大學，2019.

[3] CAI J L，ZHANG N.Mixed integer nonlinear programming foraircraft conflict avoidance by applying velocity and altitudechanges[J].Arabian Journal for Science and Engineering，2019，44（10）：8893-8903.

[4] ZORLU O.Routing unmanned aerial vehicles as adapting to ca?pacitated vehicle routing problem with genetic algorithms[C]//2015 7th International Conference on Recent Advances inSpace Technologies （RAST）.June 16-19，2015.Istanbul，Turkey.IEEE，2015：675-679.

[5] JIA Z Y，YU J Q，AI X L，et al.Cooperative multiple task assign?ment problem with stochastic velocities and time windows forheterogeneous unmanned aerial vehicles using a genetic algo?rithm[J].Aerospace Science and Technology，2018，76：112-125.

[6] 謝文光，吳康，閻芳，等.一種面向多無人機協同編隊控制的改進深度神經網絡方法[J].西北工業大學學報，2020，38（2）：295-302.

[7] CASBEER D W，HOLSAPPLE R W.Column generation for aUAV assignment problem with precedence constraints[J].Inter?national Journal of Robust and Nonlinear Control，2011，21（12）：1421-1433.

[8] YE F，CHEN J，TIAN Y，et al.Cooperative task assignment of aheterogeneous multi-UAV system using an adaptive genetic al?gorithm[J].Electronics，2020，9（4）：687.

[9] WANG Q S，LIU L，TIAN W Y.Cooperative task assignment ofmulti-UAV in road-network reconnaissance using customizedgenetic algorithm[C]//2021 IEEE 4th Advanced InformationManagement，Communicates，Electronic and Automation ControlConference （IMCEC）.June 18-20，2021.Chongqing，China.IEEE，2021：803-809.

[10] XIANG S S，CHEN Y J.Task assignment modeling and simula?tion for cooperative driving of multiple vessels[C]//2017 Inter?national Conference on Progress in Informatics and Comput?ing （PIC）.December 15-17，2017.Nanjing.IEEE，2017： 25-29.

[11] 劉昕彤.動態環境下多無人機協同控制技術研究[D].成都：電子科技大學，2017.

[12] 吳歇爾.面向多無人機的協同任務預分配及重分配研究[D].南昌：南昌航空大學，2018.

[13] 王然然，魏文領，楊銘超，等.考慮協同航路規劃的多無人機任務分配[J/OL]. 航空學報：1-11[2021-09-08].http：//kns.cnki.net/kcms/detail/11.1929.V.20200615.1408.034.html.

[14] 崔亞妮，任佳，杜文才.戰場環境下多無人機時敏任務動態分配算法[J].系統工程與電子技術，2016，38（4）：828-835.

[15] LIU J F，LIU J，YAN X M，et al.A heuristic algorithm combiningPareto optimization and niche technology for multi-objectiveunequal area facility layout problem[J].Engineering Applica?tions of Artificial Intelligence，2020（89）：103453.

[16] DUAN H B，LI P，YU Y X.A predator-prey particle swarm opti?mization approach to multiple UCAV air combat modeled bydynamic game theory[J]. CAA Journal of Automatica Sinica，2015，2（1）：11-18.

[17] GHAMRY K A，KAMEL M A，ZHANG Y M.Multiple UAVs inforest fire fighting mission using particle swarm optimization[C]//2017 International Conference on Unmanned Aircraft Sys?tems （ICUAS）.June 13-16，2017.Miami，FL，USA.IEEE，2017：1404-1409.

【通聯編輯：梁書】

基金項目：永州市科技局科技計劃項目（項目編號：2022-YZKJZD-009） ；教育部高教司產學合作協同育人項目（項目編號：220904484223137） ；湖南省大學生創新創業訓練項目（項目編號：4244） ；湖南科技學院計算機科學與技術應用特色學科資助