異構(gòu)多智能體系統(tǒng)協(xié)同任務(wù)規(guī)劃研究初探

摘要：文章探討了云環(huán)境下異構(gòu)多智能體系統(tǒng)協(xié)同任務(wù)規(guī)劃國內(nèi)外相關(guān)技術(shù)研究、共性技術(shù)和算法框架，針對云環(huán)境下異構(gòu)多智能體系統(tǒng)協(xié)同任務(wù)規(guī)劃算法在應(yīng)用效果、類型、實時響應(yīng)及效率等方面的問題，展望了異構(gòu)多智能體系統(tǒng)協(xié)同任務(wù)規(guī)劃研究中面臨的技術(shù)難題。

關(guān)鍵詞：多智能體；任務(wù)規(guī)劃；云計算

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

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

開放科學（資源服務(wù)）標識碼（OSID） ：

0 引言

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

1 國內(nèi)外相關(guān)技術(shù)研究

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

1.1 多智能體任務(wù)模型研究

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

1.2 多智能體任務(wù)分配研究

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

1.3 多智能體任務(wù)動態(tài)重分配研究

多智能體任務(wù)動態(tài)重分配，即在故障或取消任務(wù)等緊急或突發(fā)狀況時，對原任務(wù)分配進行動態(tài)調(diào)整。

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

1.4 多智能體算法優(yōu)化研究

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

2 多智能體系統(tǒng)協(xié)作共性技術(shù)

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

3 多智能體協(xié)同任務(wù)規(guī)劃算法框架

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

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

云環(huán)境下異構(gòu)多智能體協(xié)同任務(wù)規(guī)劃算法研究具有重要意義。協(xié)同任務(wù)規(guī)劃算法，使智能體系統(tǒng)的任務(wù)規(guī)劃更加合理且高效。協(xié)同任務(wù)規(guī)劃算法，是多智能體系統(tǒng)完成任務(wù)的關(guān)鍵。通過對智能體協(xié)同任務(wù)規(guī)劃問題建模將任務(wù)規(guī)劃問題轉(zhuǎn)化為一個優(yōu)化問題。在綜合考慮智能體資源能力和任務(wù)要求的基礎(chǔ)上，對多智能體系統(tǒng)資源進行有效地分配與調(diào)度，制訂合理的任務(wù)計劃，充分利用有限的系統(tǒng)資源，最大限度地完成系統(tǒng)的目標任務(wù)。多智能體協(xié)同任務(wù)規(guī)劃問題本質(zhì)上仍是NP問題的求解。因此，其模型的建立和算法的使用則是求解關(guān)鍵。智能體任務(wù)規(guī)劃模型具有眾多約束條件，使用算法求解智能體系統(tǒng)任務(wù)規(guī)劃模型是一個具有挑戰(zhàn)性的課題，也是學術(shù)界的研究熱點。

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

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

4 展望

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

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

參考文獻：

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

[2] 高揚.基于智能優(yōu)化算法的無人機任務(wù)規(guī)劃[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] 謝文光，吳康，閻芳，等.一種面向多無人機協(xié)同編隊控制的改進深度神經(jīng)網(wǎng)絡(luò)方法[J].西北工業(yè)大學學報，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] 劉昕彤.動態(tài)環(huán)境下多無人機協(xié)同控制技術(shù)研究[D].成都：電子科技大學，2017.

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

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

[14] 崔亞妮，任佳，杜文才.戰(zhàn)場環(huán)境下多無人機時敏任務(wù)動態(tài)分配算法[J].系統(tǒng)工程與電子技術(shù)，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，F(xiàn)L，USA.IEEE，2017：1404-1409.

【通聯(lián)編輯：梁書】

基金項目：永州市科技局科技計劃項目（項目編號：2022-YZKJZD-009） ；教育部高教司產(chǎn)學合作協(xié)同育人項目（項目編號：220904484223137） ；湖南省大學生創(chuàng)新創(chuàng)業(yè)訓練項目（項目編號：4244） ；湖南科技學院計算機科學與技術(shù)應(yīng)用特色學科資助