[發(fā)明專利]基于非死鎖合同網(wǎng)算法的多機(jī)分布式時(shí)序任務(wù)分配方法

在審

• 申請?zhí)枺?/td>: 202110861873.1
• 申請日: 2021-07-29
• 公開（公告）號: CN113671987A
• 公開（公告）日: 2021-11-19
• 發(fā)明（設(shè)計(jì)）人: 龍騰;曹嚴(yán);孫景亮;王仰杰;徐廣通
• 申請（專利權(quán)）人: 北京理工大學(xué)
• 主分類號: G05D1/10
• 分類號: G05D1/10
• 代理公司: 北京正陽理工知識產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11639
• 代理人: 鄔曉楠

1.基于非死鎖合同網(wǎng)算法的多機(jī)分布式時(shí)序任務(wù)分配方法，其特征在于：包括如下步驟，

步驟一：以最小化無人機(jī)任務(wù)執(zhí)行時(shí)長總和與整體任務(wù)完成時(shí)間為優(yōu)化目標(biāo)，考慮任務(wù)時(shí)序約束，建立多無人機(jī)時(shí)序任務(wù)分配模型；

步驟二：在合同網(wǎng)算法任務(wù)排序過程中充分考慮耦合時(shí)序任務(wù)影響，優(yōu)先選擇最近鄰任務(wù)，結(jié)合用于消除不可行排序方案的死鎖判據(jù)遞歸回溯，并對招標(biāo)無人機(jī)選取機(jī)制與算法收斂條件改進(jìn)，形成基于競爭機(jī)制的非死鎖合同網(wǎng)(DF-CNP)算法；在分布式架構(gòu)下并行非死鎖合同網(wǎng)(DF-CNP)算法，高效率輸出多無人機(jī)非死鎖時(shí)序任務(wù)分配結(jié)果，在合同網(wǎng)任務(wù)排序過程中結(jié)合死鎖判據(jù)避免任務(wù)時(shí)序死鎖，通過改進(jìn)招標(biāo)無人機(jī)選取機(jī)制與算法收斂條件進(jìn)一步擴(kuò)展可行解空間，提升多無人機(jī)時(shí)序任務(wù)分配結(jié)果最優(yōu)性。

2.如權(quán)利要求1所述的基于非死鎖合同網(wǎng)算法的多機(jī)分布式時(shí)序任務(wù)分配方法，其特征在于：還包括步驟三，根據(jù)步驟二輸出的多無人機(jī)非死鎖時(shí)序任務(wù)分配結(jié)果，多無人機(jī)執(zhí)行相應(yīng)偵察、打擊、評估時(shí)序任務(wù)，有效縮短多無人機(jī)任務(wù)執(zhí)行時(shí)長總和與整體任務(wù)完成時(shí)間。

3.如權(quán)利要求2所述的基于非死鎖合同網(wǎng)算法的多機(jī)分布式時(shí)序任務(wù)分配方法，其特征在于：所述執(zhí)行相應(yīng)偵察、打擊、評估時(shí)序任務(wù)中偵察、打擊、評估任務(wù)能夠根據(jù)實(shí)際任務(wù)需要刪減或拓展任務(wù)類別。

4.如權(quán)利要求1、2或3所述的基于非死鎖合同網(wǎng)算法的多機(jī)分布式時(shí)序任務(wù)分配方法，其特征在于：步驟一實(shí)現(xiàn)方法為，

考慮W個(gè)目標(biāo)，目標(biāo)表示為O＝{O₁,O₂,…,O_W}；多無人機(jī)需對每個(gè)目標(biāo)依次執(zhí)行偵察、打擊、評估任務(wù)，任務(wù)集表示為T＝{T₁,T₂,…,T_N}，記任務(wù)數(shù)量為N＝T，則N＝3W；考慮存在K架異構(gòu)無人機(jī)，表示為U＝{U₁,U₂,…,U_K}，具體分為戰(zhàn)斗型、偵察型和打擊型無人機(jī)；戰(zhàn)斗型無人機(jī)能夠執(zhí)行T中的全部任務(wù)，偵察型無人機(jī)能夠執(zhí)行偵察、評估任務(wù)，打擊型無人機(jī)僅執(zhí)行打擊任務(wù)；各任務(wù)僅由單架無人機(jī)執(zhí)行，且每一個(gè)目標(biāo)的任務(wù)時(shí)序?yàn)閭刹臁驌簟u估；

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

x_i,n∈{0,1} (3)

式(1)中，α、β為權(quán)重系數(shù)；x_i,n是二元變量，當(dāng)任務(wù)T_n分配給無人機(jī)U_i時(shí)，x_i,n＝1，反之為0；C_i,n為無人機(jī)U_i完成任務(wù)T_n的時(shí)長，表示為

其中，表示無人機(jī)U_i從任務(wù)點(diǎn)T_m抵近至任務(wù)點(diǎn)T_n的時(shí)長，表示U_i抵達(dá)任務(wù)點(diǎn)T_n后的等待時(shí)長，表示任務(wù)T_n的執(zhí)行時(shí)長。

式(4)中，表示目標(biāo)O_w上的任務(wù)X，X∈{R,A,V}；t_str(·)表示任務(wù)開始執(zhí)行的時(shí)刻，t_end(·)為任務(wù)執(zhí)行結(jié)束時(shí)刻。

5.如權(quán)利要求4所述的基于非死鎖合同網(wǎng)算法的多機(jī)分布式時(shí)序任務(wù)分配方法，其特征在于：所述的招標(biāo)者無人機(jī)選取機(jī)制改進(jìn)為：所有無人機(jī)均按無人機(jī)編號順序擔(dān)任招標(biāo)者無人機(jī)；所述算法收斂條件改進(jìn)為：所有無人機(jī)均擔(dān)任招標(biāo)者無人機(jī)后，且算法代價(jià)不再降低，則滿足算法收斂條件。

6.如權(quán)利要求5所述的基于非死鎖合同網(wǎng)算法的多機(jī)分布式時(shí)序任務(wù)分配方法，其特征在于：步驟二實(shí)現(xiàn)方法為，

步驟2.1：無人機(jī)U_i參數(shù)初始化；所述無人機(jī)U_i參數(shù)具體包括無人機(jī)U_i基本參數(shù)信息、招標(biāo)者編號、目標(biāo)位置、他機(jī)編號與類型；所述無人機(jī)U_i基本參數(shù)信息包括初始位置、最小轉(zhuǎn)彎半徑；

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

步驟2.3：招標(biāo)者無人機(jī)U_i向全體投標(biāo)者無人機(jī)發(fā)布持有任務(wù)序列與剩余任務(wù)序列；所述持有任務(wù)序列具體為無人機(jī)U_i當(dāng)前待執(zhí)行任務(wù)序列，剩余任務(wù)序列是指無人機(jī)U_i依次賣出各任務(wù)后的剩余任務(wù)序列；

步驟2.4：招標(biāo)者無人機(jī)U_i發(fā)布中標(biāo)信息；無人機(jī)U_i接收全部投標(biāo)者無人機(jī)發(fā)布的標(biāo)書及對應(yīng)投標(biāo)任務(wù)，從中選取標(biāo)書值最大的無人機(jī)作為中標(biāo)者，并向全部投標(biāo)者無人機(jī)公布中標(biāo)信息；將賣出投標(biāo)任務(wù)后的剩余任務(wù)序列作為更新后的任務(wù)排序方案；

步驟2.5：通過招標(biāo)者無人機(jī)更新策略判斷是否滿足招標(biāo)者無人機(jī)更新與算法收斂條件；若滿足招標(biāo)者無人機(jī)更新條件，則招標(biāo)者無人機(jī)編號向后順延，同時(shí)向全部投標(biāo)者無人機(jī)公布招標(biāo)者無人機(jī)更新信息；返回步驟2.2；若滿足收斂條件，則無人機(jī)U_i向所有投標(biāo)無人機(jī)發(fā)布算法收斂信息，終止非死鎖合同網(wǎng)(DF-CNP)算法，此時(shí)各無人機(jī)生成的任務(wù)分配結(jié)果即為滿足時(shí)序約束的多無人機(jī)可行分配方案；

所述招標(biāo)者無人機(jī)更新策略為：當(dāng)多輪協(xié)商后的系統(tǒng)代價(jià)無法降低，且仍存在無人機(jī)未擔(dān)任招標(biāo)者無人機(jī)，見式(6)，則招標(biāo)者無人機(jī)身份按編號順移至后續(xù)無人機(jī)；

其中，r表示第r輪交易，τ為收斂指定迭代次數(shù)，Z_auc為招標(biāo)者編號，K為無人機(jī)數(shù)量；

所述算法收斂條件為：若多次協(xié)商后系統(tǒng)代價(jià)無法降低，且此時(shí)全部無人機(jī)均已擔(dān)任過招標(biāo)者無人機(jī)，則算法收斂退出；

步驟2.6：若無人機(jī)U_i身份判斷為投標(biāo)者無人機(jī)，接收招標(biāo)者無人機(jī)發(fā)布信息后，無人機(jī)U_i與其他投標(biāo)者無人機(jī)并行開展標(biāo)書計(jì)算，選擇招標(biāo)者無人機(jī)持有任務(wù)納入自身任務(wù)序列，通過非死鎖排序算法完成非死鎖排序；依據(jù)排序結(jié)果與招標(biāo)者無人機(jī)剩余任務(wù)序列通過代價(jià)計(jì)算方法進(jìn)行代價(jià)計(jì)算，選擇最小化整體代價(jià)的任務(wù)進(jìn)行投標(biāo)，并向投標(biāo)者無人機(jī)發(fā)布標(biāo)書及對應(yīng)投標(biāo)任務(wù)；

所述非死鎖排序算法具體為：將無人機(jī)U_i持有任務(wù)視作多個(gè)節(jié)點(diǎn)，構(gòu)建當(dāng)前節(jié)點(diǎn)的鄰近任務(wù)集合依據(jù)預(yù)估代價(jià)矩陣L_i選擇距離最近的節(jié)點(diǎn)j*加入無人機(jī)U_i任務(wù)序列S_i，標(biāo)記節(jié)點(diǎn)j*為已訪問節(jié)點(diǎn)，直至非死鎖排序算法當(dāng)前搜索深度d與無人機(jī)U_i持有的任務(wù)數(shù)量N_i相同；根據(jù)S_i構(gòu)建任務(wù)時(shí)序有向圖H，并依據(jù)死鎖判據(jù)進(jìn)行S_i死鎖檢測；

若任務(wù)序列S_i非死鎖，且搜索次數(shù)λ小于等于預(yù)設(shè)閾值則非死鎖排序算法獲得一組可行排序方案，非死鎖排序算法結(jié)束；若則非死鎖排序算法遞歸退出；若任務(wù)序列S_i死鎖，則從任務(wù)序列S_i中移除最近鄰節(jié)點(diǎn)j*，重置j*為未訪問節(jié)點(diǎn)，選擇剩余最鄰近節(jié)點(diǎn)繼續(xù)排序過程；若無鄰近節(jié)點(diǎn)，則遞歸回溯至任務(wù)序列中前一節(jié)點(diǎn)繼續(xù)排序過程，直至非死鎖排序算法結(jié)束或退出；

所述預(yù)估代價(jià)矩陣L_i計(jì)算方式為：

其中，無人機(jī)U_i當(dāng)前任務(wù)集為Q_i，表示無人機(jī)U_i從任務(wù)T_m到T_n的預(yù)估抵近代價(jià)，使用任務(wù)間歐式距離進(jìn)行預(yù)估；0)為執(zhí)行任務(wù)T_n前的預(yù)估等待代價(jià)，表示無人機(jī)U_i開始執(zhí)行任務(wù)T_n的預(yù)估時(shí)刻，表示無人機(jī)U_i結(jié)束執(zhí)行任務(wù)T_m的預(yù)估時(shí)刻；表示任務(wù)T_n的執(zhí)行時(shí)長；

所述死鎖判據(jù)為：若id(H)為0或od(H)為0，只要任務(wù)調(diào)整后H無環(huán)，即滿足全局任務(wù)非死鎖；若id(H)和od(H)均不為0，只要任務(wù)調(diào)整后H無環(huán)，且H不產(chǎn)生新的邊界可達(dá)對，即能夠保證全局任務(wù)非死鎖；其中，任務(wù)調(diào)整是指無人機(jī)U_i選擇招標(biāo)者持有任務(wù)納入自身任務(wù)序列的過程；指向H的有向邊為H的入弧，其數(shù)量為H的入度，記為id(H)；由H指出的有向邊為H的出弧，其數(shù)量為H的出度，記為od(H)；

所述代價(jià)計(jì)算方法為：協(xié)商前后整體代價(jià)變化由式(8)計(jì)算

其中，招標(biāo)者無人機(jī)U_i、投標(biāo)者無人機(jī)U_j持有任務(wù)序列分別為S_i、S_j，任務(wù)集為Q_i、Q_j，持有任務(wù)數(shù)量為N_i、N_j；無人機(jī)U_j從S_i中買入任務(wù)T_m加入自身序列S_j，通過非死鎖排序，無人機(jī)U_j任務(wù)序列變?yōu)閷?yīng)無人機(jī)U_i剩余任務(wù)序列為表示無人機(jī)U_i執(zhí)行任務(wù)序列S_i的代價(jià)，α、β為式(1)中的權(quán)重系數(shù)，S_i,n表示任務(wù)序列S_i中第n個(gè)任務(wù)，表示任務(wù)序列S_i中各任務(wù)代價(jià)累加；包含三部分代價(jià)：抵近時(shí)長代價(jià)、等待時(shí)長代價(jià)和執(zhí)行時(shí)長代價(jià)，由式(5)計(jì)算；

所述標(biāo)書生成方法為：無人機(jī)U_j依次對S_i中的所有任務(wù)計(jì)算協(xié)商前后的整體代價(jià)變化，從中選取最小化整體代價(jià)的任務(wù)作為投標(biāo)任務(wù)，并發(fā)布標(biāo)書值bid_j,i為整體代價(jià)變化的最大值；

步驟2.7：投標(biāo)者無人機(jī)U_i判斷是否中標(biāo)；無人機(jī)U_i若接收到中標(biāo)信息則更新自身任務(wù)序列；若未中標(biāo)，則保持原有任務(wù)序列；

步驟2.8：若投標(biāo)者無人機(jī)U_i收到算法收斂信息，則終止非死鎖合同網(wǎng)(DF-CNP)算法，無人機(jī)U_i按當(dāng)前分配結(jié)果執(zhí)行任務(wù)；若收到招標(biāo)者更新信息，則招標(biāo)者無人機(jī)編號向后順延；返回步驟2.2。