多Agent動態(tài)任務(wù)分配問題

張家良 王迎磊 李復(fù)名 周濤

摘要： 針對多Agent動態(tài)環(huán)境下任務(wù)分配問題，建立多Agent動態(tài)任務(wù)分配模型，提出了基于改進合同網(wǎng)的動態(tài)任務(wù)分配算法。在合同網(wǎng)的基礎(chǔ)上，引入任務(wù)中轉(zhuǎn)站處理由環(huán)境變化產(chǎn)生的新任務(wù)，任務(wù)優(yōu)先級定義任務(wù)的處理順序，并對算法的招標(biāo)以及投標(biāo)階段進行了改進，設(shè)定了招標(biāo)任務(wù)閩值和投標(biāo)任務(wù)閾值。仿真結(jié)果表明該算法能在各種環(huán)境變化下快速更新任務(wù)分配方案。

【關(guān)鍵詞】動態(tài)任務(wù)分配 改進合同網(wǎng) 任務(wù)中轉(zhuǎn)站 任務(wù)優(yōu)先級

1 引言

隨著信息技術(shù)以及分布式系統(tǒng)理論的迅速發(fā)展，多Agent系統(tǒng)已經(jīng)引起研究人員的廣泛關(guān)注。Agent能感知自身以及外界狀態(tài)變化，并能產(chǎn)生相應(yīng)的自主行為。多Agent系統(tǒng)概念在軍事領(lǐng)域中的運用，是未來戰(zhàn)爭體系中的關(guān)鍵，連入網(wǎng)絡(luò)的各作戰(zhàn)單元可以看作Agent。由于戰(zhàn)爭環(huán)境復(fù)雜多變，且Agent在執(zhí)行任務(wù)過程中能力可能出現(xiàn)變化。因此，研究多Agent動態(tài)任務(wù)分配問題，對于提高多Agent協(xié)同作戰(zhàn)能力具有重要的意義。

目前，基于合同網(wǎng)的算法已經(jīng)廣泛運用在求解任務(wù)分配問題中。文獻[4]通過引入任務(wù)熟人集的概念，在招標(biāo)范圍上進行改進，減少招標(biāo)對象的數(shù)量，有效減少了協(xié)商時間。文獻[5]通過建立條件合同機制，并引入時間網(wǎng)絡(luò)約束，保證了算法能準(zhǔn)確實現(xiàn)任務(wù)重分配。文獻[6]綜合考慮Agent的負載、能力和信任度，提出基于多屬性的中標(biāo)策略，提高了算法求解的效率。但是大多數(shù)方法對環(huán)境變化產(chǎn)生的任務(wù)沒有預(yù)先處理，導(dǎo)致任務(wù)分配時較為混亂。因此，本文在傳統(tǒng)合同網(wǎng)基礎(chǔ)上，引入任務(wù)中轉(zhuǎn)站和任務(wù)優(yōu)先級協(xié)助處理任務(wù)的分配，并改進了招標(biāo)和投標(biāo)階段，提高了多Agent處理動態(tài)任務(wù)分配問題的效率。

2 多Agent動態(tài)任務(wù)分配模型

2.1 多Agent動態(tài)任務(wù)分配問題

在作戰(zhàn)開始前，指揮中心通常會根據(jù)己掌握的戰(zhàn)場信息，對己方作戰(zhàn)單元進行任務(wù)預(yù)分配。但隨著戰(zhàn)場環(huán)境的變化以及Agent在執(zhí)行任務(wù)過程中出現(xiàn)突發(fā)情況，若按照之前的方案執(zhí)行任務(wù)，可能會使得執(zhí)行任務(wù)的效能降低。因此，在出現(xiàn)環(huán)境變化后，多Agent需調(diào)整自身任務(wù)，使得執(zhí)行任務(wù)的效能保持最大。

2.2 多Agent分布式結(jié)構(gòu)

基于Agent的特點，將連入網(wǎng)絡(luò)的作戰(zhàn)單元看作Agent，各Agent通過數(shù)據(jù)鏈傳遞信息，構(gòu)成多Agent分布式結(jié)構(gòu)，如圖1所示。分布式結(jié)構(gòu)里的Agent是獨立自治的，互相之間能直接進行通信實現(xiàn)信息交換。分布式結(jié)構(gòu)擴展性強，在遇到環(huán)境變化時，無需將信息傳遞給指揮中心等待決策，自身就可以進行協(xié)調(diào)控制，從而快速調(diào)整。

2.3 多Agent動態(tài)任務(wù)分配模型

設(shè)由N個Agent對M個目標(biāo)執(zhí)行任務(wù)。每個Agent自身的任務(wù)集為Tk，執(zhí)行任務(wù)的效能為U（Tk），k=l，…，N。

多Agent動態(tài)任務(wù)分配數(shù)學(xué)模型為：

其中U（J）=J1（T）-J2（T），J1（T）和J2（T）代表執(zhí)行任務(wù)的收益和代價，其中代價分為損耗代價和航程代價。具體定義如下：

以上公式中T為Agent的任務(wù)集，即目標(biāo)列表。S為Agent對目標(biāo)執(zhí)行任務(wù)的成功概率，Z為Agent對目標(biāo)執(zhí)行任務(wù)的損傷概率，K為目標(biāo)的自身價值，L表示執(zhí)行任務(wù)的路程。ω1和ω2是損耗代價函數(shù)和航程代價函數(shù)的權(quán)重系數(shù)。

3 傳統(tǒng)合同網(wǎng)

3.1 合同網(wǎng)思想

合同網(wǎng)是在上世紀80年代由R Davis和RG Smith提出的一種協(xié)商方法。合同網(wǎng)主要運用在分布式系統(tǒng)中，通過模擬經(jīng)濟行為的招標(biāo).投標(biāo).中標(biāo)，從而實現(xiàn)任務(wù)的傳遞控制。

基于合同網(wǎng)的動態(tài)任務(wù)分配主要分為四個階段：招標(biāo)、投標(biāo)、中標(biāo)和簽約。

3.1.1 招標(biāo)階段

招標(biāo)階段是Agent在任務(wù)的執(zhí)行過程中，發(fā)現(xiàn)執(zhí)行某項任務(wù)效能過低，就把任務(wù)向外界公布進行招標(biāo)。

3.1.2 投標(biāo)階段

投標(biāo)階段是其他Agent收到招標(biāo)信息后，若還有能力執(zhí)行任務(wù)，則將招標(biāo)任務(wù)納入自身任務(wù)集，并公布標(biāo)書價格，即執(zhí)行該招標(biāo)任務(wù)的效能。

3.1.3 中標(biāo)階段

中標(biāo)階段是招標(biāo)者收到投標(biāo)者發(fā)送的標(biāo)書，衡量投標(biāo)者的標(biāo)書價格，選出其中價格最優(yōu)的標(biāo)書，并向此投標(biāo)者發(fā)送中標(biāo)信息。

3.1.4 簽約階段

簽約階段是招標(biāo)者和中標(biāo)者更新各自任務(wù)集。

合同網(wǎng)流程如圖2所示。

3.2 傳統(tǒng)合同網(wǎng)不足

傳統(tǒng)合同網(wǎng)可以在一定程度上解決動態(tài)任務(wù)分配問題，但在較復(fù)雜的場景中，傳統(tǒng)合同網(wǎng)有以下不足：

（1）傳統(tǒng)合同網(wǎng)在招標(biāo)階段，對于各種環(huán)境變化而導(dǎo)致的新任務(wù)，沒有有序的處理方法，使得招標(biāo)階段比較混亂。

（2）傳統(tǒng)合同網(wǎng)在投標(biāo)階段，未對投標(biāo)Agent做一定的限制，導(dǎo)致其他所有的Agent都參與投標(biāo)，產(chǎn)生了不必要的信息傳遞，降低了算法的效率。

（2）某些投標(biāo)Agent雖然最多再能執(zhí)行一次任務(wù)，但卻參與了多項任務(wù)的投標(biāo)，浪費了資源。

4 基于改進合同網(wǎng)的動態(tài)任務(wù)分配

4.1 任務(wù)的初始分配

在作戰(zhàn)開始前，指揮中心根據(jù)己知的戰(zhàn)場信息，在滿足約束條件下，對任務(wù)進行預(yù)分配，確定各個Agent的任務(wù)集，即Agent需要打擊的目標(biāo)列表。保證多Agent系統(tǒng)執(zhí)行任務(wù)的效能最大。本文將執(zhí)行任務(wù)的效能作為目標(biāo)函數(shù)，利用粒子群算法對目標(biāo)函數(shù)進行優(yōu)化，得到初始任務(wù)分配方案。

4.2 具體優(yōu)化內(nèi)容

當(dāng)戰(zhàn)場環(huán)境出現(xiàn)變化時，如新的目標(biāo)發(fā)現(xiàn)、某Agent失去繼續(xù)執(zhí)行任務(wù)的能力或者Agent執(zhí)行某一任務(wù)效能突然變低等。若Agent繼續(xù)按照初始任務(wù)分配方案執(zhí)行任務(wù)，可能會造成執(zhí)行任務(wù)的效能降低。因此，本文基于改進合同網(wǎng)進行動態(tài)任務(wù)分配。

在傳統(tǒng)合同網(wǎng)的基礎(chǔ)上，引入任務(wù)中轉(zhuǎn)站和任務(wù)優(yōu)先級的概念，并對算法的招標(biāo)和投標(biāo)階段進行改進，具體如下。

4.2.1 任務(wù)中轉(zhuǎn)站

任務(wù)中轉(zhuǎn)站負責(zé)協(xié)助Agent分布式結(jié)構(gòu)處理協(xié)作問題。任務(wù)中轉(zhuǎn)站的功能具體有以下幾種：

（1）負責(zé)儲存信息，這些信息包括在執(zhí)行任務(wù)的過程中發(fā)現(xiàn)的新任務(wù)，Agent損傷導(dǎo)致無法執(zhí)行任務(wù)自身的任務(wù)集以及Agent由于自身能力變化而產(chǎn)生的任務(wù)。

（2）招標(biāo)者評估標(biāo)書時，首先任務(wù)中轉(zhuǎn)站評估出各個投標(biāo)者投遞價格最優(yōu)的標(biāo)書，然后將各個投標(biāo)者價格最優(yōu)標(biāo)書投遞給招標(biāo)者進行評估。

引入任務(wù)中轉(zhuǎn)站有如下幾個優(yōu)點：

（1）可以處理Agent無法處理的情況。如在執(zhí)行任務(wù)過程中發(fā)現(xiàn)的新任務(wù)。新任務(wù)不屬于Agent本身的任務(wù)，招標(biāo)Agent無法將該任務(wù)直接納入自身投標(biāo)任務(wù)，此時任務(wù)中轉(zhuǎn)站可以將這種情況產(chǎn)生的新任務(wù)存在任務(wù)中轉(zhuǎn)站中，直接當(dāng)作招標(biāo)任務(wù)，增強了算法的擴展性。

（2）降低了各Agent之間的通信次數(shù)。任務(wù)中轉(zhuǎn)站可以預(yù)先評估最優(yōu)標(biāo)書，從而直接將價格最優(yōu)的標(biāo)書直接投遞給招標(biāo)者，減少了Agent的負擔(dān)。

（3）輔助協(xié)調(diào)各Agent之間的任務(wù)分配。當(dāng)環(huán)境變化不止一種時，任務(wù)中轉(zhuǎn)站會根據(jù)任務(wù)優(yōu)先級，依次按照優(yōu)先級處理各種情況產(chǎn)生的新任務(wù)，使任務(wù)調(diào)整過程合理且高效。

4.2.2 任務(wù)優(yōu)先級

本文定義了任務(wù)優(yōu)先級。在各種動態(tài)環(huán)境中，Agent分布式結(jié)構(gòu)會優(yōu)先處理優(yōu)先級高的任務(wù)。定義如下：

（1） Agent數(shù)量的變化。在Agent執(zhí)行任務(wù)的過程中，某些Agent可能無法執(zhí)行任務(wù)或突然增加Agent的數(shù)量，則該Agent本身的任務(wù)即當(dāng)作招標(biāo)任務(wù)處理。這種情況導(dǎo)致的任務(wù)優(yōu)先度最高。

（2）新的任務(wù)出現(xiàn)。在Agent執(zhí)行任務(wù)的過程中，可能會發(fā)現(xiàn)新的目標(biāo)，即有新的任務(wù)產(chǎn)生。這種情況導(dǎo)致的任務(wù)優(yōu)先度次于第一種情況。

（3） Agent執(zhí)行某項任務(wù)的效能突然變低。在Agent執(zhí)行任務(wù)的過程中，Agent自身能力變化導(dǎo)致執(zhí)行任務(wù)的效能突然變低，需要將此任務(wù)當(dāng)作招標(biāo)任務(wù)處理。這種情況導(dǎo)致的任務(wù)優(yōu)先度最低。

定義任務(wù)優(yōu)先度，使得Agent分布式結(jié)構(gòu)能有序處理環(huán)境變化下的任務(wù)分配，有效提高了算法的效率。

4.2.3 招標(biāo)和投標(biāo)階段的改進

為了減少不必要的通信量，本文在招標(biāo)和投標(biāo)階段進行了改進，設(shè)定了閾值，具體定義如下：

（1）招標(biāo)任務(wù)閾值，只有當(dāng)招標(biāo)Agent的執(zhí)行任務(wù)的效能低于閾值時，招標(biāo)Agent才會將該任務(wù)進行招標(biāo)。

（2）投標(biāo)Agent閾值，只有當(dāng)其他Agent執(zhí)行招標(biāo)任務(wù)的效能高于閾值時，才能進行投標(biāo)。

4.3 改進合同網(wǎng)的流程

其步驟可總結(jié)如下：

（1）確定算法的各種初始參數(shù)。

（2）利用粒子群算法，求解得到任務(wù)的初始分配方案。

（3）環(huán)境變化時，對于Agent能力削弱，若該Agent執(zhí)行任務(wù)的效能低于招標(biāo)任務(wù)閾值，則將此任務(wù)納入任務(wù)中轉(zhuǎn)站作為招標(biāo)任務(wù)，對于Agent數(shù)量變化以及新任務(wù)，則直接納入任務(wù)中轉(zhuǎn)站作為招標(biāo)任務(wù)。任務(wù)中轉(zhuǎn)站根據(jù)任務(wù)優(yōu)先級，將任務(wù)按照優(yōu)先級定義順序確定招標(biāo)任務(wù)并進行招標(biāo)。

（4）其他Agent判斷自身是否還有能力進行投標(biāo)。投標(biāo)Agent執(zhí)行招標(biāo)任務(wù)的效能高于投標(biāo)任務(wù)閩值時，才會投遞標(biāo)書。投標(biāo)Agent的標(biāo)書由任務(wù)中轉(zhuǎn)站進行處理，選出最優(yōu)標(biāo)書。

（5）任務(wù)中轉(zhuǎn)站將出價最高的標(biāo)書的投標(biāo)Agent作為中標(biāo)者。

（6）各個Agent根據(jù)招標(biāo)投標(biāo)結(jié)果，更新各自的任務(wù)集。

（7）判斷由環(huán)境變化產(chǎn)生的招標(biāo)任務(wù)是否全部分配完畢。若沒有分配完畢，則繼續(xù)執(zhí)行步驟3到6的內(nèi)容。若已分配完畢，則算法結(jié)束。

5 仿真計算實例

5.1 多Agent初始任務(wù)分配方案

本文基于改進合同網(wǎng)對任務(wù)分配問題進行仿真計算，首先得到任務(wù)初始分配方案。在仿真計算中，假設(shè)Agent數(shù)目為5個，目標(biāo)數(shù)目為12個，每個Agent執(zhí)行任務(wù)的數(shù)量不能超過4個，ω1和ω2分別為0.5和O.l。Agent位置如表l所示，Agent對目標(biāo)執(zhí)行任務(wù)的成功概率如表2所示。目標(biāo)自身位置和價值如表3所示，Agent對目標(biāo)執(zhí)行任務(wù)后的損傷概率如表4所示。

經(jīng)過200次的仿真計算表明，在上述條件下得到的結(jié)果具有穩(wěn)定性。基于上述條件，首先得到初始分配方案集。圖4給出了整體效能隨迭代次數(shù)增加的收斂曲線，隨著迭代次數(shù)增加，多Agent執(zhí)行任務(wù)的效能值收斂在一個較穩(wěn)定的數(shù)值，證明了算法的收斂性。圖5給出各Agent按照預(yù)先任務(wù)分配示意圖，表5給出各Agent任務(wù)集和效能值。Aa的目標(biāo)為4，9，效能值為0.851。Ab的目標(biāo)為7，11，效能值為0.982。Ac的目標(biāo)為6，12，效能值為1 095。Ad的目標(biāo)為10，8，3，效能值為1.639。Ae的目標(biāo)為1，2，5，效能值為1 564。上述結(jié)果為任務(wù)的初始分配方案，所消耗時間為2.7s。

5.2 多Agent動態(tài)任務(wù)分配

得到任務(wù)初始分配方案后，在各Agent執(zhí)行任務(wù)過程中，遇到以下情況，基于改進合同網(wǎng)的動態(tài)任務(wù)分配算法會進行調(diào)整，得到最優(yōu)方案。主要參數(shù)設(shè)置如下，招標(biāo)任務(wù)閾值a為O.l，投標(biāo)閩值b為O.l。

5.2.1 Agent數(shù)量損失

當(dāng)執(zhí)行任務(wù)過程中，出現(xiàn)Agent損傷或者無法繼續(xù)執(zhí)行任務(wù)的情況時，則需要進行動態(tài)任務(wù)分配。假設(shè)Ae無法執(zhí)行任務(wù)時，則將Ae之前執(zhí)行的任務(wù)放入任務(wù)中轉(zhuǎn)站中，經(jīng)算法更新任務(wù)分配方案，如圖6所示。表6給出各Agent任務(wù)集和效能值。與任務(wù)的初始分配方案相比，Ae的任務(wù)分配給其他有能力的Agent執(zhí)行，所消耗時間為0.176s。

5.2.2 新目標(biāo)的發(fā)現(xiàn)

當(dāng)執(zhí)行任務(wù)過程中，發(fā)現(xiàn)新的目標(biāo)需要打擊，則需要進行動態(tài)任務(wù)分配。假設(shè)偵察到新目標(biāo)13，14以及它們的各項參數(shù)后，并將這兩項任務(wù)轉(zhuǎn)入任務(wù)中轉(zhuǎn)站，經(jīng)算法更新任務(wù)分配方案，如圖7所示。表7給出各Agent任務(wù)集和效能值。與任務(wù)的初始分配方案相比，新任務(wù)目標(biāo)13，14分配給了Ad，Ae執(zhí)行，所消耗時間為0.122s。

5.2.3 Agent能力變化

當(dāng)執(zhí)行任務(wù)過程中，Agent出現(xiàn)能力變化，如對某個目標(biāo)成功概率降低之類的情況，則需要進行動態(tài)任務(wù)分配。假設(shè)Ad對于目標(biāo)3的成功概率降低，當(dāng)執(zhí)行對目標(biāo)3打擊任務(wù)的效能低于招標(biāo)任務(wù)閩值時，則將該任務(wù)進行招標(biāo)，經(jīng)算法更新任務(wù)分配方案，如圖8所示。表8給出各Agent任務(wù)集和效能值。與任務(wù)初始分配方案相比，Ad將對目標(biāo)3執(zhí)行的任務(wù)招標(biāo)，Ac中標(biāo)獲得目標(biāo)3的執(zhí)行任務(wù)權(quán)，所消耗時間為0.099s。

5.2.4 Agent數(shù)量損失、新目標(biāo)發(fā)現(xiàn)和Agent能力降低同時發(fā)生

當(dāng)執(zhí)行任務(wù)過程，同時發(fā)生三種情況。假設(shè)Ae損傷或無法執(zhí)行任務(wù)，偵察到新目標(biāo)13，14以及它們的各項參數(shù)，還有Ad對于目標(biāo)3的成功概率降低，導(dǎo)致執(zhí)行該任務(wù)的效能低于招標(biāo)任務(wù)閾值。將這些任務(wù)都轉(zhuǎn)入任務(wù)中轉(zhuǎn)站，基于改進合同網(wǎng)的任務(wù)分配算法重新更新任務(wù)分配方案，如圖9所示。表9給出各Agent任務(wù)集和效能值。與任務(wù)初始分配方案相比，首先Ae的任務(wù)集分配給其他有能力的Agent執(zhí)行，其次將新目標(biāo)分配給能以更高效能執(zhí)行任務(wù)的Agent，最后Ad將對目標(biāo)3執(zhí)行的任務(wù)招標(biāo)，Aa獲得執(zhí)行任務(wù)權(quán)，所消耗時間為0.161s。

5.3 小結(jié)

仿真實驗表明，在引入任務(wù)中轉(zhuǎn)站以及任務(wù)優(yōu)先級概念后，該算法能夠在各種場景變化下快速給出任務(wù)分配算法，若按粒子群算法重新得到任務(wù)分配算法，所消耗時間為2s以上時，而采用改進合同網(wǎng)的任務(wù)分配算法僅耗時0.2s左右，提高了算法求解效率。

6 結(jié)論

針對多Agent動態(tài)任務(wù)分配問題.本文建立了動態(tài)任務(wù)分配模型，并在傳統(tǒng)合同網(wǎng)的基礎(chǔ)上，提出改進合同的任務(wù)分配算法，引入任務(wù)中轉(zhuǎn)站以及任務(wù)優(yōu)先級協(xié)助處理任務(wù)分配方案，并對算法的招標(biāo)和投標(biāo)階段進行改進，設(shè)置了招標(biāo)任務(wù)閾值和投標(biāo)任務(wù)閾值。最后，通過仿真結(jié)果驗證，該算法能在各種環(huán)境變化下，快速更新任務(wù)分配方案。

參考文獻

[1] Oliveiro E，F(xiàn)ischer K.Multi-agentSystems：Which Research for WhichApplications[J].Robotics andAutonomous Systems， 1999（2 7）：91-106.

[2] C. Hewitt. Viewing controlstructures as patterns of passingmessages [J]. Artificial Intelligence，1997，8 （03）： 323-364.

[3] Alberts，D.S.Network Centric Warfare：Developing and Leveraging InformationSuperiority [M]. Washingt on， DC： CCRPPublications，Aug 1999.

[4]萬武南，張蕾.基于任務(wù)熟人集的合同網(wǎng)模型的改進[J]，計算機應(yīng)用，2003，23 （03）：3-5.

[5]龍濤，陳巖，沈林成.基于合同機制的多UCAV分布式協(xié)同任務(wù)控制[J].航空學(xué)報，2007， 28 （02）： 352-357.

[6]裘杭萍，覃垚，胡汭等，多Agent系統(tǒng)中基于改進合同網(wǎng)模型的任務(wù)分配研究[J].計算機科學(xué)，2012，39 （6A）： 279-281.

[7]C.George.Distributed Systems：Concepts and Design[M].Boston：Addison-Wesley，2011.

[8]霍霄華，陳巖，朱華勇等，多UCAV協(xié)同控制中的任務(wù)分配模型及算法[J].國防科技大學(xué)學(xué)報，2006，28 （03）： 83-88.

[9]R.Davis. Negotiation as ametaphor for distributedproblem solving [J]. ArtificialIntelligence，1983 （20）：63-109.

[10]肖玉杰，李杰，劉方等，基于合同網(wǎng)的分布式動態(tài)任務(wù)分配算法[J].艦船科學(xué)技術(shù)，2015，37 （03）：113-118.