沈秀娟,曹媛麗,衛(wèi) 連,胡 蝶

(1.曲靖師范學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，云南 曲靖 655011；2.曲靖市第二小學(xué)，云南 曲靖 655000)

0 引 言

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

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

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

1 問題提出

地震作為三大自然災(zāi)害之一,會(huì)對(duì)人類社會(huì)生活造成極大影響,比如人員傷亡和經(jīng)濟(jì)損失.地震后,對(duì)受傷、被困人員的搜救是一種高難度、高風(fēng)險(xiǎn)的行為,且不能完全保證實(shí)施搜救人員的生命安全.如果不能在一定時(shí)間內(nèi)找到受傷嚴(yán)重的待救人員,可能會(huì)錯(cuò)過最佳醫(yī)治時(shí)間,致使其殘疾或傷亡.傳統(tǒng)的震后救援方案是由施救人員和搜救犬根據(jù)先前經(jīng)驗(yàn)結(jié)合當(dāng)?shù)氐匦?、人口分布進(jìn)行施救,針對(duì)性不強(qiáng),搜救效率低.近年來,無人機(jī)在震后救災(zāi)時(shí)的應(yīng)用使得施救效率提高和人員傷亡率降低,然而搜救團(tuán)隊(duì)的無人機(jī)數(shù)量是有限的.因此,需要對(duì)無人機(jī)協(xié)同搜索方案進(jìn)行設(shè)計(jì).

經(jīng)過調(diào)查知道某地的搜救團(tuán)隊(duì)擁有2架偵察型無人機(jī),該無人機(jī)搭載合成孔徑雷達(dá)、航拍CCD相機(jī)等設(shè)備且具有航程遠(yuǎn)、留空時(shí)間長、環(huán)境適應(yīng)性強(qiáng)等特點(diǎn),可在斷電、斷網(wǎng)等極端災(zāi)害條件下,對(duì)目標(biāo)區(qū)域進(jìn)行成像,完成多譜段災(zāi)害現(xiàn)場(chǎng)探查.其性能如表1所示.

表1 無人機(jī)性能參數(shù)

本文收集該地以及其周圍市、縣所有的鎮(zhèn)(鄉(xiāng))、村(社區(qū))的地理位置坐標(biāo)和相應(yīng)人口數(shù)據(jù)進(jìn)行實(shí)驗(yàn)?zāi)M.圖1是根據(jù)所收集數(shù)據(jù)繪制的人口居住分布圖,圖中的黑色五角星表示市或縣,紅色三角形表示鎮(zhèn)(鄉(xiāng)),藍(lán)色圓圈表示村(社區(qū)).

圖1 觀測(cè)震區(qū)的人口居住分布圖

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

圖2 觀測(cè)震區(qū)人口分布熱力圖

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

2 建立模型

2.1 模型假設(shè)

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

(2)假設(shè)無人機(jī)在飛行的過程中工作狀態(tài)保持穩(wěn)定,不受地震后磁場(chǎng)、重力和天氣異常等情況影響.

(3)假設(shè)重傷及被困人員在地震后處于不動(dòng)或小范圍移動(dòng)狀態(tài),其移動(dòng)范圍可以忽略不計(jì).

2.2 模型建立

震后的黃金救援時(shí)間為72小時(shí),在此時(shí)間段內(nèi)待救人員的存活率極高.從發(fā)生地震、相關(guān)部門收到地震救援信息、救援團(tuán)隊(duì)趕往救災(zāi)地點(diǎn)、救援方案的設(shè)計(jì)到救援行動(dòng)的開展均需花費(fèi)一定的時(shí)間.因此,為了留出更多的救援時(shí)間,無人機(jī)巡航返回觀測(cè)震區(qū)情況的時(shí)間需要盡可能地縮短.綜合考慮各種因素后,認(rèn)為無人機(jī)的巡航時(shí)間應(yīng)設(shè)定為1小時(shí).

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

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

表2 軌跡圓Mi的圓心坐標(biāo)

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

按照模型假設(shè),T=0時(shí)刻無人機(jī)從機(jī)場(chǎng)出發(fā),此后每10秒成像一次.則在1小時(shí)內(nèi),每架無人機(jī)共成像360次(T=0秒時(shí)成像第1次,T=3600秒時(shí)成像第361次).

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

(1)

其中d是無人機(jī)與目標(biāo)位置的距離,α是機(jī)載雷達(dá)的檢測(cè)指數(shù).

根據(jù)分析,每架無人機(jī)在給定的1小時(shí)內(nèi),都可以成像361次,則2架無人機(jī)的所有成像結(jié)果能夠發(fā)現(xiàn)某個(gè)位置(xi,yj)上的目標(biāo)的概率為:

(2)

把繪制的觀測(cè)震區(qū)人口分布熱力圖(圖2)看成一個(gè)100×100的熱力矩陣,每個(gè)村落的人口數(shù)看成熱力值.以熱力值為指標(biāo)對(duì)每個(gè)1×1的區(qū)域進(jìn)行賦值,根據(jù)所賦數(shù)值的大小決定觀測(cè)的優(yōu)先級(jí)別.根據(jù)先前經(jīng)驗(yàn)和現(xiàn)實(shí)綜合研判,目標(biāo)出現(xiàn)在某個(gè)位置(xi,yj)的概率為:

(3)

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

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

(4)

式(1)、(2)、(3)、(4)就是所研究問題的數(shù)學(xué)模型.其中式(4)是目標(biāo)函數(shù),不同的搜索路線影響式(2)的取值.根據(jù)目標(biāo)函數(shù),可以更好地設(shè)計(jì)無人機(jī)的飛行路線,進(jìn)而達(dá)到提高抗震救災(zāi)效率的目的.

3 搜索策略

在求解無人機(jī)飛行路線的目標(biāo)搜索概率之前需要找出無人機(jī)所有可行的飛行路徑.觀測(cè)震區(qū)已經(jīng)用“軌跡圓”覆蓋,無人機(jī)按照軌跡圓的圓心連線進(jìn)行搜索飛行,相鄰圓心之間的連線實(shí)質(zhì)上構(gòu)成了一幅帶權(quán)值的無向圖.為了使找到的無人機(jī)的飛行路徑更加準(zhǔn)確,在進(jìn)行路徑搜索之前先根據(jù)軌跡圓覆蓋圖的信息建立鄰接矩陣作為輔助工具.鄰接矩陣的建立過程如下所示:

假設(shè)F表示某個(gè)無向圖,根據(jù)F的各個(gè)頂點(diǎn)之間是否可以直接連接,構(gòu)造一個(gè)矩陣,1表示可以直接連接,0表示不能直接連接,其嚴(yán)格的數(shù)學(xué)定義如下:

以圖4為例,進(jìn)一步說明鄰接矩陣的構(gòu)造過程:

圖4 無向圖的鄰接矩陣構(gòu)建示例圖

在鄰接矩陣的基礎(chǔ)上,如果不對(duì)無人機(jī)求解飛行路徑的條件進(jìn)行約束,那么路徑的數(shù)量將會(huì)難以估量,導(dǎo)致模型求解難度提升.

為了找出適合的路徑搜索算法,決定開展實(shí)驗(yàn)?zāi)M.經(jīng)過對(duì)多種已知路徑算法進(jìn)行嘗試,發(fā)現(xiàn)其結(jié)果都很難達(dá)到預(yù)期要求.借鑒相關(guān)文獻(xiàn)[11,12],利用深度優(yōu)先搜索算法和生成樹算法的特點(diǎn),對(duì)其進(jìn)行改進(jìn),得到了一種新的路徑算法.

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

圖5 第一步算法流程圖

圖6 第二步算法流程圖

Step1:輸入起點(diǎn)和步數(shù);

Step2:將圖轉(zhuǎn)換為鄰接矩陣形式表示,并用二維數(shù)組存儲(chǔ);

Step3:從起點(diǎn)開始,從鄰接矩陣遍歷與起點(diǎn)相鄰的所有通路節(jié)點(diǎn),并存儲(chǔ)編號(hào);

Step4:遍歷上一步的節(jié)點(diǎn),找出與該節(jié)點(diǎn)相鄰的所有通路節(jié)點(diǎn),并判斷是否有路徑中已存儲(chǔ)的節(jié)點(diǎn),如果有則丟棄,否則存儲(chǔ)該節(jié)點(diǎn)編號(hào);

Step5:判斷是否達(dá)到指定步數(shù),如果達(dá)到,轉(zhuǎn)到Step6,否則將轉(zhuǎn)到Step4;

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

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

Step2:設(shè)定路徑數(shù)n和路徑組合數(shù)N;

Step3:計(jì)算每條通路的權(quán)重;

Step4:根據(jù)路徑數(shù)n進(jìn)行路徑組合,并計(jì)算每個(gè)路徑組合的權(quán)重;

Step5:對(duì)路徑組合按權(quán)重從大到小進(jìn)行排序;

Step6:輸出前N個(gè)路徑組合及其權(quán)重.

4 模型求解

無人機(jī)續(xù)航時(shí)間為10小時(shí),可保證1小時(shí)內(nèi)搜索任務(wù)結(jié)束后順利返航,無需考慮中途返場(chǎng)補(bǔ)能情況.已知無人機(jī)在1小時(shí)內(nèi)可飛行130千米(即大概8個(gè)軌跡圓),決定以此為約束條件.

根據(jù)觀測(cè)震區(qū)軌跡圓覆蓋圖(圖3)建立鄰接矩陣,在鄰接矩陣基礎(chǔ)上,采用第一步算法對(duì)所有滿足約束條件的飛行路徑進(jìn)行編程求解,實(shí)現(xiàn)了從給定頂點(diǎn)出發(fā)在指定步數(shù)約束下找到所有通路.根據(jù)程序運(yùn)行結(jié)果得知符合無人機(jī)通行規(guī)則的路線一共有638條.

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

圖7 無人機(jī)最優(yōu)飛行路徑組合圖

從計(jì)算結(jié)果看,路徑搜索算法列出所有滿足約束條件的搜索路徑中,發(fā)現(xiàn)目標(biāo)概率較高的路線主要覆蓋人口密集的居民區(qū),與實(shí)際相符.在考慮無人機(jī)的數(shù)量和各種約束條件下,無人機(jī)根據(jù)路徑搜索算法所得到的最優(yōu)路徑組合即搜索目標(biāo)概率最大的飛行路徑,可以在給定時(shí)間內(nèi)最大限度地獲取災(zāi)情現(xiàn)場(chǎng)信息使救援行動(dòng)的開展更加科學(xué)高效.

5 結(jié) 語

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