面向無(wú)人機(jī)集群路徑規(guī)劃的智能優(yōu)化算法綜述

楊 旭,王 銳,張 濤

(國(guó)防科技大學(xué)系統(tǒng)工程學(xué)院,湖南長(zhǎng)沙 410073)

1 引言

隨著人工智能技術(shù)的迅猛發(fā)展,無(wú)人機(jī)(unmanned aerial vehicle,UAV)逐步朝著小型化、智能化方向發(fā)展,因其成本低、靈活性高、隱蔽性強(qiáng),被廣泛應(yīng)用于戰(zhàn)場(chǎng)偵察、聯(lián)合攻擊、應(yīng)急救援等行動(dòng),已成為未來(lái)智能化、無(wú)人化作戰(zhàn)的重要手段之一[1–2].鑒于單架無(wú)人機(jī)在續(xù)航能力、廣域偵察搜索等方面的局限性,多架無(wú)人機(jī)協(xié)同組成無(wú)人機(jī)集群(unmanned aerial vehicle swarm)執(zhí)行任務(wù)成為當(dāng)前無(wú)人機(jī)作戰(zhàn)應(yīng)用的重要模式[3].較之于單架無(wú)人機(jī),無(wú)人機(jī)集群具有明顯的規(guī)模優(yōu)勢(shì)、協(xié)同優(yōu)勢(shì)等[4],可有效提高任務(wù)完成的可靠性.然而,實(shí)現(xiàn)無(wú)人機(jī)集群高效協(xié)同的首要問(wèn)題,即是如何科學(xué)合理地為無(wú)人機(jī)集群進(jìn)行路徑規(guī)劃.

如圖1所示,當(dāng)前關(guān)于單架無(wú)人機(jī)路徑規(guī)劃的研究較多,然而面向無(wú)人機(jī)集群的路徑規(guī)劃研究則相對(duì)較少.不同于單無(wú)人機(jī)路徑規(guī)劃,無(wú)人機(jī)集群的路徑規(guī)劃除了考慮單機(jī)的可控飛行,各種威脅之外,還需考慮集群規(guī)模、功能結(jié)構(gòu)、協(xié)同方式等帶來(lái)的挑戰(zhàn),其本質(zhì)上是一個(gè)復(fù)雜的大規(guī)模約束多目標(biāo)優(yōu)化問(wèn)題.智能優(yōu)化算法因其對(duì)優(yōu)化問(wèn)題的性質(zhì)要求低、魯棒性高,而被廣泛應(yīng)用于求解路徑規(guī)劃問(wèn)題.

鑒于此,本文綜述了近些年面向無(wú)人機(jī)集群路徑規(guī)劃的智能優(yōu)化算法研究,首先介紹了無(wú)人機(jī)集群路徑規(guī)劃的基本模型,包括規(guī)劃空間表示、優(yōu)化目標(biāo)函數(shù)及約束條件等,其次闡述了基于不同智能優(yōu)化算法的無(wú)人機(jī)集群路徑規(guī)劃研究現(xiàn)狀、詳細(xì)對(duì)比分析了不同類型算法的優(yōu)勢(shì)與不足,最后對(duì)無(wú)人機(jī)集群路徑規(guī)劃研究進(jìn)行了展望.

圖1 無(wú)人機(jī)及無(wú)人機(jī)集群相關(guān)研究發(fā)展趨勢(shì)圖Fig.1 Numbers of researches about UAV and UAV swarm

2 無(wú)人機(jī)集群路徑規(guī)劃模型

路徑規(guī)劃是智能體自主完成任務(wù)的重要組成部分,要求在規(guī)劃空間中快速找到由多個(gè)線段或多個(gè)路徑點(diǎn)依次連接而成的最優(yōu)路徑.路徑表示常用兩種方式:一是由航速和航向構(gòu)成的時(shí)間序列(基于動(dòng)力學(xué));二是由空間位置坐標(biāo)構(gòu)成的時(shí)間序列(基于幾何學(xué)).無(wú)人機(jī)集群路徑規(guī)劃需要在一般路徑規(guī)劃模型的基礎(chǔ)上,進(jìn)一步綜合考慮無(wú)人機(jī)集群的環(huán)境約束、自身約束和集群內(nèi)約束.下面介紹路徑規(guī)劃中的3個(gè)要素:規(guī)劃空間、優(yōu)化目標(biāo)和約束條件.

2.1 規(guī)劃空間方法

路徑規(guī)劃無(wú)疑首先要對(duì)環(huán)境進(jìn)行建模,即構(gòu)造規(guī)劃空間,也稱為搜索空間.規(guī)劃空間是對(duì)實(shí)體環(huán)境的抽象,條件許可下,應(yīng)當(dāng)盡可能準(zhǔn)確、完整地將實(shí)體空間的信息映射到規(guī)劃空間中.實(shí)際應(yīng)用中,規(guī)劃空間是一般是三維[5–6],當(dāng)然,為簡(jiǎn)化問(wèn)題,一些研究也將空間簡(jiǎn)化為二維[7–10].常用的規(guī)劃空間表述方法有單元格法、路標(biāo)法和勢(shì)場(chǎng)法[11].

2.1.1 單元格法

單元格法是一種將空間按照合適的粒度劃分為獨(dú)立的單元并賦予相應(yīng)代價(jià)值的方法,主要包括網(wǎng)格法和單元樹(shù)法,二者的區(qū)別主要在于單元的大小是否相同.

圖2(a)描述了基于網(wǎng)格法的規(guī)劃空間,該方法使用大小相同的網(wǎng)格劃分二維環(huán)境空間,其中黑色幾何圖形表示障礙物.在三維條件下,可將平面網(wǎng)格變?yōu)榱⒎襟w.文獻(xiàn)[12–14]采用了網(wǎng)格法在三維空間下對(duì)環(huán)境進(jìn)行建模.文獻(xiàn)[15]基于網(wǎng)格法提出了一種降低高度尺寸的環(huán)境建模方法,實(shí)現(xiàn)了從三維到二維的轉(zhuǎn)換,大大減少了網(wǎng)格數(shù)量和大小.圖2(b)描述了采用單元樹(shù)法的二維規(guī)劃空間,該方法比網(wǎng)格法具有更強(qiáng)的環(huán)境適應(yīng)性,可以看出單元樹(shù)法中空間格的大小明顯不同.總體上,單元格法簡(jiǎn)單直觀、易于建模,但搜索空間較大,同時(shí)單元格的大小不易選取.

圖2 基于單元格法的規(guī)劃空間表示Fig.2 Illustration of cell method

2.1.2 路標(biāo)法

路標(biāo)法是一種按照一定的規(guī)則將空間表示成網(wǎng)絡(luò)圖的方法,如快速生成隨機(jī)樹(shù)法[16]、Voronoi圖法[17–18]和可視圖法[19–21].

Voronoi圖出于安全因素考慮要求規(guī)劃路徑和障礙物之間有一定的距離,把規(guī)劃空間劃分成若干個(gè)區(qū)域,每個(gè)區(qū)域只包含一個(gè)障礙物的邊緣,如圖3(a)所示.基于Voronoi圖法規(guī)劃空間能有效減少搜索空間,因此規(guī)劃速度快.同時(shí),該方法能夠找到威脅最小的路徑但該路徑不一定是最短的.在空間幾何建模中常采用Voronoi圖法,但該方法劃分粒度通常較大,可選路徑有限.

可視圖法,如圖3(b)所示,要求起始點(diǎn)、目標(biāo)點(diǎn)和障礙物的頂點(diǎn)之間的連線為“可視”,即不能穿過(guò)障礙物.總體而言,路標(biāo)法減小了搜索空間,但是精度較低.同時(shí),環(huán)境一旦發(fā)生變化,模型更新困難.

圖3 基于路標(biāo)法的規(guī)劃空間表示Fig.3 Landmark method

2.1.3 勢(shì)場(chǎng)法

勢(shì)場(chǎng)法是一種不依賴于圖形表示空間規(guī)劃方法.它將終點(diǎn)看做吸引源,產(chǎn)生吸引力,將障礙物、威脅等作為排斥源,產(chǎn)生排斥力,然后綜合無(wú)人機(jī)受力方向得到相關(guān)路徑.基于勢(shì)場(chǎng)法的路徑規(guī)劃便于求解,可應(yīng)用于二維和三維空間中,但是存在找不到路徑的問(wèn)題[22].

表1闡述了上述3類方法的優(yōu)缺點(diǎn).

表1 3類規(guī)劃空間方法對(duì)比Table 1 Comparison among ways of planning space

傳統(tǒng)的單元格法、勢(shì)場(chǎng)法需要對(duì)空間中的障礙物精確建模,當(dāng)環(huán)境中的障礙物較復(fù)雜且不規(guī)則時(shí),會(huì)極大地增加空間規(guī)劃難度.路標(biāo)法減少了空間規(guī)劃工作,常用于以安全指數(shù)最大化為目標(biāo)的路徑規(guī)劃問(wèn)題中,但是路徑規(guī)劃的精度較差于其他兩種方法.在無(wú)人機(jī)路徑規(guī)劃中,由于單元格法不受威脅限制且求解精度高,通常選用該方法劃分空間,通過(guò)包含起點(diǎn)和終點(diǎn)的坐標(biāo)點(diǎn)集合表示一條路徑.

2.2 目標(biāo)函數(shù)

無(wú)人機(jī)集群的路徑規(guī)劃通常需要針對(duì)不同任務(wù)需求或決策者的偏好構(gòu)建相應(yīng)的目標(biāo)函數(shù),一般使用飛行時(shí)間、飛行距離和威脅代價(jià)等作為目標(biāo)函數(shù),規(guī)劃模型可以是單目標(biāo)也可以是多目標(biāo),例如,文獻(xiàn)[23–24]采用滿足偵察覆蓋率下的路徑長(zhǎng)度最小為優(yōu)化目標(biāo);文獻(xiàn)[25]以偵察目標(biāo)數(shù)最大和所有UAV飛行距離總和最小構(gòu)建了兩目標(biāo)優(yōu)化模型;文獻(xiàn)[26]以暴露在敵方雷達(dá)監(jiān)控范圍內(nèi)滯留時(shí)間最短為優(yōu)化目標(biāo);文獻(xiàn)[27]以能源消耗代價(jià)、高度代價(jià)和威脅代價(jià)為優(yōu)化目標(biāo),其中威脅代價(jià)包括大氣威脅代價(jià)和城市建筑威脅代價(jià)等;文獻(xiàn)[28]以威脅代價(jià)、航程代價(jià)和速度代價(jià)為目標(biāo)函數(shù);文獻(xiàn)[29]以最小化路徑長(zhǎng)度和最小化威脅代價(jià)為優(yōu)化目標(biāo);文獻(xiàn)[30]則將威脅代價(jià)與時(shí)間代價(jià)加權(quán)和為優(yōu)化目標(biāo).

具體的優(yōu)化目標(biāo)函數(shù)可以表述為如下形式:

其中:F表示優(yōu)化目標(biāo);Ji代表第i個(gè)代價(jià);ωi為第i個(gè)代價(jià)對(duì)應(yīng)的權(quán)重,=1.當(dāng)不采取加權(quán)操作,把每個(gè)代價(jià)拆分為獨(dú)立的目標(biāo)時(shí),該問(wèn)題即可轉(zhuǎn)換為多目標(biāo)優(yōu)化問(wèn)題.

文獻(xiàn)[31–32]中代價(jià)函數(shù)綜合考慮了路徑長(zhǎng)度代價(jià)、威脅代價(jià)和高度代價(jià),可表示為

其中:J為總代價(jià);L為距離代價(jià),文獻(xiàn)[9]中也將其稱為油料代價(jià);T為威脅代價(jià),H為高度代價(jià).ω1,ω2,ω3為不同目標(biāo)函數(shù)對(duì)應(yīng)的權(quán)重.當(dāng)然,還可根據(jù)需要引入其他代價(jià)函數(shù),如文獻(xiàn)[33]還將偏航角引入代價(jià)函數(shù)中,把偏航角和路徑長(zhǎng)度、威脅成本綜合加權(quán)作為目標(biāo)函數(shù).

此外,如文獻(xiàn)[34]所述,路徑規(guī)劃的結(jié)果評(píng)價(jià)與目標(biāo)函數(shù)的內(nèi)容有關(guān),通常以飛行時(shí)間、距離、規(guī)避風(fēng)險(xiǎn)或避障能力、路徑的可靠性等作為評(píng)價(jià)指標(biāo).

2.3 約束條件

無(wú)人機(jī)集群路徑規(guī)劃的約束通常包括自身約束和環(huán)境約束.自身約束一般為轉(zhuǎn)彎角、飛行速度、飛行高度、爬升角、俯沖角等,根據(jù)具體問(wèn)題還會(huì)存在一些特殊約束,如文獻(xiàn)[35]提出了一種能量模型用于約束飛行過(guò)程中的能量損耗;環(huán)境約束主要包括飛行邊界、地形限制等.

與單無(wú)人機(jī)路徑規(guī)劃問(wèn)題的約束條件相比,無(wú)人機(jī)集群路徑規(guī)劃最大的特點(diǎn)在于還要考慮集群約束,通常包括無(wú)人機(jī)之間的安全飛行距離等空間協(xié)同約束、按規(guī)定時(shí)間同時(shí)或依次到達(dá)目標(biāo)點(diǎn)的時(shí)間協(xié)同約束以及按命令行動(dòng)的任務(wù)協(xié)同約束.詳見(jiàn)表2.

表2 無(wú)人機(jī)集群路徑規(guī)劃常用約束條件Table 2 Constraints of UAV swarm

空間協(xié)同約束一般可表示為

其中:dab為任意兩架無(wú)人機(jī)a和無(wú)人機(jī)b之間的距離,dmin為無(wú)人機(jī)間最小安全距離,dmax為最遠(yuǎn)飛行距離(一般可定義為最大通信范圍),N為集群中無(wú)人機(jī)的數(shù)量.

時(shí)間協(xié)同約束則通常需要考慮集群的最短估計(jì)到達(dá)時(shí)間(estimated time of arrival,ETA)[36].

3 無(wú)人集群路徑規(guī)劃優(yōu)化算法

常用的路徑規(guī)劃算法可大致分為精確方法、啟發(fā)式算法和智能優(yōu)化算法3類.相對(duì)于智能優(yōu)化算法,我們稱精確方法和啟發(fā)式算法為傳統(tǒng)方法,如混合整數(shù)線性規(guī)劃法[37]、窮舉法[38]、動(dòng)態(tài)規(guī)劃[39–40]、Voronoi圖法[41]、人工勢(shì)場(chǎng)法[42]、A*算法[43]等.傳統(tǒng)方法在解決路徑規(guī)劃問(wèn)題時(shí)存在很多局限[44–47],如精確法只適用于小規(guī)模路徑規(guī)劃問(wèn)題,當(dāng)目標(biāo)函數(shù)和約束條件較為復(fù)雜時(shí),精確方法很難給出有效解.啟發(fā)式算法易陷入局部最優(yōu),同樣也不適用于規(guī)模較大的問(wèn)題.具體的,Voronoi圖法可選擇的路徑有限;人工勢(shì)場(chǎng)法解的質(zhì)量取決于勢(shì)場(chǎng)的建立,特別是在吸引力和排斥力相等位置較多時(shí)很難找到最優(yōu)路徑,而且當(dāng)目標(biāo)點(diǎn)距離較遠(yuǎn)且附近存在威脅時(shí),也很難找到可行路徑;A*算法的效率隨著搜索空間的增加而不斷下降并且多應(yīng)用于單無(wú)人機(jī)路徑規(guī)劃[48–50].

圖4 無(wú)人機(jī)集群路徑規(guī)劃智能優(yōu)化算法占比圖Fig.4 Proportion of intelligent optimization algorithms for path planning of UAV swarm

鑒于此,越來(lái)越多的學(xué)者利用智能優(yōu)化算法求解無(wú)人機(jī)集群路徑規(guī)劃,其中蟻群算法、粒子群算法、遺傳算法是使用最為廣泛的3類方法,如圖4所示.下面分別綜述基于這3類方法的無(wú)人機(jī)集群路徑規(guī)劃研究.

3.1 蟻群算法

蟻群算法(ant colony optimization,ACO)是M.Dorigo和C.Blum提出的一種模擬蟻群覓食行為的智能優(yōu)化算法[51],ACO已廣泛應(yīng)用于多個(gè)領(lǐng)域,如旅行商問(wèn)題、無(wú)線傳感器網(wǎng)絡(luò)設(shè)計(jì)[52]、資源調(diào)度、圖著色、網(wǎng)絡(luò)路由、有序排列[53]和通信編碼[54]等.在無(wú)人機(jī)集群路徑規(guī)劃中,蟻群算法中的螞蟻個(gè)體代表無(wú)人機(jī),從一個(gè)點(diǎn)轉(zhuǎn)移到另一個(gè)點(diǎn)的概率與信息素濃度和能見(jiàn)度(啟發(fā)式信息)相關(guān),轉(zhuǎn)移概率可表示如下:

其中:信息素τij表示在訪問(wèn)軌跡點(diǎn)i后直接訪問(wèn)軌跡點(diǎn)j的期望度;啟發(fā)式信息ηij代表螞蟻隨機(jī)選擇軌跡點(diǎn)j的概率;代表了位于點(diǎn)i的螞蟻k可以直接到達(dá)的相鄰點(diǎn)的集合;α和β是兩個(gè)參數(shù),分別決定了信息素和啟發(fā)式信息的相對(duì)影響力.當(dāng)α為0時(shí),最靠近i的軌跡點(diǎn)最有可能被選出,等同于經(jīng)典的隨機(jī)貪心算法;當(dāng)β為0時(shí),則只有信息素的放大系數(shù)起作用,即只使用信息素而沒(méi)有利用任何啟發(fā)式信息引導(dǎo)搜索,此時(shí)若α大于1,算法很快就會(huì)陷入停滯.同時(shí),信息素以一定概率蒸發(fā)以避免過(guò)分累積.

蟻群算法具有良好的魯棒性、通用性和并行性,其性能受信息素的更新模型影響,缺乏有效的更新模型,則易使種群?jiǎn)适Ф鄻有远萑刖植孔顑?yōu).文獻(xiàn)[55]將蟻群算法與量子計(jì)算和禁忌搜索相結(jié)合,提供了一種獲取多條選擇路徑的集群無(wú)人機(jī)路徑規(guī)劃方法:所有量子螞蟻根據(jù)禁忌搜索和量子信息素更新節(jié)點(diǎn)選擇概率從而完成路徑搜索,根據(jù)最優(yōu)路徑的綜合代價(jià)更新量子旋轉(zhuǎn)角,使用模擬的量子旋轉(zhuǎn)門(mén)更新量子信息素,將輸出的最優(yōu)路徑存入路徑集合,判斷路徑集合中的路徑個(gè)數(shù)是否達(dá)到最大路徑個(gè)數(shù),將路徑集合中的路徑依長(zhǎng)度排序供無(wú)人機(jī)選擇.該方法能夠有效求出綜合代價(jià)最小的多條路徑且路徑具有多樣性.值得指出的是該方法沒(méi)有考慮集群間的任務(wù)、時(shí)間上的協(xié)同要求.

文獻(xiàn)[56]使用改進(jìn)的蟻群算法控制大規(guī)模無(wú)人集群,首先引入無(wú)人控制節(jié)點(diǎn)(控制節(jié)點(diǎn)不執(zhí)行具體任務(wù),是對(duì)網(wǎng)絡(luò)進(jìn)行收斂性控制的節(jié)點(diǎn),探測(cè)目標(biāo)區(qū)域的位置質(zhì)量信息,生成區(qū)域引導(dǎo)信息,并通過(guò)控制節(jié)點(diǎn)間的控制鏈路在多個(gè)控制節(jié)點(diǎn)之間共享引導(dǎo)信息),其次通過(guò)任務(wù)節(jié)點(diǎn)自發(fā)探測(cè)目標(biāo)區(qū)域,形成多等級(jí)的位置質(zhì)量信息逐級(jí)傳播,未處于目標(biāo)區(qū)域的無(wú)人節(jié)點(diǎn)根據(jù)質(zhì)量信息的梯度變化,自主進(jìn)行路徑規(guī)劃,最終區(qū)域范圍內(nèi)的所有無(wú)人節(jié)點(diǎn)都能夠收斂到多個(gè)目標(biāo)區(qū)域范圍內(nèi).該方法提升了無(wú)人集群對(duì)環(huán)境的自主適應(yīng)能力,具有較好的協(xié)同效果,但是計(jì)算復(fù)雜度大,路徑規(guī)劃的效率不高.

文獻(xiàn)[57]引入Hopfield神經(jīng)網(wǎng)絡(luò),采用Hebb規(guī)則,用輸入模式作為目標(biāo)模式來(lái)設(shè)計(jì)連接權(quán),構(gòu)建新型函數(shù),該方法在感知戰(zhàn)場(chǎng)態(tài)勢(shì)和檢索戰(zhàn)場(chǎng)威脅方面做出了相應(yīng)的戰(zhàn)術(shù)規(guī)避,降低了各平臺(tái)在實(shí)際作戰(zhàn)中的危險(xiǎn)性,縮短了搜索時(shí)間,加快了收斂速度,具備較好的實(shí)用性.

文獻(xiàn)[58]綜合蟻群算法和文化算法,在種群空間中,利用螞蟻的啟發(fā)因子、文化因子和信息素設(shè)計(jì)了一種新的蟻群覓食演化方法,通過(guò)蟻群個(gè)體間節(jié)點(diǎn)的轉(zhuǎn)移來(lái)不斷搜索螞蟻的最優(yōu)路徑,然后利用接受函數(shù)將最優(yōu)路徑傳遞到信仰空間,即為信仰空間提供一組最優(yōu)路徑.隨后對(duì)最優(yōu)路徑的綜合代價(jià)和知識(shí)進(jìn)行更新,并記錄更新后的最優(yōu)路徑.信仰空間更新后的最優(yōu)路徑通過(guò)影響函數(shù)作用于種群的進(jìn)化,并被用于更新全局信息素,防止算法陷入局部最優(yōu).該方法利用了文化算法的雙層進(jìn)化機(jī)制,有效提高了收斂速度與精度.

文獻(xiàn)[59]將無(wú)人機(jī)路徑規(guī)劃問(wèn)題轉(zhuǎn)化成旅行商(travelling salesman problem,TSP)問(wèn)題,在搜索空間中設(shè)定一系列無(wú)人機(jī)必須經(jīng)過(guò)的無(wú)人機(jī)路徑點(diǎn),然后通過(guò)蟻群算法確定每個(gè)航點(diǎn)的通過(guò)順序,從而形成無(wú)人機(jī)飛行路徑.基于TSP的無(wú)人機(jī)路徑規(guī)劃需要預(yù)知無(wú)人機(jī)的飛行航點(diǎn),但在實(shí)際使用場(chǎng)景中這一點(diǎn)是很難保證的,因此該方法也存在一定的局限性.

文獻(xiàn)[60]采用Voronoi圖法對(duì)威脅環(huán)境建模,在蟻群算法的基礎(chǔ)上引入方向性引導(dǎo)策略以提高路徑規(guī)劃效率,并使用多只螞蟻并行構(gòu)建規(guī)劃路徑,最后利用協(xié)同時(shí)間指標(biāo)對(duì)得到的多條路徑進(jìn)行選擇,為無(wú)人機(jī)集群的路徑規(guī)劃提供解決方案.

3.2 粒子群算法

粒子群優(yōu)化(particle swarm optimization,PSO)算法源于對(duì)鳥(niǎo)群捕食行為的研究,由Eberhart 和Kennedy在1995年提出,其核心思想是利用集群中的信息共享使群體從無(wú)序到有序.首先隨機(jī)初始化一組粒子,每個(gè)粒子作為一個(gè)可行解,根據(jù)目標(biāo)函數(shù)計(jì)算適應(yīng)度值,在每次迭代中根據(jù)個(gè)體最優(yōu)解和全局最優(yōu)解決定下一步行動(dòng),更新自身的速度和位置,從而獲得問(wèn)題的最優(yōu)解.為改善算法收斂性能,Shi 和Eberhart在1998年引入慣性權(quán)重,修改了速度更新方程,形成了標(biāo)準(zhǔn)粒子群算法.

文獻(xiàn)[61]和文獻(xiàn)[62]采用粒子群優(yōu)化算法進(jìn)行無(wú)人機(jī)路徑規(guī)劃,研究中將每個(gè)粒子看作是規(guī)劃空間里的一個(gè)可能經(jīng)過(guò)的路徑位置點(diǎn),通過(guò)粒子所在位置和速度的更新以獲取最佳粒子,最后形成飛行路徑,但是上述研究均局限于單無(wú)人機(jī)的路徑規(guī)劃.

文獻(xiàn)[63]將粒子群算法與小生境技術(shù)相結(jié)合,用于尋找多條路徑,然而該方法在迭代尋優(yōu)的過(guò)程中,群體可能陷入相同的小生境,從而降低算法效率.文獻(xiàn)[64]將序貫小生境技術(shù)和粒子群算法結(jié)合,在對(duì)問(wèn)題進(jìn)行建模后,首先使用粒子群算法進(jìn)行第一次規(guī)劃得到一組路徑,其次結(jié)合序列小生境技術(shù)更新當(dāng)前最優(yōu)路徑附近的代價(jià)函數(shù)模型,增大最優(yōu)路徑小生境內(nèi)其他方案的代價(jià)值,然后,再使用粒子群算法對(duì)更新后的模型進(jìn)行下一次規(guī)劃以獲取次優(yōu)路徑,經(jīng)過(guò)多次循環(huán)可得到多條路徑.該方法通過(guò)序貫優(yōu)化找到不同的局部最優(yōu)飛行路徑,通過(guò)自適應(yīng)調(diào)整已知最優(yōu)解附近空間的目標(biāo)函數(shù),避免了群體陷入相同的小生境中,因此具有較高的尋優(yōu)效率.文獻(xiàn)[65]用軌跡點(diǎn)編號(hào)生成集群路徑的解序列,由分割點(diǎn)分割出來(lái)的多個(gè)序列代表多個(gè)無(wú)人機(jī)的路徑,為解決粒子早熟問(wèn)題,引入差分進(jìn)化操作維持粒子的多樣性,再結(jié)合自適應(yīng)調(diào)整慣性權(quán)重策略通過(guò)混合粒子群算法求解.該編碼方式降低了計(jì)算難度,但是解空間維數(shù)過(guò)大,并且未考慮集群約束.

文獻(xiàn)[66]提出了基于滾動(dòng)優(yōu)化策略結(jié)合粒子群優(yōu)化算法的無(wú)人水面艇集群協(xié)同規(guī)避方法,目標(biāo)函數(shù)為路徑和轉(zhuǎn)艏角之和最小:建立了二維全局環(huán)境坐標(biāo)系、基于無(wú)人水面艇的局部坐標(biāo)系和基于傳感器綜合感知信息的局部坐標(biāo)系,將無(wú)人水面艇的綜合視域作為一個(gè)滾動(dòng)窗口,在滾動(dòng)窗口內(nèi)劃同心圓,每個(gè)同心圓上隨機(jī)產(chǎn)生一個(gè)可視覺(jué)點(diǎn),連成一條無(wú)規(guī)避路徑,當(dāng)無(wú)人機(jī)前進(jìn)時(shí)滾動(dòng)窗口和子目標(biāo)點(diǎn)也隨之變化;粒子通過(guò)最短路徑與最小轉(zhuǎn)艏角之和作為評(píng)價(jià)函數(shù),自我更新函數(shù)由動(dòng)量項(xiàng)、粒子搜索過(guò)程中的自我思考和粒子間的信息共享合作3個(gè)部分組成,動(dòng)量項(xiàng)中的慣性權(quán)重可加強(qiáng)粒子的局部搜索能力,慣性權(quán)重改進(jìn)使用了基于正切函數(shù)的慣性調(diào)整策略.該方法增強(qiáng)了搜索能力,提高了收斂速度,但滾動(dòng)窗口的大小影響著求解過(guò)程和結(jié)果,如何找到合適的窗口有待研究.

文獻(xiàn)[67]和文獻(xiàn)[68]將帶有收斂因子的粒子群算法用于無(wú)人機(jī)的路徑規(guī)劃問(wèn)題,通過(guò)收斂因子提高全局最優(yōu)位置對(duì)粒子位置更新的影響力水平,進(jìn)而提高收斂精度.但是該方法對(duì)規(guī)范空間的要求相對(duì)較高,收斂速度較慢.

文獻(xiàn)[69]研究了多無(wú)人機(jī)偵察多個(gè)目標(biāo)點(diǎn)的路徑規(guī)劃和任務(wù)分配,首先利用聚類方法將多個(gè)目標(biāo)點(diǎn)分簇,在路徑規(guī)劃中以簇中心為目標(biāo)點(diǎn),將多無(wú)人機(jī)偵察多個(gè)目標(biāo)點(diǎn)的問(wèn)題轉(zhuǎn)化為多旅行商問(wèn)題.具體先為每架無(wú)人機(jī)隨機(jī)分配目標(biāo)然后再編排目標(biāo)的訪問(wèn)順序.文章中使用了二進(jìn)制編碼矩陣(列表示被偵察的目標(biāo),行表示偵察無(wú)人機(jī))的離散粒子群優(yōu)化算法求解規(guī)劃模型,收斂速度較快,但問(wèn)題模型中沒(méi)有考慮無(wú)人機(jī)的機(jī)動(dòng)性能約束、障礙約束等,規(guī)劃空間較為簡(jiǎn)單,實(shí)用性不強(qiáng).

3.3 遺傳算法

遺傳算法(genetic algorithm,GA)源于達(dá)爾文的進(jìn)化論,是通過(guò)模仿自然界物種遺傳交叉變異的演化現(xiàn)象提出的一類智能優(yōu)化算法.標(biāo)準(zhǔn)的遺傳算法步驟為:1)初始化種群;2)種群中個(gè)體適應(yīng)度值計(jì)算;3)個(gè)體間的選擇、交叉、變異操作;4)合并父代和子代,淘汰適應(yīng)度差的個(gè)體;5)若未滿足終止條件則轉(zhuǎn)至步驟3),若滿足,則輸出近似最優(yōu)解.當(dāng)前已有不少利用遺傳算法進(jìn)行單無(wú)人機(jī)路徑規(guī)劃的研究[70–72],一般一個(gè)染色體表示一條無(wú)人機(jī)路徑,染色體中的每一個(gè)基因代表一個(gè)規(guī)劃點(diǎn).適應(yīng)度函數(shù)即為代價(jià)函數(shù),通過(guò)適應(yīng)度函數(shù)選擇較好的路徑,再通過(guò)交叉、變異等操作使染色體不斷進(jìn)化,最終得到最優(yōu)路徑.

文獻(xiàn)[73]將遺傳算法用于多無(wú)人機(jī)路徑規(guī)劃中,把飛行總距離、無(wú)人機(jī)間間隔距離、轉(zhuǎn)彎角、多無(wú)人機(jī)所覆蓋的區(qū)域等加權(quán)作為適應(yīng)度函數(shù),在三維空間中規(guī)定相同的起始點(diǎn)和目標(biāo)點(diǎn)規(guī)劃出多條路徑,但該研究未考慮集群的相關(guān)約束.

文獻(xiàn)[74]把多架無(wú)人偵察機(jī)的路徑規(guī)劃問(wèn)題轉(zhuǎn)化成多旅行商問(wèn)題,利用改進(jìn)的遺傳算法求解,采用符號(hào)編碼方式,利用1,2以及n分別代表目標(biāo)1、目標(biāo)2以及目標(biāo)n,0表示起點(diǎn)和終點(diǎn),以飛行總長(zhǎng)度和路徑相似度為適應(yīng)度函數(shù),以輪盤(pán)賭的方式進(jìn)行個(gè)體選擇,并采用改進(jìn)的三交換啟發(fā)交叉方法,將傳統(tǒng)兩條染色體參與交叉操作改為3條.仿真實(shí)驗(yàn)顯示該方法有效得到多條無(wú)人機(jī)路徑.類似的,文獻(xiàn)[75–78]也將無(wú)人機(jī)集群路徑規(guī)劃轉(zhuǎn)化為多旅行商問(wèn)題,并采用遺傳算法求解,但是文獻(xiàn)[75–76]把問(wèn)題簡(jiǎn)化成非閉環(huán)的多旅行商航路規(guī)劃,與實(shí)際應(yīng)用不符;文獻(xiàn)[77]通過(guò)添加虛擬城市,將多旅行商轉(zhuǎn)化成單旅行商,僅適用于小規(guī)模問(wèn)題;文獻(xiàn)[78]利用K–means算法將多旅行商問(wèn)題聚類為多個(gè)獨(dú)立的旅行商問(wèn)題,較之于前述方法在大規(guī)模路徑規(guī)劃問(wèn)題上性能有所提升,但搜索的最優(yōu)路徑依賴于聚類結(jié)果,簡(jiǎn)單的K–means聚類劃分難以適應(yīng)實(shí)際應(yīng)用場(chǎng)景.

文獻(xiàn)[79]為解決有障礙區(qū)域限制的多無(wú)人機(jī)遍歷多目標(biāo)點(diǎn)的路徑規(guī)劃問(wèn)題,以總飛行成本最低為目標(biāo),在運(yùn)用遺傳算法求解的過(guò)程中,設(shè)計(jì)了新的交叉算子,從父代中隨機(jī)選擇子路徑并前置,并按照一定的規(guī)則生成遍歷其余目標(biāo)點(diǎn)的路徑,在保留父代優(yōu)秀染色體的同時(shí)提升了收斂速度.

文獻(xiàn)[80]基于分層技術(shù)采用遺傳算法進(jìn)行多無(wú)人機(jī)路徑規(guī)劃,以飛行代價(jià)最小為目標(biāo),首先利用Dubins路徑搜索每架無(wú)人機(jī)的可能路徑,然后借助遺傳算法尋優(yōu),最終形成無(wú)人機(jī)的最佳飛行路徑.但是,此模型分層結(jié)構(gòu)復(fù)雜且計(jì)算量大.

3.4 其他智能優(yōu)化方法

除了上述算法,還有一些其他智能優(yōu)化算法應(yīng)用于路徑規(guī)劃中,如模擬蜂群覓食的人工蜂群算法、基于神經(jīng)網(wǎng)絡(luò)和強(qiáng)化學(xué)習(xí)的優(yōu)化方法等.人工蜂群算法中蜜源位置對(duì)應(yīng)可行路徑節(jié)點(diǎn)的坐標(biāo)值,蜜源的收益度大小對(duì)應(yīng)可行路徑節(jié)點(diǎn)坐標(biāo)的目標(biāo)函數(shù)值,尋找蜜源和采蜜的速度對(duì)應(yīng)無(wú)人機(jī)代價(jià)函數(shù)的收斂速度.文獻(xiàn)[81]提出改進(jìn)的蜂群算法,通過(guò)增加維度限制條件以控制初始蜜源的產(chǎn)生方式,結(jié)合非確定性搜索機(jī)制引入雙向規(guī)劃方法,應(yīng)用于多無(wú)人機(jī)路徑規(guī)劃,該方法有效提高了解的質(zhì)量,但同樣未充分考慮集群在時(shí)間和任務(wù)上的協(xié)同.

Gary B.Lamont等[82]將無(wú)人機(jī)群路徑規(guī)劃看作單無(wú)人機(jī)行為的累積問(wèn)題,在單無(wú)人機(jī)的基礎(chǔ)上加入群體模型,考慮了成本和風(fēng)險(xiǎn)兩類共5個(gè)代價(jià)指標(biāo),即距離總和、爬升次數(shù)、地形威脅、敵方檢測(cè)、殺傷消滅,其中距離和爬升為路徑成本,地形、檢測(cè)和殺傷為路徑風(fēng)險(xiǎn).然后采用多目標(biāo)進(jìn)化算法求解模型得到一組關(guān)于成本和風(fēng)險(xiǎn)的帕累托前沿.文獻(xiàn)[83]針對(duì)有相同的起始點(diǎn)和目標(biāo)點(diǎn)的路徑規(guī)劃問(wèn)題,根據(jù)實(shí)際要求設(shè)計(jì)了一個(gè)具有多峰值點(diǎn)的代價(jià)函數(shù),該代價(jià)函數(shù)的每一個(gè)局部極小值點(diǎn)對(duì)應(yīng)一條次優(yōu)路徑,采用多條變長(zhǎng)染色體代表不同的路徑,求解時(shí)引入K–means聚類算法,每隔若干代將種群中的個(gè)體按其空間分布進(jìn)行一次聚類,生成若干個(gè)子種群,進(jìn)化過(guò)程中,使用了交叉、擾動(dòng)、插入、刪除、交換和平滑六種進(jìn)化算子,所有個(gè)體只在各自的子種群內(nèi)部進(jìn)化,進(jìn)化結(jié)束后每個(gè)子種群可以分別生成一條最優(yōu)路徑.文獻(xiàn)[84]針對(duì)不同的起始點(diǎn)和相同的目標(biāo)點(diǎn)路徑規(guī)劃問(wèn)題,首先利用進(jìn)化計(jì)算對(duì)集群中的單個(gè)無(wú)人機(jī)進(jìn)行路徑規(guī)劃,然后考慮時(shí)間和空間等方面的協(xié)同,最終實(shí)現(xiàn)無(wú)人機(jī)集群的分層離線協(xié)同路徑規(guī)劃.

文獻(xiàn)[85]將神經(jīng)網(wǎng)絡(luò)用于多無(wú)人機(jī)路徑規(guī)劃問(wèn)題,對(duì)不同的起始點(diǎn)和目標(biāo)點(diǎn)構(gòu)造多個(gè)神經(jīng)網(wǎng)絡(luò)用以調(diào)整初始軌跡點(diǎn),先均分兩點(diǎn)間路徑長(zhǎng)度確定飛行步長(zhǎng),均勻選取初始軌跡點(diǎn),再以威脅的半徑和每個(gè)軌跡點(diǎn)到威脅中心的距離差作為神經(jīng)網(wǎng)絡(luò)的輸入,把威脅和路徑距離的加權(quán)作為神經(jīng)網(wǎng)絡(luò)的能量函數(shù),輸出一組避開(kāi)威脅且使每一條路徑總和最短的軌跡點(diǎn),最后,對(duì)軌跡點(diǎn)進(jìn)行修正得到符合要求的路徑.類似于其他方法,基于神經(jīng)網(wǎng)絡(luò)的路徑規(guī)劃方法中,飛行步長(zhǎng)和路徑的質(zhì)量息息相關(guān),步長(zhǎng)越小,路徑規(guī)劃的精度越高,但相應(yīng)的計(jì)算量增大.

文獻(xiàn)[86]集成深度神經(jīng)網(wǎng)絡(luò)和強(qiáng)化學(xué)習(xí)實(shí)現(xiàn)了多無(wú)人機(jī)協(xié)同區(qū)域監(jiān)視的路徑規(guī)劃.通過(guò)使用深度神經(jīng)網(wǎng)絡(luò)代替狀態(tài)–動(dòng)作估值函數(shù),用梯度下降法替換強(qiáng)化學(xué)習(xí)的迭代更新,首先建立多個(gè)全連接神經(jīng)網(wǎng)絡(luò)對(duì)應(yīng)多個(gè)無(wú)人機(jī)的路徑規(guī)劃,輸入層為無(wú)人機(jī)的狀態(tài)(位置、飛行速度、飛行方向),輸出層為動(dòng)作估值,以監(jiān)視面積覆蓋率為強(qiáng)化信號(hào)更新每個(gè)全連接網(wǎng)絡(luò)的參數(shù),最終根據(jù)每個(gè)訓(xùn)練后的神經(jīng)網(wǎng)絡(luò)模型確定對(duì)應(yīng)無(wú)人機(jī)的規(guī)劃路徑,后又引入Q–learning算法估計(jì)無(wú)人機(jī)每個(gè)狀態(tài)的未來(lái)獎(jiǎng)勵(lì),以改進(jìn)之前的深度強(qiáng)化學(xué)習(xí)算法.該方法中第1架無(wú)人機(jī)選取神經(jīng)網(wǎng)絡(luò)輸出最大值對(duì)應(yīng)的動(dòng)作根據(jù)的是其他無(wú)人機(jī)未更新的位置,當(dāng)其他的位置更新后,對(duì)第1架無(wú)人機(jī)而言,其選擇的動(dòng)作并不一定是最優(yōu)的.文獻(xiàn)[87]提出了基于幾何強(qiáng)化學(xué)習(xí)方法的多無(wú)人機(jī)路徑規(guī)劃,在強(qiáng)化學(xué)習(xí)的基礎(chǔ)上引入報(bào)酬矩陣,候選點(diǎn)從起點(diǎn)到終點(diǎn)的幾何路徑區(qū)域中選擇,然后基于無(wú)人機(jī)之間共享的幾何距離信息和風(fēng)險(xiǎn)信息自適應(yīng)地更新報(bào)酬矩陣.但是無(wú)人機(jī)集群的狀態(tài)空間很大,高效地選取最優(yōu)動(dòng)作較難.

3.5 算法對(duì)比

綜合國(guó)內(nèi)外相關(guān)研究發(fā)現(xiàn),大多數(shù)研究都將無(wú)人機(jī)視為質(zhì)點(diǎn),較少考慮無(wú)人機(jī)自身的性能約束;大多將無(wú)人機(jī)集群路徑規(guī)劃問(wèn)題建模為多旅行商問(wèn)題,求解多條路徑再進(jìn)行規(guī)劃的問(wèn)題.

在優(yōu)化算法上多采用蟻群算法、粒子群算法和遺傳算法及其改進(jìn)算法進(jìn)行求解,這些方法具有較好的并行性且對(duì)目標(biāo)函數(shù)特性要求低.針對(duì)具體的路徑規(guī)劃問(wèn)題,在上述3類算法的基礎(chǔ)上,學(xué)者們先后提出了大量的改進(jìn)算法,如在算法中引入神經(jīng)網(wǎng)絡(luò)規(guī)則、文化機(jī)制等提高收斂速度,縮短搜索時(shí)間.表3具體對(duì)比分析了常用的幾種智能優(yōu)化算法的優(yōu)缺點(diǎn).

4 未來(lái)研究展望

綜上所述,盡管針對(duì)無(wú)人機(jī)集群路徑規(guī)劃的智能優(yōu)化研究已有不少,但現(xiàn)有研究還存在如下問(wèn)題:

首先,現(xiàn)有研究多關(guān)注靜態(tài)全局路徑規(guī)劃,即假設(shè)在環(huán)境信息已知條件下對(duì)路徑進(jìn)行預(yù)先規(guī)劃,對(duì)未知、不確定性、強(qiáng)對(duì)抗環(huán)境下的路徑規(guī)劃和飛行過(guò)程中突發(fā)狀況的路徑動(dòng)態(tài)調(diào)整規(guī)避等相關(guān)研究較少.已有的方法也大多采用快速搜索隨機(jī)樹(shù)法、人工勢(shì)場(chǎng)法或滾動(dòng)窗口法進(jìn)行動(dòng)態(tài)避障,如文獻(xiàn)[88]利用集合點(diǎn)規(guī)劃狀態(tài)圖對(duì)突發(fā)威脅進(jìn)行實(shí)時(shí)路徑規(guī)劃;文獻(xiàn)[89]基于投影矩陣和虛擬力原理設(shè)計(jì)了兩種動(dòng)態(tài)避障策略并通過(guò)啟發(fā)式快速搜索隨機(jī)樹(shù)法進(jìn)行路徑重規(guī)劃.因此針對(duì)不確定、強(qiáng)對(duì)抗環(huán)境下無(wú)人集群的動(dòng)態(tài)路徑規(guī)劃亟需更高效的算法支撐.

其次,現(xiàn)有無(wú)人機(jī)集群路徑規(guī)劃的模型存在局限性.現(xiàn)有研究將無(wú)人機(jī)集群路徑規(guī)劃分為兩階段:生成路徑、協(xié)同規(guī)劃,大多數(shù)研究?jī)H構(gòu)建了第1階段生成路徑的模型,如何在模型中綜合考慮集群的任務(wù)、時(shí)間協(xié)同約束、航跡的平滑,從而提高路徑規(guī)劃的精確性,值得進(jìn)一步深入研究.

第三,應(yīng)用智能優(yōu)化算法求解路徑規(guī)劃模型時(shí),多采用蟻群算法、粒子群算法、遺傳算法或相關(guān)混合算法.近年來(lái),深度學(xué)習(xí)和強(qiáng)化學(xué)習(xí)等人工智能方法在序貫決策優(yōu)化問(wèn)題(如TSP,VRP等)上顯示出了較好的性能,能夠?qū)崿F(xiàn)路徑的快速規(guī)劃.文獻(xiàn)[86–87,90]已將強(qiáng)化學(xué)習(xí)用于多智能體路徑規(guī)劃中,且獲得了良好的效果.因此,如何基于深度學(xué)習(xí)和強(qiáng)化學(xué)習(xí)等方法進(jìn)行無(wú)人機(jī)集群路徑規(guī)劃是未來(lái)重要的研究方向,有望實(shí)現(xiàn)動(dòng)態(tài)、在線路徑規(guī)劃.

第四,現(xiàn)有研究對(duì)集群間的協(xié)同表述還不夠完善,有的未考慮協(xié)同,只是簡(jiǎn)單地規(guī)劃出多條路徑;有的只對(duì)時(shí)間和空間上的協(xié)同進(jìn)行了約束,總體而言,對(duì)深層次協(xié)同的研究較少.未來(lái)智能體集群更像一個(gè)生命系統(tǒng),具備整體性、層次性和相關(guān)性,智能體通過(guò)完成各自的任務(wù),在宏觀上,則可以完成高級(jí)復(fù)雜的任務(wù).因此,如何規(guī)劃好集群整體和局部的關(guān)系、局部間的關(guān)系,如何提高協(xié)同性,最大化集群效益有待進(jìn)一步研究.

表3 無(wú)人機(jī)集群路徑規(guī)劃常用算法對(duì)比Table 3 Analysis of the main algorithms

5 總結(jié)

無(wú)人機(jī)集群協(xié)同完成各種遂行作戰(zhàn)任務(wù)是未來(lái)智能化、無(wú)人化聯(lián)合作戰(zhàn)的重要應(yīng)用之一,路徑規(guī)劃作為無(wú)人機(jī)集群執(zhí)行各類任務(wù)的基礎(chǔ)技術(shù),在無(wú)人機(jī)集群應(yīng)用中發(fā)揮著重要的作用.本文綜述了無(wú)人機(jī)集群路徑規(guī)劃的模型及方法,重點(diǎn)分析了基于不同類型智能優(yōu)化算法的無(wú)人機(jī)集群路徑規(guī)劃研究,闡述了不同類型智能算法的優(yōu)勢(shì)及不足,展望了無(wú)人機(jī)集群路徑規(guī)劃的未來(lái)研究方向,可為開(kāi)展相關(guān)研究的學(xué)者提供良好的參考和借鑒.