救災無人機的優(yōu)化A＊航跡規(guī)劃算法

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

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

2.沈陽大學 信息工程學院，沈陽 110044

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

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

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

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

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

1.1 災情巡查

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

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

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

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

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

圖3 無人機巡查示意圖

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

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

圖4 無人機巡查單位面積路徑示意圖

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

1.2 地形與大氣威脅

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

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

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

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

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

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

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

圖6 大氣威脅示意圖

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

2.1 A＊算法基本思想

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

設定當下節(jié)點為n，其中f(n)是從出發(fā)點經過節(jié)點n到達目標點的預估代價，g(n)是在三維空間中從出發(fā)點到達目標節(jié)點n的實際代價，h(n)是從節(jié)點n到達目標節(jié)點的預計代價。

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

（1）將起始點存放到open表。

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

（3）如果當前節(jié)點與目的距離在最短飛行距離范圍內，轉至（4）。

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

（5）將當前節(jié)點設置為相鄰節(jié)點的父親點，加入open表，轉至步驟（2）。

（6）結束。

2.2 改進的A＊算法

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

圖7 感興趣區(qū)域

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

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

3 仿真結果與分析

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

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

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

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

表2 任意兩點距離及時間

圖8 9架無人機巡查路線圖

3.2 改進A＊算法搜索路徑結果

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

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

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

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

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

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

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

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

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

圖11 9架無人機巡航覆蓋面積范圍圖

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

3.4 生命跡象探測

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

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

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

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

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

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

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

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

4 結束語

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