非死鎖合同網(wǎng)協(xié)議驅(qū)動(dòng)的多機(jī)分布式時(shí)序任務(wù)分配

曹 嚴(yán)，龍 騰，孫景亮，徐廣通

(1. 北京理工大學(xué)宇航學(xué)院，北京 100081；2. 飛行器動(dòng)力學(xué)與控制教育部重點(diǎn)實(shí)驗(yàn)室，北京 100081；3. 清華大學(xué)精密儀器系，北京 100084)

0 引 言

多無人機(jī)(Unmanned aerial vehicle，UAV)協(xié)同能夠擴(kuò)展任務(wù)執(zhí)行能力，提升任務(wù)完成效能。作為多無人機(jī)協(xié)同的關(guān)鍵技術(shù)之一，任務(wù)分配技術(shù)是在多任務(wù)、多目標(biāo)及多無人機(jī)之間進(jìn)行協(xié)調(diào)規(guī)劃，考慮任務(wù)執(zhí)行順序、無人機(jī)性能等約束條件，以任務(wù)代價(jià)最小化為目標(biāo)，將多任務(wù)合理分配給各機(jī)。耦合的任務(wù)時(shí)序約束對(duì)多機(jī)任務(wù)分配帶來較大技術(shù)挑戰(zhàn)，易造成多無人機(jī)因?yàn)闀r(shí)序沖突而陷入死鎖現(xiàn)象，無法獲得可行解。因此，有效避免時(shí)序任務(wù)分配中的死鎖問題至關(guān)重要。

時(shí)序任務(wù)分配方法主要包括集中式與分布式兩類方法。在集中式架構(gòu)下，根據(jù)死鎖產(chǎn)生機(jī)理，通過中心節(jié)點(diǎn)實(shí)現(xiàn)整個(gè)系統(tǒng)的非死鎖任務(wù)調(diào)度。Edison等使用遺傳算法求解時(shí)序任務(wù)分配問題，通過降低死鎖個(gè)體的適應(yīng)度實(shí)現(xiàn)系統(tǒng)非死鎖分配。鄧啟波等基于圖論建立任務(wù)時(shí)序優(yōu)先級(jí)圖，給出死鎖一般形式，并定制轉(zhuǎn)置操作對(duì)陷入死鎖的個(gè)體進(jìn)行解鎖。文獻(xiàn)[8-9]定制遺傳算法的初始化和遺傳操作，確保個(gè)體在進(jìn)化過程中保持非死鎖狀態(tài)，提升了算法的全局最優(yōu)性。Wang等提出改進(jìn)量子粒子群算法，并設(shè)計(jì)時(shí)序任務(wù)次序調(diào)整策略，在算法迭代中有效生成非死鎖任務(wù)序列，該方法較傳統(tǒng)遺傳算法提高了求解穩(wěn)定性。然而，上述任務(wù)分配架構(gòu)存在中心計(jì)算節(jié)點(diǎn)，依賴全局通信，因此系統(tǒng)抗毀性較差。另外，隨著任務(wù)分配問題規(guī)模增大，集中式架構(gòu)下任務(wù)分配方法求解耗時(shí)呈超線性增長(zhǎng)，難以滿足在線實(shí)時(shí)求解的需求。

分布式架構(gòu)下各無人機(jī)不依賴于中心計(jì)算節(jié)點(diǎn)，通過機(jī)間通信協(xié)商實(shí)現(xiàn)任務(wù)的高效分配，系統(tǒng)具備更好的魯棒性與穩(wěn)定性。近年來，基于市場(chǎng)競(jìng)爭(zhēng)機(jī)制的分布式任務(wù)分配算法受到廣泛關(guān)注。吳薇楠根據(jù)任務(wù)間依賴性將時(shí)序耦合約束分為單邊依賴、相互依賴與互斥約束。Jonese等在應(yīng)對(duì)災(zāi)難響應(yīng)問題中考慮消防車滅火與路障清理兩類時(shí)序任務(wù)約束，采用分層拍賣算法對(duì)解空間進(jìn)行快速有界搜索。文獻(xiàn)[16-18]針對(duì)復(fù)雜任務(wù)環(huán)境，構(gòu)建任務(wù)優(yōu)先級(jí)圖，將任務(wù)按時(shí)序關(guān)系分層，并定制迭代拍賣算法對(duì)各層任務(wù)進(jìn)行高效求解。上述方法采用分層求解架構(gòu)處理時(shí)序任務(wù)分配問題，有效規(guī)避了任務(wù)死鎖現(xiàn)象，但固化了時(shí)序任務(wù)的分配次序，縮減了可行解空間，分配結(jié)果最優(yōu)性有待進(jìn)一步提升。Lim等在勢(shì)博弈框架下引入一種調(diào)度算法處理復(fù)雜時(shí)序任務(wù)分配問題，顯著提升了大規(guī)模問題的求解效率，但基于隨機(jī)抽樣的均衡選擇方法使其結(jié)果最優(yōu)性仍難以保證。陳璞等在通信約束任務(wù)分配問題中考慮了任務(wù)死鎖約束，但該方法主要針對(duì)目標(biāo)協(xié)同打擊動(dòng)態(tài)任務(wù)分配問題，未考慮多類型時(shí)序任務(wù)帶來的復(fù)雜耦合影響。文獻(xiàn)[21]提出了耦合約束一致性束算法(CBBA-TCC)，在保留CBBA算法最優(yōu)性特點(diǎn)的基礎(chǔ)上，可短時(shí)內(nèi)生成時(shí)序任務(wù)分配方案，但CBBA-TCC僅考慮兩類時(shí)序任務(wù)，不適用于“察打評(píng)”多時(shí)序任務(wù)下無人機(jī)協(xié)同任務(wù)場(chǎng)景。因此，有必要充分考慮各時(shí)序任務(wù)的耦合關(guān)系與死鎖影響，擴(kuò)展可行解空間，在保證分布式架構(gòu)下時(shí)序任務(wù)分配算法求解時(shí)效性優(yōu)勢(shì)的前提下，提升分配結(jié)果最優(yōu)性。

本文針對(duì)分布式時(shí)序任務(wù)分配問題，提出了基于非死鎖合同網(wǎng)協(xié)議(Deadlock-free contract net protocol, DF-CNP)的多機(jī)分布式任務(wù)分配方法，主要工作包括：

(1)提出了局部信息條件下時(shí)序任務(wù)死鎖判據(jù)，實(shí)現(xiàn)各機(jī)根據(jù)局部信息判定全局任務(wù)死鎖狀態(tài)，有效解決分布式分配過程中的任務(wù)死鎖問題。

(2)提出了最近鄰-深度優(yōu)先混合搜索算法(Nearest neighbor-depth first search，NN-DFS)，利用最近鄰準(zhǔn)則降低任務(wù)排序代價(jià)，通過深度優(yōu)先搜索滿足任務(wù)非死鎖約束，實(shí)現(xiàn)各機(jī)非死鎖任務(wù)排序，提升分配結(jié)果最優(yōu)性。

1 預(yù)備知識(shí)及問題建模

1.1 代數(shù)圖論相關(guān)知識(shí)

通過構(gòu)建有向圖對(duì)無人機(jī)與時(shí)序任務(wù)間關(guān)系進(jìn)行描述與分析。對(duì)于任意分配方案，可由有向圖=(,)表示。中的元素稱為的頂點(diǎn)，為的有向邊集。若=(,)∈，則稱為有向邊的起點(diǎn)，為的終點(diǎn)。描述了任務(wù)間的時(shí)序關(guān)系，(,)表示應(yīng)在前被執(zhí)行。若存在一條從到的有向路，則稱頂點(diǎn)到頂點(diǎn)是可達(dá)的。

1.2 時(shí)序任務(wù)分配建模

考慮個(gè)目標(biāo)，多無人機(jī)需對(duì)每個(gè)目標(biāo)依次執(zhí)行偵察()、打擊()、評(píng)估()任務(wù)，任務(wù)集表示為={,,…,}，記任務(wù)數(shù)量為，則=3?？紤]存在架異構(gòu)無人機(jī)，表示為={,, …,}，具體可分為戰(zhàn)斗型、偵察型和打擊型無人機(jī)。戰(zhàn)斗型無人機(jī)可執(zhí)行全部任務(wù)，偵察型無人機(jī)可執(zhí)行偵察、評(píng)估任務(wù)，打擊型無人機(jī)僅執(zhí)行打擊任務(wù)。本文假設(shè)各任務(wù)僅由單架無人機(jī)執(zhí)行，且每個(gè)目標(biāo)的任務(wù)時(shí)序?yàn)椤?/p>

考慮任務(wù)執(zhí)行過程中減小系統(tǒng)整體任務(wù)代價(jià)與均衡各機(jī)代價(jià)，以最小化無人機(jī)任務(wù)執(zhí)行時(shí)長(zhǎng)總和與整體任務(wù)完成時(shí)間為優(yōu)化目標(biāo)，構(gòu)建多無人機(jī)時(shí)序任務(wù)分配模型如下

(1)

s.t.

(2)

,∈{0,1}

(3)

=1,2,…,

(4)

式中:,為權(quán)重系數(shù)，取值根據(jù)需求確定；,是二元變量，當(dāng)任務(wù)分配給無人機(jī)時(shí)，, =1，否則為0；無人機(jī)完成任務(wù)的時(shí)長(zhǎng)為

(5)

2 非死鎖合同網(wǎng)協(xié)議算法流程

DF-CNP通過“招標(biāo)-投標(biāo)-中標(biāo)”的規(guī)則實(shí)現(xiàn)任務(wù)的轉(zhuǎn)移和分配。由于標(biāo)書計(jì)算的獨(dú)立性，該方法支持分布式并行求解，能夠在局部信息條件下獲得時(shí)序任務(wù)分配方案。局部信息條件具體為：在每輪協(xié)商中，招標(biāo)者與投標(biāo)者存在信息交互，而投標(biāo)者之間無交互。

各機(jī)在分布式架構(gòu)下并行運(yùn)行DF-CNP實(shí)現(xiàn)多機(jī)非死鎖時(shí)序任務(wù)分配，以無人機(jī)為例，DF-CNP算法流程如圖1所示，具體步驟如下：

1)參數(shù)初始化。具體包括基本參數(shù)信息(初始位置、最小轉(zhuǎn)彎半徑)、招標(biāo)者編號(hào)、目標(biāo)位置、他機(jī)編號(hào)與類型。

2)生成非死鎖初始分配方案。本文設(shè)計(jì)如下兩條規(guī)則生成初始分配方案，規(guī)則I：各機(jī)按目標(biāo)數(shù)量均勻分配，同一目標(biāo)上的任務(wù)需統(tǒng)一分配至一架無人機(jī)。規(guī)則II：若按規(guī)則I生成的初始方案中某些任務(wù)超出能力范圍(打擊型無人機(jī)無法執(zhí)行偵察任務(wù))，則將該任務(wù)按無人機(jī)編號(hào)轉(zhuǎn)移至后續(xù)具備任務(wù)執(zhí)行能力的無人機(jī)。

3)身份判斷。每輪協(xié)商開始前，對(duì)自身身份進(jìn)行判斷，若當(dāng)前身份是投標(biāo)者，轉(zhuǎn)入步驟7，等待招標(biāo)者發(fā)布任務(wù)序列；反之，當(dāng)前身份是招標(biāo)者，執(zhí)行步驟4)。

4)招標(biāo)者發(fā)布任務(wù)序列。依次賣出持有任務(wù)，對(duì)剩余任務(wù)進(jìn)行非死鎖排序，并向市場(chǎng)內(nèi)全體投標(biāo)者發(fā)布剩余任務(wù)序列。

5)招標(biāo)者發(fā)布中標(biāo)信息。接收投標(biāo)者發(fā)布的標(biāo)書信息，從中選取標(biāo)書值最大的無人機(jī)作為中標(biāo)者，向市場(chǎng)公布中標(biāo)結(jié)果。將賣出投標(biāo)任務(wù)后的剩余任務(wù)序列作為更新后的任務(wù)排序方案。

6)判斷是否滿足招標(biāo)者更新與算法收斂條件。若滿足收斂條件，則向市場(chǎng)發(fā)布算法收斂信息，本機(jī)算法運(yùn)行結(jié)束；若滿足招標(biāo)者更新條件，則招標(biāo)者編號(hào)向后順延。返回步驟3)。

7)若當(dāng)前身份為投標(biāo)者，接收招標(biāo)者發(fā)布信息后，與其他投標(biāo)者并行開展標(biāo)書計(jì)算，將招標(biāo)者賣出任務(wù)納入自身任務(wù)序列，完成非死鎖排序。依據(jù)排序結(jié)果與招標(biāo)者剩余任務(wù)序列計(jì)算代價(jià)變化量，選擇最小化整體代價(jià)的任務(wù)進(jìn)行投標(biāo)，并向投標(biāo)者發(fā)布標(biāo)書及對(duì)應(yīng)投標(biāo)任務(wù)。

8)投標(biāo)者判斷是否中標(biāo)。若接收到中標(biāo)信息則更新自身任務(wù)序列。若未中標(biāo)，則保持原有任務(wù)序列。

9)若投標(biāo)者收到算法收斂信息，則本機(jī)算法運(yùn)行結(jié)束，按當(dāng)前分配結(jié)果執(zhí)行任務(wù)。若收到招標(biāo)者更新信息，則招標(biāo)者編號(hào)向后順延。返回步驟3)。

DF-CNP算法步驟4)、6)、7)中涉及的非死鎖任務(wù)排序方法、代價(jià)計(jì)算與標(biāo)書生成、招標(biāo)者更新策略與算法收斂條件是本文的主要?jiǎng)?chuàng)新點(diǎn)，詳細(xì)描述見第3、4節(jié)。

圖1 DF-CNP算法流程圖Fig.1 Flowchart of DF-CNP algorithm

3 局部信息條件下非死鎖任務(wù)排序

針對(duì)時(shí)序任務(wù)分配中存在的死鎖現(xiàn)象，本文給出了局部信息條件下的死鎖判據(jù)，用于判斷當(dāng)前分配方案的全局任務(wù)死鎖狀態(tài)。提出了一種最近鄰-深度優(yōu)先混合搜索算法，對(duì)無人機(jī)自身任務(wù)進(jìn)行非死鎖排序，減小任務(wù)執(zhí)行代價(jià)。

3.1 死鎖判據(jù)

任務(wù)死鎖是由不合理任務(wù)執(zhí)行順序?qū)е碌母鳈C(jī)陷入無盡互相等待的現(xiàn)象，死鎖分配方案對(duì)應(yīng)有向圖含環(huán)，環(huán)上每架無人機(jī)都在等待其他無人機(jī)任務(wù)執(zhí)行結(jié)束。

全局任務(wù)分配方案對(duì)應(yīng)有向圖D，在局部信息條件下，本文考慮單機(jī)掌握的信息構(gòu)成子圖H, H?D，并給出如下定義。

指向子圖H的有向邊為子圖H的入弧，其數(shù)量為子圖I的入度，記為O。由子圖H指出的有向邊為子圖H的出弧，其數(shù)量為子圖H的出度，記為O。

H入弧的終點(diǎn)為H的入點(diǎn)，H出弧的起點(diǎn)為H的出點(diǎn)。若H中存在入點(diǎn)到出點(diǎn)是可達(dá)的，則該兩節(jié)點(diǎn)稱為H的邊界可達(dá)對(duì)。

圖2所示有向圖D不存在環(huán)，因此圖2為非死鎖分配方案。虛線框內(nèi)代表子圖H，根據(jù)上述定義，,是H的入弧，,是H的入點(diǎn)，I=2；是H的出弧，是H的出點(diǎn)，O= 1；(,)是H的邊界可達(dá)對(duì)。

圖2 典型有向圖與子圖示意圖Fig.2 Typical directed graph and subgraph

在假設(shè)初始整體任務(wù)分配方案非死鎖的前提下，本文提出單機(jī)根據(jù)局部信息(子圖H)推斷全局任務(wù)(有向圖D)非死鎖狀態(tài)的判據(jù)，具體如下。

若I為0或O為0，只要任務(wù)調(diào)整后H無環(huán)，即可滿足全局任務(wù)非死鎖。

由于I為0或O為0，則H內(nèi)任意節(jié)點(diǎn)無法與H外節(jié)點(diǎn)構(gòu)成環(huán)路。由初始分配方案非死鎖可知，H外節(jié)點(diǎn)構(gòu)成的有向圖內(nèi)不含環(huán)路。因此，當(dāng)H內(nèi)節(jié)點(diǎn)局部調(diào)整后H無環(huán)，即整體有向圖D均無環(huán)，從而保證全局任務(wù)分配方案非死鎖，證畢。

若I和O均不為0，只要任務(wù)調(diào)整后H無環(huán)，且H不產(chǎn)生新的邊界可達(dá)對(duì)，即可保證全局任務(wù)非死鎖。

由初始分配方案非死鎖可知，H外節(jié)點(diǎn)構(gòu)成的有向圖內(nèi)不含環(huán)路。任務(wù)調(diào)整后H內(nèi)無環(huán)，因此僅需考慮H內(nèi)節(jié)點(diǎn)與外部節(jié)點(diǎn)構(gòu)成環(huán)路的兩種情況。

1) 任務(wù)調(diào)整前H存在邊界可達(dá)對(duì)。任務(wù)調(diào)整后，若該邊界可達(dá)對(duì)仍存在，考慮到局部任務(wù)調(diào)整對(duì)外部節(jié)點(diǎn)狀態(tài)無影響，且調(diào)整前外部節(jié)點(diǎn)與該邊界可達(dá)對(duì)不構(gòu)成環(huán)路，因此調(diào)整后其與外部節(jié)點(diǎn)仍不構(gòu)成環(huán)路；若任務(wù)調(diào)整后該可達(dá)對(duì)不存在，則其與外部節(jié)點(diǎn)不構(gòu)成環(huán)路。由于該可達(dá)對(duì)的任意性，調(diào)整后的邊界可達(dá)對(duì)狀態(tài)均無法導(dǎo)致D產(chǎn)生環(huán)。由于任務(wù)調(diào)整不產(chǎn)生新的可達(dá)對(duì)，因此保證全局任務(wù)在調(diào)整后非死鎖。

2) 任務(wù)調(diào)整前H不存在邊界可達(dá)對(duì)，由調(diào)整后H不產(chǎn)生新的邊界可達(dá)對(duì)可知，調(diào)整后H內(nèi)任意節(jié)點(diǎn)與H外節(jié)點(diǎn)無法構(gòu)成環(huán)路，因此整體有向圖D均無環(huán)。滿足全局任務(wù)非死鎖，證畢。

圖3 任務(wù)死鎖判斷示例Fig.3 Example of task deadlock judgment

結(jié)合判據(jù)1～2，單機(jī)根據(jù)局部信息推斷全局任務(wù)滿足非死鎖狀態(tài)的判據(jù)可由式(6)表示

(6)

式中：H′表示調(diào)整前的子圖；表示子圖H內(nèi)環(huán)路集合；表示H內(nèi)邊界可達(dá)對(duì)集合。

依據(jù)上述判據(jù)，無人機(jī)在分布式協(xié)商過程中僅需依據(jù)局部信息構(gòu)建整體任務(wù)有向圖子圖，通過檢測(cè)環(huán)路狀態(tài)和子圖邊界可達(dá)對(duì)狀態(tài)，即可推斷分配后全局任務(wù)的死鎖狀態(tài)，舍棄陷入死鎖的交易結(jié)果，保留非死鎖方案持續(xù)分配過程。

3.2 非死鎖任務(wù)排序

本文提出一種最近鄰-深度優(yōu)先混合搜索算法對(duì)各機(jī)任務(wù)排序。最近鄰搜索是在排序中，選取距離當(dāng)前任務(wù)最近的下一任務(wù)排入任務(wù)序列，從而降低任務(wù)執(zhí)行代價(jià)，但排序過程無法考慮任務(wù)間時(shí)序關(guān)系。為此，通過深度優(yōu)先搜索遞歸回溯實(shí)現(xiàn)對(duì)可行解空間的持續(xù)探索，運(yùn)用死鎖判據(jù)消除陷入死鎖任務(wù)排序方案，確保全局任務(wù)分配結(jié)果的可行性。

設(shè)當(dāng)前任務(wù)集為，為無人機(jī)持有的任務(wù)數(shù)量。考慮中任務(wù)與，構(gòu)建任務(wù)間預(yù)估代價(jià)矩陣={}×，其中：

(7)

NN-DFS基于進(jìn)行非死鎖任務(wù)排序，具體算法步驟如下：

1)參數(shù)初始化。將持有任務(wù)視作多個(gè)節(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)=1，標(biāo)記全部節(jié)點(diǎn)狀態(tài)為未訪問節(jié)點(diǎn)，初始搜索深度=0，初始搜索次數(shù)=0。

2)任務(wù)排序。依據(jù)預(yù)估代價(jià)矩陣選擇的最近鄰節(jié)點(diǎn)*加入任務(wù)序列，標(biāo)記*為已訪問節(jié)點(diǎn)，=+1，并更新*為當(dāng)前節(jié)點(diǎn)進(jìn)行最近鄰排序。重復(fù)該步驟，直至=，表明NN-DFS當(dāng)前已得到一組完整的任務(wù)序列，此時(shí)令=+1。

4 代價(jià)計(jì)算、招標(biāo)者更新與收斂條件

(8)

依次對(duì)中的所有任務(wù)計(jì)算買賣前后的代價(jià)變化，從中選取最小化整體代價(jià)的任務(wù)作為投標(biāo)任務(wù)*，并發(fā)布標(biāo)書值B,為代價(jià)變化的最大值。

(9)

B,=Δ(*)

(10)

招標(biāo)者匯集標(biāo)書后，根據(jù)DF-CNP步驟5決策本輪中標(biāo)者。通常，招標(biāo)者的選取通過對(duì)比各機(jī)任務(wù)負(fù)載(任務(wù)數(shù)量、預(yù)期航程)選舉產(chǎn)生。但任務(wù)負(fù)載小的無人機(jī)較難成為招標(biāo)者，因此部分解的搜索空間被限制。為提升任務(wù)分配方案的最優(yōu)性，設(shè)計(jì)招標(biāo)者更新條件為：當(dāng)多輪協(xié)商買賣后的系統(tǒng)整體代價(jià)無法降低，且仍存在無人機(jī)未擔(dān)任招標(biāo)者。

(11)

式中：表示第輪交易；為收斂指定迭代次數(shù)；為招標(biāo)者編號(hào)；為無人機(jī)數(shù)量。此時(shí)招標(biāo)者身份按編號(hào)順移至后續(xù)無人機(jī)。

算法收斂條件為：若多次買賣后系統(tǒng)整體代價(jià)無法降低，且全部無人機(jī)均已擔(dān)任過招標(biāo)者，則算法收斂退出，此時(shí)式(11)中=。通常的選取與時(shí)序任務(wù)數(shù)量相關(guān)，文中需執(zhí)行偵察、打擊和評(píng)估任務(wù)，則取≥3。

5 仿真校驗(yàn)

本節(jié)在典型的任務(wù)場(chǎng)景下，通過仿真試驗(yàn)驗(yàn)證DF-CNP的有效性，并與非死鎖遺傳算法(TB-GA)、CBBA-TCC算法進(jìn)行性能對(duì)比。其中對(duì)CBBA-TCC算法進(jìn)行適應(yīng)性改進(jìn)，使其能夠處理包含3類時(shí)序任務(wù)的問題。DF-CNP基于分布式架構(gòu)，因此仿真試驗(yàn)在多臺(tái)PC機(jī)上進(jìn)行，計(jì)算耗時(shí)統(tǒng)計(jì)中考慮硬件通信傳輸延遲帶來的影響，模擬多架無人機(jī)在真實(shí)環(huán)境下分布式信息交互。仿真硬件環(huán)境為Inter Xeon E5-4620 2.2 GHz處理器和16 G內(nèi)存；軟件環(huán)境為Visual Studio 2015。

為充分體現(xiàn)本文方法的最優(yōu)性，根據(jù)文獻(xiàn)[9]仿真參數(shù)設(shè)置，將TB-GA交叉概率與任務(wù)時(shí)序變異概率分別增加至0.85與0.3，種群規(guī)模與最大迭代次數(shù)分別增加至200與100，提升對(duì)比算法最優(yōu)性；CBBA-TCC中無人機(jī)任務(wù)容量設(shè)置為想定中總?cè)蝿?wù)數(shù)量，其余參數(shù)設(shè)置參考文獻(xiàn)[21]，其中任務(wù)價(jià)值遞減系數(shù)根據(jù)文獻(xiàn)[21]中救援任務(wù)設(shè)置為0.1。

5.1 想定I

任務(wù)分配結(jié)果如圖4所示，其甘特如圖5所示。甘特圖中方塊左端時(shí)刻代表無人機(jī)開始執(zhí)行當(dāng)前任務(wù)，方塊右端時(shí)刻代表無人機(jī)完成當(dāng)前任務(wù)。方塊之間的時(shí)間間隔代表無人機(jī)抵近或等待執(zhí)行任務(wù)時(shí)長(zhǎng)。由圖4和圖5可知，上述時(shí)序任務(wù)分配結(jié)果滿足異構(gòu)飛行平臺(tái)約束和任務(wù)時(shí)序非死鎖約束。

圖4 任務(wù)分配結(jié)果(想定I)Fig.4 Task allocation result for Scenario I

圖5 任務(wù)執(zhí)行時(shí)間甘特圖(想定I)Fig.5 Gantt chart of task execution time for Scenario I

為充分對(duì)比DF-CNP、TB-GA、CBBA-TCC的最優(yōu)性與時(shí)效性，開展50次仿真測(cè)試，統(tǒng)計(jì)結(jié)果如圖6所示。DF-CNP目標(biāo)函數(shù)均值(126.8 s)與計(jì)算耗時(shí)均值(0.489 s)相比TB-GA(目標(biāo)函數(shù)均值138.6 s、計(jì)算耗時(shí)均值23.32 s)分別降低了8.5%與97.9%，表明DF-CNP在確保求解最優(yōu)性的前提下，計(jì)算效率具有明顯優(yōu)勢(shì)。由圖6中數(shù)據(jù)散布可知，TB-GA計(jì)算結(jié)果具有一定隨機(jī)性，而DF-CNP為確定性算法，其求解魯棒性更優(yōu)。與CBBA-TCC(目標(biāo)函數(shù)均值152.8 s、計(jì)算耗時(shí)均值0.274 s)相比，DF-CNP在滿足亞秒級(jí)規(guī)劃效率的前提下，最大任務(wù)執(zhí)行時(shí)長(zhǎng)降低了20.5%，表明DF-CNP求解結(jié)果的最優(yōu)性更高。

圖6 算法最優(yōu)性與求解耗時(shí)對(duì)比(想定I)Fig.6 Comparison of optimality and runtime for Scenario I

5.2 想定II

圖7 任務(wù)執(zhí)行時(shí)間甘特圖(11個(gè)目標(biāo)規(guī)模)Fig.7 Gantt chart of task execution time involving 11 targets

圖8 代價(jià)值對(duì)比結(jié)果(目標(biāo)規(guī)模7至11個(gè))Fig.8 Comparison of cost involving 7 to 11 targets

圖9 求解耗時(shí)對(duì)比結(jié)果(目標(biāo)規(guī)模7至11個(gè))Fig.9 Comparison of runtime involving 7 to 11 targets

表時(shí)算法求解代價(jià)值標(biāo)準(zhǔn)差Table 1 Standard deviation of solution cost under

綜上可得，DF-CNP能夠?qū)崿F(xiàn)異構(gòu)無人機(jī)時(shí)序任務(wù)分配的非死鎖約束。通過非死鎖任務(wù)排序與招標(biāo)者更新策略定制，充分?jǐn)U展了合同網(wǎng)算法對(duì)最優(yōu)解的搜索空間，提高了結(jié)果最優(yōu)性；在分布式架構(gòu)與市場(chǎng)競(jìng)爭(zhēng)機(jī)制下，DF-CNP處理較大規(guī)模問題具備在線求解能力。

6 結(jié) 論

為實(shí)現(xiàn)分布式架構(gòu)下異構(gòu)無人機(jī)非死鎖時(shí)序任務(wù)分配，本文基于市場(chǎng)競(jìng)爭(zhēng)機(jī)制提出了非死鎖合同網(wǎng)協(xié)議，通過仿真試驗(yàn)驗(yàn)證了研究成果的有效性，具體結(jié)論如下：

1)在初始全局任務(wù)分配方案滿足非死鎖約束的前提下，本文提出了局部信息條件下任務(wù)死鎖判據(jù)，并定制了最近鄰-深度優(yōu)先混合搜索算法，實(shí)現(xiàn)各機(jī)非死鎖任務(wù)排序，提升分配結(jié)果最優(yōu)性。

2)本文提出的DF-CNP支持在分布式架構(gòu)下有效處理異構(gòu)無人機(jī)時(shí)序任務(wù)分配問題。通過與TB-GA及CBBA-TCC等算法對(duì)比，DF-CNP具備更好的求解最優(yōu)性，并滿足在線規(guī)劃時(shí)效性需求。隨著想定中無人機(jī)和目標(biāo)的規(guī)模增加，DF-CNP求解最優(yōu)性優(yōu)勢(shì)更為明顯。

DF-CNP采用了傳統(tǒng)的買賣合同機(jī)制，對(duì)有效解空間的搜索能力有限，后續(xù)研究中可定制多類型合同機(jī)制，進(jìn)一步提高算法最優(yōu)性。