分布式協(xié)同動(dòng)態(tài)任務(wù)規(guī)劃的建模與一體化求解方法

崔乃剛，吳蔚楠，郭繼峰

（哈爾濱工業(yè)大學(xué) 航天學(xué)院，哈爾濱 150001）

分布式協(xié)同動(dòng)態(tài)任務(wù)規(guī)劃的建模與一體化求解方法

崔乃剛，吳蔚楠，郭繼峰

（哈爾濱工業(yè)大學(xué) 航天學(xué)院，哈爾濱 150001）

以多異構(gòu)無(wú)人機(jī)執(zhí)行偵查、打擊、評(píng)估任務(wù)為背景，開展了協(xié)同任務(wù)規(guī)劃問(wèn)題建模、一體化求解算法設(shè)計(jì)。采用分布式規(guī)劃框架及圖論思想對(duì)問(wèn)題進(jìn)行建模，且將無(wú)人機(jī)避碰、燃油、任務(wù)執(zhí)行次序作為約束條件，并充分考慮任務(wù)分配與路徑規(guī)劃存在的強(qiáng)耦合特性，采用禁忌/遺傳算法，設(shè)計(jì)包含任務(wù)序列和路徑位姿點(diǎn)的基因編碼，將問(wèn)題進(jìn)行一體化求解。結(jié)果表明：算法能夠適用于動(dòng)態(tài)任務(wù)場(chǎng)景，且能夠較為快速地解決任務(wù)空間較為復(fù)雜的規(guī)劃問(wèn)題。

異構(gòu)無(wú)人機(jī)；一體化求解；協(xié)同任務(wù)規(guī)劃；分布式?jīng)Q策；Dubins路徑；禁忌/遺傳混合算法

無(wú)人飛行器（后文均用 UAV表述）越來(lái)越多地被用來(lái)執(zhí)行各種自主任務(wù)[1]，而這些任務(wù)的成功與否依賴于UAV的自主程度。根據(jù)Kendou[2]提出的無(wú)人飛行系統(tǒng)自主等級(jí)可知，當(dāng)前相對(duì)成熟的是 UAV本體的自主控制、單機(jī)自主避障與路徑規(guī)劃等自主等級(jí)較低的技術(shù)，為了適應(yīng)更為復(fù)雜的任務(wù)需求，需要采用多機(jī)協(xié)同替代單機(jī)執(zhí)行任務(wù)，而協(xié)同任務(wù)規(guī)劃技術(shù)是協(xié)同控制領(lǐng)域的關(guān)鍵技術(shù)。

協(xié)同任務(wù)規(guī)劃問(wèn)題是一個(gè)典型的組合優(yōu)化問(wèn)題，文獻(xiàn)[3-8]均證明其為 NP（Non-deterministic polynomial）完全問(wèn)題，故其求解難度較大。為了降低求解難度，通常將協(xié)同任務(wù)規(guī)劃問(wèn)題簡(jiǎn)化為協(xié)同任務(wù)分配和路徑規(guī)劃兩個(gè)子問(wèn)題，弱化或不考慮它們之間的耦合性，采用分層解耦的方法對(duì)它們進(jìn)行分別求解[3,7,10-14]。這些解法的共同點(diǎn)為：將任務(wù)分配和路徑規(guī)劃分別求解，在任務(wù)分配求解時(shí)不考慮對(duì)象本身的運(yùn)動(dòng)學(xué)約束、環(huán)境障礙、威脅區(qū)約束，僅考慮任務(wù)本身的時(shí)序約束，任務(wù)間的相互影響關(guān)系等；路徑規(guī)劃將任務(wù)分配的結(jié)果作為其輸入，尋找滿足 UAV自身約束、障礙、威脅區(qū)、避碰等約束的平滑航跡。分層解耦方式降低了問(wèn)題的求解難度，且能夠適用于任務(wù)空間態(tài)勢(shì)確定的離線任務(wù)規(guī)劃問(wèn)題。但是，實(shí)際的任務(wù)空間態(tài)勢(shì)通常是時(shí)變且不確定的，而分層解耦方法的解算過(guò)程是異步的，由于任務(wù)分配過(guò)程的時(shí)間消耗，其運(yùn)算結(jié)果并非響應(yīng)當(dāng)前的任務(wù)空間態(tài)勢(shì)，從而帶來(lái)的路徑規(guī)劃結(jié)果往往不能滿足實(shí)際任務(wù)需求，且極有可能造成任務(wù)失效。所以，分層解耦求解方法的應(yīng)用范圍有限，且不能滿足實(shí)際任務(wù)需求。

基于此，文獻(xiàn)[5,15-18]對(duì)任務(wù)規(guī)劃問(wèn)題的一體化求解算法進(jìn)行了研究。A. Richards[15]采用歐幾里德線段集表示 UAV的路徑規(guī)劃結(jié)果，通過(guò)建立混合整數(shù)線性規(guī)劃模型完成對(duì)協(xié)同任務(wù)規(guī)劃問(wèn)題的等效，最后采用一體化求解方法完成問(wèn)題求解；Rasmussen[16]采用圖論等效方法完成任務(wù)規(guī)劃模型建立，并通過(guò)圖搜索算法完成對(duì)相同 UAV協(xié)同任務(wù)規(guī)劃問(wèn)題的求解；Shima[5]采用集中式一體化任務(wù)規(guī)劃求解方法，通過(guò)圖論方法完成 UAV協(xié)同任務(wù)規(guī)劃問(wèn)題的等效，采用Dubins路徑表示UAV飛行路徑，最后通過(guò)遺傳算法完成問(wèn)題求解；Deng[17]在文獻(xiàn)[5]的基礎(chǔ)上，附加考慮了 UAV的彈藥數(shù)量約束，通過(guò)改變遺傳算法的基因編碼方式，完成了問(wèn)題的求解。以上文獻(xiàn)均是基于集中式架構(gòu)完成協(xié)同任務(wù)規(guī)劃問(wèn)題的建模與求解，將規(guī)劃運(yùn)算過(guò)程完全在地面站或某個(gè) UAV上完成，而集中式架構(gòu)普遍存在對(duì)通信鏈路依賴性較強(qiáng)、可靠性較差等缺點(diǎn)[7]，所以其實(shí)用性較差。Edison[18]提出了采用分布式一體化策略求解協(xié)同任務(wù)規(guī)劃問(wèn)題的思路，但是其并未實(shí)現(xiàn)。由協(xié)同任務(wù)規(guī)劃一體化求解方法的研究現(xiàn)狀可知，現(xiàn)有方法主要存在以下不足：

1）采用集中式架構(gòu)，可靠性及規(guī)劃更新速度較慢；

2）能夠適應(yīng)的任務(wù)場(chǎng)景較為簡(jiǎn)單；

3）考慮到的約束條件較少，不能反映真實(shí)任務(wù)場(chǎng)景。

鑒于現(xiàn)有的協(xié)同任務(wù)規(guī)劃方法存在的普遍問(wèn)題，基于文獻(xiàn)[5][15-17]的研究成果，以異構(gòu) UAV協(xié)同執(zhí)行偵查確定、打擊、評(píng)估任務(wù)為背景，基于分布式規(guī)劃策略，通過(guò)圖論思想將協(xié)同任務(wù)規(guī)劃問(wèn)題進(jìn)行描述，在考慮 UAV轉(zhuǎn)彎半徑約束、特性（包括載荷特性、巡航速度）約束、任務(wù)執(zhí)行時(shí)序性約束、偵查范圍約束、避碰約束等前提下，采用一體化求解方法，設(shè)計(jì)禁忌/遺傳算法，完成協(xié)同任務(wù)規(guī)劃問(wèn)題求解。

1 協(xié)同任務(wù)規(guī)劃問(wèn)題建模

1.1 參數(shù)定義

以UAV協(xié)同執(zhí)行偵查、打擊、評(píng)估任務(wù)為背景，首先對(duì)涉及到的相關(guān)參數(shù)進(jìn)行定義。

目標(biāo)集與任務(wù)集：

UAV的異構(gòu)性主要體現(xiàn)在兩個(gè)方面：1）UAV的可執(zhí)行的任務(wù)不一致；2）UAV的速度和極限轉(zhuǎn)彎半徑不一致。UAV可分為三類：1）作戰(zhàn)UAV：可執(zhí)行所有任務(wù)，用偵查UAV：可執(zhí)行偵查和評(píng)估任務(wù)，用彈藥 UAV：僅能執(zhí)行打擊透明目標(biāo)任務(wù)，用

1.2 問(wèn)題的數(shù)學(xué)描述

在給定一個(gè)包含Ntask個(gè)子任務(wù)的任務(wù)集和Nuav個(gè)可分配 UAV的情況下，任務(wù)規(guī)劃的目標(biāo)為：在滿足任務(wù)自身約束和外部約束條件的前提下，尋求一種最優(yōu)的分配方案，使系統(tǒng)的效用最大。該問(wèn)題包含連續(xù)的規(guī)劃路徑以及離散的決策變量，是一個(gè)典型的組合優(yōu)化問(wèn)題。

不失一般性，任務(wù)規(guī)劃問(wèn)題可描述如下：

由式(2)可知，任務(wù)規(guī)劃的可行解集由S×χ×Γ決定，但是由于協(xié)同任務(wù)存在多UAV多目標(biāo)、UAV異構(gòu)、UAV燃油約束、UAV避碰、任務(wù)間存在時(shí)間序列約束等因素，將會(huì)極大地增加問(wèn)題解集的勢(shì)，對(duì)問(wèn)題的求解帶來(lái)較大的難度。

1.3 問(wèn)題的簡(jiǎn)化

本文采用圖論的思想，將任務(wù)規(guī)劃問(wèn)題用有向圖形式等效描述[5]，完成對(duì)問(wèn)題的適當(dāng)簡(jiǎn)化，并基于分布式規(guī)劃架構(gòu)，將任務(wù)決策和路徑規(guī)劃過(guò)程分布到各UAV上，完成對(duì)問(wèn)題的分布式描述。

通過(guò)離散UAV在目標(biāo)處的進(jìn)入航向角（UAV航向角定義參見圖1），完成對(duì)任務(wù)規(guī)劃問(wèn)題的簡(jiǎn)化，再通過(guò)圖論思想將任務(wù)空間表述為有向圖。

圖1 UAV的航向角定義Fig.1 Definition of UAV orientation angle

離散后的航向角可表示如下：

式中：nd表示航向角的離散化程度，nd取值越大，離散化程度越高；iφ表示UAV在目標(biāo)處的航向角。

根據(jù)圖論的思想，有向圖由頂點(diǎn)V和有向邊E組成。協(xié)同任務(wù)規(guī)劃問(wèn)題的有向圖頂點(diǎn)可表示如下：

式中：M表示包含離散化后的所有任務(wù)位姿點(diǎn)的集合；N表示包含所有UAV初始位姿點(diǎn)的集合；V為M與N的并集，表示有向圖的所有頂點(diǎn)集合，

有向圖的邊E為M中各頂點(diǎn)間的有向連線、 N中各UAV初始位姿點(diǎn)與M中的目標(biāo)點(diǎn)的有向連線的并集。

下面通過(guò)實(shí)例說(shuō)明離散簡(jiǎn)化過(guò)程，設(shè)置偵查(Search)、打擊(Attack)、評(píng)估(Verify)任務(wù)場(chǎng)景如下：

2) 目標(biāo)為2個(gè)：Ntarget=2，且每個(gè)目標(biāo)處對(duì)應(yīng)的任務(wù)數(shù)量為 3，均包括偵查(S)、打擊(A)、評(píng)估(V)三項(xiàng)任務(wù)，即

有：

圖2為該任務(wù)場(chǎng)景對(duì)應(yīng)的有向圖。

圖2 協(xié)同任務(wù)規(guī)劃問(wèn)題的有向圖例圖Fig.2 Example diagram of the SAV task planning by graph theory

由圖 2可知，圖中的有向邊路徑表示 UAV1、UAV2、UAV3的任務(wù)次序與飛行路徑：綠線表示UAV1首先搜索目標(biāo)1并對(duì)其進(jìn)行攻擊，最后再飛向目標(biāo)2處完成對(duì)目標(biāo)2的毀傷效果評(píng)估；紫線表示UAV2對(duì)目標(biāo)1進(jìn)行毀傷效果評(píng)估；藍(lán)線表示UAV3首先對(duì)目標(biāo)2進(jìn)行搜索，然后對(duì)目標(biāo)2進(jìn)行攻擊。

上述有向圖對(duì)應(yīng)任務(wù)規(guī)劃的一個(gè)可行解，其解集可表示為S為所有飛行路徑的解集，由圖2可知，其解集包括6條飛行路徑，每一條路徑的長(zhǎng)度對(duì)應(yīng)兩個(gè)位姿點(diǎn)間的 Dubins路徑，路徑總長(zhǎng)度為所有 Dubins路徑長(zhǎng)度之和。

χ代表任務(wù)分配的決策變量集，由圖2可知：

式中，ijχ表示第i個(gè)UAV與第j個(gè)任務(wù)的匹配結(jié)果。

Γ代表規(guī)劃結(jié)果中各任務(wù)的執(zhí)行時(shí)間戳，僅需滿足偵查、打擊、評(píng)估任務(wù)的執(zhí)行次序即可。

由上述分析可知，可將 UAV的總飛行距離作為協(xié)同任務(wù)規(guī)劃問(wèn)題的指標(biāo)，則該問(wèn)題的效用函數(shù)可簡(jiǎn)化為如下形式：

式中：c為系統(tǒng)的效用值；為有向圖中頂點(diǎn)集V的基數(shù)，即頂點(diǎn)的個(gè)數(shù)；為取值為0或1的決策變量，表示第j架UAV是否選擇有向圖中第k個(gè)頂點(diǎn)與第m個(gè)頂點(diǎn)連線對(duì)應(yīng)的Dubins路徑作為其飛行路徑；skm為對(duì)應(yīng)該UAV選擇的Dubins路徑的長(zhǎng)度。

將式(5)進(jìn)行分布式處理，分布到各 UAV上進(jìn)行獨(dú)立求解，即：

式(6)為式(5)的分布式形式，可將單個(gè)cj的運(yùn)算分布到每個(gè)UAV完成獨(dú)立解算。

為了反映較為真實(shí)的任務(wù)空間，還需要滿足如下5項(xiàng)約束：

1）任務(wù)完成約束：UAV需要執(zhí)行完所有規(guī)定的任務(wù)，可表示為：

2）任務(wù)時(shí)序約束：對(duì)于某一目標(biāo)，其偵查、打擊、評(píng)估三項(xiàng)任務(wù)間需滿足如下約束條件：

即該目標(biāo)需要先進(jìn)行偵查才能進(jìn)行攻擊，且被攻擊后才能進(jìn)行毀傷評(píng)估。

3）載荷約束：只有裝有相應(yīng)任務(wù)載荷的UAV才能執(zhí)行對(duì)應(yīng)的任務(wù)，即只有作戰(zhàn) UAV才能執(zhí)行所有三項(xiàng)任務(wù)，偵查 UAV只能執(zhí)行偵查和評(píng)估任務(wù)，彈藥類UAV只能執(zhí)行攻擊任務(wù)。

4）避碰約束：主要考慮多UAV間的避碰約束，采用不相交路徑法[8]，即UAV的路徑存在相交點(diǎn)，當(dāng)且僅當(dāng)UAV同時(shí)到達(dá)相交點(diǎn)時(shí)，才會(huì)發(fā)生碰撞，給出避碰約束如下。

令sp,sq分別表示UAVp和UAVq的Dubins路徑，若sp與sq存在相交點(diǎn)?，則需要滿足：

式中：d?,p,q表示相交點(diǎn)處路徑sp,?與sq,?的長(zhǎng)度之差；分別表示 UAV的安全圓半徑；分別表示UAV在路徑sp,?、sq,?的平均飛行速度。

5）燃油約束：

式中，kχ表示第k個(gè)UAV的任務(wù)分配決策矩陣，Lk為第k個(gè)UAV可飛行的總路徑長(zhǎng)度。

由目標(biāo)函數(shù)式(5)(6)和約束條件(7)～(11)完成描述了異構(gòu)UAV的分布式協(xié)同任務(wù)規(guī)劃問(wèn)題。

最后給出UAV的運(yùn)動(dòng)學(xué)模型，將其等效為Dubins Car模型。

給出如下假設(shè)：

1）戰(zhàn)場(chǎng)環(huán)境是事先已知的，且戰(zhàn)場(chǎng)環(huán)境的態(tài)勢(shì)信息獲取是瞬間完成且準(zhǔn)確的；

2）僅考慮二維平面內(nèi)的規(guī)劃問(wèn)題；

3）各UAV之間的通信鏈路是可靠且信息一致的，且數(shù)據(jù)傳輸是瞬間完成的；

4）UAV的巡航速度為恒定的。

Dubins Car等效建模的思想主要來(lái)自于Dubins得出的證明結(jié)論：兩個(gè)位姿點(diǎn)間的最短路徑是 Dubins路徑[9]，

Dubins Car模型適合于描述有轉(zhuǎn)彎半徑約束的UAV狀態(tài)，故建立UAV運(yùn)動(dòng)學(xué)方程如下：

將遺傳算法作為求解上述混合整數(shù)優(yōu)化問(wèn)題的主算法，基于分布式架構(gòu)[19]，采用一體化求解方法，重新設(shè)計(jì)遺傳算法的基因編碼方式，由任務(wù)分配信息和路徑規(guī)劃信息組成染色體，最后加入禁忌搜索思想，對(duì)遺傳算法進(jìn)行改進(jìn)，完成問(wèn)題的求解。

式中：x,y為笛卡爾慣性坐標(biāo)系下的水平分量；v為UAV巡航速度；φ為UAV速度方向與x方向的夾角，稱為UAV航向角，且規(guī)定順時(shí)針?lè)较驗(yàn)檎?，參見圖2；r為UAV的極限轉(zhuǎn)彎半徑，r越大，其機(jī)動(dòng)能力越差；u為UAV的控制輸入量，易知，

2 禁忌/遺傳算法及算法評(píng)估準(zhǔn)則

2.1 禁忌/遺傳混合算法的基本步驟

禁忌/遺傳混合算法的主體是遺傳算法，只是將禁忌搜索算法的思想引入遺傳算法中，對(duì)遺傳算法中的交叉或者變異操作進(jìn)行一定的改進(jìn)，提高遺傳算法的搜索速度，避免遺傳算法的“早熟”現(xiàn)象。

禁忌/遺傳混合算法的基本步驟如圖3所示。

圖3 禁忌/遺傳混合算法的基本步驟Fig.3 Flow diagram of the tabu/genetic hybrid search algorithm

2.2 算法評(píng)估準(zhǔn)則

算法的定量分析主要包括三個(gè)方面：

1）算法品質(zhì)

算法品質(zhì)定義為如下形式：

式中：Jbase表示所有參與評(píng)估的算法得出的解對(duì)應(yīng)的最小航跡長(zhǎng)度；表示某算法得出的解對(duì)應(yīng)的航跡長(zhǎng)度；quality表示該算法對(duì)應(yīng)的算法品質(zhì)。

由式(13)可知，算法品質(zhì)可用于量化描述某算法相比于其他算法的性能優(yōu)劣。算法品質(zhì)可與蒙特卡洛法配合使用，當(dāng)算法運(yùn)行的次數(shù)為N時(shí)，其算法的品質(zhì)得分為：

2）算法運(yùn)行速度品質(zhì)

3）算法品質(zhì)與運(yùn)行時(shí)間的加權(quán)

算法的優(yōu)劣不能單一的通過(guò)運(yùn)行時(shí)間和算法品質(zhì)進(jìn)行評(píng)估。通過(guò)設(shè)定權(quán)值，從算法品質(zhì)和運(yùn)行時(shí)間兩方面評(píng)估算法的優(yōu)劣：

3 仿真驗(yàn)證與分析

算法測(cè)試環(huán)境為Interval Zero RTX64實(shí)時(shí)操作系統(tǒng)。

任務(wù)空間場(chǎng)景基本參數(shù)如表1所示。

表1 任務(wù)空間設(shè)置Tab.1 Setting of task scenes

1）任務(wù)場(chǎng)景1

任務(wù)空間參數(shù)設(shè)置如表1所示，UAV的安全圓半徑均為50 m，每架UAV可飛行的總路徑長(zhǎng)度為10 km。

分配結(jié)果如表2所示。

表2 算法運(yùn)行分配結(jié)果Tab.2 Allocation result of the algorithm

算法運(yùn)行結(jié)果對(duì)應(yīng)的Dubins路徑如圖4所示。

記錄算法在RTX64環(huán)境下的運(yùn)行時(shí)間為21.92 s。

圖4 UAV規(guī)劃結(jié)果對(duì)應(yīng)的Dubins路徑Fig.4 Dubins trajectory of scenario with 3 targets and 5 UAVs

2）任務(wù)場(chǎng)景2

其他參數(shù)不變，考慮目標(biāo)位置發(fā)生變化的情況。設(shè)Target 1和Target 2在仿真開始后10s開始機(jī)動(dòng)：Target 1向笛卡爾坐標(biāo)系X軸正向移動(dòng)1700 m，向Y軸機(jī)動(dòng)400 m；Target 2向Y軸移動(dòng)800 m，且機(jī)動(dòng)過(guò)程瞬間完成。

算法得到的分配結(jié)果與表2中相同，得到的更新Dubins路徑如圖5所示。

由圖5的仿真結(jié)果可知，由于目標(biāo)機(jī)動(dòng)，UAV2、UAV3、UAV4的Dubins路徑均發(fā)生變化，算法完成了對(duì)動(dòng)態(tài)環(huán)境的響應(yīng)，記錄算法運(yùn)算時(shí)間為26.41 s。

圖5 目標(biāo)機(jī)動(dòng)時(shí)的重規(guī)劃結(jié)果對(duì)應(yīng)的Dubins路徑Fig.5 Dubins trajectory of scenario with moving targets

3）任務(wù)場(chǎng)景3

任務(wù)場(chǎng)景3的參數(shù)設(shè)置如表1所示，設(shè)置任務(wù)空間在 20 km×20 km范圍內(nèi)，UAV的極限轉(zhuǎn)彎半徑為UAV的速度大小為v∈[60 m/s,80 m/s]，禁忌/遺傳算法的基本參數(shù)設(shè)置如表3所示。

表3 禁忌/遺傳混合算法參數(shù)設(shè)置Tab.3 Parameters setting on tabu/genetic hybrid algorithm

采用蒙特卡洛分析方法，設(shè)置實(shí)驗(yàn)次數(shù)為100，用于對(duì)比分布式一體化求解方法與優(yōu)化工具CLPEX、典型分布式分層解耦求解算法[12]的性能，令 ==0.5 α β ；記錄算法運(yùn)行的時(shí)間和算法得出的總路徑長(zhǎng)度，如表4所示。

表4 各算法運(yùn)行結(jié)果Tab.4 Results of three algorithms

各算法的運(yùn)行時(shí)間對(duì)比結(jié)果如圖6所示。

圖6 基于蒙特卡洛試驗(yàn)的各算法運(yùn)行時(shí)間對(duì)比結(jié)果Fig.6 Running time results of three algorithms based on Monte Carlo test

根據(jù)上述結(jié)果可知，相比CPLEX，雖然分布式一體化解法得出的解對(duì)應(yīng)的總路徑長(zhǎng)度略大，但分布式一體化解法的平均運(yùn)算時(shí)間縮短約90s，綜合兩項(xiàng)算法評(píng)估標(biāo)準(zhǔn)，分布式一體化解法性能更好；相比MRTA-RTPP[12]，分布式一體化解法得出的解更逼近最優(yōu)解，但MRTA-RTPP[12]方法的運(yùn)算速度更快，其平均運(yùn)算時(shí)間比分布式一體化解法快約5 s，其運(yùn)算時(shí)間優(yōu)勢(shì)并不明顯，綜合兩項(xiàng)評(píng)估標(biāo)準(zhǔn)，分布式一體化解法性能更優(yōu)。

4 結(jié) 論

1）相比于分層解耦求解方法，一體化求解方法更接近最優(yōu)解；分布式規(guī)劃框架將問(wèn)題的求解分散到各 UAV實(shí)體上，可有效提高算法的求解速度。實(shí)驗(yàn)證明，在任務(wù)空間存在一定動(dòng)態(tài)性的情況下，基于分布式架構(gòu)的一體化求解算法具有較好的實(shí)時(shí)性，可以完成任務(wù)的快速響應(yīng)，具有一定的實(shí)用價(jià)值，且算法對(duì)比實(shí)驗(yàn)在實(shí)時(shí)系統(tǒng) RTX上進(jìn)行，運(yùn)行環(huán)境相對(duì)穩(wěn)定，對(duì)比結(jié)果具有說(shuō)服力。

2）在考慮UAV避碰、UAV燃油、UAV任務(wù)載荷、UAV異構(gòu)、任務(wù)執(zhí)行次序等約束條件下，結(jié)合Dubins Car模型可實(shí)現(xiàn)UAV飛行航跡與UAV動(dòng)力學(xué)模型的等效轉(zhuǎn)換，基于圖論思想，通過(guò) UAV的飛行航向角的離散化完成對(duì)協(xié)同任務(wù)規(guī)劃這一NP問(wèn)題的離散簡(jiǎn)化，可以實(shí)現(xiàn)對(duì)協(xié)同任務(wù)規(guī)劃問(wèn)題的等效建模。通過(guò)與針對(duì)混合整數(shù)線性規(guī)劃的優(yōu)化算法包 CPLEX的仿真對(duì)比，證明建模方法具有一定的有效性和實(shí)用性。

3）由于未考慮UAV間的通信延遲、UAV的飛行航跡的高度維，且假設(shè)偵查類UAV完成偵查任務(wù)是瞬間完成的，故現(xiàn)有工作存在不足，且一體化求解算法不能適用于任務(wù)空間更為復(fù)雜（參與任務(wù)的實(shí)體數(shù)大于20）的情況，求解過(guò)程需要考慮“死鎖”情況，所以建模方法與算法仍需進(jìn)一步改善；同時(shí)，經(jīng)初步分析可知，UAV飛行航向角的離散程度的nd越大，算法求解時(shí)間亦會(huì)增加，但是帶來(lái)的解的最優(yōu)度并不能顯著提高，所以離散量nd的取值也是后續(xù)研究的關(guān)鍵內(nèi)容。

（References）：

[1]Maza I, Caballero F, Capitan J, et al. Experimental results in multi-UAV coordination for disaster management and civil security applications[J]. Journal of intelligent &robotic systems, 2011, 61(1): 563-585.

[2]Kendou F. Survey of advances in guidance, navigation,and control of unmanned rotorcraft systems[J]. Journal of Field Robotics, 2012, 29(2): 315-378.

[3]Rathinam S, Sengupta R, Darbha S. A resource allocation algorithm for multivehicle systems with nonholonomic constraints[J]. IEEE Trans. Autom. Sci. Eng.,2007, 4(1): 98-104.

[4]Savla K, Frazzoli E, Bullo F. On the point-to-point and traveling salesperson problems for Dubins’ vehicle[C]//American Control Conference. June 2005: 786-791.

[5]Edison E, Shima T. Integrated task assignment and path optimization for cooperating uninhabited aerial vehicles using genetic algorithms[J]. Computers and Operations Research, 2010, 38(1): 340-356.

[6]Cons M S, Shima T, Domshlak C. Integrating task and motion planning for unmanned aerial vehicles[J]. Unmanned Systems, 2014, 2(1): 19-38.

[7]Ponda S S, Johnson L B, Geramifard A, et al. Cooperative mission planning for multi-UAV teams[M]. Handbook of Unmanned Aerial Vehicles. Springer Netherlands,2015: 1447-1490.

[8]Chandler P R, Pachter M, Swaroop D, et al. Complexity in UAV cooperative control[C]//American Control Conference. IEEE, 2002, Vol.3: 1831-1836.

[9]Dubins L E. On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents[J]. American Journal of Mathematics, 1957, 79(3): 497-516.

[10]沈林成, 陳璟, 王楠. 飛行器任務(wù)規(guī)劃技術(shù)綜述[J]. 航空學(xué)報(bào), 2014, 35(3): 593-606.Shen Lin-cheng, Chen Jing, Wang Nan. Survey on task planning technology for aircraft[J]. Acta Aeronautica Et Astronautica Sinica, 2014, 35(3): 593-606.

[11]Tsourdos A, White B, Shanmugavel M. Cooperative path planning of unmanned aerial vehicles[M]. John Wiley &Sons, 2010.

[12]Woosley B, Dasgupta P. Multi-robot task allocation with real-time path planning[C]//Proc. of the Twenty-Sixth International Florida Artificial Intelligence Research Society Conference. 2013: 574-579.

[13]Arsie A, Savla K, Frazzoli E. Efficient routing algorithms for multiple vehicles with no explicit communications[J].IEEE Transactions on Automatic Control, 2009, 54(10):2302-2317.

[14]Moon S, Oh E, Shim D H. Integral framework of task assignment and path planning for multiple unmanned aerial vehicles in dynamic environments[J]. Journal of Intelligent & Robotic Systems, 2013, 70(1-4): 303-313.

[15]Richards A, Bellingham J, Tillerson M, et al. Coordination and control of multiple UAVs[C]//AIAA Guidance,Navigation, and Control Conference. Monterey, CA. 2002.

[16]Rasmussen S J, Shima T. Tree search algorithm for assigning cooperating UAVs to multiple tasks[J]. International Journal of Robust and Nonlinear Control, 2008,18(2): 135-153.

[17]Deng Q B, Yu J Q, Wang N F. Cooperative task assignment of multiple heterogeneous unmanned aerial vehicles using a modified genetic algorithm with multi-type genes[J]. Chinese Journal of Aeronautics, 2013, 26(5): 1238-1250.

[18]Edison E. Task assignment and path optimization for cooperating uninhabited aerial vehicles[D]. Technion Israel Institute of Technology, Faculty of Aerospace Engineering, 2009.

[19]Pospichal P, Jaros J, Schwarz J. Parallel genetic algorithm on the cuda architecture[M]. Applications of Evolutionary Computation. Springer Berlin Heidelberg, 2010: 442-451.

[20]黃榮, 崔乃剛, 韋常柱, 等. 基于 RRT-GPM 兩階策略的導(dǎo)彈編隊(duì)協(xié)同突防最優(yōu)軌跡快速設(shè)計(jì)[J]. 中國(guó)慣性技術(shù)學(xué)報(bào), 2015, 23(3): 356-362.Huang Rong, Cui Nai-gang, Wei Chang-zhu, et al. Rapid trajectory optimization for cooperative penetration of missile formation based on two-stage RRT-GMP strategy[J]. Journal of Chinese Inertial Technology, 2015, 23(3):356-362.

[21]鄭重, 熊朝華, 黨宏濤, 等. 時(shí)變通信延遲下的無(wú)人機(jī)編隊(duì)魯棒自適應(yīng)控制[J]. 中國(guó)慣性技術(shù)學(xué)報(bào), 2016,24(1): 108-113.Zheng Zhong, Xiong Zhao-hua, Dang Hong-tao, et al.Robust adaptive control for unmanned aerial vehicle’s formation with time-varying communication delays[J]. Journal of Chinese Inertial Technology, 2016, 24(1): 108-113.

Integrated distributed method for dynamic cooperative mission planning problem

CUI Nai-gang, WU Wei-nan, GUO Ji-feng
(School of Astronautics, Harbin Institute of Technology, Harbin 150001, China)

Based on multi-heterogeneous UAVs in dynamic mission scenario of reconnaissance, striking and verifying, this paper establishes the models for cooperative mission planning problem, and designs an integrated distributed algorithm. Because of the disadvantages of the centralized planning framework, this paper adopts distributed planning framework. First, the graph theory is employed to transform the mission planning problem into directed graph under the constraint conditions of collision avoiding, fuel consuming,and the mission sequence. The Dubins Car Model is used to stand for the UAV’s kinematic model. Then,without decoupling the planning solution problems, this paper designs an integrated planning framework, and adopts the genetic/tabu search hybrid algorithm to solve the planning problem. At Last, some examples was presented in several simulation scenarios to compare the performance and computational results from different algorithms, which show that the integrated distributed method can be applied to the dynamic mission scenario, and can rapidly solve the planning problem with complex missions.

heterogeneous UAVs; integrated method; cooperative mission planning; distributed decisionmaking; Dubins path; tabu/genetic hybrid algorithm

1005-6734(2017)04-0523-07

10.13695/j.cnki.12-1222/o3.2017.04.018

TP29

A

2017-04-08；

2017-07-20

國(guó)家自然科學(xué)基金（11472090）

崔乃剛（1965—），男，教授，博士生導(dǎo)師，主要飛行器總體設(shè)計(jì)、制導(dǎo)控制、任務(wù)規(guī)劃領(lǐng)域研究。E-mail: Cui_Naigang@163.com