基于改進啟發式搜索的動態路線最優選擇技術

摘要：本文針對無人機對于動態路線最優選擇問題進行了研究。基于傳統的啟發式搜索算法，本文改進了該方法的鄰近目標的搜索策略，并構建了虛擬探索目標，并以最小損失函數為基本原則，構建了改進啟發式搜索策略的動態路線最優選擇模型。該模型可應用于戰場無人機偵察和外場電力巡檢等領域，能夠有效提升搜索效率。

關鍵詞：圖搜索；最優路線；人工智能；啟發式搜索；路徑尋優

近年來，無人機的生產工藝逐漸成熟，功能也日益增多，功能算法日趨完善，為未來的戰場無人化戰爭奠定了堅實的基礎。無人機以靈活機動、視野廣闊、價格低廉等優勢，成為戰場偵察領域的主力。然而，在復雜多變的外場多目標偵察問題中，如何設計多目標勘測的最優最短航路規劃問題成為提高外場作業效率和能力的關鍵。無人機航路規劃算法是無人機正確、正常執行任務的主要核心，靈活增減途徑興趣點的多目標航路規劃算法是提供無人機安全飛行和提高無人機智能水平的根本保證。目前，主流的航路規劃算法有遺傳算法、蟻群算法等。本文基于啟發式搜索策略，在傳統算法對單目標進行最優路徑的基礎上，增加多目標的搜索策略，自適應在無人機飛行過程中，突發性增加興趣點后的自由靈活航路規劃任務。

一、有信息搜索

啟發式搜索又稱為有信息搜索，該算法利用相關輔助信息引導搜索過程，減少搜索范圍，降低問題復雜度。與廣度優先搜索和深度優先搜索策略這類無信息搜索算法不同，有信息搜索算法能夠獲得中間額外信息參與計算[1]。啟發式搜索算法在使用計算過程中需要滿足三個條件：一是定義啟發函數，在求解起點與目標點的最短距離中，計算和估計當前點到達目標點的代價；二是定義評價函數，根據搜索算法的不同而具有明顯差異，用于選擇最佳的邊緣節點；三是輔助信息，計算目標點與當前節點的最短距離，作為額外搜索啟發信息。有信息搜索的最佳優先搜索算法是根據評估函數對每個節點預測期望值，每次搜索時優先拓展期望值最大的節點，其中最具代表性的是貪婪最佳優先搜索和A*搜索兩種算法[2-4]。

（一） 貪婪最佳優先搜索

貪婪最佳優先搜索算法是一種基礎簡單的啟發式搜索算法，其基本思想是按照節點距目標的距離對節點表進行排序，以節點的估計距離為標準選擇待擴展節點，評價函數即為啟發函數。在搜索問題解法時，每一步算法會先查看所有鄰近節點，選擇最低開銷。然而，該算法存在兩個缺陷：一是不一定能夠得到最優解，二是容易陷入死循環[5]。

（二）搜索

基于貪婪最佳優先搜索算法的改進算法是求解最短路徑最有效的直接式搜索方法。該算法的評價函數為當前的最小開銷代價與后續最小開銷代價的總和。在算法設計時，需要滿足兩個條件：一是估計代價要小于實際代價，二是后續節點的代價應小于當前節點代價的單調性[6-7]。

（三）輔助信息

啟發式搜索的輔助信息為評估總損失的評價函數。在尋路任務中，兩點之間的直線距離為啟發函數，計算從節點到目標節點之間所形成路徑的最小代價值，那么它可能是完整解的路徑耗散，也可能是當前解到目標節點的路徑耗散，貪婪最佳優先算法的表達為：f（x）=g（x），A*算法的公式表達為：f（x）=g（x）+h（x），其中h（x）就是啟發式函數[8]。

二、算法設計與主要方法

為了應對航線飛行過程中到達既定目標后可能隨機出現的下一個偵察目標，我們可以采用隊列編程思想，使用基于算法的改進啟發式搜索最短路徑策略。

改進算法的具體算法流程如圖1所示。

三、節點距離計算

傳統A*算法根據使用背景不同，一般來說采用歐式距離或曼哈頓距離來計算輔助信息。然而，由于GIS多基于柵格地圖，因此它的搜索過程可以理解為如下所示。

基于本文的優化搜索策略算法，具體實現描述見圖2。

圖2中，Now為無人機當前所在位置，1、2、3、4為戰場偵察目標點，Destination為飛行終點，其運行的距離計算如表2。

根據虛擬節點的布設，可以得知在運行算法的搜索策略下，當下一個節點的歐式距離一致時，通過虛擬運行的方法，可以根據輔助信息極小化的原理，高效地獲取最優的規劃路線。

四、結束語

該算法的優勢在于在處理動態可隨機增加目標點的背景條件下，能夠高效、快速、最小損失估計地對所有偵察目標進行航線規劃。同時，為了減小起始點到相似鄰近目標對后續偵察冗余航線規劃的影響，引入了虛擬構設的無人機。通過計算各優選航線的代價估計，獲得優化航線的順序隊列，并遞歸實現動態可增加目標的推薦路線，直至完成所有目標的遍歷。該方法的缺點在于構設虛擬無人機并執行最優路線搜索，會消耗部分內存空間。隨著偵察目標的逐漸增多，會影響該算法的實效性。因此，該算法屬于以消耗內存換取算法最優的設計方法。后續會在減小內存訪問部分進行進一步優化。在該算法的設計仿真過程中，曾把尋找最短路徑的改進算法替換為貪婪最佳優先算法和無信息搜索的廣度優先的Dijkstra算法。在固定兩個偵察目標點的初始位置的情況下，發現二者的搜索路徑差別不大。

經查閱，Dijkstra算法是一種廣度優先遍歷算法。它使用了相同路徑長度（同權）的節點同時遍歷的優先級隊列，每次從隊列中取出到起點路徑最短的點優先遍歷。若所有節點之間移動的代價（權）是相等的，則Dijkstra就退化為廣度優先算法[9]。在更新的過程中，Dijkstra算法是無方向的，與終點無關。但是，算法以預估代價的方式將終點加入總體代價中，這樣更新的過程優化算法就有一個明顯的指向性。這主要與既定的搜索范圍即總窗口大小有關。此外，在搜索范圍內加入多個偵察目標，更加縮小了無人機對搜索目標的區域范圍。如果擴大搜索范圍，則算法會有明顯的優勢。

作者單位：張晗 李海龍 李嘉俊 董建業 中國電子科技集團公司第二十二研究所

參" 考" 文" 獻

[1] 冉東可，彭富倫，李紅光.基于算法的路徑規劃研究綜述[J].電子技術與軟件工程，2020（24）：11-12.

[2] 劉子豪，趙津，劉暢，等.基于改進算法室內移動機器人路徑規劃[J].計算機工程與應用，2021，57（02）：186-190.

[3] 李素娟.無人機航路規劃及評價方法研究[D].南京：南京航空航天大學，2012.

[4] 劉生偉，馬鉞，孟樹峰，等. 改進算法的AGV路徑規劃[J].計算機應用，2019，39（S2）：41-44.

[5] Shilong Xuan.Unmanned Vessels Path Planning Based On" Algorithm[J].International Core Journal of Engineering，2021，7（2）.

[6] Min Haitao et al. The hybrid path planning algorithm based on improved" and artificial potential field for unmanned surface vehicle formations[J].Ocean Engineering，2021，223

[7] 占偉偉，王維，陳能成，等.一種利用改進算法的無人機航跡規劃[J].武漢大學學報（信息科學版），2015，40（03）：315-320.

[8] 李棟，曹義華，馮婷.基于地形特征的簡易地形模擬算法[J].航空計算技術，2005（02）：32-35.

[9] 李素娟，肖前貴，高艷輝，等.多約束條件下無人機航路規劃動態評價方法[J].指揮控制與仿真，2012，34（02）：36-39.