蟻群算法在無人機物流路徑規劃中的應用

何光勤，黃鑫

（中國民用航空飛行學院，廣漢 618307）

0 引言

相對于傳統的地面交通運輸，航空運輸更加快捷；而在航空運輸中無人機又擁有不可代替的優點。無人機運輸相對于傳統的航空運輸，其所需要的地面基礎設施少，并能在一些偏遠區域用較少時間進行運輸。無人機的操作也更加簡單智能，能夠自由調度，且運行成本低。在短距離運輸，特別是特大型城市的區間物流或基礎設施落后的山區，無人機運輸方式能使物品運輸更加高效便捷，這是其它的運輸方式不能做到的［1］。

最近幾年國內外對無人機物流問題已經進行了大量的研究，研究較多的還是無人機避障飛行路徑研究。無人機避障研究主要是周圍地形環境危險源研究與最優飛行路線研究兩方面。趙嶷飛等人［2］通過對無人機的起降、巡航等狀態的研究，建立了參數化的垂直速度剖面的模型，然后將退火順發與粒子群算法用于任務剖面優化。李憲強等人［3］為避免無人機三維航跡規劃過程中，蟻群算法陷入局部最優解，引入了人工勢場算法對蟻群算法的狀態轉移函數進行優化。仇鈞正［4］提出一中在有雷達與武器威脅的環境下，將預測控制模型與社群蜘蛛算法相結合的無人機動態路徑規劃方案。黃龍楊等人［5］通過對蟻群算法原理和模型的分析，對算法狀態轉移函數更新規則進行改進，引入調節信息素的因子，最后使用改進后的蟻群算法對二維柵格環境模型進行航跡仿真［5］。沈培志等人［6］通過無人機路徑規劃的研究分析，提出了多不同價值目標與多危險源下的無人機飛行決策模型。張宏宏等人［7］針對無人機運行環境安全系數低的情況，對環境模型進行風險評估，再將安全系數作為綜合代價，最后改進一群算法對三維空間進行路徑規劃［7］。揭東等人［8］在無人機沖突模型中加入角度與速度改變的調度策略，使用改進一起拿算法對多機解脫進行路徑規劃。吳成振等人［9］通過構造無人機定位誤差模型，利用貪心算法對無人機二維路徑快速規劃。

本文將在蟻群算法基礎上，對模型中的信息素揮發進行自適應調整，通過多次迭代使信息素揮發系數降低，直至其保持在合理范圍內。然后將改進后的算法應用到無人機物流航跡規劃中，并通過MATLAB軟件完成仿真實驗，最后輸出無人機二維航跡的優化解。

1 問題描述

2019年杭州已經有物流科技公司開展關于無人機物流運行場景的測試飛行。2020年，民航局召開無人機在低空運行的相關的規則標準與法規的立項開題評審會。伴隨著社會快速的發展，低空空域的開放以及相關制度規則的完善，無人機路徑規劃將在實際生活中的運用越來越多。

在實際應用中無人機物流路徑規劃問題就是怎樣在高樓大廈密集的城市給無人機規劃一條安全飛行路線，在起始地與目的地之間找到最優路徑。在模型中無人機路徑規劃就是在已經建立的二維避障環境中，通過算法找到一條不與任何障礙物相交的最優路徑。

本文的無人機路徑規劃主要由兩步構成：第一步構建包含有障礙物區的區域和自由移動的環境模型；第二步在建立的環境地圖模型上采用改進蟻群算法進行路徑搜索，找到最優路徑。關于環境模型，本文采用了柵格法。柵格法通過自由柵格與障礙物柵格能夠描繪無人機的工作環境。同時柵格法還能夠實現空間與時間的消耗最優。關于路徑搜索，本文采用了改進蟻群算法。

2 改進蟻群算法

2.1 算法描述

近幾十年，學者對生物在自然界生存時所表現出來的智能行為進行了研究與模擬，提出了各種智能算法，例如粒子群算法、蟻群算法、魚群算法、菌群優化算法、人工蜂群算法等。其中蟻群算法就是科學家對自然界螞蟻的種群生物習性進行觀察研究，提出的一種自啟發式算法。蟻群算法具有自然界螞蟻選擇路徑時的隨機性和路徑上信息素的揮發機制。螞蟻通過路徑上的信息素進行正反饋信息交流，從無序狀態轉換到有序狀態。路徑規劃就是人工蟻群對自然界蟻群尋找食物源的活動進行的模仿。

在算法中的人工螞蟻都是獨立個體，可以通過信息素進行信息交流與協作。在剛開始時每只人工螞蟻帶著相同的任務目標，以局部移動的方式獨立地隨機地朝各方向出發尋找食物。過一段時間之后，人工螞蟻會在走過的路徑上留下信息素，信息素會隨著時間的推移而揮發。之后的人工螞蟻會根據通過路徑節點上的信息素的狀態來進行信息交流與協作，以便從一種離散狀態轉移到另一種離散狀態量。當人工螞蟻的數量足夠多的時候，相互協作的蟻群就能構造出路徑規劃的最優解。

蟻群算法設計中，將m只人工螞蟻投放到起點，進行路徑探索。剛開始時節點i到節點j的路徑上信息素τij(0)=c（c為常數）。隨著人工螞蟻的路過，路徑上的信息素將會發生改變。第k只人工螞蟻將根據路徑上的信息素τij()t與啟發式信息（從節點i到節點j路徑距離倒數）ηij()t，在下一步可以選擇的點集合J k()t中，獨立地選擇下一個節點。其中，α、β分別表示信息素和啟發信息的相對重要程度。綜上，人工螞蟻選擇先下一個節點的概率pkij(t)為：

隨著時間的推移，算法中信息素將會像自然界的信息素一樣，揮發掉一部分。算法將通過對路徑上信息素的更新來實現這一點。路徑上信息素的狀態信息，將由路徑上的信息素蒸發系數與本次迭代中路徑節點中信息素增量△τij表示。

當求解的問題規模比較大時，蟻群算法在進行計算的過程中存在搜索時間較長和在路徑的搜索過程中易于陷入停滯的現象。原因是蟻群算法在模仿信息素的揮發系數時，設置的是固定的數值。當信息素揮發系數設置過大時，算法的全局搜索能力會降低；當信息素揮發系數設置過小時，算法的收斂速度將會降低。通過探尋算法的全局搜索能力與收斂速度之間的平衡點，本文提出了在蟻群算法信息素揮發機制的基礎上進行改進的解決辦法。在數學模型上對基礎蟻群算法的信息素揮發系數進行自適應的調整，使信息素的揮發系數在每次迭代之后在一定范圍內變化，而不是一個固定常數。通過對信息素揮發系數的自適應調整，可以提高算法在路徑搜索的時間效率和求解精度。

一些從未被搜索到的路徑由于信息素的揮發系數的存在，可能會使路徑上的信息素將有保持為0，進而降低算法的全局搜索能力，且容易使蟻群算法限于停滯。當信息素的揮發值過大時，使得算法人工蟻群選擇此條路徑的概率會過大，此時算法的收斂速度將會降低。通過自適應的改變ρ值

將信息素揮發值ρ限制在一定的范圍內，并隨著時間的推移ρ值可以自適應的發生改變，以避免以固定不變的去更新路徑上信息素的量和選擇每條路徑的概率，同時提高算法的收斂速度。ρmin可以保證信息素的揮發不會過小，而使算法在路徑搜索過程中陷入停滯。

2.2 改進蟻群算法實現

將改進的蟻群算法運用于路徑規劃，主要分為4步：①用柵格法建立二維環境模型。②將參數初始化。③構建問題的解。④求解。改進蟻群算法流程如圖1所示。

圖1 改進群算法流程

3 仿真研究結果

為驗證改進后蟻群算法在無人機路徑規劃上的求解性能，本節以MATLAB為仿真平臺，進行兩次仿真驗證。仿真平臺為MATLAB，設置20×20的二維柵格圖，黑色區域設置為環境障礙物，人工蟻群起點為（0，20），目的地為（20，0）。圖2（a）為傳統蟻群算法的無人機路徑仿真圖，圖2（b）為傳統蟻群算法在搜索路徑時的收斂曲線，在迭代了45次后蟻群找到了最短路徑，路徑長度為30。圖3（a）為改進蟻群算法的無人機路徑仿真圖，圖3（b）為改進蟻群算法在搜索路徑時的收斂曲線，在迭代了16次之后蟻群找到最短路徑，最短路徑長度為30。

圖2 傳統蟻群算法的無人機路徑仿真（續）

圖2 傳統蟻群算法的無人機路徑仿真

圖3 改進蟻群算法的無人機路徑仿真

4 仿真研究結果

本文研究了改進后蟻群算法在無人機在物流配送中二維航跡中的規劃。通過對傳統的模仿自然界蟻群尋找食物時在路上留下一定量的信息素的蟻群算法進行改造，使路徑上的信息素自適應的調整，每次迭代后信息素的揮發系數在規定的范圍內進行調整，防止路徑上的信息素過高或者過低。仿真結果表明運用改進后蟻群算法在對路徑進行全局搜索時擁有更高的效率，在較少的時間內就能找到最短路徑。無人機在實際運行中是在三維環境中運行，后續的研究將會著重于三維地形研究。