基于多約束投標(biāo)策略的改進(jìn)合同網(wǎng)算法

姜月秋，宗 睿，關(guān)啟學(xué)，關(guān)世杰，張 昕

(沈陽(yáng)理工大學(xué)， 沈陽(yáng) 110159)

隨著戰(zhàn)場(chǎng)環(huán)境的動(dòng)態(tài)變化和作戰(zhàn)任務(wù)的復(fù)雜多樣性，單架無(wú)人機(jī)的自身能力有限，執(zhí)行任務(wù)受損傷的概率比較大，已經(jīng)無(wú)法滿(mǎn)足戰(zhàn)爭(zhēng)的需求。相比單架無(wú)人機(jī)，多無(wú)人機(jī)協(xié)同作戰(zhàn)在時(shí)間和空間上都占有比較大的優(yōu)勢(shì)，具有更好的靈活性，可以充分發(fā)揮自身的優(yōu)勢(shì)去完成更復(fù)雜的工作，提高工作效率和任務(wù)的成功率[1]。多無(wú)人機(jī)協(xié)同作戰(zhàn)的廣泛應(yīng)用，促使多無(wú)人機(jī)協(xié)同任務(wù)分配技術(shù)得到了迅速的發(fā)展。多無(wú)人機(jī)協(xié)同任務(wù)分配[2]，指的是根據(jù)各種設(shè)備和系統(tǒng)提供的環(huán)境信息，以及無(wú)人機(jī)自身的性能，對(duì)多架無(wú)人機(jī)進(jìn)行任務(wù)的分配，并且能夠隨著動(dòng)態(tài)環(huán)境的變化進(jìn)行實(shí)時(shí)協(xié)商和任務(wù)方案的調(diào)整[3]。

世界各國(guó)對(duì)無(wú)人機(jī)等智能體的協(xié)同任務(wù)分配方面高度重視，各個(gè)領(lǐng)域的學(xué)者和專(zhuān)家進(jìn)行了大量研究，提出了大量任務(wù)分配算法，有離散粒子群優(yōu)化法[4]、遺傳算法[5]、黑板模型算法[6]、基于概率估計(jì)的交叉熵法[7]、合同網(wǎng)算法[8]。

在合同網(wǎng)算法中，無(wú)人機(jī)擔(dān)任的角色非常靈活，可以擔(dān)任招標(biāo)者，也可以擔(dān)任投標(biāo)者。所有的無(wú)人機(jī)之間都可以進(jìn)行通信，是一種非常靈活且魯棒性較高的分布式任務(wù)分配算法。文獻(xiàn)[9]為了適應(yīng)Agent能力動(dòng)態(tài)變動(dòng)的環(huán)境，引入信任度的概念，提出了動(dòng)態(tài)合同網(wǎng)。后來(lái)研究人員通過(guò)引入交互信任度、熟人信任度和閾值等策略提高效率。信任是對(duì)無(wú)人機(jī)能夠完成任務(wù)的相信程度[10]，當(dāng)無(wú)人機(jī)在完成任務(wù)時(shí)可以更新信任度，或者根據(jù)熟人推薦的評(píng)定信息來(lái)更新信任度[11]。文獻(xiàn)[12]使用任務(wù)信任度和任務(wù)負(fù)載率雙重因素對(duì)合同網(wǎng)進(jìn)行改進(jìn)，并用信任度閾值的策略對(duì)任務(wù)的發(fā)布范圍進(jìn)行彈性選擇。文獻(xiàn)[13]將合同網(wǎng)協(xié)議與管理者之間的直接談判相結(jié)合，文獻(xiàn)[14]采用了合同網(wǎng)算法模型，為了使任務(wù)分配更能適用于動(dòng)態(tài)環(huán)境，建立能力模型和執(zhí)行的任務(wù)描述，通過(guò)將正在執(zhí)行的任務(wù)進(jìn)行招標(biāo)來(lái)動(dòng)態(tài)改變自身能力以進(jìn)行任務(wù)的再分配，這種協(xié)商策略的引入，明顯地改善了任務(wù)分配的效果，但也增加了決策的成本，導(dǎo)致通信量增大。文獻(xiàn)[15]采用傳統(tǒng)合同網(wǎng)算法，引入了一種計(jì)算邊際成本的投標(biāo)模型和評(píng)標(biāo)模型，雖然能夠改善任務(wù)分配的效果，但同時(shí)也增大了系統(tǒng)中的通信量。

1 傳統(tǒng)合同網(wǎng)算法

合同網(wǎng)算法(contract net protocol，CNP)是由Randall Davis和Reid G.Smith于1980年提出的，用于解決分布式問(wèn)題的任務(wù)協(xié)作和任務(wù)分配算法，該算法通過(guò)模擬人類(lèi)在活動(dòng)中的招投評(píng)標(biāo)機(jī)制，實(shí)現(xiàn)任務(wù)分配。合同網(wǎng)算法的基本思想是通過(guò)招標(biāo)、投標(biāo)、中標(biāo)、簽約4個(gè)階段，如圖1所示。

1) 招標(biāo)階段：系統(tǒng)中的某架無(wú)人機(jī)發(fā)現(xiàn)新任務(wù)或者發(fā)現(xiàn)有任務(wù)無(wú)法獨(dú)立完成需要分配時(shí)，該無(wú)人機(jī)作為招標(biāo)者，制定招標(biāo)信息后，向其它無(wú)人機(jī)發(fā)布招標(biāo)信息尋求幫助，通知其他無(wú)人機(jī)作為投標(biāo)者來(lái)參與此次招標(biāo)活動(dòng)。

2) 投標(biāo)階段：系統(tǒng)中的其他無(wú)人機(jī)接收到招標(biāo)者發(fā)送的招標(biāo)信息后，參考招標(biāo)信息中的能力和資源需求，以及自身的具體情況，制定參與投標(biāo)的標(biāo)書(shū)，并發(fā)送給招標(biāo)者參與投標(biāo)。

3) 中標(biāo)階段：招標(biāo)者接收到投標(biāo)者的標(biāo)書(shū)后，根據(jù)具體的投標(biāo)信息評(píng)估準(zhǔn)則進(jìn)行評(píng)標(biāo)，選擇出最合適的投標(biāo)者成為本輪招標(biāo)活動(dòng)的中標(biāo)者。

4) 簽約階段：根據(jù)合同信息，招標(biāo)者和中標(biāo)者達(dá)成一致后，雙方簽訂合同，中標(biāo)者的任務(wù)序列中加入此任務(wù)，至此完成一次任務(wù)的分配。

圖1 傳統(tǒng)合同網(wǎng)算法任務(wù)分配過(guò)程框圖

傳統(tǒng)的合同網(wǎng)算法雖然能夠?qū)⑷蝿?wù)成功的分配給系統(tǒng)成員，但是仍然存在不足之處，降低了任務(wù)分配的效率和系統(tǒng)的整體效能。傳統(tǒng)合同網(wǎng)算法中，沒(méi)有限制可以參與投標(biāo)的無(wú)人機(jī)數(shù)量，不管有沒(méi)有足夠的能力執(zhí)行任務(wù)，只要是接收到招標(biāo)信息的無(wú)人機(jī)，都可以參與到投標(biāo)活動(dòng)中進(jìn)行投標(biāo)。這樣頻繁的通信，會(huì)加重系統(tǒng)的通信負(fù)擔(dān)。若系統(tǒng)中的無(wú)人機(jī)數(shù)量不斷增加，就會(huì)造成系統(tǒng)中的通信量快速增大，甚至?xí)?dǎo)致系統(tǒng)的擁堵和癱瘓。本文選擇合同網(wǎng)算法解決多無(wú)人機(jī)的協(xié)同任務(wù)分配問(wèn)題，設(shè)計(jì)了一種合同網(wǎng)改進(jìn)算法，在投標(biāo)階段進(jìn)行改進(jìn)，不僅降低了系統(tǒng)中的投標(biāo)者的數(shù)量，均衡了通信量，還降低了無(wú)人機(jī)的工作負(fù)載，并使其保持在一個(gè)穩(wěn)定的水平。

2 改進(jìn)合同網(wǎng)算法

2.1 任務(wù)效能模型

無(wú)人機(jī)協(xié)同任務(wù)分配方案的好壞需要用某個(gè)指標(biāo)來(lái)衡量，所以本文建立了任務(wù)效能模型，該模型以無(wú)人機(jī)完成任務(wù)時(shí)所獲得的收益函數(shù)和付出的代價(jià)函數(shù)為基礎(chǔ)，通過(guò)計(jì)算2個(gè)函數(shù)的差值來(lái)反應(yīng)任務(wù)分配方案的優(yōu)劣和可行性。

無(wú)人機(jī)UAVi完成任務(wù)獲得的收益主要由任務(wù)自身的價(jià)值以及無(wú)人機(jī)UAVi執(zhí)行任務(wù)的能力共同來(lái)決定。任務(wù)自身的價(jià)值是預(yù)先設(shè)定好的，無(wú)人機(jī)UAVi執(zhí)行任務(wù)的能力是根據(jù)數(shù)據(jù)庫(kù)的歷史信息獲取的，主要體現(xiàn)在無(wú)人機(jī)自身的性能和無(wú)人機(jī)歷史網(wǎng)絡(luò)吞吐量，無(wú)人機(jī)自身性能包括無(wú)人機(jī)攜帶的武器裝備、傳感器、最大續(xù)航時(shí)間和可靠性等，通常以概率進(jìn)行描述。

無(wú)人機(jī)UAVi對(duì)某目標(biāo)Tj執(zhí)行攻擊任務(wù)，目標(biāo)Tj的自身價(jià)值為Vj，UAVi對(duì)該目標(biāo)的摧毀概率為Pj，無(wú)人機(jī)UAVi對(duì)目標(biāo)進(jìn)行攻擊后的生存概率為Ps，則無(wú)人機(jī)UAVi執(zhí)行該攻擊任務(wù)Tj所獲得的收益Reward(Tj)為：

Reward(Tj)=Vj*Pj*Ps

無(wú)人機(jī)UAVi完成任務(wù)Tj所需要付出的代價(jià)表示為cost(Tj)，該代價(jià)函數(shù)主要考慮以下2個(gè)方面：

一是作用在無(wú)人機(jī)上的阻力，阻力計(jì)算公式為

式中，Cx0為零升阻力系數(shù)，CL為升力系數(shù)，通常也是通過(guò)風(fēng)洞實(shí)驗(yàn)得來(lái)的：

CL=CLa(α-α0)

式中：α為迎角，α0為升力等于零時(shí)的迎角，CLa與翼型有關(guān)，近似為常數(shù)。

A為機(jī)翼的展弦比：

式中：L為翼展長(zhǎng)度，S為機(jī)翼的面積。需要注意的是，兩者的數(shù)量單位要保持一致。

綜上所述可得，作用在無(wú)人機(jī)上的阻力為：

則無(wú)人機(jī)付出的阻力代價(jià)表示為

二是無(wú)人機(jī)UAVi執(zhí)行任務(wù)Tj的風(fēng)險(xiǎn)代價(jià)，用無(wú)人機(jī)自身的價(jià)值Vi和無(wú)人機(jī)在執(zhí)行任務(wù)過(guò)程中的損耗概率Pk來(lái)表示，即：

Riskcost(Tj)=Vi*Pk

因此，無(wú)人機(jī)UAVi執(zhí)行任務(wù)Tj的代價(jià)為：

cost(Tj)=w1*Xcost(Tj) +w2*Riskcost(Tj)

w1和w2表示的是對(duì)于任務(wù)分配結(jié)果的影響程度，值越大，說(shuō)明該因素對(duì)于任務(wù)分配的結(jié)果有很大的影響。其中w1+w2=1。

通過(guò)上述對(duì)無(wú)人機(jī)的收益函數(shù)Reward(Tj)和代價(jià)函數(shù)cost(Tj)的定義，可得無(wú)人機(jī)UAVi完成任務(wù)Tj的任務(wù)效能U(Tj)為

U(Tj)=Reward(Tj)-cost(Tj)

在計(jì)算時(shí)需要先將不同的單位進(jìn)行統(tǒng)一，即分別對(duì)任務(wù)收益Reward(Tj)和任務(wù)代價(jià)cost(Tj)進(jìn)行歸一化處理，統(tǒng)一成相同的量綱后再進(jìn)行運(yùn)算。

綜上所述，多無(wú)人機(jī)協(xié)同任務(wù)分配的目標(biāo)函數(shù)模型為

Uij表示無(wú)人機(jī)UAVi執(zhí)行完任務(wù)Tj后所獲得的任務(wù)效能。也就是說(shuō)，多無(wú)人機(jī)協(xié)同任務(wù)分配的最終目標(biāo)是，使系統(tǒng)中的所有無(wú)人機(jī)執(zhí)行完任務(wù)序列中的所有任務(wù)后，系統(tǒng)的整體任務(wù)效能達(dá)到最大。

2.2 投標(biāo)策略

傳統(tǒng)合同網(wǎng)算法中，在接收到招標(biāo)者發(fā)布的任務(wù)后，系統(tǒng)中所有的無(wú)人機(jī)均可參與投標(biāo)，這就會(huì)造成系統(tǒng)通信頻繁，同時(shí)招標(biāo)者后續(xù)的評(píng)標(biāo)工作負(fù)擔(dān)也會(huì)增大。那么，為了減少系統(tǒng)中的通信量，最簡(jiǎn)單直接的辦法就是減少投標(biāo)者的數(shù)量。

本文設(shè)計(jì)了一種基于無(wú)人機(jī)能力評(píng)估方法的投標(biāo)策略。無(wú)人機(jī)的能力評(píng)估方法，是以無(wú)人機(jī)的能力大小為評(píng)判標(biāo)準(zhǔn)，需要結(jié)合無(wú)人機(jī)之前和當(dāng)下的情況來(lái)進(jìn)行綜合評(píng)估。投標(biāo)者可以根據(jù)自己曾經(jīng)完成任務(wù)的相關(guān)歷史信息，獲得自己的歷史任務(wù)效能；其次，還要以投標(biāo)者執(zhí)行本輪招標(biāo)任務(wù)的任務(wù)效能為依據(jù)進(jìn)行判斷；最后，根據(jù)投標(biāo)者自身的當(dāng)前狀態(tài)，獲取投標(biāo)者的工作負(fù)載和網(wǎng)絡(luò)吞吐量。根據(jù)以上4個(gè)方面，獲取評(píng)估所需要的相關(guān)信息，使投標(biāo)者對(duì)自己的能力進(jìn)行評(píng)估。

引入工作負(fù)載為T(mén)i，即無(wú)人機(jī)UAVi完成任務(wù)的最短時(shí)間為T(mén)i，則平均工作負(fù)載為

式中，w1為系統(tǒng)中執(zhí)行任務(wù)的無(wú)人機(jī)數(shù)量。

所以，無(wú)人機(jī)UAVi的工作負(fù)載系數(shù)為

工作負(fù)載系數(shù)CTi的含義是：

當(dāng)CTi<0時(shí)，說(shuō)明第i架無(wú)人機(jī)的工作負(fù)載比系統(tǒng)中的平均負(fù)載低；

當(dāng)CTi>0時(shí)，說(shuō)明第i架無(wú)人機(jī)的工作負(fù)載比系統(tǒng)中的平均負(fù)載高；

當(dāng)CTi

當(dāng)Wt>10時(shí)，說(shuō)明此時(shí)無(wú)人機(jī)網(wǎng)絡(luò)超負(fù)荷，應(yīng)減少任務(wù)量。

當(dāng)1

當(dāng)0.5

當(dāng)Wt≤0.5時(shí)，說(shuō)明此時(shí)無(wú)人機(jī)網(wǎng)絡(luò)負(fù)載小，適合增加任務(wù)量。

綜上所述，無(wú)人機(jī)的能力Ai可表示為

β1和β2分別表示歷史任務(wù)效能和執(zhí)行本輪招標(biāo)任務(wù)的任務(wù)效能的影響因子。β1+β2=1。

圖2 改進(jìn)合同網(wǎng)算法任務(wù)分配過(guò)程框圖

基于無(wú)人機(jī)能力評(píng)估方法的投標(biāo)策略，既考慮了無(wú)人機(jī)的歷史任務(wù)效能和本輪招標(biāo)任務(wù)的任務(wù)效能，又考慮了無(wú)人機(jī)的工作負(fù)載。不僅保證了投標(biāo)者執(zhí)行任務(wù)的穩(wěn)定性和可靠性，還保證了投標(biāo)者執(zhí)行本次任務(wù)能夠獲得較大的任務(wù)效能。另外，也避免了給無(wú)人機(jī)帶來(lái)過(guò)大的工作壓力。

3 仿真與分析

為了驗(yàn)證本文所設(shè)計(jì)算法的有效性，進(jìn)行了多組計(jì)算機(jī)模擬仿真實(shí)驗(yàn)。假設(shè)系統(tǒng)中有8架無(wú)人機(jī)對(duì)50個(gè)目標(biāo)執(zhí)行任務(wù)，信道容量為600 bps，模擬戰(zhàn)場(chǎng)區(qū)域是邊長(zhǎng)為 10 km的正方形區(qū)域。

圖3為無(wú)人機(jī)改進(jìn)合同網(wǎng)算法與另外2種算法中投標(biāo)者的數(shù)量對(duì)比仿真曲線，系統(tǒng)中有8架無(wú)人機(jī)，一共對(duì)30個(gè)任務(wù)進(jìn)行了招標(biāo)，每個(gè)招標(biāo)任務(wù)的投標(biāo)者數(shù)量如圖所示。由仿真結(jié)果的對(duì)比可以看出，改進(jìn)合同網(wǎng)算法中，每個(gè)招標(biāo)任務(wù)的投標(biāo)者數(shù)量要明顯小于傳統(tǒng)合同網(wǎng)算法中的投標(biāo)者數(shù)量，平均減少了56.25%。而在傳統(tǒng)合同網(wǎng)算法中，系統(tǒng)中所有的無(wú)人機(jī)都作為投標(biāo)者進(jìn)行了投標(biāo)，故投標(biāo)者的數(shù)量即為系統(tǒng)中無(wú)人機(jī)的數(shù)量，始終保持不變。文獻(xiàn)[14]投標(biāo)階段考慮了當(dāng)前能力，投標(biāo)數(shù)量相應(yīng)減少。改進(jìn)合同網(wǎng)算法中的投標(biāo)者在投標(biāo)前對(duì)歷史和當(dāng)前的自身能力還有現(xiàn)階段任務(wù)狀況進(jìn)行考慮，只有具備任務(wù)要求能力并且大于招標(biāo)者能力的投標(biāo)者才會(huì)參與投標(biāo)，這樣就減小了投標(biāo)者的數(shù)量以及招標(biāo)者的評(píng)標(biāo)壓力。

圖3 投標(biāo)者數(shù)量仿真曲線

圖4為中標(biāo)者改進(jìn)合同網(wǎng)算法與另外2種算法中的執(zhí)行任務(wù)的時(shí)間對(duì)比仿真曲線。

圖4 執(zhí)行任務(wù)時(shí)間仿真曲線

執(zhí)行任務(wù)的時(shí)間就是上文所定義的工作負(fù)載，由圖可以看出，改進(jìn)合同網(wǎng)算法中，對(duì)能否成為投標(biāo)者有了工作負(fù)載的約束，如果此時(shí)工作負(fù)載較高，則拒絕投標(biāo)，從而使中標(biāo)者執(zhí)行任務(wù)的時(shí)間降低，并且使得每次中標(biāo)者的執(zhí)行任務(wù)時(shí)間相當(dāng)。文獻(xiàn)[14]算法，可以選擇將優(yōu)先級(jí)低的任務(wù)重新分配，并對(duì)該任務(wù)進(jìn)行招標(biāo)，以此來(lái)尋找系統(tǒng)的最優(yōu)分配方案，但任務(wù)再分配會(huì)導(dǎo)致任務(wù)完成時(shí)間增加。在傳統(tǒng)合同網(wǎng)算法中，中標(biāo)者的執(zhí)行任務(wù)時(shí)間比改進(jìn)合同網(wǎng)算法高很多，上下波動(dòng)范圍較大，不穩(wěn)定。說(shuō)明改進(jìn)合同網(wǎng)算法中的投標(biāo)策略在考慮工作負(fù)載這一因素后，不僅能夠降低無(wú)人機(jī)的執(zhí)行任務(wù)的時(shí)間，還能使其保持在相對(duì)穩(wěn)定狀態(tài)。

圖5為中標(biāo)者在改進(jìn)合同網(wǎng)算法與另外2種算法的中的無(wú)人機(jī)網(wǎng)絡(luò)吞吐量仿真曲線。其值越小，說(shuō)明無(wú)人機(jī)的任務(wù)分配越合理，即已選擇當(dāng)前通信狀態(tài)比較空閑的無(wú)人機(jī)參與投標(biāo)。由圖可知，改進(jìn)合同網(wǎng)算法中，經(jīng)過(guò)投標(biāo)策略的設(shè)定，對(duì)能否成為投標(biāo)者考慮了當(dāng)前無(wú)人機(jī)吞吐量，使得每一個(gè)無(wú)人機(jī)充分利用網(wǎng)絡(luò)帶寬，網(wǎng)絡(luò)吞吐量處于比較穩(wěn)定狀態(tài)。對(duì)于文獻(xiàn)[14]算法來(lái)說(shuō)，由于該算法能夠?qū)⒆陨淼恼谔幚淼娜蝿?wù)進(jìn)行招標(biāo)，這樣會(huì)增加標(biāo)書(shū)的數(shù)量進(jìn)而增加系統(tǒng)的通信量，會(huì)造成通信負(fù)擔(dān)。在傳統(tǒng)合同網(wǎng)算法中，中標(biāo)者的網(wǎng)絡(luò)吞吐量大小不一，波動(dòng)范圍較大，不能很好地利用網(wǎng)絡(luò)帶寬，造成了資源浪費(fèi)，也很可能會(huì)造成網(wǎng)絡(luò)擁塞。進(jìn)而說(shuō)明，改進(jìn)合同網(wǎng)算法中的投標(biāo)策略在考慮網(wǎng)絡(luò)吞吐量這一因素后，不僅能降低網(wǎng)絡(luò)的數(shù)據(jù)流量，均衡網(wǎng)絡(luò)吞吐量，還可以有效減少網(wǎng)絡(luò)擁塞。

圖5 中標(biāo)者吞吐量仿真曲線

圖6為改進(jìn)合同網(wǎng)算法與另外2種算法系統(tǒng)任務(wù)效能的仿真曲線，仿真次數(shù)為30次。

圖6 任務(wù)效能仿真曲線

由仿真對(duì)比結(jié)果可以看出，改進(jìn)合同網(wǎng)算法的系統(tǒng)任務(wù)效能優(yōu)于另外2種算法。說(shuō)明通過(guò)對(duì)無(wú)人機(jī)進(jìn)行工作負(fù)載以及網(wǎng)絡(luò)吞吐量的進(jìn)行投標(biāo)約束，從而減少無(wú)人機(jī)付出的代價(jià)，選擇了當(dāng)前狀態(tài)比較好的無(wú)人機(jī)投標(biāo)，提高任務(wù)效能。多無(wú)人機(jī)協(xié)同任務(wù)分配方案的好壞就是通過(guò)任務(wù)效能這個(gè)變量來(lái)體現(xiàn)的，說(shuō)明改進(jìn)的合同網(wǎng)算法能夠很好的對(duì)模型進(jìn)行求解，提高分配效率，驗(yàn)證了其可行性和有效性。

4 結(jié)論

本文提出了一種改進(jìn)的合同網(wǎng)算法。仿真結(jié)果表明，改進(jìn)的合同網(wǎng)算法與傳統(tǒng)的合同網(wǎng)算法相比，在保證系統(tǒng)任務(wù)效能的前提下，投標(biāo)者的數(shù)量明顯減少，從而大大降低了系統(tǒng)中的通信量。另外，無(wú)人機(jī)的工作負(fù)載不僅得到了明顯降低，無(wú)人機(jī)網(wǎng)絡(luò)吞吐量處于均衡水平。優(yōu)化效果明顯，驗(yàn)證了改進(jìn)算法的可行性和有效性。