無人機叢集——航跡規劃你不知道的各種演算法優缺點

我們都知道無人機（UAV ）因具有可探測性低、造價低廉、不懼傷亡、起降簡單、操作靈活、系統配置多樣化、自動控制智慧化等特點，因而在未來一體化聯合作戰中扮演越來越重要的角色。然而早期的無人機都是按照地面任務規劃中心預先計算並設定好的航跡飛行，但是隨著無人機所承擔的任務越來越複雜，其飛行環境的不確定性，對航跡規劃的要求也將越來越高。

無人機航跡規劃的主要根據任務目標規劃滿足約束條件的飛行軌跡，是無人機先進任務規劃系統的關鍵組成部分。航跡規劃的目的是根據預設數字地圖，透過GPS/INS組合導航系統，在適當時間內計算出最優或次最優的飛行軌跡。考慮到數字地圖誤差及隨機環境的影響（ 如隨機風場等），要求無人機在飛行過程中具有動態修正軌跡的能力，能迴避敵方威脅環境，安全地完成預定任務。無人機航跡規劃。主要包括環境資訊（ 如隨機風場、敵方雷達掃描半徑範圍、及導彈高炮打擊威脅區、地形因素）、無人機系統約束、航跡規劃器、無人機自動駕駛儀等。航跡規劃總框架圖如圖1所示：

航跡總框圖如圖1所示

再者，根據執行任務”飛機效能的不同，航跡規劃可以分為攻擊無人機航跡規劃及偵察無人機航跡規劃；根據規模的不同，可以分為單機及多機協同編隊航跡規劃；根據飛行過程的不同，可以分為爬升航跡規劃、著陸航跡規劃、及巡航航跡規劃；根據飛行環境的不同，可以分為確定環境及不確定環境航跡規劃。此外，按照實現功能可以劃分為離線靜態航跡預規劃及線上動態實時航跡規劃。其演算法可分可行性方向演算法、通用動態演算法及實時最佳化演算法。根據規劃範圍可分為全域性規劃演算法及區域性尋優演算法。如Dynapath演算法是一種前向鏈動態規劃技術，在大的任務區域內進行航線規劃是典型的大範圍最佳化問題，Dynapath 演算法可以得到問題的全域性最優解。但該演算法具有維數爆炸特性的缺陷。

航跡規劃按照步驟可以分為兩個層次：第一層是整體參考航跡規劃；第二層是區域性航跡動態最佳化。整體參考航跡規劃是飛行前在地面上進行的。參考航跡的優劣依據預先確定的效能指標，一般根據無人機飛行的任務要求、安全要求、飛行時間和其他戰略、戰術考慮等因素組合確定，以此最優效能為標準，透過動態路徑規劃演算法生成一條最優參考航跡。有了參考航跡之後，無人機受環境及自身約束條件如最小轉彎半徑、滾轉角等限制，在實際飛行中並非嚴格沿著參考航跡來飛，而是對參考航跡進行區域性動態最佳化，最後生成最優航跡。按照幾何學的觀點可以分為基於圖形和基於柵格的規劃方案。一般來說，前者較為精確，但需要較長的收斂時間；此外按照規劃決策可以分為

傳統規劃演算法及智慧規劃演算法

。

接下來，來分享一下關於無人機航跡規劃演算法方面的相關內容：

航跡規劃演算法可以分為傳統經典演算法和現代智慧演算法兩大類。其中，前者主要包括動態規劃法、導數相關法、最優控制法；後者主要包括啟發式尋優搜尋、遺傳演算法、人工神經網路（ANN），群體智慧（SA： Swarm Intelligence，主要包括蟻群演算法（ACO）、粒子群演算法（PSO）蜂群演算法（ABC））等。

傳統規劃演算法

（1）動態規劃演算法

動態規劃演算法是解決多級決策最最佳化問題的常見演算法。該演算法應用於無人機航跡規劃中，要求模型相對簡單，不要求威脅場連續性，可以獲得全域性最優解，但缺陷是隨著規劃區域的擴大，受狀態空間的限制，會出現組合爆炸，只能應用於小範圍內的搜尋（如在無人機高空作業並且威脅單一的情況下可取得良好的效果），不易應用於三維空間。因此，必須降維簡化計算，以提高速度，如將三維航跡分解為水平方向和垂直方向兩個二維航跡並分別進行計算，或透過數字地圖預處理技術，將三維最優航跡規劃轉化為安全曲面上的二維航跡規劃。

（2）導數相關法

採用導數相關法，主要有最速下降法、牛頓法、共軛梯度法、擬牛頓法、信賴域方法和最小二乘法，其中最速下降法目前使用比較多。最速下降法是S。J。Asseo於1982年提出的，它應用最速下降法求解地形跟蹤（TF： Terrain Following） 及地形規避（TA： Terrain Avoiding）問題。該方法相對較簡單，收斂速度較快，需要地形一階編導連續，相對最優控制法對地形要求不高：但由於演算法是建立在目標函式梯度基礎上，要求導函式連續、迭代運算量大，且易陷入區域性最優解。通常，該演算法中關於威脅的考慮過於簡單，僅以飛行方向同威脅方向的夾角作為威脅大小的計算依據。將威脅場迭加於地形之上，相當於透過增加地形的高度來實現對威脅場的處理，因此，不能反映地形對威脅的遮蔽作用。

（3）最優控制方法

最優控制演算法在火箭、衛星軌道規劃中有廣泛的應用。該演算法對地形要求較嚴，一般要求地形的二階偏導函式連續；模型及其引數相對複雜，在複雜地形下可能出現死鎖，容易發散，規劃時間長。因此，在處理TF/TA問題時，一般將問題進行分解。TF主要考慮垂直面內的運動，TA則是水平面的運動，不同的平面內分別進行規劃。直升飛機的地形跟蹤三維路線直接生成法以速度方向與地形的切平面座標軸間的夾角作為控制量，飛機的位置座標作為狀態變數，將路線規劃問題化為一起點固定、終端自由、時間自由的最優控制問題，透過不斷地改變初始航向的方法，使路線的終點接近目標點。這種方法的優點在於將兩端固定的問題簡化為一端固定、一端自由的問題，從而大大簡化了伴隨向量的求解。

傳統方法存在著共同的缺點，未考慮啟發因素，不具備智慧搜尋功能，容易陷入區域性最優，演算法透過大規模的反覆迭代以彌補智慧導向能力的缺乏。因此，演算法計算時間長。

智慧規劃演算法

（1）啟發式尋優搜尋

啟發式搜尋是在狀態空間中的搜尋，對每一個搜尋的位置進行評估，得到最好的位置，再從這個位置進行搜尋直到目標，省略大量的搜尋路徑，提高效率。A*演算法是一種經典的啟發式搜尋演算法，該演算法一般應用於基於柵格的數字地圖中，多用於解決靜態規劃的問題。在應用過程中，一般取距離代價和威脅代價等方面的加權和來表示實際代價。A*演算法同樣存在隨搜尋區間的增大，內部儲存資料增加，搜尋時間過長，實時性無法保證的問題，一般應用於二維空間的搜尋。通常對基本A*演算法進行改進，使之能應用於實時規劃。如三維稀疏A*演算法（SAS）透過準確有效的剪除不符合要求的狀態來使規劃快速收斂。採用柵格的形式構造飛行環境，運用一種改進的A*演算法搜尋，將距離代價、威脅代價以及機動性代價三者的加權和作為路徑代價，並運用模糊技術為三者的權值進行分配，針對環境的變化可以調整權係數，對動態環境有較高的適應性。採用各柵格代價值（MCarray）作為輸入產生各柵格到目標節點的最小代價值（BCarray）作為啟發式項，取得了良好效果。傳統的A*演算法存在搜尋速度慢和耗記憶體空間大的缺陷。為了加快搜索過程和節省記憶體空間，透過分割槽搜尋並結合飛行約束削減搜尋節點，提出了稀疏A*演算法。透過建立Cheap表及降低搜尋空間的方法，改進A*演算法，解決了演算法進行大空間搜尋時，耗時急劇增加的問題，因此提高了演算法的效率。模擬結果表明，該方法計算速度快，易於實現。

（2）遺傳演算法

遺傳演算法（GA）是可用於複雜系統最佳化的具有魯棒性的搜尋演算法。該演算法透過染色體的複製、交叉、變異得到新的個體，並對個體效能進行評估，從而得到最優的符合要求的個體。與傳統的最佳化演算法相比，主要有以下特點： （1） GA以決策變數的編碼作為運算物件。傳統的最佳化演算法往往直接決策變數的實際值本身，而遺傳演算法以它的某種編碼形式。（2） GA直接以適應度作為搜尋資訊，無需導數等其它輔助資訊。（3） GA使用多個點的搜尋資訊，具有隱含並行性。（4） GA使用機率搜尋技術，而非確定性規則。但是由於無人機航跡規劃存在時間上和計算機資源的約束，GA會出現早熟現象，得不到全域性的最優解。

利用極座標描述威脅位置和航跡點，將路徑編碼由二維縮減至一維，透過降低搜尋空間來提高最佳化效率。採用遺傳演算法並以偵察效率指標評估的計算方法，解決了航跡規劃中的偵察效率量化問題，透過該方法得到的偵察航跡可以有效地提高無人機的偵察效率“。遺傳演算法的關鍵在於對群體的編碼，經過大量的實驗表明，使用浮點數編碼比二進位制編碼在CPU計算時間上更加有效。初始群體的選取應具有多樣性，使得規劃空間的每一個體都有機會參與進化。利用導航點的座標資訊以及一位校驗位對航跡進行實值編碼，結合航跡的約束條件以及評價函式對航跡群體進行分析，然後採用自設定的幾種遺傳運算元對群體進行操作。採用更能符合實際的B樣條曲線來表示航跡，對無人機全域性和區域性航跡進行規劃。遺傳演算法良好群體搜尋效能，固有的平行計算能力等優點都使得此演算法在航跡規劃中被廣泛應用。但遺傳演算法進行路徑規劃存在費時的問題，一般將其應用於參考航跡的規劃過程，很難應用於實時規劃。從演算法結構上進行改造，將變異操作從交叉操作中分離出來，成為獨立的並列於交叉的遺傳尋優操作；在交叉操作中，以“門當戶對”原則進行個體的配對，利用混沌序列確定交叉點，實行單點交叉，以確保演算法收斂精度；在變異操作中，利用混沌序列對染色體中多個基因進行變異，避免了演算法早熟。

（3）神經網路方法

由於Hopfield網路引入了“能量函式”的概念，在達到穩定時網路的能量最小，所以很自然地可以用其特殊的非線性動態結構來解決最佳化之類的技術問題。一種基於Hopfield神經網路的無人機地形跟隨（TF）/地形迴避（TA）的航跡規劃方法將地形資訊反映到演算法引數連線權中，利用擴充套件的Hopfield模型結合無人機約束條件實現航跡安全、合理的規劃。使用基於距離變換的序列模擬構建數值勢場， 加速了數值勢場的傳播。在學習過程中，透過調整連線權係數改變區域性勢場分佈。試驗表明，演算法在單處理器上可以進行有效的快速航跡規劃，該方法具有較高的效率和環境適應性。

蟻群演算法

蟻群演算法（ ACO）是一種用來在圖中尋找最佳化路徑的機率型技術，其靈感來源於螞蟻在尋找食物過程中發現路徑的行為。該方法具有正反饋、分散式計算和富於建設性的貪婪啟發式搜尋的特點。為提高無人機作戰任務的成功率，提出了基於蟻群演算法的適用於航跡規劃的最佳化方法，該方法可以保證無人機能夠以最小的被發現機率及可接受的航程到達目標點。保留最優解、自適應狀態轉換規則和自適應資訊激素更新規則，有效地提高了演算法收斂速度和解的效能”。基於改進蟻群演算法的無人機三維航跡規劃方法，則以保證在敵方防禦區域內以最小的被發現機率以及可接受的航程到達目標點。首先對無人機三維航跡規劃模型進行分析，在此基礎上採用蟻群演算法對三維航跡進行最佳化。其次，將最短路徑的資訊反饋到系統中作為搜尋的指導訊號，並改進節點選擇方法，以提高應用蟻群演算法搜尋無人機三維航跡的效率。最後，將所研究的方法應用於無人機的三維航跡規劃。模擬結果表明，本文提出的方法是有效的。改進蟻群演算法的初始資訊素強度與啟發因子，並以島嶼進攻戰役這一特定作戰任務為例，就實現了偵察多目標時的航跡規劃問題。在每次迴圈結束，保留其最佳結果及改進螞蟻狀態轉換規則，對基本蟻群演算法提出了改進，提供了一種新的有效的航跡最佳化演算法。模擬結果表明，改進的演算法克服了原演算法的收斂速度慢、易於過早陷入區域性最優的缺點。針對傳統蟻群演算法在搜尋過程中出現停滯現象，還研究出一種Q-學習的自適應蟻群演算法的無人機航跡規劃方法，模擬結果表明，該方法也是一種有效的航跡規劃方法。

綜上所述，各種智慧最佳化演算法都有其自身特點，程式設計的複雜程度也不一樣，啟發式尋優搜尋對動態環境有較高的適應性，可應用於實時規劃，但存在搜尋速度慢和耗記憶體空間大的缺陷。蟻群演算法在概念上較為接近航跡規劃問題，程式設計相對比較容易，但隨著問題規模的擴大，需要較大的儲存空間；遺傳演算法目前使用比較廣泛，但是由於航跡長度的不確定，導致編碼長度動態修改，增加了程式設計的複雜度；神經網路法適用於TF/ TA的航跡規劃，而對於具有雷達、導彈及高炮等威脅因素未作考慮。此外，為有效利用演算法各自的優勢，混合演算法將成為航跡規劃演算法的發展趨勢。

無人機實時航跡規劃是當今無人機叢集配合，叢集戰術再規劃，叢集戰術目標再製定等高階自主飛行的技術基礎，也是提高無人機的生存機率的一種最有效的手段。如果你想更系統，更快速的推進無人機叢集專案研究，可以在已經開發好的無人機叢集平臺上開展專案實驗及科研。

現在已經開發好的無人機叢集科研平臺，可用於無人系統的動態建模和控制研究、運動規劃、避障控制、多資訊融合、編隊控制、多智慧體協調控制、無人系統自主控制等研究方向。

可進行的多機編隊飛行實驗非常全面及具有實用性：

❉多無人機協同搜尋區域分割與覆蓋演算法模擬

❉多無人機任務分配策略實驗

❉多機編隊隊形設計、保持、變換和防撞實驗；

❉多無人機任務航跡規劃實驗

❉多無人機通訊組網實驗

在無人機編隊飛行方面，可提供無人機編隊飛圓形、空間8字、空間螺旋，隊形變換，從跟隨、空地協同等無人機編隊例程。這些例程完全開源。多種影片教程由淺入深地為使用者講解實驗的原理、步驟、目標等，並附有相應的配套例程程式碼，方便使用者快速掌握、理解。

而且平臺開放性高，介面豐富。可以很方便地進行二次開發。還可根據使用者的實際需求定製整個系統平臺，並提供相應的技術支撐和詳細的例程及說明書指導。滿足使用者的個性化和差異化需求，使平臺更加契合使用者的使用特點和習慣，提升體驗感和互動率，減少使用者熟悉平臺的時間成本，大大提高使用者的開發效率和體驗。

重要的是，叢集研發平臺所有的例程都可以在模擬平臺中模擬模擬。可以軟體在環模擬，硬體在環模擬，實現模擬和實物開發有機結合。可以在實測之前透過模擬測試驗證演算法的可靠性和有效性，然後無縫切換到本叢集研發平臺。大大提高研發效率。

平臺介面不僅豐富、而且開放性強，使用者不需要掌握太多的底層程式設計技術即可完成演算法的修改和驗證。支援C、C++、Python、ROS、Matlab/Simulink等多種程式設計環境，提供完善的二次開發介面。

相容的定位系統也覆蓋全面，目前涵蓋主流的室內外定位方式。可提供光學定位系統、UWB定位系統、鐳射定位系統、GPS、RTK等多種定位平臺，定位系統覆蓋面積可根據客戶要求定製。

在通訊方面：支援WIFI、數傳、等多種叢集通訊方式。

隨著對無人機航跡規劃要求的越來越高，未來無人機航跡規劃在演算法方面的發展方向及研究重點主要有： （1）不確定環境下的實時航跡規劃。對多感測資訊運用不確定性理論進行綜合處理，以便合理有效利用各種資訊，對戰場態勢進行評估，真正實現在無人干預的情況下，根據探測結果自動修改航跡； （2）戰術級的強實時的航跡規劃問題； （3）高效的全域性搜尋方法和區域性搜尋方法的混合使用；（4） 多工目標（如低空突防、目標搜尋營救、資訊偵察等任務）綜合的規劃演算法： （5） 多機協同規劃演算法。要求執行任務時，整體代價達到最優：（6）針對地形、敵情資訊處理方法的研究演算法。此項研究直接決定了規劃路徑的質量。