基于拍賣鴿群優化算法的多無人機追蹤分布式任務分配

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

基于拍賣鴿群優化算法的多無人機追蹤分布式任務分配

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

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

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

無人機；目標追蹤；任務分配；拍賣；鴿群優化

近些年，無人機技術廣泛應用于各個研究領域，人們對無人機完成復雜任務的需求不斷增長[1]．其中，無人機追蹤地面目標是一個熱點研究方向，但是單架無人機執行追蹤任務存在覆蓋范圍有限、容錯性低等局限性．因此許多學者對多無人機協作進行大量的研究，其中作為多機協同的一大關鍵技術，任務分配得到了廣泛關注[2]．

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

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

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

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

1?多無人機追蹤任務分配建模

1.1?問題描述

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

(1) 無人機是同構的，飛行速度相同；

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

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

圖1?追蹤場景多無人機任務分配示意

假設各無人機、目標定位精確，即各無人機內存儲的距離矩陣相同．

1.2?約束條件

1.3?性能指標

針對多個目標追蹤任務，本文主要從追蹤效果、節約能源等角度，采用以下性能指標.

1.4?分布式多指標任務分配模型

2?拍賣鴿群優化算法

2.1?分布式拍賣框架

本文將拍賣思想運用于多無人機追蹤任務分配，將無人機作為競拍者，地面目標作為競拍物品．各無人機互相共享信息，實時調整自身的競拍價格，最終通過多輪競拍敲定任務分配方案．本文假定無人系統已構成通信網絡，各無人機能夠通過信息共享獲取全局信息．

各無人機需要根據當前信息對自身的競拍價格進行優化更新，并重新共享給其他無人機，進行下一輪競拍．

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

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

2.2?基于目標優先級的任務分配方案解算

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

差值計算式為

定義目標優先級指數為

步驟1 對每個目標使用式(13)計算目標指數優先級指數，并根據目標指數優先級指數進行排序，獲得目標分配順序．

步驟2 各目標按照順序進行任務分配，優先分配給出價最高的無人機．

步驟5 判斷是否所有目標都已分配，若有目標未進行分配，則返回步驟2．

步驟6 未分配的無人機選擇距離最近的目標進行輔助追蹤.

2.3?基于鴿群優化算法的競拍價更新策略

2.3.1?鴿群優化算法

2.3.2?鴿群位置評價

2.3.3?鴿群優化算法更新競拍價流程

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

鴿群位置編碼為無人機對各目標的競拍增價，初始化鴿群位置；

end while

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

end while．

2.4?拍賣鴿群優化算法流程

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

步驟3 鴿群位置編碼為該無人機對各目標的競拍增價，并利用鴿群優化算法優化該無人機對各目標的競拍增價．

步驟4 向其余無人機發送更新后的競拍價，并接收其余無人機發送的新競拍價．

步驟5 更新競價矩陣，并使用基于目標優先級的任務分配方案解算策略解算出任務分配方案．

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

2.5?算法復雜度分析

圖2?基于拍賣鴿群優化算法的任務分配流程

3?仿真和實驗驗證

本文對所提算法進行了數值仿真、Gazebo虛擬仿真和實機飛行實驗，進而驗證了其性能和可行性．

3.1?數值仿真

3.1.1?靜態任務分配驗證

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

圖3?數值仿真地圖

圖4?基于本文所提算法的任務分配結果

圖5?基于經典拍賣算法的任務分配結果

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

（a）追蹤總距離

（b）分配均衡性

（c）最大追蹤距離

（d）加權性能指標

圖6?拍賣鴿群優化算法優化曲線

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

表1?2種算法優化結果對比

Tab.1?Comparison results of the two algorithms

3.1.2?動態任務分配驗證

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

圖7?多無人機追蹤過程

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

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

圖8?不同時刻的任務分配結果

Fig.8?Task allocation results at different moments

3.2?Gazebo虛擬仿真

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

（a）時刻1

（b）時刻2

（c）時刻3

（d）時刻4

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

Fig.9?Tracking in Gazebo virtual simulation

圖10?無人機與地面目標運動軌跡

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

3.3?實機戶外實驗驗證

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

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

（a）時刻1

（b）時刻2

（c）時刻3

（d）時刻4

圖12?戶外任務分配實驗過程

Fig.12?Process of outdoor task allocation experiment

圖13?三維無人機與地面目標運動軌跡

圖14?二維無人機與地面目標運動軌跡

圖15?戶外實驗中拍賣鴿群優化算法優化曲線

4?結?語

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

［1］ 侯永宏，劉?艷，呂華龍，等. 一種基于雙目視覺的無人機自主導航系統[J]. 天津大學學報(自然科學與工程技術版)，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混合優化算法的協同空戰火力分配[J]. 航空學報，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.

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

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

(責任編輯：孫立華)