韓曉微，韓 震，岳高峰，崔建江

1.沈陽大學(xué) 科技創(chuàng)新研究院，沈陽 110044

2.沈陽大學(xué) 信息工程學(xué)院，沈陽 110044

3.東北大學(xué) 信息科學(xué)與工程學(xué)院，沈陽 110004

隨著無人機(jī)智能化水平的提高，無人機(jī)（Unmanned Aerial Vehicle，UAV）在災(zāi)難救援領(lǐng)域大展身手，解決了救援人員無法第一時間到達(dá)災(zāi)區(qū)的救援難題[1-3]。無人機(jī)航跡規(guī)劃是救援任務(wù)中最重要的環(huán)節(jié)，全局優(yōu)化的航跡規(guī)劃在減少飛行距離的同時也提高救援效率[4-7]，受到廣大學(xué)者的火熱研究。

無人機(jī)在各大災(zāi)區(qū)搶險救災(zāi)中的航跡規(guī)劃問題，各國研究學(xué)者已經(jīng)做了大量研究工作，提出的各種智能航跡規(guī)劃算法已經(jīng)在實際救災(zāi)任務(wù)中得到驗證[8]。馬云紅提出了基于改進(jìn)A*算法的三維無人機(jī)路徑規(guī)劃[9]，陳海等人將凸多邊形區(qū)域中的無人機(jī)覆蓋航跡規(guī)劃問題為研究重點(diǎn)，提出了一種凸多邊形區(qū)域的無人機(jī)覆蓋航跡規(guī)劃問題轉(zhuǎn)化為凸多邊形寬度問題算法[10]，李季等人提出基于改進(jìn)A-Star算法的無人機(jī)航跡規(guī)劃算法[11]，解決無人機(jī)在未知危險環(huán)境中的威脅規(guī)避問題，其目的是綜合路徑代價影響的因素，從而達(dá)到無人機(jī)航跡規(guī)劃威脅避讓效果，低空突防中無人機(jī)的飛行環(huán)境的復(fù)雜性，綜合考慮了飛行高度、航跡長度等因素，搜索一條兩個航路點(diǎn)之間的最優(yōu)航跡，SUN 等人提出基于A*算法規(guī)劃無人機(jī)路徑[12]，將危險區(qū)域以多邊形建模，利用子節(jié)點(diǎn)安全性檢測策略，解決了實際環(huán)境下突然出現(xiàn)的威脅區(qū)動態(tài)路徑規(guī)劃問題，Tsai等人提出了一種隨機(jī)數(shù)快速搜索的算法來確定三維空間的初步航跡[13]，并通過改進(jìn)的A-Star算法降低了無人機(jī)在飛行中能量的消耗。Nuske提出了一種改進(jìn)的稀疏切向網(wǎng)絡(luò)算法[14]，利用測地線性質(zhì)的切線流形上的切線表面周圍障礙快速規(guī)劃。Ryan提出了一種禁忌搜索算法應(yīng)用在多無人機(jī)協(xié)同偵查任務(wù)規(guī)劃問題，并將該問題轉(zhuǎn)化為多旅行商問題[15]。

綜上所述，為進(jìn)一步提高傳統(tǒng)規(guī)劃算法在搜索速度以及與巡查距離混合優(yōu)化的耦合度，本文采用蛇形割圓法對重點(diǎn)圓形巡查區(qū)域航跡規(guī)劃，同時采用提取感興區(qū)域方式選擇較優(yōu)搜索方向、通過加權(quán)評估法重新定義航跡估計函數(shù)，基于以上內(nèi)容改進(jìn)的A*算法，合理分配無人機(jī)數(shù)量的同時也縮短了無人機(jī)到達(dá)災(zāi)區(qū)的飛行時間。

1 無人機(jī)群航跡規(guī)劃模型建立

1.1 災(zāi)情巡查

某地區(qū)地震后，根據(jù)災(zāi)情分出七個重點(diǎn)區(qū)域，且每個重點(diǎn)區(qū)域均以方圓十公里為界限，需派出無人機(jī)對其進(jìn)行巡查完成任務(wù)，在巡查任務(wù)之前需對震區(qū)進(jìn)行三維圖重建，通過軟件MATLAB 將某震災(zāi)區(qū)的2 913 列，2 775行高程數(shù)據(jù)進(jìn)行數(shù)據(jù)處理，得到震區(qū)三維立體圖，如圖1所示。

圖1 震區(qū)三維立體圖

為了提高無人機(jī)巡查任務(wù)的效率，在震區(qū)三維立體圖中，根據(jù)震區(qū)現(xiàn)象將7 個重點(diǎn)地震區(qū)域中心位置及其中心方圓10 km 區(qū)域標(biāo)示出來，將其記為集合Sn={S1,S2,S3,S4,S5,S6,S7} ，得到俯視二維示意圖，如圖2所示。

無人機(jī)在海拔4 200 m 處巡查到的海拔3 000 m 處面積以及1個重點(diǎn)區(qū)域面積時，根據(jù)人類對天空仰望目標(biāo)物的常規(guī)角度，從災(zāi)區(qū)水平地面任意點(diǎn)觀測無人機(jī)的最適仰角要小于60°，且無人機(jī)在搜救過程中，其搜救效果不能被障礙物所影響，將該巡查任務(wù)擬化成圓錐體示意圖，如圖3所示。

圖2 震后7個重點(diǎn)區(qū)域示意圖

圖3 無人機(jī)巡查示意圖

由圖3得到無人機(jī)巡查有效范圍，即無人機(jī)在海拔3 000 m平面巡查視線圓形區(qū)域的半徑，簡化后數(shù)學(xué)模型：

即無人機(jī)巡查半徑為r1，重點(diǎn)區(qū)域為半徑10 km的圓形，在凸多邊形區(qū)域航跡規(guī)劃問題中[2]，從飛行航程和飛行時間考慮分析，重點(diǎn)巡查區(qū)域的巡查時間較為固定，且無人機(jī)在轉(zhuǎn)彎期間會增加額外飛行距離，故轉(zhuǎn)彎次數(shù)越少，整體執(zhí)行任務(wù)的飛行時間越短，基于在凸多邊形飛行區(qū)域中，最少轉(zhuǎn)彎次數(shù)方向與凸多邊形某條邊平行的思路，設(shè)計了蛇形割圓法對圓形重點(diǎn)震區(qū)(R=10 km)進(jìn)行巡查，該巡查過程假設(shè)無人機(jī)航速不變。當(dāng)無人機(jī)在某一特定多邊形飛行區(qū)域執(zhí)行任務(wù)，轉(zhuǎn)彎的次數(shù)與飛行距離成正比關(guān)系，即轉(zhuǎn)彎數(shù)越少，飛行路程越短，轉(zhuǎn)彎數(shù)越多，飛行路程越長，巡查經(jīng)過路徑及面積示意圖，如圖4所示，條形陰影部分為巡查面積，每個矩形的長對稱軸為巡查路線。

圖4 無人機(jī)巡查單位面積路徑示意圖

將巡查重點(diǎn)區(qū)域放置到平面直角坐標(biāo)系中，以上述巡查直徑作為寬度的矩形來切割重點(diǎn)區(qū)域中心圓，從而建立最短航跡路程Lmin的目標(biāo)函數(shù)，其中點(diǎn)為巡查路徑與重點(diǎn)區(qū)域中心圓交點(diǎn)坐標(biāo)，且滿足都在無人機(jī)攜帶視頻采集裝置巡查重點(diǎn)區(qū)域S,無人機(jī)在飛行過程中的飛行速度為60 km/h，單架無人機(jī)完成一個災(zāi)區(qū)巡查時間為ts。

1.2 地形與大氣威脅

本文在建立模型的時候充分考慮災(zāi)區(qū)的實際情況，引入地形威脅和大氣威脅，使其更加符合實際自然規(guī)律，提高模型的實用性。在無人機(jī)航跡規(guī)劃問題中，地形限制問題通過建立數(shù)學(xué)模型來模擬已知災(zāi)區(qū)區(qū)域三維地形，從而建立數(shù)學(xué)模型為：

Z(x,y)為山峰表面任意一點(diǎn)投影到水平面的坐標(biāo)值，hi為第i個山峰的高度值，(ai,bi)為山峰中心投影到水平面的坐標(biāo)值，λi為第i個山峰的坡度系數(shù)值，通過改變其值可模擬山峰陡度。

將山峰外輪廓抽象為三角形狀模型，如圖5 所示，無人機(jī)到山峰中垂線的距離為dm，中垂線到山峰表面的距離為dh。

圖5 無人機(jī)環(huán)繞山體飛行示意圖

無人機(jī)飛行安全距離介于dmin和dmax之間，當(dāng)無人機(jī)與山峰表面距離大于dmax時，危險度為0，當(dāng)距離趨于dmin時，危險度越大，山峰對無人機(jī)的威脅度為Tm：

大氣中惡劣環(huán)境區(qū)域可擬化為一個球體，球體半徑分為最小威脅Remin和最大威脅Remax，大氣威脅示意圖，如圖6所示。

當(dāng)無人機(jī)處于最大威脅區(qū)域之外時，無人機(jī)不受任何影響，威脅度為0，隨著無人機(jī)向危險球體中心的靠近，無人機(jī)受到的威脅將越來越大，LUAV為無人機(jī)到球體中心的距離，大氣威脅對無人機(jī)的威脅為Tw：

圖6 大氣威脅示意圖

2 無人機(jī)巡查路徑優(yōu)化與求解

2.1 A＊算法基本思想

A*算法是一種啟發(fā)式搜索算法。在巡查三維狀態(tài)空間中起始點(diǎn)到目標(biāo)點(diǎn)的最小代價路徑問題上被廣泛使用，大量應(yīng)用在無人機(jī)的航跡規(guī)劃問題中。主要是通過搜索空間中持續(xù)評估航跡的估價函數(shù)值來啟發(fā)式搜索節(jié)點(diǎn)來尋找最優(yōu)航跡[10]。A*算法常規(guī)的評估函數(shù)表示為：

設(shè)定當(dāng)下節(jié)點(diǎn)為n，其中f(n)是從出發(fā)點(diǎn)經(jīng)過節(jié)點(diǎn)n到達(dá)目標(biāo)點(diǎn)的預(yù)估代價，g(n)是在三維空間中從出發(fā)點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)n的實際代價，h(n)是從節(jié)點(diǎn)n到達(dá)目標(biāo)節(jié)點(diǎn)的預(yù)計代價。

A*算法擁有open 表和closed 表兩個數(shù)據(jù)集合庫，open表用來存放已生成待考察的節(jié)點(diǎn)，closed表保存已考察過的節(jié)點(diǎn)，算法步驟如下：

（1）將起始點(diǎn)存放到open表。

（2）查詢open 表，找到f(n)，將它視為當(dāng)前節(jié)點(diǎn)進(jìn)行處理，若此節(jié)點(diǎn)為終點(diǎn)，結(jié)束所有操作，否則，將該節(jié)點(diǎn)存放到closed表中。

（3）如果當(dāng)前節(jié)點(diǎn)與目的距離在最短飛行距離范圍內(nèi)，轉(zhuǎn)至（4）。

（4）根據(jù)節(jié)點(diǎn)情況進(jìn)行拓展。

（5）將當(dāng)前節(jié)點(diǎn)設(shè)置為相鄰節(jié)點(diǎn)的父親點(diǎn)，加入open表，轉(zhuǎn)至步驟（2）。

（6）結(jié)束。

2.2 改進(jìn)的A＊算法

搜索方向、搜索步長是A*算法搜索效率的主要影響因素。本文通過尋找感興趣區(qū)域的方式優(yōu)化搜索方向，從而提高無人機(jī)搜索災(zāi)區(qū)任務(wù)的效率，在視覺圖像領(lǐng)域，在需要被處理的原圖上，以不規(guī)則多邊形的輪廓框選出需要被處理的區(qū)域，多邊形多數(shù)以圓、方框方式呈現(xiàn)，其被框選出的區(qū)域為感興趣區(qū)（ROI）[16-20]。通過提取感興趣區(qū)域的方法框選重點(diǎn)關(guān)注的區(qū)域，可減少圖像處理的周期，提高識別精度。在制定震區(qū)巡查任務(wù)之前需要無人機(jī)攜帶采集攝像頭進(jìn)行大范圍信息采集，針對某一震區(qū)事件，對該震區(qū)中7個較為嚴(yán)重的區(qū)域進(jìn)行行巡查，假設(shè)7個重點(diǎn)震區(qū)都是以半徑為10 km（并記為S）的圓形區(qū)域，并標(biāo)記出區(qū)域S中的感興趣區(qū)域以內(nèi)的災(zāi)情，建立巡查時間模型，災(zāi)區(qū)感興區(qū)域如圖7 所示。每個重點(diǎn)區(qū)域海拔低于3 000 m的區(qū)域面積理論所需巡查時間為tj′,S′ 為每個重點(diǎn)區(qū)域海拔低于 3 000 m 的感興趣區(qū)域面積，Sj為每個重點(diǎn)區(qū)域面積(j=A,B,C,D,E,F,G)，ts為無人機(jī)巡查單位面積所需時間，具體表達(dá)式如式（8）所示：

圖7 感興趣區(qū)域

2.3 航跡路徑代價函數(shù)

由于在無人機(jī)航跡搜索過程中，g(n)與h(n)對航跡的評估代價并不相同[12]，故采用加權(quán)評估的方法，通過仿真實驗合理設(shè)定不同的權(quán)重系數(shù)ω1、ω2(ω1+ω2=1)；巡查無人機(jī)在執(zhí)行任務(wù)期間，為保證在安全距離平穩(wěn)飛行，將飛行高度作為重要考慮因素之一，因此，將地形威脅程度Tm，大氣威脅程度Tw，飛行高度代價Th引入到實際代價函數(shù)g(n)中，同樣設(shè)定ω3、ω4、ω5(ω3+ω4+ω5=1)進(jìn)行約束，啟發(fā)函數(shù)h(n)表示無人機(jī)通過蛇形割圓法到達(dá)目標(biāo)節(jié)點(diǎn)的預(yù)計軌跡路線距離，具體表達(dá)式為：

3 仿真結(jié)果與分析

3.1 航跡規(guī)劃環(huán)境模型

本文仿真實驗所使用的計算機(jī)操作系統(tǒng)為Windows 10專業(yè)版，開發(fā)環(huán)境為MATLAB 2016b，所使用的數(shù)據(jù)均來自中國地震臺網(wǎng)。假設(shè)無人機(jī)垂直方向的爬升角度在-15°至+15°范圍中，飛行安全距離需大于50 m，垂直方向最大飛行距離為5 000 m，無人機(jī)巡查任務(wù)從基地H（110，0）（單位：km）處派出開始，到完成巡查任務(wù)返回到基地為止，巡查任務(wù)期間，在巡查視線不被障礙物阻擋基礎(chǔ)上，以及從災(zāi)區(qū)水平地面任意點(diǎn)觀測無人機(jī)的最適仰角要小于60°，則該點(diǎn)被視為巡查點(diǎn)，要求在4小時內(nèi)完成巡查海拔3 000 m以下災(zāi)區(qū)，通過改進(jìn)的A*算法優(yōu)化完成任務(wù)的無人機(jī)最小派出量，提高災(zāi)區(qū)巡查覆蓋率，表1為巡查感興趣區(qū)域所需時間。

表1 巡查各感興趣區(qū)域所需時間h

災(zāi)后震區(qū)共有7個重點(diǎn)區(qū)域中心，且給定一個無人機(jī)基地H，將這8 個位置點(diǎn)的每兩點(diǎn)之間構(gòu)成一段飛行軌跡，每段距離通過位置點(diǎn)坐標(biāo)即可求出，由于無人機(jī)飛行速度恒定，其任意兩個位置點(diǎn)之間單程時間亦可算出，距離及時間如表2所示結(jié)果。

表2 任意兩點(diǎn)距離及時間

圖8 9架無人機(jī)巡查路線圖

3.2 改進(jìn)A＊算法搜索路徑結(jié)果

相比于傳統(tǒng)的A*算法，本文改進(jìn)的A*算法先是通過蛇形割圓法對巡查區(qū)域進(jìn)行飛行路線規(guī)劃，并通過提取感興趣區(qū)域方式選擇搜索方向，結(jié)合巡查各重點(diǎn)區(qū)域所需時間以及重點(diǎn)區(qū)域中心、基地各兩點(diǎn)之間距離和單程飛行時間，得出如表3所示無人機(jī)飛行路線說明。

從表3 可以得出至少需要9 架無人機(jī)執(zhí)行此任務(wù)，現(xiàn)將9架無人機(jī)的飛行路線用不同顏色進(jìn)行表示如圖8（a）～（f）所示。

3.3 求解發(fā)現(xiàn)次生災(zāi)害巡查方案

次生災(zāi)害是震區(qū)常見現(xiàn)象，為了避免次生災(zāi)害造成二次災(zāi)害，制定使用無人機(jī)在震區(qū)海拔不高于4 000 m的震區(qū)（不限定在重點(diǎn)震區(qū)S）上空巡邏（假設(shè)無人機(jī)巡查速度不變）的方案，被巡查區(qū)域為藍(lán)色區(qū)域如圖9所示。

以無人機(jī)為中心，在起始點(diǎn)將周圍①～⑧的點(diǎn)作為待擴(kuò)展的方向點(diǎn)，依次判斷8個方向是否滿足以下3個條件：（1）非山體；（2）非震區(qū)邊界；（3）該點(diǎn)未被巡查過。如果滿足這3 個條件，則無人機(jī)向該擴(kuò)展方向繼續(xù)巡查，經(jīng)過多次訓(xùn)練，得出最優(yōu)飛行規(guī)則模型如圖10所示。

圖9 震區(qū)海拔高度低于4 000 m區(qū)域（紫色部分）

圖10 無人機(jī)飛行規(guī)則模型示意圖

考慮到無人機(jī)續(xù)航問題，無人機(jī)從巡查任務(wù)開始到返回基地H 最大續(xù)航時間為8 h 時，無人機(jī)可正常返回基地，基于以上無人機(jī)巡查要求，巡航直至將震區(qū)海拔高度低于4 000 m區(qū)域均巡查到，經(jīng)目標(biāo)模型計算，震區(qū)海拔高度低于4 000 m 區(qū)域完全巡查一次需要39 架次無人機(jī)，覆蓋面范圍圖如圖11所示。

對比傳統(tǒng)A*算法，驗證改進(jìn)A*算法性能優(yōu)良，通過將拓展節(jié)點(diǎn)數(shù)與巡查時間轉(zhuǎn)化為面積覆蓋率的指標(biāo)進(jìn)行評估，所謂拓展節(jié)點(diǎn)數(shù)與覆蓋率反應(yīng)的就是無人機(jī)巡航效果，如式（12）所示：

圖11 9架無人機(jī)巡航覆蓋面積范圍圖

通過將上述表1 無人機(jī)飛行感興趣區(qū)域時間代入模型，計算得出本文算法的覆蓋率為88.96%，拓展節(jié)點(diǎn)數(shù)由52 330降至15 324個，文中方法在無人機(jī)航跡規(guī)劃的巡查性能性上具有重要的實際意義。

3.4 生命跡象探測

為了加快救援速度，將地震帶來的傷害降到最低，需要無人機(jī)搭載生命探測裝置來探測震區(qū)災(zāi)民生命的跡象，給救援隊伍提供準(zhǔn)確的災(zāi)民定位信息，擬從基地H（110，0），J（110，55）（單位：km）處各派出15 架無人機(jī)完成巡查任務(wù)，以合理分配無人機(jī)的數(shù)量和最短搜索時間為基礎(chǔ)，優(yōu)化出最優(yōu)的飛行軌跡，從而提高無人機(jī)搜索災(zāi)民的效率。

通過將震區(qū)山體進(jìn)行等海拔分層處理，計算巡查每層所需時間，將30架無人機(jī)合理分配到巡查區(qū)域，仿真軟件將海拔3 000 m 以下區(qū)域篩選出，并將全區(qū)域山體進(jìn)行分層掃描，得到2、3、4 層高面分層區(qū)域圖如圖12（a）～（c）所示。

圖12 山體分2層、3層、4層等高面示意圖

同理前文災(zāi)區(qū)巡查面積示意圖，將無人機(jī)在巡查處到分層海拔層面積投影作為無人機(jī)巡查的單位面積，計算無人機(jī)巡查每個等海拔層面所需時間，山體分3層時無人機(jī)巡查每個等海拔層面所需時間如表4。

表4 山體2、3、4層時巡查每個等海拔層面所需時間

當(dāng)震區(qū)山體分為2層時，計算得知無人機(jī)巡查2 059 m海拔層面需要51 h，巡查3 000 m 海拔層面需要369 h。題中擬派出30 架無人機(jī)，每架無人機(jī)的最大續(xù)航時間為8 h，因此一共最多有240 h 可以用來巡查，小于震區(qū)山體分為2 層時所需巡查時間，故按2 層分割山體海拔并不能完成此巡查任務(wù)，不采取此分層次數(shù)；當(dāng)震區(qū)山體分為4 層時，相鄰兩層交叉覆蓋面積太大，無人機(jī)巡查效率大大降低，且延長了巡查時間，故不采取此分層次數(shù)；則只有分3層方案符合實際規(guī)劃需求。

為使第一架執(zhí)行任務(wù)無人機(jī)從基地派出到最后一架完成任務(wù)的無人機(jī)飛回基地的整體任務(wù)時間盡量縮短，并規(guī)定每個層面被巡查時間不超過2～3 h，則完成最終任務(wù)的最短時間為每層均被巡查完的最大時間。合理分配H、J兩基地處各飛出的15架無人機(jī)，由于最高海拔層面積較大，需要無人機(jī)數(shù)量多，故將從J基地出發(fā)的15架無人機(jī)均派到最高海拔層巡查。此外，設(shè)從基地H處派往1 726 m海拔層面2架無人機(jī)，派往2 374 m海拔層面x架無人機(jī)，派往2 059 m 海拔層面y架無人機(jī)。則應(yīng)滿足：

通過上述約束條件，求解得出從基地H 處派往1 726 m 海拔層面2 架無人機(jī)，派往2 374 m 海拔層面9 架無人機(jī)，派往2 059 m 海拔層面4 架無人機(jī)，最短時間間隔為2.8 h，且其飛行路線也應(yīng)用問題一所建立的巡查路線模型程序求得，故不在此重述。

4 結(jié)束語

通過研究分析現(xiàn)有無人機(jī)在三維空間航跡規(guī)劃算法，針對目前無人機(jī)在三維空間航跡規(guī)劃使用A*算法存在派出無人機(jī)數(shù)量多，規(guī)劃軌跡長，巡查時間長的問題不足，提出了一種優(yōu)化A*的航跡算法。改進(jìn)的A*算法在某災(zāi)區(qū)巡查問題中得到實際驗證，文中算法所實現(xiàn)巡查覆蓋率達(dá)88.96%。能夠滿足災(zāi)區(qū)無人機(jī)巡查任務(wù)實際需求，本文所設(shè)計的優(yōu)化預(yù)測的航跡A*改進(jìn)算法在災(zāi)區(qū)巡查任務(wù)中具有重要意義。