基于改進鴿群算法與領航跟隨法的無人車編隊方法

支奕琛，谷玉海，龍伊娜，徐小力

(1.北京信息科技大學現代測控技術教育部重點實驗室，北京 100192；2.北京信息科技大學機電工程學院，北京 100192)

0 前言

由于單個無人車在自主建圖、自主導航等方面的能力有限，很難獨自完成如協作運輸、集群勘探等工作任務，所以近年來多無人車系統協同工作成為行業研究的熱點。無人技術范疇中多無人車協同編隊發揮的作用非常關鍵，如協同反恐、偵查和聯合搜救等，因此多無人車系統編隊成為關鍵的課題。對于多無人車系統編隊來說，無人車在執行任務的過程中需要實現自主協同并形成編隊隊形，同時保持隊形向目標點行進。結合任務具體要求，隊形可以是直線、正方形或者三角形等多種。

路徑規劃是指在有障礙物的環境下向機器人提供從起點到終點途中的道路信息并規劃出一條較優路徑。對于移動機器人，規劃出一條良好的路徑與在路徑上成功避障十分重要，不合適的路徑可能會導致與其他物體碰撞致使機器人損壞或浪費大量時間。Voronoi圖法、遺傳算法、蟻群算法、粒子群算法等都是應用較為廣泛的路徑規劃算法，具有很強的代表性。康冰等人設計禁忌柵格，對螞蟻的線路進行引導、控制，并結合時空數據及時更新調整，獲得了全新的蟻群算法。

結合當前文獻資料，控制多無人車編隊是以虛擬結構法(Virtual-Structure)、基于行為的方法(Behavior-based)、領航-跟隨型法、基于路徑跟蹤的方法、人工勢場法、圖論法等為主。領航-跟隨型編隊控制方法的優勢在于分析難度小，并且更加精準，在多無人車編隊控制中適用性較強。領航-跟隨型編隊控制法中，通常領航者可以是一個，也可以是多個，除此以外都屬于跟隨者。在編隊的過程中，領航者負責選擇最優路徑向目標點前進，并在前進過程實時避障，而跟隨者利用領航者當前的信息調整各自的狀態，實現與領航者保持一定的距離和角度，從而達到編隊效果。

文中編隊是利用改進鴿群算法與領航跟隨法融合實現的。對鴿群算法進行改進，在鴿群算法的前期設置初始解使其初始化，能夠提升算法的效率。另外，在算法的地磁算子中加入相應的權重指標，提升算法在整體路徑中的規劃效率。通過MATLAB進行仿真，結果表明：與PSO算法、量子粒子群優化(Quantum Particle Swarm Optimization,QPSO)算法相比，改進的鴿群算法規劃的路徑及算法運行時間比其他算法更短，驗證了改進鴿群算法的優越性。路徑規劃完成后，通過領航跟隨方法控制無人車編隊，以領航者無人車位置與編隊隊形為依據，完成所有虛擬機器人位置信息的計算；控制所有跟隨者無人車向虛擬機器人運動，使隊形得以實現。

1 鴿群算法

1.1 鴿群行為說明

鴿子是一種十分常見的鳥，世界各地都在廣泛飼養。古時候在沒有手機等智能通信設備的情況下，人們都采用鴿子進行遠程書信交流，鴿子的記憶能力可見一斑。此外，它還是一種依賴習慣的動物，很多鴿子都可以利用一些建筑物或者標記點進行飛行，甚至還可以結合磁場信息、太陽的運動等，以順利達到指定位置。

1.2 鴿群算法

在飛行過程中，鴿群具備非常突出的導航能力以及辨識方向的能力。研究者在對它們進行長時間的研究后，受到啟發，創建了相應的鴿群算法(Pigeon-Inspired Optimization，PIO)。PIO算法重點根據兩個方面形成，即地磁算子、地標算子。不斷地對二者進行迭代處理，可以快速運算得到其中代表性粒子的速度數據，從而明確種群的最優數據。

引進相應的地磁算子。地磁算子迭代更新的方法：以和表示第只鴿子所在的位置和速度。在每輪迭代中，鴿群中的個體都可以用公式(1)(2)計算并更新個體的速度和位置。

()=(-1)e-+[-(-1)]

(1)

()=(-1)+()

(2)

式中：表示地磁算子；表示隨機數；表示當前全局最優位置。

引進相應的地標算子，鴿群按照其當前的分布情況，評估目前的坐標與目的地是否相同。若方位相似或者相同，鴿群繼續前進，直奔最終地點；若相反，則令群體的中心位置為目標，調整自身的行為。在不斷迭代后，種群的規模會下降。以第次迭代為例，地標算子的更新方法如下：

(3)

(4)

()=(-1)+[()-(-1)]

(5)

式中：為第次迭代時種群的數量；()為第次迭代后第只鴿子的位置；[()]為()位置的適應度。

結合地標算子的運算及分析，可以更高效率地確定目標位置，使鴿群更直接、穩定地到達目的地。

2 改進鴿群算法

(1)改進鴿群算法

鴿群算法的不足之處是收斂速率偏低，且局部最優出現率偏高。本文作者在原算法的前提下，在前期設置一個初始解，在進行初步處理后，能夠簡化算法，減少計算時間，從而能夠提高計算效率。同時，在算法的地磁算子中加入相應的權重指標，提升算法在整體路徑中的規劃效率。權重指標的公式為

式中:、分別表示慣性權重系數的最小值和最大值；和分別表示當前鴿群內部適應度的最小值和平均值。

(2)改進鴿群算法路徑規劃流程

改進鴿群算法路徑規劃流程如圖1所示。

圖1 改進鴿群算法路徑規劃流程

3 領航跟隨法編隊控制

多無人車編隊與單無人車進行比較，其優勢主要表現為魯棒性更好、擴展能力更強且更加靈活。以行為為基礎的方法、虛擬結構法和領航跟隨法是多無人車編隊控制法中應用最為廣泛的幾種。其中，領航跟隨法控制方法難度更小且效果更精準、穩定性更強，在多無人車編隊控制中適用性較好。

該控制方法原理：編隊內全部無人車除了領航者都是跟隨者。領航者以地圖信息為依據對最優路徑進行確定并完成避障，將控制指令發送給領航者進而對編隊整體進行控制，跟隨者時刻與領航者保持相應的角度與間距，使隊形得到保證。多無人車編隊完成后，所有無人車都要避障，并且不能與編隊內其他無人車出現碰撞現象。橫縱隊形和三角隊形是目前最常見的編隊，具體如圖2所示。

圖2 常見的多無人車編隊隊形

領航跟隨法有-控制和-控制2種控制模式。-控制方式即每個跟隨者無人車以一定的距離和角度跟隨領航者無人車，從而實現編隊隊形。-控制方式即每個跟隨者無人車以固定的距離跟隨2個領航者無人車。現采用-控制方式，其實現步驟如下：

步驟1，領航者根據地圖信息使用改進鴿群算法進行路徑規劃，規劃出供無人車行駛的最優路徑；

步驟2，領航者無人車沿著最優路徑行駛，并利用避障算法進行避障，同時領航者無人車實時檢測自身的位姿信息，根據使用的隊形用-控制方式生成虛擬機器人的軌跡發送給跟隨者無人車；

步驟3，跟隨者無人車不斷地接收領航者機器人發送的運動控制指令和軌跡，調整自身的速度和運動方向，沿著虛擬機器人的軌跡運動。跟隨者無人車實時探測周圍的環境信息，當遇到障礙物時，在原地等待一段時間，當領航者無人車通過后，跟隨者無人車會行駛至領航者無人車上一時刻的位置，避開障礙物以后，跟隨者恢復原本軌跡，編隊隊形得以恢復。

結合改進鴿群算法和領航跟隨法的編隊方法流程如圖3所示。

圖3 編隊方法流程

4 仿真實驗與結果分析

4.1 路徑規劃仿真

為進一步驗證算法的實際效果，通過MATLAB進行仿真。分析過程中，柵格尺寸確定為20×20。對相應算法進行初始化處理，借助算法獲得整體最優路線。為分析算法的效果，利用PSO算法、QPSO算法進行比較分析。結果如圖4所示。3種算法的收斂結果如圖5所示，數據對比如表1所示。

圖4 3種算法的全局路徑規劃

圖5 3種算法的收斂比較

表1 3種算法的數據比較

由圖4、圖5、表1可以看出：PSO算法和QPSO算法雖然都可以規劃出一條路徑，但是從算法的運行時間、收斂性、路徑長度分析，改進的鴿群算法更具有優越性。

4.2 多無人車編隊仿真

以3個無人車組成三角形隊形為例進行仿真驗證。設定領航者、跟隨者起始位置和目標點位置，領航者與跟隨者在行駛途中沒有遇到障礙物，無人車沿直線從起點行駛至目標點，所有無人車全程保持三角隊形，行駛軌跡如圖6所示。

圖6 無障礙環境下無人車軌跡

在起點與終點的連線上增加一個障礙物，這時領航者無人車遇到障礙物但跟隨者無人車沒有遇到障礙物，當領航者無人車行駛至障礙物前時會避開障礙物行駛至一條新的路徑到達終點，且跟隨者無人車會與領航者無人車保持三角隊形繞開障礙物并運動到目標點，如圖7所示。

圖7 領航者遇到障礙物下的無人車軌跡

當領航者無人車行駛的路線上沒有障礙物但跟隨者無人車行駛路線上出現障礙物，編隊會進行短暫的隊形變換，跟隨者無人車會在障礙物前原地等待一段時間，領航者通過障礙物以后，跟隨者會重復領航者行跡以實現避障，繞過障礙物后跟隨者無人車會返回原虛擬無人車的軌跡上，恢復三角隊形，如圖8所示。

圖8 跟隨者遇到障礙物下的無人車軌跡

當道路只能通過一個無人車時，跟隨者無人車會在障礙物前等待一段時間，當領航者無人車通過狹窄的通道后，跟隨者無人車會輪流運動到領航者的位置，呈縱行隊依次通過狹窄的道路，當所有的無人車通過狹窄的通道后，再恢復至設定的隊形，如圖9所示。

圖9 狹窄環境下無人車路徑軌跡

5 算法實際應用

為進一步驗證該編隊算法的有效性，將其運用到真實的無人車上，實現無人車的編隊控制。

如圖10所示，障礙物位于3臺小車周圍，領航者無人車使用改進鴿群算法規劃出一條直線路徑向前行駛，運用領航跟隨法進行編隊控制使后面兩輛跟隨者無人車以一定的距離和角度跟隨領航者無人車以三角隊形從起點運動到終點。

圖10 無障礙環境下的編隊過程

如圖11(a)所示，在路徑的起點和終點設置一個障礙物，領航者遇到障礙物，而跟隨者未遇到，領航者小車會重新規劃出一條路徑繞開障礙物，此時跟隨者小車依舊會與領航者小車保持隊形繞開障礙物，并到達終點，過程如圖11(b)—(e)所示。

圖11 領航者遇到障礙物時的編隊過程

如圖12(a)所示，領航者無人車行駛路徑上沒有出現障礙物，但是跟隨者無人車行駛的路徑上出現障礙物，此時會進行短暫的編隊隊形變換，跟隨者無人車在障礙物前等待一段時間，等待領航者無人車通過障礙物后，跟隨者小車運動到領航者小車上一時刻的位置從而繞過障礙物，跟隨者小車繞過障礙物后，恢復三角隊形到達終點，過程如圖12(b)—(h)所示。

圖12 跟隨者遇到障礙物時的編隊過程

如圖13(a)所示，當無人車編隊通過狹窄道路環境只能通過一輛無人車時，跟隨者無人車會在障礙物前等待一段時間，等待領航者無人車通過狹窄通道，跟隨者小車依次運動到領航者位置，呈一字形隊形或縱行隊形通過狹窄通道，全部無人車都順利從狹窄的通道通過以后，隊形恢復并向終點行進，具體如圖13(b)—(e)所示。

圖13 存在狹窄環境下的編隊過程

6 結語

本文作者將鴿群算法和領航跟隨者算法相結合，通過引進相應的權重系數對鴿群算法進行改進。在仿真中，改進的鴿群算法規劃的路徑和運行時間比其他算法更短，驗證了改進鴿群算法的優越性。領航跟隨者算法在隊形保持、隊形變換方面都十分出色，多無人車編隊在并未遇到障礙物的情況下，能夠以最初編隊隊形一直向目標點行進，如果中途有障礙物存在或者路徑過于狹窄，編隊隊形會適當變化以順利通過或者避開障礙物，當所有的無人車通過狹窄環境或避開障礙物時，多無人車編隊又會恢復設定的隊形繼續運動到終點。結果表明：所提編隊方法可以控制多無人車以一定的隊形有效地從起點行駛至目標點，并可以成功地避開障礙物和通過狹窄環境，該編隊方法可靠、有效。研究結果為多無人車編隊提供了參考。