一種面向地震場景的無人機協同搜索路徑規劃算法

沈秀娟,曹媛麗,衛 連,胡 蝶

(1.曲靖師范學院 數學與統計學院，云南 曲靖 655011；2.曲靖市第二小學，云南 曲靖 655000)

0 引 言

地震作為一種突發性、規模性的自然災害,對人類的生產生活造成嚴重威脅.如果發生在人口密集的區域,往往會造成巨大的人員傷亡和經濟損失.面對震后的危險性及不確定性,緊靠傳統的人工救援方法無法快速有效且安全地解決救援問題.隨著科學技術的進步,無人機的研發日趨成熟.面對震后場景,采用群體無人機協同搜索救援,可以提高救援效率[1].震后情況復雜,如何科學合理地利用無人機輔助救援行動,制定最佳的無人機協同搜索路徑規劃方案顯得尤為重要[2].

由于無人機用途廣泛且投入成本低,對于無人機的應用研究已成為國內外學者研究的熱點話題之一.在國外方面,Jotrao 等人提出混合整數規劃(MIP)方法和模擬退火啟發式算法來研究在指定的燃料限制內無人機怎樣設計飛行路徑可獲取更多的信息[3].Wang等人基于非支配排序遺傳算法,提出了一種大規模約束的無人機路徑規劃智能算法[4].Lu等人利用蒙特卡洛樹搜索和粒子群算法提出了一種充分利用智能離散和連續搜索算法的星載分布式軌跡規劃統一框架,并將其運用到多無人機協同航跡規劃和避障中進行仿真實驗[5].Luo等人針對復雜環境下多無人機協同目標搜索問題提出了一種閉環路徑規劃方法[6].國內學者也積極進行了探索和研究:駱文冠等人考慮路徑長度、風險成本、高度成本和平滑程度四個指標,建立應急無人機路徑規劃模型,提出一種基于強化學習的布谷鳥搜索算法對模型求解[7].楊春寧等人基于Voronoi圖構型的多無人機區域覆蓋模型和概率地圖信息更新融合的協同搜索策略對未知區域無人機協同搜索方法及效率進行分析[8].劉培賓、盛懷潔以“全時域視場覆蓋”為指標,結合一致性算法解決反輻射無人機協同搜索問題[9].王洪民等人針對多無人機協同搜索追蹤區域內多運動目標問題,考慮無人機的傳感器與避撞等約束和目標隨機運動等特征,提出以垂線搜索為基礎的多無人機協同搜索追蹤策略[10].上述研究對多無人機協同控制方案和航行路線進行規劃和設計時大都采用聚類、遺傳算法、粒子群算法、神經網絡算法等,在操作過程中不易理解,且這些算法在實踐過程中或多或少都存在一些不足,不能廣泛應用到現實生活中.

為了增強無人機協同搜索路徑規劃算法的實用性,文章考慮采用操作簡單且易理解的深度優先搜索算法,并用生成樹子樹的方式對路徑進行存儲.然而,傳統的深度優先搜索算法[11]是從一個節點沿著一條路徑一直搜索下去,進行深度優先遍歷,每個節點只能被訪問一次.雖然該方法可以窮盡所有的節點,但它在路徑搜索中費時費力,不夠高效.同樣,傳統的生成樹算法[12]可以系統地訪問到圖中所有頂點,但生成樹的不唯一性,也增加了搜索的難度.本文在綜合考慮各種利弊之后,提出了一種基于深度優先搜索和生成樹算法的改進的路徑規劃策略,對多無人機協同的航行軌跡進行設計.該策略在深度優先遍歷過程中嵌入目標函數和代價函數并對生成樹進行減枝優化,同時對生成樹子樹所存儲的路徑以一定的權重計算目標搜索概率,用搜索概率的大小對子樹進行編號排序,使得路徑搜索算法在滿足約束條件的情況下更加精準高效.該方法為今后無人機在抗震救災過程中的協同搜索航行方案提供了一種新的思路.

1 問題提出

地震作為三大自然災害之一,會對人類社會生活造成極大影響,比如人員傷亡和經濟損失.地震后,對受傷、被困人員的搜救是一種高難度、高風險的行為,且不能完全保證實施搜救人員的生命安全.如果不能在一定時間內找到受傷嚴重的待救人員,可能會錯過最佳醫治時間,致使其殘疾或傷亡.傳統的震后救援方案是由施救人員和搜救犬根據先前經驗結合當地地形、人口分布進行施救,針對性不強,搜救效率低.近年來,無人機在震后救災時的應用使得施救效率提高和人員傷亡率降低,然而搜救團隊的無人機數量是有限的.因此,需要對無人機協同搜索方案進行設計.

經過調查知道某地的搜救團隊擁有2架偵察型無人機,該無人機搭載合成孔徑雷達、航拍CCD相機等設備且具有航程遠、留空時間長、環境適應性強等特點,可在斷電、斷網等極端災害條件下,對目標區域進行成像,完成多譜段災害現場探查.其性能如表1所示.

表1 無人機性能參數

本文收集該地以及其周圍市、縣所有的鎮(鄉)、村(社區)的地理位置坐標和相應人口數據進行實驗模擬.圖1是根據所收集數據繪制的人口居住分布圖,圖中的黑色五角星表示市或縣,紅色三角形表示鎮(鄉),藍色圓圈表示村(社區).

圖1 觀測震區的人口居住分布圖

由于同一觀測震區的人口分布和震后受損程度不一樣,為了更好地進行觀測,本文根據損失最小和獲救人數最多原則,決定以人口數量分布為主要參考因素,以村(社區)為基本單位對震區進行劃分.圖2是進行劃分后的人口分布熱力圖,圖中藍色圓圈表示居住人口在0～1 000以內的村落、綠色圓圈表示居住人口在1 000～2 000以內的村落,紅色圓圈表示居住人口在2 000～3 000以內的村落,黑色圓圈表示居住人口在3 000以上的村落.

圖2 觀測震區人口分布熱力圖

不同顏色的圓圈決定了觀測順序和觀測次數的不同.黑色圓圈的分布地為重點觀測區域,紅色圓圈為次重點觀測區域,綠色圓圈為一般重點觀測區域,藍色圓圈為一般觀測區域.觀察圖2可知,觀測震區的右下方人口分布非常密集,觀測震區的中上方和左下方有較多人口分布.由于震后救災時間緊張,而重點觀測區域分布不集中,同時有無人區的存在,我們需要考慮怎樣設計無人機的飛行路線使得無人機在最短時間內巡視重點觀測區域時兼顧其他觀測區域,返回更多的災情信息.

2 建立模型

2.1 模型假設

(1)假設無人機從機場起飛前已充分考慮震區的特殊地形地勢并設計出合理的飛行高度,起飛后都是按該高度以勻速對震區進行巡航.

(2)假設無人機在飛行的過程中工作狀態保持穩定,不受地震后磁場、重力和天氣異常等情況影響.

(3)假設重傷及被困人員在地震后處于不動或小范圍移動狀態,其移動范圍可以忽略不計.

2.2 模型建立

震后的黃金救援時間為72小時,在此時間段內待救人員的存活率極高.從發生地震、相關部門收到地震救援信息、救援團隊趕往救災地點、救援方案的設計到救援行動的開展均需花費一定的時間.因此,為了留出更多的救援時間,無人機巡航返回觀測震區情況的時間需要盡可能地縮短.綜合考慮各種因素后,認為無人機的巡航時間應設定為1小時.

在充分考慮無人機的數量、性能參數等約束條件下,以救災型無人機的起飛點為圓心,以最大探測距離8千米為半徑繪制出無人機的探測范圍(如圖3中的圓1).為了對觀測震區進行科學合理的巡查和航行軌跡設計的便利,以起始圓為基準,用一系列平行且相切的圓對觀測震區進行全覆蓋,這些平行且相切的圓稱為“軌跡圓”.圖3是軌跡圓對觀測震區的覆蓋情況圖.

由圖3可知,覆蓋觀測震區需要32個互不重疊的軌跡圓.按照從上到下、從左到右的順序,依次將32個軌跡圓的圓心坐標記為Mi(xi,yi),i=1,2,…,32.根據軌跡圓的命名規則,將其中的第i個軌跡圓稱為圓Mi,其圓心坐標如表2所示.

表2 軌跡圓Mi的圓心坐標

所建立的模型假設無人機的飛行軌跡是沿著相鄰(相切)的軌跡圓的圓心直線飛行.無人機的巡航速度是130千米/小時,兩個相切的軌跡圓的圓心Mi(xi,yi)和Mj(xi,yi)之間的距離是16千米,因此,搜尋時間內無人機大概可以飛過8個相鄰的圓,加上起飛時機場位置所在的圓,將這9個圓循序依次排列起來,并將其稱為該飛機的飛行路線.例如:第一架無人機U1從機場M1起飛,沿著相鄰的圓,依次飛過M1、M2、M3、M6、M7、M12、M18、M24、M25,則記G1(M1、M2、M3、M6、M7、M12、M18、M24、M25)為U1的一條飛行路線.

按照模型假設,T=0時刻無人機從機場出發,此后每10秒成像一次.則在1小時內,每架無人機共成像360次(T=0秒時成像第1次,T=3600秒時成像第361次).

通常,無人機離目標越近,拍攝次數越多,發現目標的概率越大.定義qu,i,j,k,其中u=1,2表示無人機架次,i=1,…,100表示某位置的橫坐標,j=1,…,100表示某位置的縱坐標,k=1,…,361表示成像的次數.例如q1,75,60,77表示第一架無人機第77次成像時發現位置為(75,60)處的目標的概率.影像中發現目標的概率為:

(1)

其中d是無人機與目標位置的距離,α是機載雷達的檢測指數.

根據分析,每架無人機在給定的1小時內,都可以成像361次,則2架無人機的所有成像結果能夠發現某個位置(xi,yj)上的目標的概率為:

(2)

把繪制的觀測震區人口分布熱力圖(圖2)看成一個100×100的熱力矩陣,每個村落的人口數看成熱力值.以熱力值為指標對每個1×1的區域進行賦值,根據所賦數值的大小決定觀測的優先級別.根據先前經驗和現實綜合研判,目標出現在某個位置(xi,yj)的概率為:

(3)

其中hij表示位置(xi,yj)的熱力值.

結合式(2)和式(3),可以得到某條搜索路線的方案能夠找到目標的概率為:

(4)

式(1)、(2)、(3)、(4)就是所研究問題的數學模型.其中式(4)是目標函數,不同的搜索路線影響式(2)的取值.根據目標函數,可以更好地設計無人機的飛行路線,進而達到提高抗震救災效率的目的.

3 搜索策略

在求解無人機飛行路線的目標搜索概率之前需要找出無人機所有可行的飛行路徑.觀測震區已經用“軌跡圓”覆蓋,無人機按照軌跡圓的圓心連線進行搜索飛行,相鄰圓心之間的連線實質上構成了一幅帶權值的無向圖.為了使找到的無人機的飛行路徑更加準確,在進行路徑搜索之前先根據軌跡圓覆蓋圖的信息建立鄰接矩陣作為輔助工具.鄰接矩陣的建立過程如下所示:

假設F表示某個無向圖,根據F的各個頂點之間是否可以直接連接,構造一個矩陣,1表示可以直接連接,0表示不能直接連接,其嚴格的數學定義如下:

以圖4為例,進一步說明鄰接矩陣的構造過程:

圖4 無向圖的鄰接矩陣構建示例圖

在鄰接矩陣的基礎上,如果不對無人機求解飛行路徑的條件進行約束,那么路徑的數量將會難以估量,導致模型求解難度提升.

為了找出適合的路徑搜索算法,決定開展實驗模擬.經過對多種已知路徑算法進行嘗試,發現其結果都很難達到預期要求.借鑒相關文獻[11,12],利用深度優先搜索算法和生成樹算法的特點,對其進行改進,得到了一種新的路徑算法.

算法分為兩步,第一步用于求解所有滿足約束條件的通路,第二步用于求出最優的路徑組合.使用者可根據自己的需求決定是否進行第二步算法.第一步,對深度優先搜索的每一個路徑點選擇都根據人口熱力值的分布情況賦予不同權值,然后根據鄰接矩陣、目標函數和所設置的步數條件判斷從上一個路徑點到下一個路徑點是否可以通行,確認可通行后,有序保存該路徑節點.為了保證所得路徑各不相同,算法通過代價函數在每一次循環迭代中都對鄰接矩陣實時更新.最后把每一條篩選出來的路徑都以生成樹子樹的形式進行存儲,形成滿足約束條件的所有通路.第二步,根據第一步所得的所有滿足約束條件的通路,算法可以任意指定由多少條路徑進行組合,最終根據使用者設置的所需組合數留下權重最大即搜索概率較大的組合.留下的路徑組合即為滿足條件的最優路徑組合.第一、二步算法流程圖見圖5、圖6.算法的具體步驟如下:

圖5 第一步算法流程圖

圖6 第二步算法流程圖

Step1:輸入起點和步數;

Step2:將圖轉換為鄰接矩陣形式表示,并用二維數組存儲;

Step3:從起點開始,從鄰接矩陣遍歷與起點相鄰的所有通路節點,并存儲編號;

Step4:遍歷上一步的節點,找出與該節點相鄰的所有通路節點,并判斷是否有路徑中已存儲的節點,如果有則丟棄,否則存儲該節點編號;

Step5:判斷是否達到指定步數,如果達到,轉到Step6,否則將轉到Step4;

Step6:輸出所有滿足指定步數的路徑.

Step1:輸入滿足約束條件的所有通路;

Step2:設定路徑數n和路徑組合數N;

Step3:計算每條通路的權重;

Step4:根據路徑數n進行路徑組合,并計算每個路徑組合的權重;

Step5:對路徑組合按權重從大到小進行排序;

Step6:輸出前N個路徑組合及其權重.

4 模型求解

無人機續航時間為10小時,可保證1小時內搜索任務結束后順利返航,無需考慮中途返場補能情況.已知無人機在1小時內可飛行130千米(即大概8個軌跡圓),決定以此為約束條件.

根據觀測震區軌跡圓覆蓋圖(圖3)建立鄰接矩陣,在鄰接矩陣基礎上,采用第一步算法對所有滿足約束條件的飛行路徑進行編程求解,實現了從給定頂點出發在指定步數約束下找到所有通路.根據程序運行結果得知符合無人機通行規則的路線一共有638條.

已知有兩架無人機可供我們使用,采用第二步算法對無人機可能的飛行路線組合進行編程求解.根據程序運行結果得知兩架無人機可能的飛行路線組合共有:638×638個.為了設計出符合預期效果的無人機巡航方案,表3列出了目標搜索概率較大的前十種路徑組合,發現最大搜索概率為0.73,搜索概率最大的路徑組合的飛行路線如圖7所示.

圖7 無人機最優飛行路徑組合圖

從計算結果看,路徑搜索算法列出所有滿足約束條件的搜索路徑中,發現目標概率較高的路線主要覆蓋人口密集的居民區,與實際相符.在考慮無人機的數量和各種約束條件下,無人機根據路徑搜索算法所得到的最優路徑組合即搜索目標概率最大的飛行路徑,可以在給定時間內最大限度地獲取災情現場信息使救援行動的開展更加科學高效.

5 結 語

地震后,救援時間每拖延一分,被困人員面臨的生命威脅便加重一分.救災型無人機在震后救援中的應用使得施救團隊充分了解災情現場信息,能夠制定出合理的救援方案,提高救援效率.但是怎樣使用無人機能夠更好地在復雜情況下實施救援,需要制定一個科學可行的方案.多無人機協同搜索路徑規劃方案的設計往往受無人機性能、既定飛行時間、搜索目標等因素的影響.針對多無人機協同搜索最優路徑組合的求解,本文把深度優先搜索算法和生成樹算法結合起來并對其進行改進,得到了一種新的路徑搜索算法.算法首先對深度優先搜索的每一個節點都根據給定的數據賦予一定的權值;然后按指定步數、代價函數和目標函數進行路徑節點的選擇,得出所有符合要求的合理路徑;最后根據指定路徑組合數和無人機的架數輸出權重最大即搜索概率最大的路徑組合.通過仿真模擬實驗,驗證了算法的可行性與合理性,為以后救災過程中多無人機協同搜索路徑規劃問題提供了新的思路.