張云飛
(河海大學 計算機與信息學院, 南京 211100)
無人機利用無線電遙控設備和控制裝置操縱,應用于民用和軍事,能夠解決人類無法解決的難題??紤]到無人機自身的特殊性,特別是面對戰(zhàn)爭威脅時,如何快速、準確地確定最佳航路,是保證在日益復雜、多變的現(xiàn)代戰(zhàn)場環(huán)境下,無人機能夠順利完成任務的關鍵條件[1]。因此,需要對其路徑規(guī)劃進行優(yōu)化。
使用路徑規(guī)劃算法計算無人機最優(yōu)飛行軌跡,目前最常用的兩種方法主要為蟻群算法和啟發(fā)式搜索算法[2]。其中,啟發(fā)式搜索算法是一種最小代價函數(shù),它基于最小代價,在從初始點到當前點再到目標點的搜索過程中,連續(xù)地對目標節(jié)點進行擴展,從而形成一組最小代價路由,使一組節(jié)點到達最優(yōu)路徑。啟發(fā)式搜索通常用來解決靜態(tài)的不確定規(guī)劃問題,廣泛應用于地圖中。該方法具有很強的收斂能力,常用于單點搜索,在快速搜索路徑上有較好的效果,但隨著搜索區(qū)域的增大,其記憶數(shù)據(jù)也隨之增大,使搜索時間變長[3]。該算法難以實現(xiàn)無人機約束的融合,只能生成一條路徑,無法滿足某些特殊任務的需要,導致無人機路徑不可行;蟻群算法是一種基于動物從洞穴中尋找食物這一最短路徑現(xiàn)象的合作發(fā)現(xiàn)方法,該方法采用路徑規(guī)劃的方法,首先使給定路徑的所有節(jié)點都處在信息素的作用范圍內(nèi),然后蟻群算法通過這些節(jié)點達到目標路徑,避免了路徑中節(jié)點對信息素的影響,從而減少了路徑中節(jié)點的數(shù)目,提高了路徑的可重復性,直到找到了最佳路徑為止[4]。然而,蟻群算法在無人機飛行路徑規(guī)劃過程中存在計算步驟復雜、計算量大的問題。
因此,針對上述兩種路徑規(guī)劃算法中存在的問題,結合貝葉斯決策方法,設計無人機航跡自動規(guī)劃方案。在無人機飛行路徑自動規(guī)劃硬件部分,分別設計了自動規(guī)劃模塊、動畫演示模塊、地圖導航模塊及數(shù)據(jù)導出模塊,在硬件模塊設計的基礎上,利用貝葉斯決策算法設計無人機飛行路徑自動規(guī)劃流程,傳統(tǒng)路徑規(guī)劃方法存在規(guī)劃準確性較差的問題,為此基于貝葉斯決策算法設計無人機飛行路徑自動規(guī)劃流程。確定貝葉斯先驗概率,在此基礎上從預測距離和障礙物節(jié)點數(shù)量兩個方面,準確選擇節(jié)點預測區(qū)域,計算飛行安全距離,初步規(guī)劃避障路線,計算后驗概率,選擇備份區(qū)選擇節(jié)點。最后利用重復循環(huán)機制綜合循環(huán)結果并選擇最優(yōu)路徑。
傳統(tǒng)路徑規(guī)劃方法存在規(guī)劃準確性較差的問題,為此基于貝葉斯決策算法設計無人機飛行路徑自動規(guī)劃方法。首先設計無人機飛行路徑自動規(guī)劃硬件模塊,實現(xiàn)無人機飛行路徑自動規(guī)劃的功能運行,并結合基于貝葉斯決策的無人機飛行路徑自動規(guī)劃流程,確定貝葉斯先驗概率,據(jù)此從預測距離和障礙節(jié)點數(shù)量兩方面出發(fā),獲得精準的備選節(jié)點預測區(qū)域,計算飛行安全距離初步規(guī)劃避障路線,計算后驗概率,選定選擇飛行區(qū)域內(nèi)備選節(jié)點。最后通過 repeat循環(huán)機制,綜合循環(huán)結果,選取最優(yōu)路徑,實現(xiàn)無人機飛行路徑的準確規(guī)劃。
無人機飛行路徑自動規(guī)劃模塊主要有4個部分,分別是自動規(guī)劃模塊、動畫演示模塊、地圖導航模塊和數(shù)據(jù)導出模塊,如圖1所示。
圖1 無人機飛行路徑自動規(guī)劃模塊
由圖1可知,在自動規(guī)劃模塊中設置操作按鈕,負責控制無人機飛行;動畫演示模塊負責展示飛機飛行路線;地圖導航模塊負責為無人機飛行路徑規(guī)劃提供精準定位數(shù)據(jù);數(shù)據(jù)導出模塊負責導出并保存相關數(shù)據(jù)。
1.1.1 自動規(guī)劃模塊
按照無人機航路的要求,自動規(guī)劃模塊主要是由自動規(guī)劃的路徑選項分類器、自動規(guī)劃的操作模塊、坐標顯示模塊組成的,其中路徑選項分類器在選擇航路時,分別按4個按鈕進行設置,分別控制起點、終點、落腳點、禁飛區(qū);自動規(guī)劃的操作模塊包含了3個按鈕,分別是規(guī)劃按鈕、優(yōu)化按鈕、演示按鈕;坐標顯示模塊主要顯示了場景坐標、起點坐標和終點坐標[5]。在開始和結束時,單擊顯示區(qū)域的開始和結束按鈕,威脅點和禁止按鈕來確定威脅區(qū)域和禁飛區(qū),然后,通過操作舊按鈕來制定路徑規(guī)劃的自動規(guī)劃選項模塊,生成黑色的路線圖,并通過新按鈕生成新的航行路線圖。自動規(guī)劃模塊結構示意圖如圖2所示。
圖2 自動規(guī)劃模塊結構示意圖
1.1.2 動畫演示模塊
動畫演示模塊主要負責顯示初始航跡和優(yōu)化航跡的兩個航跡,通過按動視圖按鈕,即動畫演示按鈕,將看到一架小型模擬飛機按計劃飛行。模擬小飛機不僅能在初始飛行路徑飛行,而且能在優(yōu)化后的最佳飛行路徑飛行。這種生動、直觀的動畫演示模式,使優(yōu)化航跡更加清晰準確[6]。
動畫演示模塊主要包括索引模塊、非線性變形器、聲音編輯器,其中索引模塊支持跨平臺操作,具有多線程設計,支持大量用戶訪問;非線性變形器的控制柄顯示在動畫場景中,節(jié)點將列在通道盒內(nèi),這些節(jié)點包括控制柄節(jié)點和彎曲變形器節(jié)點[7]。使用顯示操縱器工具,為動畫演示提供交互編輯功能;聲音編輯器包括聲卡、調(diào)音臺和混音器,使用240PRO型號的LEWITT聲卡,如圖3所示。
圖3 LEWITT聲卡結構
如圖3所示,聲卡結構包括輸入/輸出系統(tǒng)、電池、插座、芯片、接口等。聲卡結構中的芯片組負責從各個模塊中提取聲音信號,通過AD轉換器,將聲音信號轉換為數(shù)字形式。采用復用數(shù)字信號處理器處理語音指令,不僅減輕了 CPU的工作負荷,同時也提高了執(zhí)行速度。
1.1.3 地圖導航模塊
地圖導航模塊是基于單片機體系結構特性設計的,采用超低功耗、體積小巧的 GNSS芯片,具有超高的靈活性[8]。接收端采用 UBX或 NMEA協(xié)議,通過串口將射頻信號發(fā)送到天線的輸入端,并提供位置、速度、時間等信息。
LS-TM8N地圖導航模塊如圖4所示。
圖4 LS-TM8N地圖導航模塊
由圖4可知,顯示在主地圖上的地圖范圍在導航窗口位置發(fā)生變化時也發(fā)生變化,為實現(xiàn)這一目標,最重要的一步是在導航窗口中將數(shù)據(jù)與中間主地圖顯示區(qū)域中的數(shù)據(jù)對齊。
1.1.4 數(shù)據(jù)導出模塊
在航路規(guī)劃設計中,航路規(guī)劃路線、航路起始點、地圖威脅點等信息會在主圖中顯示,數(shù)據(jù)導出模塊以bmp格式圖片文件的形式對這些信息導出并保存[9]。當航路規(guī)劃完成后,想要對需要保存的路線圖生成紙張,可單擊位于自動路徑規(guī)劃界面的右上方的SaveButton,通過點擊此按鈕,就會將數(shù)據(jù)信息進行保存。
貝葉斯法解決了傳統(tǒng)遺傳算法在交叉、變異等方面存在的問題,通過貝葉斯網(wǎng)分析種群質量,利用貝葉斯網(wǎng)中的參數(shù)反映染色體與基因的關系程度,利用貝葉斯網(wǎng)的演化規(guī)律,利用貝葉斯優(yōu)化算法更新無人機飛行規(guī)劃路線[10]。貝葉斯決策原理為:
利用多種選擇機制,從當前規(guī)劃路線中選取最佳規(guī)劃路線?;跀?shù)據(jù)信息,使用后驗概率的貝葉斯元胞蟻群算法計算最佳規(guī)劃路線;利用計算結果,聯(lián)合賦值產(chǎn)生新的個體集合。經(jīng)過以上步驟反復執(zhí)行直至達到獲取最佳規(guī)劃路線為止,該方法的終止條件可為運行到某個代次、群體中存在足夠多的解[11-13]。
進行路徑規(guī)劃時,根據(jù)貝葉斯決策原理,結合貝葉斯元胞蟻群算法,對無人機飛行路徑進行規(guī)劃,詳細步驟如下。
1)確定貝葉斯先驗概率:
在貝葉斯元胞可以飛行區(qū)域N1(Sn)內(nèi),依據(jù)導出的數(shù)據(jù),確定備選節(jié)點概率,該概率即為最優(yōu)路徑選擇中的先驗概率,公式為:
(1)
式(1)中,Th表示貝葉斯元胞可以飛行區(qū)域N1(Sn)內(nèi)的信息素。
2)確定貝葉斯元胞備選節(jié)點條件概率:
設預測半徑為RR,構造預測區(qū)域RD,對于元胞鄰居可行區(qū)域N1(Sn)內(nèi)的任意一個備選節(jié)點Wi:
RD(Wi)={dot|dist(Wi,dot)
dot∈L}
(2)
式(2)中,Angle(n)表示不同備選節(jié)點間的夾角,該夾角最大值為80°。備選節(jié)點的預測區(qū)域,如圖5所示。
圖5 備選節(jié)點的預測區(qū)域
由圖5可知,對于備選節(jié)點預測區(qū)域的確定需從兩個方面考慮,分別是預測距離和障礙節(jié)點數(shù)量。其中預測距離指的是無人機到達目標位置的距離和無人機與障礙物位置的距離;障礙節(jié)點指的是無人機可以飛行區(qū)域內(nèi)出現(xiàn)的障礙目標。結合上述兩個方面內(nèi)容,可以獲取精準備選節(jié)點預測區(qū)域[14-16]。
3)避障規(guī)劃:
為了防止避障失敗,無人機需要一定的飛行安全距離,這里設定為D0,針對無人機和障礙節(jié)點的距離,定義條件概率:
f(Wi)=
(3)
式(3)中,mindist(Wi,obstacle)表示備選節(jié)點和障礙物之間的距離,該距離值越小,說明條件概率值越小。通過對上述全部數(shù)據(jù)進行歸一化處理后,能夠得到貝葉斯元胞可以飛行區(qū)域內(nèi)的條件概率[17],計算公式為:
(4)
式(4)中,G表示規(guī)劃事件;P(Wi|G)表示后驗概率。根據(jù)規(guī)劃路徑找到最優(yōu)解后,可以在所選擇的預測區(qū)域內(nèi)尋找備選節(jié)點,由此得到全局最優(yōu)解,該解中包含了所有節(jié)點概率評估結果[18]。
4)確定貝葉斯元胞備選節(jié)點后驗概率:
貝葉斯元胞備選節(jié)點后驗概率,計算公式為:
(5)
式(5)中的Wi指的是依照事先規(guī)劃好的路線,通過后驗概率選擇無人機在可以飛行區(qū)域內(nèi)的備選節(jié)點。
5)更新無人機飛行信息:
詳細步驟如下。
1)該方法首先對地圖區(qū)域進行矩形設置,將其網(wǎng)格離散化,然后利用灰度矩陣H和信息素矩陣IM建立相應的網(wǎng)格;
2)設定無人機飛行規(guī)劃模擬批次數(shù)量為m,同批次數(shù)量為m0。
3)批次循環(huán)開始for(i=1:m);
4)同批次內(nèi)無人機的循環(huán)開始for(j=1:m0);
5)使用 repeat循環(huán)機制,確定當前無人機可以飛行的區(qū)域,由此確定備選節(jié)點的先驗概率、條件概率和后驗概率。為了完成螞蟻移動,在無人機到達目標節(jié)點之前,對其進行抽樣,完成重復循環(huán)。
6)同批次無人機的循環(huán)結束,確定m0條路徑并按照距離最短選擇局部最優(yōu)路徑;
7)在圈形軌跡識別完成之后,剔除局部最優(yōu)路徑;
8)在下一批無人機模擬航行中使用優(yōu)化后的局部最優(yōu)路徑更新信息;
9)飛行批次m循環(huán)結束,綜合m次飛行模擬結果選取最優(yōu)路徑。
綜上所述,能夠得出無人機飛行路徑自動規(guī)劃流程,如圖6所示。
圖6 無人機飛行路徑自動規(guī)劃流程
為了驗證基于貝葉斯決策的無人機飛行路徑自動規(guī)劃方法研究合理性,在集成開發(fā)環(huán)境下進行試驗驗證分析。
在集成開發(fā)環(huán)境下,劃分區(qū)域單元格,并將其劃分為可飛行和不可飛行兩種,其數(shù)據(jù)展示結果如圖7所示。
圖7 數(shù)據(jù)展示界面
由圖7可知,黑色單元格表示不可飛行,藍色單元格表示可飛行。
在實驗數(shù)據(jù)支持下,分別使用啟發(fā)式搜索算法、蟻群算法和基于貝葉斯決策自動規(guī)劃方法對比分析無人機飛行遇到靜態(tài)或動態(tài)障礙物的避障能力。
2.2.1 靜態(tài)障礙物
3種方法遇到靜態(tài)障礙物的避障能力,對比結果如8所示。
由圖8可知,使用啟發(fā)式搜索算法遇到了兩個障礙物,使用蟻群算法遇到了一個障礙物,使用基于貝葉斯決策自動規(guī)劃方法沒有遇到障礙物。上述實驗結果表明,基于貝葉斯決策自動規(guī)劃方法能精準規(guī)避靜態(tài)障礙物,無人機飛行路徑規(guī)劃的準確性較好,避障性能優(yōu)。
圖8 3種方法靜態(tài)障礙物避障能力對比分析
2.2.2 動態(tài)障礙物
3種方法遇到動態(tài)障礙物的避障能力,對比結果如9所示。
由圖9可知,使用啟發(fā)式搜索算法沒有障礙物,但飛行路線較遠,使用蟻群算法遇到了兩個障礙物,使用基于貝葉斯決策自動規(guī)劃方法沒有遇到障礙物。實驗結果表明,基于貝葉斯決策自動規(guī)劃方法能精準規(guī)避動態(tài)障礙物,無人機飛行路徑規(guī)劃的準確性較好,避障性能優(yōu)。由于貝葉斯決策算法能夠通過先驗概率和后驗概率規(guī)劃無人機飛行路徑,結合貝葉斯元胞蟻群算法獲取最優(yōu)路徑,因此該方法的避障能力較好。
圖9 3種方法動態(tài)障礙物避障能力對比分析
通過上述分析結果可知,基于貝葉斯決策自動規(guī)劃方法,無人機飛行路徑自動規(guī)劃效果較好,無論是遇到靜態(tài)障礙物,還是動態(tài)障礙物,都能良好避障。
在貝葉斯決策下實現(xiàn)了無人機飛行路徑的自動規(guī)劃,優(yōu)化后的航跡使無人機飛行更加精準可靠,確保任務的順利完成。實驗結果表明,該方法對靜態(tài)障礙物及動態(tài)障礙物的避障能力均較好,能夠準確捕獲避障信號,實現(xiàn)障礙物自動規(guī)劃。因為實際的路徑規(guī)劃通常包含多個目標節(jié)點,所以多目標路徑規(guī)劃更有實際意義。采用貝葉斯決策方法對多目標路徑規(guī)劃進行了優(yōu)化研究,同時對同一批執(zhí)行不同任務的目標節(jié)點進行了路徑規(guī)劃,使路徑規(guī)劃更具有合理性。