胡超芳，宋思涵，徐嘉均，王迪迪

基于拍賣鴿群優(yōu)化算法的多無人機(jī)追蹤分布式任務(wù)分配

胡超芳，宋思涵，徐嘉均，王迪迪

(天津大學(xué)電氣自動化與信息工程學(xué)院，天津 300072)

無人機(jī)技術(shù)已經(jīng)廣泛應(yīng)用于各種研究領(lǐng)域，任務(wù)分配是多無人機(jī)協(xié)同的關(guān)鍵技術(shù)之一，對多無人機(jī)任務(wù)完成質(zhì)量的影響極大，針對多個目標(biāo)追蹤場景下的多無人機(jī)任務(wù)分配問題，提出了一種基于拍賣鴿群優(yōu)化(auction-PIO)算法的分布式分配方法．首先采用追蹤總距離、分配均衡性、任務(wù)完成時間3個性能指標(biāo)，結(jié)合追蹤任務(wù)約束條件，建立了分布式多指標(biāo)0/1整數(shù)規(guī)劃模型．然后以拍賣策略作為分布式優(yōu)化框架，無人機(jī)作為拍賣者對地面目標(biāo)進(jìn)行競拍出價，通過多輪競拍確定任務(wù)分配方案．為提高拍賣分配的最優(yōu)性，增強(qiáng)了各無人機(jī)間的共享信息量，進(jìn)而使無人機(jī)可對所有目標(biāo)進(jìn)行競拍出價，并引入PIO算法更新各無人機(jī)的競拍價格，將鴿子位置編碼為無人機(jī)對各地面目標(biāo)的競拍增價，利用地圖指南針?biāo)阕雍偷貥?biāo)算子迭代更新種群位置，實(shí)現(xiàn)對無人機(jī)競拍價格的優(yōu)化更新．在此基礎(chǔ)上，設(shè)計基于目標(biāo)優(yōu)先級的解算策略，用于將競價矩陣和距離矩陣解算為任務(wù)分配方案，并進(jìn)行了算法的計算復(fù)雜度分析．最后對所提拍賣鴿群優(yōu)化算法分別進(jìn)行了數(shù)值仿真、Gazebo虛擬仿真和實(shí)機(jī)戶外飛行實(shí)驗(yàn)，結(jié)果表明：所提算法擁有良好的任務(wù)分配性能，不但在數(shù)值仿真對比中，優(yōu)化性能比經(jīng)典拍賣算法提高了12.16%，而且虛擬仿真和戶外實(shí)驗(yàn)也說明算法能夠滿足實(shí)用性要求.

無人機(jī)；目標(biāo)追蹤；任務(wù)分配；拍賣；鴿群優(yōu)化

近些年，無人機(jī)技術(shù)廣泛應(yīng)用于各個研究領(lǐng)域，人們對無人機(jī)完成復(fù)雜任務(wù)的需求不斷增長[1]．其中，無人機(jī)追蹤地面目標(biāo)是一個熱點(diǎn)研究方向，但是單架無人機(jī)執(zhí)行追蹤任務(wù)存在覆蓋范圍有限、容錯性低等局限性．因此許多學(xué)者對多無人機(jī)協(xié)作進(jìn)行大量的研究，其中作為多機(jī)協(xié)同的一大關(guān)鍵技術(shù)，任務(wù)分配得到了廣泛關(guān)注[2]．

多無人機(jī)任務(wù)分配問題是指考慮多無人機(jī)有限資源約束，以整體任務(wù)效果最優(yōu)為目標(biāo)，將各具體任務(wù)分配給不同無人機(jī)．其分配執(zhí)行策略主要包括集中式和分布式兩種，其中集中式分配是將所有無人機(jī)信息匯聚在一個控制中心進(jìn)行分配計算的，分配方法分為最優(yōu)化方法[3]和啟發(fā)式方法[4]．最優(yōu)化的方法是找到任務(wù)分配問題的最優(yōu)解，然而當(dāng)問題規(guī)模增大時，最優(yōu)化方法的求解復(fù)雜度急劇升高．啟發(fā)式算法追求計算時間與求解精度之間的平衡，集中式任務(wù)分配大多用啟發(fā)式算法，如遺傳算法[5]、蟻群算法等[6].但是集中式分配難以擺脫計算量大、依賴處理中心?等局限，因此分布式算法成為任務(wù)分配領(lǐng)域的研究?熱點(diǎn).

在分布式的框架下，各無人機(jī)獨(dú)立獲取信息并進(jìn)行決策，擁有較好的實(shí)時性和魯棒性．常見的分布式任務(wù)分配算法包括基于博弈論的任務(wù)分配[7]、基于群體行為激勵的任務(wù)分配[8]、基于市場競拍機(jī)制的任務(wù)分配[9-10]．其中，基于博弈論的任務(wù)分配方法針對多無人機(jī)間任務(wù)執(zhí)行的相互依存性，引入了博弈論思想使多個無人機(jī)互相競爭協(xié)商，從而得到較優(yōu)任務(wù)分配結(jié)果．該方法采用隱式通信模式，系統(tǒng)通信負(fù)載小，但因其分配結(jié)果由規(guī)則設(shè)定，很大程度上與閾值的選擇有關(guān)，較難保證分配效果．基于群體行為激勵的任務(wù)分配方法將無人機(jī)感知環(huán)境信息映射到無人機(jī)行為模式的改變，實(shí)現(xiàn)全局任務(wù)分配方案的自動調(diào)整．該方法通信量較小、速度快，具有一定魯棒性，僅適用于解決個體行為較為簡單的多智能體系統(tǒng)．市場機(jī)制是模擬市場競價、競拍過程的一種分布式策?略[11]，其本質(zhì)是各個智能體追求自身收益最大，在某種協(xié)議的限定下與其他智能體對話協(xié)商，從而動態(tài)實(shí)現(xiàn)任務(wù)分配．基于市場機(jī)制具有適中的計算成本和通信負(fù)載，求解效率高，適合進(jìn)行實(shí)時任務(wù)分配，近些年受到了廣泛的關(guān)注與研究．

分布式拍賣算法是一種常用的基于市場機(jī)制的任務(wù)分配方法[12]．對于多無人機(jī)任務(wù)分配而言，各無人機(jī)通常作為拍賣者，對最感興趣的任務(wù)進(jìn)行出價，出價最高的無人機(jī)獲得任務(wù)，未競拍成功的無人機(jī)可以繼續(xù)提高報價進(jìn)行競爭，直到各無人機(jī)都獲得最大收益，其中競拍價更新策略的設(shè)計極大地影響算法性能[13]．經(jīng)典拍賣算法的競拍價更新原則是最大凈利潤與第2大凈利潤之差，由于對信息的利用有限，僅能優(yōu)化單一指標(biāo)[9]．Lee等[14]為了保證機(jī)器人的任務(wù)完成可靠性，將多種有限資源作為確定拍賣價格的影響因素，提出了面向資源的分散拍賣算法．該算法求解速度快，然而只考慮有限資源而不重視任務(wù)收益，在其他場景并不適用．Braquet等[15]為了獲得最佳評估的競拍價向量，將其定義為系統(tǒng)總效益與缺少一個智能體的系統(tǒng)總效益之差．該定義雖然可以獲取最佳評估的競拍價向量，但計算量難以控制，且在某些場景中系統(tǒng)總效益很難確定．由此可見，競拍價格更新策略的設(shè)計存在求解精度與計算量之間的矛盾．群體智能算法近些年常常被應(yīng)用于解決優(yōu)化問題，鴿群優(yōu)化(PIO)算法相較于其他群體智能算法有更好的收斂性和求解精度[16]，已廣泛應(yīng)用于各種連續(xù)優(yōu)化問題[17-18]，因此鴿群優(yōu)化算法擁有應(yīng)用于拍賣算法中競拍價更新的潛質(zhì)，種群編碼和個體位置的評價策略是鴿群優(yōu)化算法應(yīng)用的關(guān)鍵．

本文針對多個目標(biāo)追蹤場景下的多無人機(jī)任務(wù)分配問題[19]展開研究．首先提出了追蹤總距離、任務(wù)分配均衡性、任務(wù)完成時間3個性能指標(biāo)，綜合每個目標(biāo)至少有一架無人機(jī)追蹤，每架無人機(jī)只能追蹤一個目標(biāo)的約束條件，構(gòu)建了分布式多指標(biāo)0/1整數(shù)規(guī)劃模型．在求解算法設(shè)計方面，以拍賣策略作為分布式實(shí)現(xiàn)框架并進(jìn)行了改進(jìn)．為了提高拍賣優(yōu)化的最優(yōu)性，各無人機(jī)共享更多信息，即不再只對單一目標(biāo)進(jìn)行出價，而是對所有目標(biāo)均給出報價．此外，考慮基于規(guī)則式的競拍價更新策略存在求解精度與計算量之間的矛盾，鑒于鴿群優(yōu)化算法在處理該矛盾上的優(yōu)勢，采用鴿群優(yōu)化算法對競拍價進(jìn)行優(yōu)化更新. 鴿群位置編碼與評價成為鴿群優(yōu)化算法在拍賣策略中應(yīng)用的關(guān)鍵問題．本文將鴿群位置編碼為競拍增價，并設(shè)計了一種基于目標(biāo)優(yōu)先級的任務(wù)分配方案解算策略，將無人機(jī)競價信息解算為任務(wù)分配方案，用于鴿群優(yōu)化算法的個體位置評價．最后，通過與經(jīng)典拍賣算法進(jìn)行的數(shù)值仿真對比，優(yōu)化性能提高了12.16%，驗(yàn)證了本文方法的有效性，并將其移植到Gazebo仿真環(huán)境和多無人機(jī)協(xié)同追蹤實(shí)驗(yàn)系統(tǒng)，進(jìn)行了虛擬仿真與實(shí)機(jī)飛行測試，進(jìn)一步驗(yàn)證了本文方法的實(shí)用性．

1?多無人機(jī)追蹤任務(wù)分配建模

1.1?問題描述

以城市環(huán)境為具體應(yīng)用背景，多架無人機(jī)追蹤多個地面目標(biāo)問題如圖1所示，通過任務(wù)分配，各無人機(jī)明確需要追蹤的目標(biāo)，并盡可能靠近所跟蹤的目標(biāo)，使目標(biāo)時刻處于無人機(jī)視野范圍內(nèi)．本文以圖1中的虛線表示任務(wù)匹配關(guān)系，做出如下假設(shè)：

(1) 無人機(jī)是同構(gòu)的，飛行速度相同；

(2) 每個目標(biāo)的追蹤需求相同，即每一架無人機(jī)可以追蹤任意一個目標(biāo)，每個目標(biāo)可以被任意一架無人機(jī)追蹤；

(3) 地面目標(biāo)的位置和移動是已知的．

圖1?追蹤場景多無人機(jī)任務(wù)分配示意

假設(shè)各無人機(jī)、目標(biāo)定位精確，即各無人機(jī)內(nèi)存儲的距離矩陣相同．

1.2?約束條件

1.3?性能指標(biāo)

針對多個目標(biāo)追蹤任務(wù)，本文主要從追蹤效果、節(jié)約能源等角度，采用以下性能指標(biāo).

1.4?分布式多指標(biāo)任務(wù)分配模型

2?拍賣鴿群優(yōu)化算法

2.1?分布式拍賣框架

本文將拍賣思想運(yùn)用于多無人機(jī)追蹤任務(wù)分配，將無人機(jī)作為競拍者，地面目標(biāo)作為競拍物品．各無人機(jī)互相共享信息，實(shí)時調(diào)整自身的競拍價格，最終通過多輪競拍敲定任務(wù)分配方案．本文假定無人系統(tǒng)已構(gòu)成通信網(wǎng)絡(luò)，各無人機(jī)能夠通過信息共享獲取全局信息．

各無人機(jī)需要根據(jù)當(dāng)前信息對自身的競拍價格進(jìn)行優(yōu)化更新，并重新共享給其他無人機(jī)，進(jìn)行下一輪競拍．

然而經(jīng)典拍賣算法的競拍價更新規(guī)則僅考慮無人機(jī)自身的利益最大，在實(shí)際的大規(guī)模任務(wù)分配問題中，還對整體指標(biāo)有相應(yīng)的要求，例如本文提出的任務(wù)分配均衡性、任務(wù)完成時間，直接應(yīng)用經(jīng)典拍賣算法的競拍價格更新原則無法獲得良好的任務(wù)分配效果，因此在后續(xù)算法設(shè)計中，本文引入了鴿群優(yōu)化算法進(jìn)行各無人機(jī)競拍價格的更新．

在各無人機(jī)共享信息并更新競價矩陣后，需要結(jié)合距離矩陣解算出任務(wù)分配方案，并與上一輪獲得的任務(wù)分配方案進(jìn)行比較，若相同則判定算法收斂，否則繼續(xù)進(jìn)行拍賣優(yōu)化．為了保證算法速度，以及解算得到的任務(wù)分配方案滿足追蹤場景下的約束條件式(3)，本文設(shè)計了一種基于目標(biāo)優(yōu)先級的任務(wù)分配方案解算策略，該策略同時也應(yīng)用于鴿群優(yōu)化算法的種群評價環(huán)節(jié)．

2.2?基于目標(biāo)優(yōu)先級的任務(wù)分配方案解算

式中avg表示具有最高競拍價的無人機(jī)．

差值計算式為

定義目標(biāo)優(yōu)先級指數(shù)為

步驟1 對每個目標(biāo)使用式(13)計算目標(biāo)指數(shù)優(yōu)先級指數(shù)，并根據(jù)目標(biāo)指數(shù)優(yōu)先級指數(shù)進(jìn)行排序，獲得目標(biāo)分配順序．

步驟2 各目標(biāo)按照順序進(jìn)行任務(wù)分配，優(yōu)先分配給出價最高的無人機(jī)．

步驟5 判斷是否所有目標(biāo)都已分配，若有目標(biāo)未進(jìn)行分配，則返回步驟2．

步驟6 未分配的無人機(jī)選擇距離最近的目標(biāo)進(jìn)行輔助追蹤.

2.3?基于鴿群優(yōu)化算法的競拍價更新策略

2.3.1?鴿群優(yōu)化算法

2.3.2?鴿群位置評價

2.3.3?鴿群優(yōu)化算法更新競拍價流程

使用鴿群優(yōu)化算法更新各無人機(jī)的競拍價過程偽代碼如下所示.

鴿群位置編碼為無人機(jī)對各目標(biāo)的競拍增價，初始化鴿群位置；

end while

使用地標(biāo)算子式(15)更新鴿群位置；

end while．

2.4?拍賣鴿群優(yōu)化算法流程

步驟1 向其他無人機(jī)發(fā)送自己的位置和初始競拍價，接收其他無人機(jī)發(fā)送的位置和初始競拍價．

步驟3 鴿群位置編碼為該無人機(jī)對各目標(biāo)的競拍增價，并利用鴿群優(yōu)化算法優(yōu)化該無人機(jī)對各目標(biāo)的競拍增價．

步驟4 向其余無人機(jī)發(fā)送更新后的競拍價，并接收其余無人機(jī)發(fā)送的新競拍價．

步驟5 更新競價矩陣，并使用基于目標(biāo)優(yōu)先級的任務(wù)分配方案解算策略解算出任務(wù)分配方案．

步驟6 與上一次任務(wù)分配方案對比，若一致則輸出任務(wù)分配結(jié)果，否則返回步驟3．

2.5?算法復(fù)雜度分析

圖2?基于拍賣鴿群優(yōu)化算法的任務(wù)分配流程

3?仿真和實(shí)驗(yàn)驗(yàn)證

本文對所提算法進(jìn)行了數(shù)值仿真、Gazebo虛擬仿真和實(shí)機(jī)飛行實(shí)驗(yàn)，進(jìn)而驗(yàn)證了其性能和可行性．

3.1?數(shù)值仿真

3.1.1?靜態(tài)任務(wù)分配驗(yàn)證

采用隨機(jī)分布在非建筑位置上的50架無人機(jī)與35個地面目標(biāo)對靜態(tài)任務(wù)分配進(jìn)行測試，圖4和圖5分別展示了使用本文提出的拍賣鴿群優(yōu)化算法和經(jīng)典拍賣算法的靜態(tài)任務(wù)分配效果．其中品紅色三角形表示無人機(jī)，藍(lán)色的圓形表示地面目標(biāo)，綠色的連線表示無人機(jī)追蹤目標(biāo)的匹配關(guān)系，兩種方法均能獲得可行的任務(wù)分配方案．在圖中，紅色的加粗直線和圓圈表示本文所提方法任務(wù)分配方案優(yōu)于經(jīng)典拍賣算法任務(wù)分配方案的例子．可以看出經(jīng)典拍賣算法容易出現(xiàn)過長距離的追蹤，這會導(dǎo)致整體任務(wù)完成時間延長，同時也會出現(xiàn)5架無人機(jī)追蹤同一目標(biāo)的任務(wù)分配不均的狀況，而本文所提方法可以獲得更加理想的任務(wù)分配結(jié)果．

圖3?數(shù)值仿真地圖

圖4?基于本文所提算法的任務(wù)分配結(jié)果

圖5?基于經(jīng)典拍賣算法的任務(wù)分配結(jié)果

圖6(a)～(c)展示了各性能指標(biāo)在迭代過程中的變化過程，均保持著下降趨勢，個別指標(biāo)出現(xiàn)暫時上升是為了對其他性能指標(biāo)進(jìn)行優(yōu)化，由圖6(d)可以看出在迭代過程中，加權(quán)性能指標(biāo)持續(xù)優(yōu)化下降．表1展示了所提算法與經(jīng)典拍賣算法的優(yōu)化結(jié)果性能指標(biāo)對比，由表1可知，所提方法的所有性能指標(biāo)均優(yōu)于經(jīng)典拍賣算法，尤其是在任務(wù)分配均衡性和最大追蹤距離方面，總體優(yōu)化性能相較于經(jīng)典拍賣算法提高了12.16%．

（a）追蹤總距離

（b）分配均衡性

（c）最大追蹤距離

（d）加權(quán)性能指標(biāo)

圖6?拍賣鴿群優(yōu)化算法優(yōu)化曲線

Fig.6?Optimization curves of the auction-PIO algorithm

表1?2種算法優(yōu)化結(jié)果對比

Tab.1?Comparison results of the two algorithms

3.1.2?動態(tài)任務(wù)分配驗(yàn)證

動態(tài)任務(wù)分配驗(yàn)證中，為了保證結(jié)果的清晰和直觀，無人機(jī)數(shù)量為9架，地面目標(biāo)數(shù)量為5個．無人機(jī)以7.5m/s的速度做勻速運(yùn)動，地面目標(biāo)以5m/s的速度做勻速運(yùn)動，運(yùn)動軌跡如圖7所示，無人機(jī)使用本文所提方法進(jìn)行任務(wù)分配，并根據(jù)航跡規(guī)劃計算出的航跡對地面目標(biāo)進(jìn)行追蹤．追蹤效果如圖7所示，其中藍(lán)色圓形連成的曲線代表地面目標(biāo)的運(yùn)動軌跡，品紅色的三角形表示無人機(jī)飛行的航點(diǎn)，較大的圓形和三角形為地面目標(biāo)和無人機(jī)的初始位置，所有目標(biāo)均受到了較好的追蹤．此外，在無人機(jī)飛行過程中，由于受到任務(wù)分配算法的控制，共有兩架飛機(jī)的追蹤任務(wù)發(fā)生了改變，如圖8所示，時間先后順序?yàn)?a)～(d)．可以看出，本文所提的任務(wù)分配算法能夠?yàn)闊o人機(jī)選擇最佳任務(wù)，提高追蹤任務(wù)完成效率．

圖7?多無人機(jī)追蹤過程

（a）時刻1 ?? （b）時刻2

（c）時刻3 ?? （d）時刻4

圖8?不同時刻的任務(wù)分配結(jié)果

Fig.8?Task allocation results at different moments

3.2?Gazebo虛擬仿真

仿真環(huán)境中設(shè)置5架無人機(jī)和3個地面運(yùn)動行人，5架無人機(jī)間隔2m呈一字形排列．行人的速度設(shè)置為1m/s．仿真的追蹤過程如圖9所示，算法得到的任務(wù)分配方案如圖9(a)所示，并繪制出無人機(jī)和地面目標(biāo)的運(yùn)動軌跡如圖10所示，多無人機(jī)可以通過本文算法解算出合理的追蹤任務(wù)分配方案．圖11展示了拍賣鴿群優(yōu)化算法迭代過程中的加權(quán)性能指標(biāo)的變化曲線，共迭代5次達(dá)到最優(yōu)，任務(wù)分配方案解算時間不超過0.5s，滿足追蹤系統(tǒng)性能需求．

（a）時刻1

（b）時刻2

（c）時刻3

（d）時刻4

圖9?Gazebo虛擬仿真追蹤過程

Fig.9?Tracking in Gazebo virtual simulation

圖10?無人機(jī)與地面目標(biāo)運(yùn)動軌跡

圖11?虛擬仿真中拍賣鴿群優(yōu)化算法迭代優(yōu)化曲線

3.3?實(shí)機(jī)戶外實(shí)驗(yàn)驗(yàn)證

多無人機(jī)協(xié)同追蹤實(shí)驗(yàn)系統(tǒng)由5架無人機(jī)及配套設(shè)備構(gòu)成，無人機(jī)間利用局域網(wǎng)進(jìn)行ROS話題的訂閱和發(fā)布，實(shí)現(xiàn)位置、競拍價格的共享．無人機(jī)使用機(jī)載計算機(jī)進(jìn)行上層控制，運(yùn)行任務(wù)所提分配算法和已有的航跡規(guī)劃算法，任務(wù)分配算法負(fù)責(zé)選擇待追蹤目標(biāo)并將其位置發(fā)送到航跡規(guī)劃算法，規(guī)劃的航跡通過串口通信傳遞給成熟的底層飛控進(jìn)行無人機(jī)位置控制．實(shí)驗(yàn)系統(tǒng)通過差分GPS獲取無人機(jī)精確定位信息，為了充分驗(yàn)證分配算法的性能，本文通過UWB局部定位系統(tǒng)來獲取地面目標(biāo)精確定位信息．將經(jīng)過虛擬仿真驗(yàn)證的程序移植到多無人機(jī)協(xié)同追蹤實(shí)驗(yàn)系統(tǒng)，算法參數(shù)同Gazebo虛擬仿真保持一致．

實(shí)驗(yàn)布置與仿真中保持一致，實(shí)驗(yàn)過程如圖12所示．使用本文提出的任務(wù)分配算法獲得到的匹配關(guān)系如圖12(a)所示．以無人機(jī)1上電位置為坐標(biāo)原點(diǎn)，繪制5架無人機(jī)和3個地面目標(biāo)的運(yùn)動軌跡，圖13為三維運(yùn)動軌跡效果，圖14為俯視二維運(yùn)動軌跡效果，其中彩色線條表示無人機(jī)的運(yùn)動軌跡，黑色線條表示地面目標(biāo)的運(yùn)動軌跡，無人機(jī)系統(tǒng)能夠?qū)Φ孛婺繕?biāo)進(jìn)行較好的追蹤．算法迭代過程中加權(quán)性能指標(biāo)變化曲線如圖15所示，3次迭代后達(dá)到最優(yōu)，總用時小于0.3s，任務(wù)分配算法速度滿足實(shí)驗(yàn)系統(tǒng)需求．在本文的研究中，動力學(xué)約束由已有的航跡規(guī)劃和底層控制滿足．實(shí)驗(yàn)結(jié)果表明：在具備有效的航跡規(guī)劃和底層控制方法的基礎(chǔ)上，通過本文所提算法可以快速解算出合理的任務(wù)分配方案并實(shí)現(xiàn)多無人機(jī)追蹤多個地面目標(biāo)．

（a）時刻1

（b）時刻2

（c）時刻3

（d）時刻4

圖12?戶外任務(wù)分配實(shí)驗(yàn)過程

Fig.12?Process of outdoor task allocation experiment

圖13?三維無人機(jī)與地面目標(biāo)運(yùn)動軌跡

圖14?二維無人機(jī)與地面目標(biāo)運(yùn)動軌跡

圖15?戶外實(shí)驗(yàn)中拍賣鴿群優(yōu)化算法優(yōu)化曲線

4?結(jié)?語

本文對多無人機(jī)協(xié)同追蹤場景的分布式任務(wù)分配進(jìn)行了建模和算法設(shè)計．建立了包含3個性能指標(biāo)和兩個約束條件的分布式任務(wù)分配模型．在此基礎(chǔ)上，提出了拍賣鴿群優(yōu)化算法，將拍賣策略作為分布式實(shí)現(xiàn)框架，并設(shè)計了一種基于目標(biāo)優(yōu)先級的任務(wù)分配方案解算策略，引入鴿群優(yōu)化算法更新各無人機(jī)的競拍價，最后通過數(shù)值仿真、Gazebo虛擬仿真、實(shí)機(jī)戶外實(shí)驗(yàn)證明了算法的有效性和實(shí)用性．目前的研究僅實(shí)現(xiàn)了在相對理想條件下的追蹤場景任務(wù)分配，仍有許多方面需要繼續(xù)深入研究和改進(jìn)，例如：多無人機(jī)任務(wù)分配和航跡規(guī)劃一體化的研究；滿足更多約束的任務(wù)分配算法研究．

［1］ 侯永宏，劉?艷，呂華龍，等. 一種基于雙目視覺的無人機(jī)自主導(dǎo)航系統(tǒng)[J]. 天津大學(xué)學(xué)報(自然科學(xué)與工程技術(shù)版)，2019，52(12)：1262-1269.

Hou Yonghong，Liu Yan，Lü Hualong，et al. An autonomous navigation systems of UAVs based on bin-ocular vision[J]. Journal of Tianjin University (Science and Technology)，2019，52(12)：1262-1269(in Chi-nese).

［2］ Kurdi H A，Ebtesam A，Maram A，et al. Autonomous task allocation for multi-UAV systems based on the lo-cust elastic behavior[J]. Applied Soft Computing，2018，71(1)：110-126.

［3］ Silvestrin P V，Ritt M. An iterated tabu search for the multi-compartment vehicle routing problem[J]. Com-puters & Operations Research，2017，81(1)：192-202.

［4］ 李?儼，董玉娜. 基于SA-DPSO混合優(yōu)化算法的協(xié)同空戰(zhàn)火力分配[J]. 航空學(xué)報，2010，31(3)：626-631.

Li Yan，Dong Yuna. Weapon-target assignment based on simulated annealing and discrete particle swarm optimi-zation in cooperative air combat[J]. Acta Aeronautica et Astronautica Sinica，2010，31(3)：626-631 (in Chinese).

［5］ Muhuri P K，Rauniyar A. Immigrants based adaptive genetic algorithms for task allocation in multi-robot sys-tems[J]. International Journal of Computational In-telligence and Applications，2017，16(1)：1750025.

［6］ Pendharkar P C. An ant colony optimization heuristic for constrained task allocation problem[J]. Journal of Com-putational Science，2015，7(1)：37-47.

［7］ Cui R X，Guo J，Gao B. Game theory-based negotia-tion for multiple robots task allocation[J]. Robotica，2013，31(6)：923-934.

［8］ Bonabeau E，Sobkowski A，Guy T，et al. Adaptive task allocation inspired by a model of division of labor in social insects[C]// Biocomputation and Emergent Com-puting，1997：36-45.

［9］ Bertsekas D P. The auction algorithm：A distributed relaxation method for the assignment problem[J]. Annals of Operations Research，1988，14(1)：105-123.

［10］ Adhau S，Mittal M L，Mittal A. A multi-agent system for distributed multi-project scheduling：An auction-based negotiation approach[J]. Engineering Applications of Artificial Intelligence，2012，25(8)：1738-1751.

［11］ Edalat N，Tham C K，Xiao W. An auction-based strat-egy for distributed task allocation in wireless sensor net-works[J]. Computer Communications，2012，35(8)：916-928.

［12］ Song T，Yan X，Liang A，et al. A distributed bidirec-tional auction algorithm for multi-robot coordination[C]// 2009 International Conference on Research Challenges in Computer Science. Shanghai，China，2009：145-148.

［13］ Saravanan S，Ramanathan K C，Ramya M M，et al. Review on state-of-the-art dynamic task allocation strate-gies for multiple-robot systems[J]. Industrial Robot，2020，14(1)：929-942.

［14］ Lee D H，Zaheer S A，Kim J H. A resource-oriented，decentralized auction algorithm for multirobot task allo-cation[J]. IEEE Transactions on Automation Science & Engineering，2015，47(6)：1469-1481.

［15］ Braquet M，Bakolas E. Greedy decentralized auction-based task allocation for multi-agent systems[J]. IFAC-Papers on Line，2021，54(20)：675-680.

［16］ Qiu H，Duan H. Multi-objective pigeon-inspired optimi-zation for brushless direct current motor parameter de-sign[J]. Science China Technological Sciences，2015，58(11)：1915-1923.

［17］ Li C，Duan H. Target detection approach for UAVs via improved pigeon-inspired optimization and edge poten-tial function[J]. Aerospace Science and Technology，2014，39(1)：352-360.

［18］ Duan H，Wang X. Echo state networks with orthogonal pigeon-inspired optimization for image restoration[J]. IEEE Transactions on Neural Networks and Learning Systems，2016，27(11)：2413-2425.

［19］ Hu C，Qu G，Zhang Y. Pigeon-inspired fuzzy multi-objective task allocation of unmanned aerial vehicles for multi-target tracking[J]. Applied Soft Computing，2022，126(1)：109310.

［20］ Duan H，Qiao P，Yang Y. Pigeon-inspired optimiza-tion：A new swarm intelligence optimizer for air robot path planning[J]. International Journal of Intelligent Comput-ing & Cybernetics，2014，7(1)：24-37.

Distributed Task Allocation Based on Auction-PIO Algorithm for Multi-UAV Tracking

Hu Chaofang，Song Sihan，Xu Jiajun，Wang Didi

(School of Electrical and Information Engineering，Tianjin University，Tianjin 300072，China)

Unmanned aerial vehicle(UAV)technology has been applied widely in various research fields. Task allocation is crucial in multi-UAV cooperation and has a significant impact on the quality of task completion. In this paper，a distributed allocation method based on auction algorithm with pigeon-inspired optimization(auction-PIO)was proposed for multi-UAV task allocation in a multi-target tracking scenario. First，three performance indices including total tracking distance，allocation balance，and task completion time，were proposed. Along with the constraints of the tracking task，a distributed multi-index 0-1 integer programming model was established. Second，the auction strategy was used as the distributed optimization framework，and the UAV was regarded as the auctioneer to bid for the ground target. The task allocation result was determined through multiple rounds of bidding. In order to enhance the optimality of allocation，the information shared among UAVs was increased such that UAVs were able to bid for all targets. Additionally，the PIOalgorithm was introduced to update the bidding prices for targets. The position of pigeon was encoded into the increment of UAVs bidding prices for targets. The map compass operator and landmark operator were used to update swarm positions iteratively so that the bidding prices of UAVs could be updated as well. On this basis，a solution strategy based on target priority was designed to convert the computation result of bidding matrix and distance matrix into allocation matching relationship. Moreover，the computational complexity of the proposed algorithm was analyzed. Finally，the numerical simulation，Gazebo virtual simulation，and outdoor flight experiment of actual UAVs were implemented for the proposed algorithm. The results show that the proposed auction-PIO algorithm has a good allocation performance. In the numerical simulation，the optimization performance of the proposed algorithm is improved by 12.16% compared with that of the classical auction algorithm. Moreover，the virtual simulation and the outdoor experiment also show that the proposed algorithm can meet the requirement of practicability.

unmanned aerial vehicle(UAV)；target tracking；task allocation；auction；pigeon-inspired optimization(PIO)

V279

A

0493-2137(2024)04-0403-12

10.11784/tdxbz202301009

2023-01-09；

2023-03-13.

胡超芳（1973—??），男，博士，教授.

胡超芳，cfhu@tju.edu.cn.

天津市科技計劃資助項(xiàng)目(19YFHBQY00040)；天津大學(xué)自主創(chuàng)新基金資助項(xiàng)目(2022XSU-0003).

the Science and Technology Program of Tianjin，China(No.19YFHBQY00040)，Tianjin University Innovation Foundation (No.2022XSU-0003).

(責(zé)任編輯：孫立華)