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

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

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

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2024）31-0018-03

開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID） ：

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

多智能體系統(tǒng)可分為同構(gòu)多智能體系統(tǒng)和異構(gòu)多智能體系統(tǒng)，其具備分布式、自主性強(qiáng)、協(xié)調(diào)性好、效率高、開發(fā)成本低、魯棒性強(qiáng)等優(yōu)勢(shì)。多智能體系統(tǒng)主要研究多智能體的協(xié)作，實(shí)質(zhì)是每個(gè)智能體在協(xié)作過程中的交互學(xué)習(xí)過程。通常使用貝葉斯學(xué)習(xí)和強(qiáng)化學(xué)習(xí)方法對(duì)智能體數(shù)量、結(jié)構(gòu)、類型、協(xié)同策略等內(nèi)容進(jìn)行學(xué)習(xí)。智能體協(xié)作問題求解的目的是使得每個(gè)智能體之間能夠合理有效地合作，通過協(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)鍵。通過對(duì)智能體協(xié)同任務(wù)規(guī)劃問題建模將任務(wù)規(guī)劃問題轉(zhuǎn)化為一個(gè)優(yōu)化問題。在綜合考慮智能體資源能力和任務(wù)要求的基礎(chǔ)上，對(duì)多智能體系統(tǒng)資源進(jìn)行有效地分配與調(diào)度，制訂合理的任務(wù)計(jì)劃，充分利用有限的系統(tǒng)資源，最大限度地完成系統(tǒng)的目標(biāo)任務(wù)。多智能體協(xié)同任務(wù)規(guī)劃問題本質(zhì)上仍是NP問題的求解。因此，其模型的建立和算法的使用則是求解關(guān)鍵。智能體任務(wù)規(guī)劃模型具有眾多約束條件，使用算法求解智能體系統(tǒng)任務(wù)規(guī)劃模型是一個(gè)具有挑戰(zhàn)性的課題，也是學(xué)術(shù)界的研究熱點(diǎn)。

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

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

4 展望

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

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

參考文獻(xiàn)：

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

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

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

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

[14] 崔亞妮，任佳，杜文才.戰(zhàn)場(chǎng)環(huán)境下多無(wú)人機(jī)時(shí)敏任務(wù)動(dòng)態(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)編輯：梁書】

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