多無人機的路徑規劃算法

劉浩 李劍鋒 曾達

摘要：考慮到多無人機可在數據采集時可在傳感器圓周邊界進行的情形，將此場景視為一種組合優化問題，該無人機的路徑應用問題具有較大解空間特點，在路徑規劃問題中的經典的算法（如n-splitour、RA、APF等算法）無法進行多無人機無交叉路徑優化，為此本文以n-splitour算法獲得n條無人機最短路徑并設計消除n條無人機路徑之間存在交叉可能的方法，同時尋求局部尋優，再通過設計對局部優化方法以確定每個傳感器圓周邊界訪問點的位置，從而可以高效地獲取多個無人機的規劃路徑解。最后通過仿真實驗驗證了所設計的多無人機路徑規劃算法能較為良好地解決多無人機在傳感器下數據采集中的路徑規劃問題。

引言

從目前實際應用分析，無人機數據采集是無人機無線網絡中最重要的工作任務之一。傳統的無人機數據采集模式首先依賴于各個傳感器的實際地理位置進行，無人機數據的傳輸和收集得貼近傳感器，才能完成所需數據的傳輸。

而在實際無人機工作的場景中，經常會存在如下因素影響無人機感知數據的采集：

1） 對于大量且范圍廣的目標監控應用，通過隨機噴灑的方式部署傳感器節點可能本身就會形成一個非完全連通的傳感器網絡;

2） 由于傳感器的實際位置限制、無人機和傳感器能量損耗過快、航飛時風速過大等原因，無人機可能無法按時到達或根本無法到達傳感器所在位置，從而影響實時的數據采集工作;

3）各無人機在訪問傳感器時，可能會因為自身能耗限制，導致同一傳感器數據頻繁轉發采集，會造成非必要的數據重復或滯后，就會造成數據采集中的實時性和有效性。

針對上述問題，本文主要研究，如何獲得多無人機在多傳感器數據采集工作任務中的最短路徑，從而降低傳感器中的數據采集延遲或者失效及無人機航飛時的能耗的問題。在充分研究了傳感器節點在傳送數據時確實有有效的數據傳輸范圍之后，本文研究的問題可理解為帶有圓形鄰域（傳感器節點的數據有效傳輸近似范圍）且相鄰數據傳輸范圍可相互覆蓋的旅行商問題，目前該問題已經被證明為APX-Hard。在實際無人機應用之中，由于傳感器的數目非常多，且所在地域較為遼闊，所以該問題的解決和優化就顯得更為重要。

本文的數據采集路徑規劃問題研究是基于多無人機且航飛路徑端點設在傳感器數據傳輸范圍的圓周邊界上的節點路徑規劃的問題，該優化問題具有解空間大難于求解優化的特點，經典的n-splitour等算法無法進行多無人機路徑優化，而且較大概率會產生交叉的無人機低效的路徑解，對此本研究首先利用n-splitour算法得到n條無人機路徑，并設計了順序交換的局部尋優方法，再通過設計多無人機算法確定每個傳感器數據傳輸圓形范圍上訪問點的位置以達到對其多無人機路徑規劃的局部尋優，從而可以高效地獲取近似最優的多無人機的規劃路徑的解。

1 多無人機路徑的問題描述

假設在實際工作平面上放置了n個傳感器節點，其中表示第1至n個傳感器的所在地理位置，其數據通信范圍是一個標準圓形的區域，R表示對應的數據通信半徑，其中Lbase-station表示基站（無人機初始位置）位置，Rbase-station=0。現假設有x個無人機分別由基站出發，每個無人機則會根據自己所分配規劃完成的航飛路徑依次經過所在路徑下的傳感器節點的圓形通信范圍，完成數據采集后將再次回到基站，記第p個無人機需要訪問的傳感器節點數目為mp。將第p條無人機路徑第一次進入到路徑上第q個傳感器節點的通信范圍的位置稱為節點q上的數據采集點，記作。在各種可能的無人機路徑規劃方案中，讓每一個無人機路徑長度中最大的取值最小，減少無人機的路徑遍歷時間，從而降低數據采集的航飛路徑時間損耗。多無人機路徑規劃問題的公式就可表示為：

上式中，d（x，y）表示x與y兩點間的距離。

2.多無人機路徑規劃近似算法

多無人機路徑如何指派以及各個無人機訪問點的位置及順序等如何確定均需要優化。為此將上述問題分解為兩個步驟求解：第一步是基于n-splitour解決多個無人機的航飛路徑指派問題，并設計出無交叉路徑的局部尋優方法，第二步是提出了梯度下降搜索算法解決訪問點的位置優化問題，具體多無人機路徑規劃算法的設計步驟和分析如下。

2.1?n個無人機路徑指派問題的求解

通過對n-splitour算法的研究可發現，每一條無人機路徑的開始路勁和結束路勁，可能與自身規劃路徑之前的路勁發生邊邊相交關系。但是依據三角不等式，在TSP問題中最優解的路徑是一定不會存在相交邊的情況，為此設計交換的方法（TSP問題中2opt或3opt算法）對無人機路徑去除邊與邊相交的情況，從而更進一步縮短每個無人機路徑的長度，則可達到局部尋優的效果。具體設計的分為以下四步如下：

1使用現有TSP算法尋找到一條無人機航飛TSP回路;2采用n-splitour算法得到n個無人機的航飛路徑;3檢測各個無人機路徑中的起始邊及結束邊產生的自相交;4若3）檢測到有自相交，則消除各個無人機路徑中的起始邊及結束邊產生的自相交。

2.2?訪問點位置的優化

由上述算法可以得到每一個無人機航飛的路徑的解，但還需要確定無人機路徑上在傳感器數據傳輸范圍上即圓周邊界上的訪問點的位置。由于無人機所在的訪問點要求在傳感器通信圓周上。在尋找最短路徑上，每一個無人機的訪問點將對應的θ的取值范圍，可以由[0，2π]縮小到由該傳感器數據傳輸圓周到下一個傳感器數據傳輸圓周的兩條外切線所包圍的區間。

為了壓縮搜索范圍，提高求解效率。如下圖所示考慮無人機通過A、B兩個傳感器的情形，無人機從基站出發，依次訪問傳感器A、B后，再回到基站。傳感器A上訪問點的可行取值區域位于弧A1A2內側，與弧A3A4內側的交集部分即弧A2A3內側之間，同理傳感器B上的可行區域在弧B1B3內側之間。對于有多個傳感器節點的情形，每個傳感器節點對應弧段的起始范圍可用近似的方法計算得到。

3?算法仿真

為了驗證本文所提出的多無人機路徑規劃模型的合理性及其優化求解算法的正確性，進行了如下仿真實驗。計算機的硬件平臺為英特爾處理器i7-9750H 2.6GHz，8GB內存，其軟件平臺為Matlab2018b。仿真實驗在長寬各500的區域內隨機拋灑100個傳感器節點。實驗隨機生成了1000個樣本，統計結果見表1，其中計算時間為各次計算的均值。通過實驗結果，在ρ=π/40時可取得最短的平均長度，在ρ=π/20時雖與前者的平均長度接近，但相對前者計算時間有了明顯減少。

下圖顯示了一個采用了3個無人機進行路徑規劃，傳感器節點通信范圍是均勻分布場景下的路徑規劃實例圖。

4結論

本文將實際應用場景的多無人機航飛數據采集中的路徑規劃問題建模為路徑端點在傳感器通信圓周之上的組合優化問題，并設計了求解的近似算法，驗證了多無人機路徑規劃模型的合理性及其優化求解算法的正確性，

參考文獻：

[1]Gupta L.， Jain R.， Vaszkun G. 無人機通信網絡中關鍵技術研究進展[J]。通信學報，2016，35（2）：457-461。

[2]Maurice K.，Joseph A.，Chadi A. 無人機輔助車輛網絡建模與性能分析[J]。汽車工程學報，2019，38（9）：889 - 898。

基金號：南寧理工學院2019年度校級科研項目+基于無人機在無線傳感網數據采集中的路徑規劃研究+KY200901;

2020年廣西高校中青年教師科研基礎能力提升項目+5050KY58011。

作者簡介：劉浩（1990-），男，漢族，廣西桂林人，桂林理工大學碩士，講師，研究方向：計算智能