基于改進麻雀搜索算法的無人機集群置信傳播協(xié)同定位方法

熊 智，李欣童，熊 駿，陳明星，劉建業(yè)

(1. 南京航空航天大學自動化學院導航研究中心，南京 211106； 2. 先進飛行器導航、控制與健康管理工業(yè)和信息化部重點實驗室，南京 211106)

近年來，無人機飛行任務已經(jīng)從單一無人機向集群無人機的方向發(fā)展，無人機集群通過信息的相互合作與傳輸，執(zhí)行多個無人機的特殊編隊任務[1]。它不是簡單意義上“量”的增加，而是在智能上有“質(zhì)”的突破，具備在復雜動態(tài)環(huán)境下能實現(xiàn)大規(guī)模自主性的集群協(xié)同效應的能力，有著任務分散化、分布式智能化、去中心自主化等潛在價值。

無人機任務執(zhí)行中需要高精度定位信息，在近距離編隊飛行系統(tǒng)中，無人機需要準確、實時的定位信息來進行避碰、任務調(diào)度和精確控制[2][3]。受成本與無人機機載的約束，只有少量無人機能攜帶高性能傳感器[4]。針對大規(guī)模集群無人機的定位精度問題，國內(nèi)外學者對協(xié)同定位算法進行了探究。與傳統(tǒng)的僅依賴單個無人機傳感器的多源融合方法相比，協(xié)同定位充分利用了協(xié)同網(wǎng)絡中所有節(jié)點之間的幾何關系和所有機載傳感器的觀測數(shù)據(jù)[5,6]。文獻[7]針對非線性模型，設計了一種動態(tài)非參數(shù)置信傳播算法獲得無人機位置信息，但計算量較大，只對二維空間進行了仿真，不適合大規(guī)模集群無人機使用。文獻[8]提出了一種基于相對位置估計和置信傳播的協(xié)同定位框架。利用消息傳遞算法的優(yōu)勢結(jié)合卡爾曼濾波，實現(xiàn)低成本近距無人機編隊協(xié)同定位。

實時性是集群無人機協(xié)同定位的一項技術痛點，網(wǎng)絡中存在大量過剩冗余的協(xié)同信息，對定位精度貢獻度不高，導致計算負荷大且無法滿足精度及實時性需求。如何對節(jié)點的協(xié)同信息進行篩選，找到穩(wěn)定可靠的信源無人機是集群無人機中需要解決的難題。集群的協(xié)同精度不僅與自身的傳感器設備有關，還與飛行構型有關，構型的優(yōu)劣可以用幾何精度因子（GDOP）量化，GDOP 越小，對集群定位就越有利。文獻[9]分析了節(jié)點數(shù)量和傳感器精度對無線傳感器網(wǎng)絡定位精度的影響，提出了定位精度下限的計算方法。文獻[10]使用無人車輔助無人機的導航，無人車位置設計用于減少無人車和無人機之間的GDOP，仿真結(jié)果顯示大幅降低了無人機的定位誤差。因此對集群無人機導航中的信源節(jié)點進行篩選，可以簡化協(xié)同定位算法的過程。麻雀搜索算法（Sparrow Search Algortihm, SSA）是2020 年由shen 提出的一種最新的群智優(yōu)化算法，比傳統(tǒng)的優(yōu)化算法具有精度高，穩(wěn)定性好等特點[11]，常用于處理非線性復雜系統(tǒng)的優(yōu)化問題，適用于集群編隊這類實時性要求高的應用場景。將SSA 算法應用到信源無人機的篩選中，利用GDOP作為篩選標準，可以選擇出最優(yōu)的組合方式。因此研究基于SSA 優(yōu)化的無人機集群協(xié)同定位方法，從而提高導航系統(tǒng)性能，具有重要的研究意義。

本文提出了一種基于改進SSA 的無人機集群置信傳播（Belief Propagation, BP）協(xié)同定位方法，利用BP 框架不斷進行信息更新推斷，在無人機進行信息交互時，提出了以GDOP 值為適應度函數(shù)的改進SSA，尋優(yōu)得到最優(yōu)幾何構型，與該最優(yōu)構型中的無人機進行信息交互，從而實現(xiàn)了對低貢獻度信息的排除和篩選，在確保精度的基礎上減少計算量，最終仿真驗證本方法的有效性。

1 集群無人機置信傳播協(xié)同定位方法

假設有N架無人機，無人機i從0 時刻到t時刻的所有狀態(tài)信息量觀測量包括衛(wèi)星和相鄰無人機的相對測距信息。假設具有一階馬爾可夫性，即根據(jù)貝葉斯定理，預測和更新過程為

式(1)為預測過程，t時刻之前所有觀測量式(2)為更新過程，通過t時刻獲得的最新觀測信息按照式(2)更新。初始化條件為因此可得后驗概率分布為

通過式(3)構建因子圖，進而采用置信傳播算法求解。無人機群定位問題通過因子圖模型的形式進行建模，即可求得任一節(jié)點的狀態(tài)，協(xié)同定位問題即為計算t時刻前機載導航信息和觀測信息的后驗概率分布，即位置置信度(Positional Belief, PB)：

根據(jù)集群協(xié)同定位的特征，將與變量有關的因子分為預測因子和修正因子。其中修正因子包含兩類：自身觀測信息,iselfz和與鄰節(jié)點相互觀測信息(j屬于i節(jié)點的一個鄰節(jié)點)。由此建立無人機集群協(xié)同定位過程的因子圖模型[12]。如圖1 為BP 圖模型推理。

圖1 編隊無人機協(xié)同定位因子圖Fig.1 FG of swarm UAVs localization system

結(jié)合集群無人機的實際情況，給出下列合理假設：

① 所有無人機的初始位置信息和狀態(tài)信息更

新過程是相互獨立：

③ 無人機自身的觀測信息在不同時刻相互獨立的，且只和無人機當前時刻以及前一時刻的狀態(tài)有關：

④ 第i架無人機的自身觀測量只和它自身的狀態(tài)量有關，即不同無人機之間的自身觀測量是相互獨立的；并且相鄰無人機之間的相對觀測信息是條件獨立的：

基于以上假設，結(jié)合式(3)任一時刻協(xié)同網(wǎng)絡中后驗概率分布可分解為式(10)[8]。

結(jié)合圖1 和式(10)可以進一步進行因式分解，最終對BP 進行最小均方誤差估計，具體算法執(zhí)行步驟將在2.5 節(jié)詳述。由式(11)和式(12)可以看出，協(xié)同信息和BP 的連續(xù)乘積帶來了大量計算負荷，而節(jié)點i流入的協(xié)同信息越多，對狀態(tài)節(jié)點也會有著更好的估計效果。但協(xié)同信息越多，相應的計算量就越大，因此需要排除低貢獻度信息，對協(xié)同信息進行篩選，簡化協(xié)同定位算法的過程，本文提出了一種改進的麻雀搜索算法平衡計算量與精度的問題。

2 改進的麻雀搜索算法

2.1 麻雀搜索算法

SSA 算法模擬麻雀尋找食物的過程就是尋優(yōu)的過程，其種群表示如下：

其中，S為麻雀種群矩陣，sF為適應度值矩陣，ns代表第n只麻雀，即指代第n種無人機的組合方式，為麻雀算法中一只麻雀的一維數(shù)組，d是變量的維數(shù)，為第n只麻雀的適應度值，即第n種組合方式的GDOP 值。計算每一只麻雀適應度if，選出當前最優(yōu)值bf和其對應的無人機組合方式以及當前最劣的適應度值wf和其對應無人機組合方式

麻雀覓食過程可定義為發(fā)現(xiàn)者-加入者模型，并加入警戒者機制。按照各自的規(guī)則進行迭代，位置更新方程分別如下:

其中iter為迭代次數(shù)，為第j個麻雀在第k維的無人機編號，α和Q為隨機數(shù)，L是一個一行多維的全一矩陣，R2∈[0,1]和ST∈[0.5,1]分別為預警值和安全值。當預警值小于安全值時搜索環(huán)境安全，發(fā)現(xiàn)者可廣泛搜索，帶領種群獲得更高的適應度值；當預警值大于安全值表示麻雀遇到了捕食者，迅速調(diào)整策略飛向安全區(qū)。

χ和K為隨機數(shù)；當fj＞fb為警戒者位于種群邊緣，處于危險狀態(tài)；fj=fb為警戒者處于種群中間意識到危險，需要趨向其他麻雀群。

2.2 適應度函數(shù)

本文假設測距誤差為零均值高斯分布，無人機集群保持時鐘同步，測距值如下形式：

上標e表示地心地固ECEF 坐標系，對式(17)進行泰勒展開并保留一階項，得到可拓展如下形式：

Hi為方向余弦矩陣，載體位置偏差的誤差協(xié)方差為，σ2為測距誤差的方差，GDOP就被定義為的跡的平方根。

2.3 改進麻雀搜索算法

標準的麻雀搜索算法中，因為大多數(shù)智能算法的初始值都由隨機數(shù)產(chǎn)生，會使數(shù)值遠離最優(yōu)值，影響最終效果；并且種群會在中后期無法跳出局部最優(yōu)，本章采取混沌初始化和自適應t 分布變異兩種改進方式，避免傳統(tǒng)麻雀搜索算法陷入局部最優(yōu)，提高搜索能力。

2.3.1 混沌初始化

混沌是指在確定性動力學系統(tǒng)中表現(xiàn)出的不可預測的、類似隨機性的運動，具有隨機性、規(guī)律性、在一定范圍內(nèi)不重復遍歷等特點。Tent Map混沌模型為經(jīng)典的混沌模型，其Tent 映射表達式如下：

其中Gk+1、Gk為k+1 和k時刻的狀態(tài)值，為映射參數(shù)。如圖2 所示，藍色圓圈和紅色星號分別代表了混沌模型和隨機數(shù)產(chǎn)生的初值結(jié)果。隨機數(shù)在橢圓框中取值集中，而在矩形框中基本沒有取值，因此采用Tent Map 混沌模型代替隨機數(shù)初始化，不僅保持種群的多樣性和覆蓋性，而且使得算法脫離局部最優(yōu)值，有更強的全局搜索能力[13]。本文利用混沌初始化模型更新發(fā)現(xiàn)者、追隨者、警戒者。

圖2 混沌模型與隨機數(shù)初始化對比Fig.2 Comparison of chaos model and random number initialization

2.3.2 自適應t 分布變異

設定變異閾值，當小于閾值時，進行自適應t 分布變異，定義如下：

2.4 算法步驟

綜上所述，基于改進SSA 的BP 無人機集群協(xié)同定位算法流程如圖3 所示。

圖3 算法流程圖Fig.3 Flowchart of algorithms

步驟1：初始化所有節(jié)點的位置，混沌初始化SSA算法；

步驟5：回到步驟3 進行迭代，確保高精度位置信息通過BP 送達到集群中每架無人機，直到位置置信度收斂；

步驟6：對后驗位置信息，即位置PB 求均值得到對應無人機狀態(tài)信息的最小均方誤差估計，且成為下一時刻t+1 時刻的信息初始值。

3 仿真分析

3.1 仿真條件設置

設置如下仿真環(huán)境：以搭載高精度傳感器的長機為中心，100 m 范圍內(nèi)隨機生成30 架僚機，如圖4(a)所示。長機僚機飛行軌跡如圖4(b)所示。所有無人機搭載測距范圍為60 m 的UWB 模塊，考慮無人機軸距及荷載等原因，將相鄰無人機之間的安全距離設為6 m，每一架僚機選擇與相鄰五架無人機信息協(xié)同信息的交互。表1 為無人機機載傳感器參數(shù)配置，量測噪聲均設置為高斯噪聲。

圖4 仿真場景和飛行軌跡Fig.4 Simulation scenario and trajectory

表1 傳感器參數(shù)配置Tab.1 Sensor parameters configuration

3.2 仿真結(jié)果與分析

首先探究改進麻雀搜索算法性能。種群規(guī)模設為N= 20，迭代次數(shù)為200，發(fā)現(xiàn)者個數(shù)和警戒者麻雀個數(shù)均取種群規(guī)模的20%。選擇某時刻無人機i的GDOP，并與原始粒子群算法、原始麻雀搜索算法和改進粒子群算法適應度值進行對比，適應度值對比曲線結(jié)果如圖5 所示。

圖5 算法收斂曲線Fig.5 Algorithm convergence curve

圖中經(jīng)典算法粒子群和改進粒子群算法過早陷入了局部最優(yōu)解，原始麻雀搜索算法在55 次迭代后收斂精度優(yōu)于前兩種算法。本文的改進麻雀搜索算法收斂速度和收斂精度優(yōu)于任何對比算法。

采用本文的改進SSA 優(yōu)化的BP 算法，隨機選取集群系統(tǒng)中兩架僚機進行定位精度的分析，圖6 給出了如下所示的三種不同算法下僚機在地球坐標系下三個坐標方向上的定位誤差對比曲線。

① 本文算法：本文提出的改進麻雀搜索算法優(yōu)化的置信傳播無人機集群協(xié)同定位算法；

② BP 協(xié)同：文獻[8]中提出的協(xié)同導航方法；

③ 無協(xié)同：僚機采用低精度的INS/GPS 系統(tǒng)進行松組合導航，長僚機之間不進行信息交互。

圖6 表明，低性能僚機采用本文算法協(xié)同定位方法，極大提高了僚機的定位誤差精度，誤差曲線明顯優(yōu)于其余兩種對比方法。并且進一步對三種算法僚機的定位誤差精度進行定量的分析，對該無人機定位均方根誤差(RMSE)和精確率（Accuracy）進行了統(tǒng)計，精確率定義為結(jié)果如表2 所示。

根據(jù)圖6 和表2 所示的結(jié)果，本文算法具有較小的RMSE 誤差和較精確的估計精度，與原始BP 算法相比，估計更加穩(wěn)定和準確。根據(jù)定義中的可以推斷出經(jīng)過改進SSA 算法優(yōu)化后，最優(yōu)的GDOP值使得協(xié)同信息提高了對僚機定位的貢獻度。

圖6 定位誤差對比曲線Fig.6 Comparison on position errors

表2 定位誤差統(tǒng)計結(jié)果Tab.2 Statistics of position error

為了將提出的協(xié)同定位框架與其他框架進行比較，無人機定位估計誤差的計算公式如式(23)所示。

為了體現(xiàn)集群中僚機的整體表現(xiàn)，采用誤差累積分布函數(shù)(CDF)，對比不同方法編隊飛行中的所有僚機的定位誤差。如圖7 顯示了累積分布三種方法的CDF，并與長機進行比較。

由圖7 可以看出，本文所提出的方法的定位精度是最為接近長機定位精度的，并且優(yōu)于原始BP 算法。例如，集群中無協(xié)同定位只有0.3%的定位誤差小于0.5 m，但本文所提出的方法可將該比例提高到97.1%，略低于高精度長機（98.9%），高于原始BP（81.9%）。

圖7 定位誤差累積分布比較Fig.7 CDF comparison of positioning errors

本文算法對定位估計精度進行了優(yōu)化，針對本文方法的復雜度進行進一步的分析。對上述方法的算法效率進行了對比，并設置了對照組：隨機選擇五條協(xié)同信息CM，與本文算法進行精度上和效率上的對比。利用Matlab 的‘tic’和‘toc’函數(shù)獲得記錄每個周期代碼的運行時間，用來表示算法框架的計算負載。結(jié)果如圖8 所示。

圖8 定位誤差與處理時間對比Fig.8 Comparison of positioning error and processing time

圖8 表示，本文算法計算負載遠小于原始BP 算法，每個周期的時間提升為原始BP 的2.8 倍。與對照組相比在計算量上二者較為近似，在定位精度上優(yōu)于對照組，驗證了本文方法的有效性，簡化了協(xié)同定位算法過程的計算復雜度，提升了僚機的整體導航性能。

4 結(jié) 論

針對無人機集群協(xié)同導航的問題，本文提出利用改進SSA 算法優(yōu)化的BP 算法，對基本的麻雀搜索算法進行混沌初始化和自適應變異改進，增加探索能力和種群多樣性，并驗證了收斂性和精度。并且研究了基于因子圖的集群無人機編隊協(xié)同定位模型，將無人機定位問題轉(zhuǎn)化為求解后驗概率分布問題。仿真結(jié)果表明，改進的麻雀搜索算法收斂速度和精度優(yōu)于所有對比算法。本文協(xié)同定位框架能夠提升集群中整體僚機定位精度，優(yōu)于原始BP 算法，既解決了計算量大的問題，又提高了協(xié)同導航性能，在保證精度的基礎上簡化了計算量，且不依賴高精度傳感器，降低了成本，實現(xiàn)了無人機集群的高精度實時協(xié)同定位。