一種面向地震場(chǎng)景的無(wú)人機(jī)協(xié)同搜索路徑規(guī)劃算法

沈秀娟,曹媛麗,衛(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)的人工救援方法無(wú)法快速有效且安全地解決救援問(wèn)題.隨著科學(xué)技術(shù)的進(jìn)步,無(wú)人機(jī)的研發(fā)日趨成熟.面對(duì)震后場(chǎng)景,采用群體無(wú)人機(jī)協(xié)同搜索救援,可以提高救援效率[1].震后情況復(fù)雜,如何科學(xué)合理地利用無(wú)人機(jī)輔助救援行動(dòng),制定最佳的無(wú)人機(jī)協(xié)同搜索路徑規(guī)劃方案顯得尤為重要[2].

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

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

1 問(wèn)題提出

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

經(jīng)過(guò)調(diào)查知道某地的搜救團(tuán)隊(duì)擁有2架偵察型無(wú)人機(jī),該無(wú)人機(jī)搭載合成孔徑雷達(dá)、航拍CCD相機(jī)等設(shè)備且具有航程遠(yuǎn)、留空時(shí)間長(zhǎng)、環(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 無(wú)人機(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í)有無(wú)人區(qū)的存在,我們需要考慮怎樣設(shè)計(jì)無(wú)人機(jī)的飛行路線使得無(wú)人機(jī)在最短時(shí)間內(nèi)巡視重點(diǎn)觀測(cè)區(qū)域時(shí)兼顧其他觀測(cè)區(qū)域,返回更多的災(zāi)情信息.

2 建立模型

2.1 模型假設(shè)

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

(2)假設(shè)無(wú)人機(jī)在飛行的過(guò)程中工作狀態(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)的開(kāi)展均需花費(fèi)一定的時(shí)間.因此,為了留出更多的救援時(shí)間,無(wú)人機(jī)巡航返回觀測(cè)震區(qū)情況的時(shí)間需要盡可能地縮短.綜合考慮各種因素后,認(rèn)為無(wú)人機(jī)的巡航時(shí)間應(yīng)設(shè)定為1小時(shí).

在充分考慮無(wú)人機(jī)的數(shù)量、性能參數(shù)等約束條件下,以救災(zāi)型無(wú)人機(jī)的起飛點(diǎn)為圓心,以最大探測(cè)距離8千米為半徑繪制出無(wú)人機(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è)無(wú)人機(jī)的飛行軌跡是沿著相鄰(相切)的軌跡圓的圓心直線飛行.無(wú)人機(jī)的巡航速度是130千米/小時(shí),兩個(gè)相切的軌跡圓的圓心Mi(xi,yi)和Mj(xi,yi)之間的距離是16千米,因此,搜尋時(shí)間內(nèi)無(wú)人機(jī)大概可以飛過(guò)8個(gè)相鄰的圓,加上起飛時(shí)機(jī)場(chǎng)位置所在的圓,將這9個(gè)圓循序依次排列起來(lái),并將其稱為該飛機(jī)的飛行路線.例如:第一架無(wú)人機(jī)U1從機(jī)場(chǎng)M1起飛,沿著相鄰的圓,依次飛過(guò)M1、M2、M3、M6、M7、M12、M18、M24、M25,則記G1(M1、M2、M3、M6、M7、M12、M18、M24、M25)為U1的一條飛行路線.

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

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

(1)

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

根據(jù)分析,每架無(wú)人機(jī)在給定的1小時(shí)內(nèi),都可以成像361次,則2架無(wú)人機(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)就是所研究問(wèn)題的數(shù)學(xué)模型.其中式(4)是目標(biāo)函數(shù),不同的搜索路線影響式(2)的取值.根據(jù)目標(biāo)函數(shù),可以更好地設(shè)計(jì)無(wú)人機(jī)的飛行路線,進(jìn)而達(dá)到提高抗震救災(zāi)效率的目的.

3 搜索策略

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

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

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

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

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

為了找出適合的路徑搜索算法,決定開(kāi)展實(shí)驗(yàn)?zāi)M.經(jīng)過(guò)對(duì)多種已知路徑算法進(jìn)行嘗試,發(fā)現(xiàn)其結(jié)果都很難達(dá)到預(yù)期要求.借鑒相關(guān)文獻(xiàn)[11,12],利用深度優(yōu)先搜索算法和生成樹(shù)算法的特點(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).為了保證所得路徑各不相同,算法通過(guò)代價(jià)函數(shù)在每一次循環(huán)迭代中都對(duì)鄰接矩陣實(shí)時(shí)更新.最后把每一條篩選出來(lái)的路徑都以生成樹(shù)子樹(shù)的形式進(jìn)行存儲(chǔ),形成滿足約束條件的所有通路.第二步,根據(jù)第一步所得的所有滿足約束條件的通路,算法可以任意指定由多少條路徑進(jìn)行組合,最終根據(jù)使用者設(shè)置的所需組合數(shù)留下權(quán)重最大即搜索概率較大的組合.留下的路徑組合即為滿足條件的最優(yōu)路徑組合.第一、二步算法流程圖見(jiàn)圖5、圖6.算法的具體步驟如下:

圖5 第一步算法流程圖

圖6 第二步算法流程圖

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

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

Step3:從起點(diǎn)開(kāi)始,從鄰接矩陣遍歷與起點(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 模型求解

無(wú)人機(jī)續(xù)航時(shí)間為10小時(shí),可保證1小時(shí)內(nèi)搜索任務(wù)結(jié)束后順利返航,無(wú)需考慮中途返場(chǎng)補(bǔ)能情況.已知無(wú)人機(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é)果得知符合無(wú)人機(jī)通行規(guī)則的路線一共有638條.

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

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

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

5 結(jié) 語(yǔ)

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