摘要：本文針對無人機(jī)對于動態(tài)路線最優(yōu)選擇問題進(jìn)行了研究。基于傳統(tǒng)的啟發(fā)式搜索算法，本文改進(jìn)了該方法的鄰近目標(biāo)的搜索策略，并構(gòu)建了虛擬探索目標(biāo)，并以最小損失函數(shù)為基本原則，構(gòu)建了改進(jìn)啟發(fā)式搜索策略的動態(tài)路線最優(yōu)選擇模型。該模型可應(yīng)用于戰(zhàn)場無人機(jī)偵察和外場電力巡檢等領(lǐng)域，能夠有效提升搜索效率。

關(guān)鍵詞：圖搜索；最優(yōu)路線；人工智能；啟發(fā)式搜索；路徑尋優(yōu)

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

一、有信息搜索

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

（一） 貪婪最佳優(yōu)先搜索

貪婪最佳優(yōu)先搜索算法是一種基礎(chǔ)簡單的啟發(fā)式搜索算法，其基本思想是按照節(jié)點(diǎn)距目標(biāo)的距離對節(jié)點(diǎn)表進(jìn)行排序，以節(jié)點(diǎn)的估計(jì)距離為標(biāo)準(zhǔn)選擇待擴(kuò)展節(jié)點(diǎn)，評價函數(shù)即為啟發(fā)函數(shù)。在搜索問題解法時，每一步算法會先查看所有鄰近節(jié)點(diǎn)，選擇最低開銷。然而，該算法存在兩個缺陷：一是不一定能夠得到最優(yōu)解，二是容易陷入死循環(huán)[5]。

（二）搜索

基于貪婪最佳優(yōu)先搜索算法的改進(jìn)算法是求解最短路徑最有效的直接式搜索方法。該算法的評價函數(shù)為當(dāng)前的最小開銷代價與后續(xù)最小開銷代價的總和。在算法設(shè)計(jì)時，需要滿足兩個條件：一是估計(jì)代價要小于實(shí)際代價，二是后續(xù)節(jié)點(diǎn)的代價應(yīng)小于當(dāng)前節(jié)點(diǎn)代價的單調(diào)性[6-7]。

（三）輔助信息

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

二、算法設(shè)計(jì)與主要方法

為了應(yīng)對航線飛行過程中到達(dá)既定目標(biāo)后可能隨機(jī)出現(xiàn)的下一個偵察目標(biāo)，我們可以采用隊(duì)列編程思想，使用基于算法的改進(jìn)啟發(fā)式搜索最短路徑策略。

改進(jìn)算法的具體算法流程如圖1所示。

三、節(jié)點(diǎn)距離計(jì)算

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

基于本文的優(yōu)化搜索策略算法，具體實(shí)現(xiàn)描述見圖2。

圖2中，Now為無人機(jī)當(dāng)前所在位置，1、2、3、4為戰(zhàn)場偵察目標(biāo)點(diǎn)，Destination為飛行終點(diǎn)，其運(yùn)行的距離計(jì)算如表2。

根據(jù)虛擬節(jié)點(diǎn)的布設(shè)，可以得知在運(yùn)行算法的搜索策略下，當(dāng)下一個節(jié)點(diǎn)的歐式距離一致時，通過虛擬運(yùn)行的方法，可以根據(jù)輔助信息極小化的原理，高效地獲取最優(yōu)的規(guī)劃路線。

四、結(jié)束語

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

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

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

參" 考" 文" 獻(xiàn)

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

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

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

[4] 劉生偉，馬鉞，孟樹峰，等. 改進(jìn)算法的AGV路徑規(guī)劃[J].計(jì)算機(jī)應(yīng)用，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ìn)算法的無人機(jī)航跡規(guī)劃[J].武漢大學(xué)學(xué)報（信息科學(xué)版），2015，40（03）：315-320.

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

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