基于精英族系遺傳算法的AUV集群路徑規(guī)劃

馮豪博, 胡 橋, 趙振軼

(1. 西安交通大學(xué)機(jī)械工程學(xué)院, 陜西 西安 710049;2. 陜西省智能機(jī)器人重點(diǎn)實(shí)驗(yàn)室, 陜西 西安 710049)

0 引 言

隨著無人化技術(shù)的迅猛發(fā)展,水下無人集群系統(tǒng)的軍用和民用價(jià)值日益凸顯。自主式水下航行器(autonomous underwater vehicle, AUV)因其作業(yè)范圍廣、安全性高、功能性強(qiáng)等特點(diǎn),逐漸發(fā)展成為應(yīng)用最為廣泛的水下無人設(shè)備。由于AUV集群對協(xié)同控制能力的高需求,路徑規(guī)劃系統(tǒng)成為了AUV集群智能系統(tǒng)必不可少的重要組成部分,長期以來一直受到國內(nèi)外學(xué)者的廣泛關(guān)注。

多智能體路徑規(guī)劃(multi-agent path planning,MAPP)問題是一類尋找多個(gè)智能體從起始位置到目標(biāo)位置且無沖突的最優(yōu)路徑集合問題。MAPP被廣泛應(yīng)用于情報(bào)偵察、目標(biāo)監(jiān)視、集群作戰(zhàn)等領(lǐng)域,而與單智能體路徑規(guī)劃相比,多智能體系統(tǒng)的航行控制更為復(fù)雜。對于AUV集群而言,在航行過程中不僅需要考慮島嶼、暗礁、船舶等復(fù)雜環(huán)境的影響,還需要對AUV間航路規(guī)劃進(jìn)行統(tǒng)籌協(xié)調(diào),因此AUV集群航行控制系統(tǒng)需要具備規(guī)劃多條無沖突的可行路徑的能力。

在無人集群的單路徑規(guī)劃方面,國內(nèi)外學(xué)者的大量研究已經(jīng)取得了各種各樣的成果。Sang等針對人工勢場法容易陷入局部的問題,通過A算法進(jìn)行全局路徑規(guī)劃獲得子目標(biāo)序列,再使用子目標(biāo)人工勢場法實(shí)現(xiàn)水面無人艇艦隊(duì)的航路規(guī)劃。王樂樂等針對多機(jī)器人在形成編隊(duì)隊(duì)形情形下的路徑規(guī)劃問題,建立搜索樹擴(kuò)展方向與隊(duì)形方向之間的聯(lián)系,將快速搜索樹算法應(yīng)用到集群編隊(duì)路徑規(guī)劃中。Lima等針對無人集群在三角形隊(duì)形情況下的路徑規(guī)劃問題,提出一種新的路徑規(guī)劃數(shù)學(xué)建模方法,并基于粒子群優(yōu)化、差分進(jìn)化等算法的仿真驗(yàn)證了該數(shù)學(xué)模型的可行性。

AUV集群沿著單路徑航行時(shí),通常以形成多機(jī)編隊(duì)的方式行進(jìn),對環(huán)境的障礙分布情況、可行空間大小有著很高的要求。在AUV集群向目標(biāo)點(diǎn)行進(jìn)的過程中,編隊(duì)規(guī)模越大,在維持隊(duì)形的情況下所需的路徑寬度也越大。在以單機(jī)行進(jìn)方式航行的情況下,AUV集群沿著不同路徑行進(jìn)能更加充分利用環(huán)境空間,相比于單路徑行進(jìn),其總耗時(shí)(第一臺AUV出發(fā)時(shí)間與最后一臺AUV到達(dá)時(shí)間的間隔)更短。而在以多AUV編隊(duì)行進(jìn)的情況下,環(huán)境空間障礙密集程度對編隊(duì)規(guī)模起到了限制作用,根據(jù)AUV集群規(guī)模選擇合適的編隊(duì)規(guī)模和路徑數(shù)量將有利于規(guī)劃所需路徑、縮短行進(jìn)耗時(shí)。因此,多路徑規(guī)劃在實(shí)現(xiàn)AUV集群航行路徑規(guī)劃過程中起到重要作用。

相比于無人集群的單路徑規(guī)劃,國內(nèi)外學(xué)者對于基于多路徑的MAPP研究則相對較少。李征等針對傳統(tǒng)路徑規(guī)劃算法難以滿足多無人機(jī)協(xié)同飛行需求的問題,通過最優(yōu)控制建模將多無人機(jī)路徑規(guī)劃問題轉(zhuǎn)化為非線性優(yōu)化問題,提出一種基于Radau偽譜法的無人機(jī)集群路徑規(guī)劃方法,但此方法主要基于數(shù)值求解方式,可擴(kuò)展性較低。Babel針對無人集群同時(shí)或順序到達(dá)目標(biāo)點(diǎn)的航跡規(guī)劃問題,提出一種基于同時(shí)到達(dá)原則的無人集群路徑規(guī)劃方法,但該方法所產(chǎn)生的路徑存在交叉現(xiàn)象且并不能實(shí)現(xiàn)時(shí)間最優(yōu)的目的。丁佳宇等采取人工勢場法,將已規(guī)劃路徑點(diǎn)作為障礙點(diǎn),對無人機(jī)依次規(guī)劃路徑實(shí)現(xiàn)無人機(jī)集群的路徑規(guī)劃,但該方法不能對各路徑間關(guān)系進(jìn)行協(xié)調(diào)優(yōu)化,隨著無人機(jī)集群規(guī)模的增大,所規(guī)劃的路徑長度將顯著增長。

本文針對多路徑規(guī)劃問題,以路徑長度為評價(jià)指標(biāo),通過將基因適應(yīng)度項(xiàng)加人適應(yīng)度評價(jià)函數(shù),并通過隱性基因調(diào)節(jié)路徑寬度,提出了精英族系遺傳算法(elite family genetic algorithm, EFGA)。同時(shí),在EFGA的基礎(chǔ)上,本文針對AUV集群路徑規(guī)劃問題,提出了一種MAPP方法。仿真結(jié)論表明,所提方法能夠通過求解無沖突路徑集合實(shí)現(xiàn)AUV集群的多路徑規(guī)劃,減少AUV集群的航行時(shí)間。

1 環(huán)境模型

環(huán)境建模起著將環(huán)境信息抽象為易于計(jì)算機(jī)處理的數(shù)據(jù)信息的作用,對后續(xù)的路徑規(guī)劃尤為重要。常用的環(huán)境建模方法有柵格法、可視圖法、拓?fù)浞ǖ?。為簡化問題的分析和求解,本文將三維水下空間簡化為二維。由于AUV編隊(duì)規(guī)模的大小會根據(jù)不同的需求發(fā)生變化,因此本文選擇使用具有柵格粒度可調(diào)特點(diǎn)的柵格空間建模。

1.1 柵格空間建模

柵格法的原理是將整個(gè)空間按照一定的粒度拆分成一個(gè)個(gè)連續(xù)但不交叉的柵格,每一塊柵格的狀態(tài)由其所處位置的環(huán)境信息決定。模型如圖1所示,將正方形空間平均分為10×10的格柵網(wǎng)格,其中白色柵格表示可達(dá)空間,黑色柵格表示不可達(dá)空間。由于出發(fā)區(qū)域和終點(diǎn)區(qū)域的大小對路徑規(guī)劃結(jié)果的影響較小,因此忽略出發(fā)區(qū)域和終點(diǎn)區(qū)域大小的影響,起點(diǎn)用黃色柵格表示,終點(diǎn)用藍(lán)色柵格表示。

圖1 柵格空間建模Fig.1 Environment modeling in grid space

通過序號和坐標(biāo)(,)共同對柵格空間進(jìn)行描述。柵格序號以一定的縱橫規(guī)律對每一塊柵格進(jìn)行編號,柵格坐標(biāo)與柵格所在行列相互對應(yīng)。柵格坐標(biāo)與序號轉(zhuǎn)換關(guān)系如下:

(1)

式中:為柵格序號;為柵格所在列數(shù);為柵格所在行數(shù);為柵格空間總列數(shù);Mod(·)為取余操作;Floor(·)為向下取整操作。

1.2 柵格粒度劃分原則

柵格粒度是指柵格空間中每個(gè)柵格的尺寸大小。柵格粒度的劃分對模型精度、路徑規(guī)劃求解難度有著重要影響。柵格法粒度可調(diào)的特點(diǎn)使其適用范圍廣,但存在時(shí)空開銷和求解精度存在沖突的問題。過大的劃分粒度會導(dǎo)致環(huán)境信息的大量丟失,無法對環(huán)境空間進(jìn)行充分的描述,導(dǎo)致路徑規(guī)劃結(jié)果與預(yù)期不符。而過小的劃分粒度則會使路徑規(guī)劃算法所需內(nèi)存空間和算力資源大為增加,造成不必要的計(jì)算機(jī)資源浪費(fèi),且AUV集群的運(yùn)動控制性能也制約著過于精確的路徑的準(zhǔn)確執(zhí)行。

在進(jìn)行柵格空間建模時(shí),通常采取將障礙邊界擴(kuò)大而使AUV或AUV編隊(duì)等效為質(zhì)點(diǎn)的簡化方式,但這種方式會使AUV間避碰約束信息丟失,導(dǎo)致需要對AUV間距離關(guān)系進(jìn)行額外約束,并且這種簡化方式會導(dǎo)致空間建模精度隨著AUV或AUV編隊(duì)尺寸的增大而降低,降低路徑規(guī)劃求解結(jié)果的精度。

為解決AUV間避碰約束信息丟失的問題,實(shí)現(xiàn)對AUV與環(huán)境、AUV間位置關(guān)系的有效描述,提升柵格空間建模精度,根據(jù)對不同求解精度的需求,本文提出了兩種柵格粒度劃分原則。

1.2.1 基于編隊(duì)規(guī)模的粒度劃分原則

在AUV集群在簡單環(huán)境中以編隊(duì)方式行進(jìn)的情況中,路徑求解精度易于得到保證,為減小算法求解開銷,采用基于編隊(duì)規(guī)模的粒度劃分原則。

如圖2所示,以三角形編隊(duì)為例,AUV與障礙間安全距離為,AUV間安全距離為,圖示三角形編隊(duì)規(guī)模尺寸則為2+2。在這種情況下,選取編隊(duì)規(guī)模尺寸為柵格粒度。對于AUV以獨(dú)立行進(jìn)方式在簡單環(huán)境中航行的情況下,類似地可以將2作為柵格粒度進(jìn)行柵格空間建模。

圖2 基于編隊(duì)規(guī)模的粒度劃分Fig.2 Grid division according to formation size

1.2.2 基于相對復(fù)雜系數(shù)的粒度劃分原則

對于較為復(fù)雜的環(huán)境,為保證求解精度,采用基于相對復(fù)雜系數(shù)的粒度劃分原則。相對復(fù)雜系數(shù)是環(huán)境復(fù)雜度與編隊(duì)規(guī)模尺寸或AUV尺寸之間的度量。環(huán)境障礙尺寸越小,編隊(duì)規(guī)模尺寸或AUV尺寸越大,則相對復(fù)雜系數(shù)越大。

如圖3所示,以三角形編隊(duì)為例,AUV與障礙間安全距離為,AUV間安全距離為l,則圖示三角形編隊(duì)規(guī)模尺寸=2+2。

圖3 基于環(huán)境復(fù)雜系數(shù)的粒度劃分Fig.3 Grid division based on environment complexity coefficient

在這種情況下,柵格粒度選取如下:

(2)

式中:為相對復(fù)雜系數(shù),∈{|=2+1,∈}。一般取值與編隊(duì)的行列數(shù)量相關(guān),但當(dāng)環(huán)境過于復(fù)雜時(shí),也可選取較大的值。當(dāng)=1時(shí),與基于編隊(duì)規(guī)模的粒度劃分的結(jié)果相同。

2 EFGA

遺傳算法最初由文獻(xiàn)[23]于1976年提出,是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法,被國內(nèi)外學(xué)者廣泛應(yīng)用于求解路徑規(guī)劃問題。但標(biāo)準(zhǔn)遺傳算法的核心思想僅對個(gè)體與環(huán)境之間的關(guān)系進(jìn)行考慮,適應(yīng)度函數(shù)完全由環(huán)境因素所決定,以獲得適應(yīng)度最高的單一個(gè)體為優(yōu)化目的,并不適用于求解MAPP問題。

為了更好地求解MAPP問題,本文在標(biāo)準(zhǔn)遺傳算法的基礎(chǔ)上,選取合適的遺傳算子,將基因適應(yīng)度項(xiàng)加入適應(yīng)度評價(jià)函數(shù)中,同時(shí)對個(gè)體與環(huán)境之間的關(guān)系、個(gè)體間的相互競爭關(guān)系進(jìn)行考量,應(yīng)用精英族系策略,將優(yōu)化目標(biāo)由最優(yōu)路徑轉(zhuǎn)化為無沖突的最優(yōu)路徑集合,并通過隱性基因?qū)崿F(xiàn)對路徑寬度的調(diào)節(jié),提出了適用于多路徑規(guī)劃的EFGA算法。

2.1 顯性基因和隱性基因

為了滿足不同AUV編隊(duì)規(guī)模對可調(diào)路徑寬度的需求,本節(jié)對顯性基因和隱性基因進(jìn)行定義。如圖4所示,在以相對復(fù)雜系數(shù)作為粒度劃分原則且=3的柵格空間中,紅色實(shí)線表示所劃分的路徑,黃色柵格為顯性基因,綠色柵格為隱性基因,即顯性基因?qū)?yīng)為路徑所經(jīng)過的所有柵格,隱性基因?qū)?yīng)為集群編隊(duì)沿著路徑行進(jìn)所經(jīng)過的除顯性基因以外的所有相鄰柵格。

圖4 顯性基因與隱性基因Fig.4 Dominant gene and recessive genes

若已知顯性基因柵格坐標(biāo)集合為,則隱性基因柵格坐標(biāo)集合計(jì)算如下:

(3)

在以編隊(duì)規(guī)模為原則進(jìn)行柵格空間建模的情況下,個(gè)體只含有顯性基因不含有隱性基因,=?。

2.2 基因編碼方式

個(gè)體的基因序列由其顯性基因采用柵格序號編碼形成,如圖5所示。

圖5 基因序列
Fig.5 Gene sequence

個(gè)體的基因序列可用集合表示為={,,,…,}。

為使每個(gè)基因序列代表著一條連通路徑,對其進(jìn)行以下約束:

(1) 對?≠且,∈[1,],有≠;

(2) 對?∈[1,],∈,其中為所有可達(dá)柵格的柵格序號集合;

(3) 對?∈[1,-1],,+1對應(yīng)的柵格需相互接觸,包括邊接觸和頂點(diǎn)接觸;

(4) 對?∈[1,-1],,+1形成的路徑不能斜穿不可達(dá)柵格,如圖6所示。

圖6 斜穿不可達(dá)柵格Fig.6 Passing through unreachable grid obliquely

2.3 遺傳算子

為更好地保持種群個(gè)體多樣性和維持種群個(gè)體數(shù)量,采用復(fù)制、淘汰、變異和交叉4個(gè)遺傳算子。

231 復(fù)制算子

采用三元錦標(biāo)賽選擇法。種群中每個(gè)個(gè)體均有相同的概率發(fā)起復(fù)制錦標(biāo)賽。在發(fā)起錦標(biāo)賽的個(gè)體和在種群中隨機(jī)選取的兩個(gè)個(gè)體中,適應(yīng)度最大的個(gè)體將復(fù)制產(chǎn)生一個(gè)新個(gè)體加入到種群中。個(gè)體發(fā)起復(fù)制錦標(biāo)賽的概率計(jì)算如下:

(4)

式中:為當(dāng)前種群個(gè)體數(shù)量;[,]為期望種群個(gè)體數(shù)量范圍;min為最小復(fù)制概率;max為最大復(fù)制概率

232 淘汰算子

采用三元錦標(biāo)賽選擇法。種群中每個(gè)個(gè)體均有相同的概率發(fā)起淘汰錦標(biāo)賽。在發(fā)起錦標(biāo)賽的個(gè)體和在種群中隨機(jī)選取的兩個(gè)個(gè)體中,其中適應(yīng)度最小的個(gè)體將被從種群中剔除。個(gè)體發(fā)起淘汰錦標(biāo)賽的概率計(jì)算如下:

(5)

式中:min為最小淘汰概率;max為最大淘汰概率。

233 變異算子

為保持種群搜索全局空間的能力,采用如下變異算子,其過程如圖7所示。種群中每個(gè)個(gè)體均有相等的變異概率,發(fā)生變異的個(gè)體會從基因序列中隨機(jī)位置刪除一段隨機(jī)長度的基因段(首位和末位除外),并在基因序列兩斷點(diǎn)處相應(yīng)的柵格所形成的矩形空間范圍內(nèi)隨機(jī)產(chǎn)生一個(gè)新基因,并通過增加基因使其滿足上文所述約束條件,形成新的連通路徑。

圖7 變異算子Fig.7 Mutation operation

234 交叉算子

為進(jìn)一步提高種群多樣性,交叉算子采用單點(diǎn)交叉法和三元錦標(biāo)賽法。種群中每個(gè)個(gè)體被選為父個(gè)體的概率相同。在每次選取父個(gè)體后,從種群中隨機(jī)選取3個(gè)與父個(gè)體具有至少一個(gè)相同基因(基因序列首位和末位除外)的母個(gè)體,其中與父個(gè)體適應(yīng)度差值最大的母個(gè)體將與父個(gè)體進(jìn)行單點(diǎn)交叉變異操作。

2.4 精英個(gè)體與精英族系

為了實(shí)現(xiàn)多路徑規(guī)劃,本文在基因相似度的基礎(chǔ)上,提出了精英個(gè)體與精英族系的概念。

241 基因相似度

基因相似度是對兩個(gè)個(gè)體的顯性基因和隱性基因中相同基因所占比重的度量。個(gè)體對個(gè)體的基因相似度為個(gè)體和個(gè)體相同基因數(shù)量與個(gè)體基因數(shù)量的比值。個(gè)體對個(gè)體的顯性基因相似度, ,和隱性基因相似度, ,計(jì)算如下:

(6)

式中:,,,分別為個(gè)體和的顯性基因集合和隱性基因集合;Length(·)為求集合元素個(gè)數(shù)操作。

242 精英個(gè)體

在種群進(jìn)化過程中,若種群最優(yōu)適應(yīng)度值在連續(xù)代內(nèi)不發(fā)生變化,則認(rèn)為在當(dāng)前競爭環(huán)境中種群已經(jīng)進(jìn)化出了一個(gè)精英個(gè)體,精英個(gè)體所對應(yīng)的路徑至少可以認(rèn)為是陷入某一局部最優(yōu)的求解結(jié)果。若越大,精英個(gè)體為局部最優(yōu)解的可能性越低,但進(jìn)化出所需數(shù)量的精英個(gè)體所需迭代次數(shù)也越多。若越小,種群則可能來不及進(jìn)化出基因相似度較低的新的精英個(gè)體。因此,的選取需要平衡精英個(gè)體數(shù)量、路徑解的質(zhì)量和基因相似度三者間的關(guān)系。

243 精英族系

對于精英個(gè)體和個(gè)體,若其基因相似度滿足一定精英族系判別條件(如, ,>,其中為[0,1]區(qū)間內(nèi)某一恒定值),則認(rèn)為個(gè)體屬于所在精英族系。

精英族系判別條件的引入,可以實(shí)現(xiàn)對精英個(gè)體進(jìn)行族系劃分。精英族系判別條件約寬松(取值越小),屬于不同精英族系的精英個(gè)體所對應(yīng)的路徑的重合度則越小。因此,通過精英族系判別條件的選取,可以對精英個(gè)體所對應(yīng)的路徑重合度進(jìn)行調(diào)節(jié)。

2.5 適應(yīng)度函數(shù)

傳統(tǒng)路徑規(guī)劃的目標(biāo)是進(jìn)化出一個(gè)適應(yīng)度最優(yōu)的個(gè)體,其基于路徑長度的適應(yīng)度函數(shù)反應(yīng)了個(gè)體對環(huán)境的適應(yīng)能力。但對于多路徑規(guī)劃問題,所期望的是在有限的環(huán)境中進(jìn)化出適應(yīng)度總和盡量高的多個(gè)個(gè)體,因此個(gè)體間也存在相互競爭的關(guān)系。為對路徑間的重合度進(jìn)行評價(jià),本文提出了基因適應(yīng)度的概念。

采用基因競爭強(qiáng)度作為不同個(gè)體占據(jù)同一柵格時(shí)相互競爭關(guān)系強(qiáng)度的度量。對于精英個(gè)體,其所產(chǎn)生的顯性基因競爭強(qiáng)度和隱性基因競爭強(qiáng)度計(jì)算如下:

(7)

式中:coef和coef分別為顯性基因競爭強(qiáng)度系數(shù)和隱性基因競爭強(qiáng)度系數(shù)。

對于?∈,的種群顯性基因競爭強(qiáng)度()和種群隱性基因競爭強(qiáng)度()分別計(jì)算如下:

(9)

式中:為顯性基因中包含的精英個(gè)體集合;為隱性基因中包含的精英個(gè)體集合;ST為起點(diǎn)柵格序號和終點(diǎn)柵格序號的集合。

個(gè)體的基因適應(yīng)度如下:

(10)

式中:和分別為顯性基因適應(yīng)度系數(shù)和顯性基因適應(yīng)度系數(shù)。

綜合考慮路徑長度和路徑重合度,本文所用適應(yīng)度函數(shù)如下:

(11)

式中:(,+1)為和+1間的歐幾里得距離;為個(gè)體的基因序列長度。

2.6 精英選擇策略

精英個(gè)體的篩選過程就是對路徑的篩選過程,精英個(gè)體的選擇應(yīng)遵循以下原則:

(1) 同一精英族系中只能含有一個(gè)精英個(gè)體;

(2) 在精英個(gè)體數(shù)達(dá)到上限后,新的精英個(gè)體在滿足使所有精英個(gè)體適應(yīng)度總和增大的情況下,會取代原有精英個(gè)體。

基于以上原則,根據(jù)新的精英個(gè)體elite更新原精英個(gè)體集合的偽代碼如算法1所示。

算法 1 精英選擇策略輸入 精英個(gè)體elite,精英個(gè)體集合E輸出 精英個(gè)體集合E1 初始化:最大精英個(gè)體數(shù)EliteUpLimit,精英族系判別條件Ss2 IsNewFamily=13 For ?e∈E do4 Sx,elite,e=GeneticSimility(elite, e)5 If Sx,elite,e>Ss do6 IsNewFamily=07 relativeelite=e8 break9 If IsNewFamily=1 and Length(E)OldAllFitness do15 E←E-relativeelite+elite16 Return E

2.7 EFGA偽代碼

EFGA的偽代碼如算法2所示。

算法 2 EFGA輸入 所需路徑數(shù)K,柵格空間Map輸出 精英個(gè)體集合E1 初始化:復(fù)制概率Pe,淘汰概率Pr,變異概率Pm,交叉概率Pc,個(gè)體集合P,個(gè)體數(shù)N2 P←InitializePopulation(Map)3 E=?4 For i=1 to i=N do5 Pr←ReplicationProbability(P)6 Pe←EliminationProbability(P)7 For ?individual∈P do8 findividual←Fitness(individual)9 If max(findividual)>maxFitness do10 maxFitness,elite=max(findividual)11 k=012 Else do13 k=k+114 If k>K do15 E←EliteSelectionStrategy(E, elite)16 GeneFitnessUpdate()17 For ?individual∈P do18 If random()

3 MAPP

以航行耗時(shí)最短為目標(biāo)的無人集群路徑規(guī)劃是指在滿足智能體與障礙、智能體與智能體間均不發(fā)生碰撞的條件下,以無人集群從起始位置到終點(diǎn)位置的航行耗時(shí)作為評價(jià)參數(shù)的路徑規(guī)劃問題。

針對此類路徑規(guī)劃問題,本文在上述EFGA的基礎(chǔ)上,引入當(dāng)量路徑長度的概念,提出了一種MAPP方法。

3.1 當(dāng)量路徑長度

當(dāng)量路徑長度是對智能體或智能體編隊(duì)的出發(fā)等待時(shí)間和沿著路徑從起點(diǎn)到終點(diǎn)所需走過的路徑長度的一種度量。由于沿著同一路徑航行的智能體或智能體編隊(duì)需保持一定的安全距離,因此智能體或智能體編隊(duì)只能在保持安全距離的前提下依次出發(fā)沿著路徑航行,這就導(dǎo)致后出發(fā)的智能體或智能體編隊(duì)需要等待一定時(shí)間。對于路徑Path,若規(guī)模為×的水下無人集群形成隊(duì)規(guī)模為的編隊(duì)依次沿著該路徑行進(jìn),編隊(duì)間的安全距離為,則當(dāng)量路徑長度計(jì)算如下:

=+(-1)

(12)

式中:為路徑Path的實(shí)際長度;(-1)是對第個(gè)編隊(duì)的出發(fā)等待時(shí)間的評價(jià)項(xiàng)。

當(dāng)AUV集群沿著多條路徑航行時(shí),路徑規(guī)劃結(jié)果應(yīng)使路徑集合中的最大當(dāng)量路徑長度盡量小。當(dāng)集群規(guī)模、航行速度均相同時(shí),編隊(duì)規(guī)模越大,AUV集群的航行時(shí)間相對越短,但對路徑的寬度要求也越高。

3.2 MAPP方法

針對個(gè)智能體和條路徑的MAPP問題,基于EFGA和當(dāng)量路徑長度設(shè)計(jì)MAPP方法偽代碼如算法3所示。

算法 3 MAPP輸入 所需路徑數(shù)K,柵格空間Map,智能體集合AGENT輸出 智能體路徑集合PATHAGENT1 初始化:智能體間安全距離safedistance2 PATH←EFGA(K, Map)3 For ?path∈PATH do4 PATHAGENT(path)=?5 Le(path)=L(path)6 For ?agent∈AGENT do7 path=min(Le)8 PATHAGENT(path)←PATHAGENT(path)+a-gent9 Le(path)=Le(path)+safedistance10Return PATHAGENT

4 仿真實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證EFGA求解多路徑問題和AUV集群路徑規(guī)劃問題的可行性、算法性能以及參數(shù)設(shè)定對求解結(jié)果的影響,在Matlab R2016b中進(jìn)行了相關(guān)仿真,硬件系統(tǒng)環(huán)境為i5-10400 @ 2.90Ghz,16.0 GB RAM,操作系統(tǒng)版本為Windows10 19041.746。

EFGA參數(shù)設(shè)定為初代種群個(gè)體數(shù)30,期望種群個(gè)體數(shù)范圍[100,200],最大進(jìn)化代數(shù)500,精英族系判別條件max(, ,,,, ,, ,,, ,)>05,其余參數(shù)如表1所示。其中,取柵格空間總行數(shù)和總列數(shù)中的最大值。

表1 EFGA參數(shù)

4.1 簡單環(huán)境下多路徑規(guī)劃

為驗(yàn)證EFGA在簡單環(huán)境中求解多路徑問題的可行性,在圖8所示的20×20柵格空間中,起點(diǎn)為(2,2),終點(diǎn)為(19,19),利用表1中EFGA-2和EFGA-3算法對所需路徑分別為2和3的多路徑規(guī)劃問題進(jìn)行求解,并用EFGA-1進(jìn)行單路徑規(guī)劃作為對比。在分別進(jìn)行100次仿真后,取典型理想解和典型不理想解如圖8所示,統(tǒng)計(jì)數(shù)據(jù)如表2所示。

圖8 簡單環(huán)境下多路徑規(guī)劃典型求解結(jié)果Fig.8 Typical results of multi-path planning in simple environment

表2 EFGA-1～EFGA-3的仿真統(tǒng)計(jì)數(shù)據(jù)

由圖8(a)～圖8(c)可見,EFGA同時(shí)具備規(guī)劃單路徑和多路徑的能力,精英族系判別條件和基因適應(yīng)度的引入使各路徑間能保持較低的重合度,使可達(dá)空間得到充分有效的利用。但圖8(d)中的求解結(jié)果表明算法所規(guī)劃的多路徑可能會存在“交叉”現(xiàn)象,后續(xù)可通過引入交叉懲罰函數(shù)來降低此現(xiàn)象發(fā)生的可能性。

在表2中：平均收斂代數(shù)為所有精英個(gè)體已收斂時(shí)代數(shù)的平均值;平均收斂耗時(shí)為所有精英個(gè)體已收斂時(shí)算法運(yùn)行時(shí)間的平均值;平均路徑重合度為每條路徑的重合長度之和與所有路徑的總長度之比。由表2分析可知,隨著所需路徑的增多,算法平均收斂耗時(shí)近似成比例增加,但平均路徑長度無明顯增長,平均路徑重合度雖有所增大但仍維持在很低水平。上述分析表明,針對簡單環(huán)境中的多路徑規(guī)劃問題,EFGA能穩(wěn)定地規(guī)劃出重合度很低、路徑長度相近的多條路徑。

4.2 競爭強(qiáng)度系數(shù)對路徑重合度的調(diào)節(jié)能力

由于過大的競爭強(qiáng)度系數(shù)通常會導(dǎo)致種群個(gè)體多樣性的急劇銳減而出現(xiàn)過早收斂的情況,因此可以采用逐步增大競爭強(qiáng)度系數(shù)的方法在維持種群個(gè)體多樣性基礎(chǔ)上逐漸降低路徑重合度。為驗(yàn)證競爭強(qiáng)度系數(shù)對路徑重合度的調(diào)節(jié)能力,利用表1中EFGA-4～EFGA-6算法在圖8柵格空間中對路徑規(guī)劃問題進(jìn)行求解。分別進(jìn)行100次仿真后,統(tǒng)計(jì)數(shù)據(jù)如表3所示。

表3 EFGA-4～EFGA-6的仿真統(tǒng)計(jì)數(shù)據(jù)

分析表3中數(shù)據(jù)可知,在其余參數(shù)相同的情況下,隨著競爭強(qiáng)度系數(shù)的增大,路徑重合度呈現(xiàn)減小趨勢,平均路徑長度呈現(xiàn)緩慢增長的趨勢,但路徑長度變化仍在可接受范圍內(nèi)。

以上分析表明,針對簡單環(huán)境中的多路徑規(guī)劃問題,可以通過選取合適的競爭強(qiáng)度系數(shù)實(shí)現(xiàn)對路徑重合度的有效調(diào)節(jié)。

4.3 復(fù)雜環(huán)境下路徑規(guī)劃

為驗(yàn)證EFGA在復(fù)雜環(huán)境中規(guī)劃路徑的能力,在圖9所示相對復(fù)雜系數(shù)=3的50×50柵格空間中,起點(diǎn)為(3,3),終點(diǎn)為(38,38),利用表1中EFGA-7～EFGA-9算法對所需路徑分別為1～3的路徑規(guī)劃問題進(jìn)行求解。分別進(jìn)行100次仿真后,取典型理想解和典型不理想解如圖9所示,統(tǒng)計(jì)數(shù)據(jù)如表4所示。

圖9 復(fù)雜環(huán)境下多路徑規(guī)劃典型求解結(jié)果Fig.9 Typical results of multi-path planning in complex environment

表4 EFGA-7～EFGA-9的仿真統(tǒng)計(jì)數(shù)據(jù)

由圖9(a)可見,EFGA具備規(guī)劃具有一定寬度的路徑的能力。圖9(b)和圖9(c)表明,即使在環(huán)境可行空間非常有限的情況下,EFGA也可以求解出重合度較低的多路徑解。但圖9(d)中的路徑規(guī)劃結(jié)果表明,隨著路徑數(shù)量的增多,有限的可行空間可能會導(dǎo)致在某些狹隘處路徑間出現(xiàn)大范圍重合或“交叉”現(xiàn)象。

在表4中，平均路徑重合度為通過分析表4統(tǒng)計(jì)數(shù)據(jù)可知,隨著所需路徑的增多,算法平均收斂耗時(shí)顯著增加,平均路徑重合度也有明顯增長,但平均路徑長度增幅仍維持在較低水平。由表2和表4數(shù)據(jù)可知,相比于簡單環(huán)境路徑規(guī)劃問題,由于隱性基因造成的算法空間復(fù)雜度增大,算法求解復(fù)雜環(huán)境中路徑規(guī)劃問題所需時(shí)間顯著增加,路徑重合度也有明顯增大。

4.4 AUV集群路徑規(guī)劃

為了驗(yàn)證MAPP方法求解不同情形下AUV集群路徑規(guī)劃問題的可行性,并與傳統(tǒng)單路徑規(guī)劃方法進(jìn)行對比驗(yàn)證該方法在減少AUV集群航行時(shí)間上的有效性,在圖10所示20 m×20 m環(huán)境空間中分別進(jìn)行獨(dú)立航行方式對比仿真和編隊(duì)航行方式對比仿真,其中黑色區(qū)域?yàn)檎系K,黃色區(qū)域?yàn)槠瘘c(diǎn),藍(lán)色區(qū)域?yàn)榻K點(diǎn)。

圖10 環(huán)境空間Fig.10 Environment space

4.4.1 獨(dú)立航行方式

為了比較采用MAPP方法和傳統(tǒng)單路徑規(guī)劃方法時(shí)AUV集群的航行總耗時(shí),對圖10所示環(huán)境空間基于相對復(fù)雜系數(shù)的粒度劃分原則進(jìn)行柵格粒度為1 m的柵格空間建模,利用表1中EFGA-10～EFGA-12算法對所需路徑分別為1～3的路徑規(guī)劃問題進(jìn)行求解,并基于路徑互不重合的求解結(jié)果用上述MAPP方法進(jìn)行AUV集群航行模擬,AUV集群規(guī)模取10,編隊(duì)規(guī)模取1,AUV航行速度取1 m/s,AUV間安全距離取1 m。在分別進(jìn)行100次仿真后,取典型路徑規(guī)劃結(jié)果如圖11所示,統(tǒng)計(jì)數(shù)據(jù)如表5所示。

圖11 獨(dú)立航行方式情況下AUV集群路徑規(guī)劃典型求解結(jié)果Fig.11 Typical results of AUV swarm path planning based on independent navigation type

表5 基于EFGA-10～EFGA-12的AUV集群路徑規(guī)劃結(jié)果統(tǒng)計(jì)數(shù)據(jù)

在表5中，平均當(dāng)量路徑長度為EFGA路徑規(guī)劃完成后的平均當(dāng)量路徑長度;平均行進(jìn)耗時(shí)為第一臺AUV出發(fā)時(shí)間與最后一臺AUV到達(dá)時(shí)間的間隔。通過分析表5統(tǒng)計(jì)數(shù)據(jù)可知,AUV集群沿著2條路徑行進(jìn)和3條路徑行進(jìn)的行進(jìn)耗時(shí)比沿著單路徑行進(jìn)的行進(jìn)耗時(shí)分別減少了11.8%和15.2%。隨著路徑的增多,增加路徑數(shù)所帶來的行進(jìn)耗時(shí)減幅逐漸減小,而EFGA規(guī)劃互不重合的路徑集合所需時(shí)間卻顯著增加,因此通常需要綜合考慮柵格空間大小、集群規(guī)模和計(jì)算資源等因素選取合適的路徑數(shù)。

上述分析表明,本文所提出的MAPP方法可以在基因適應(yīng)度的基礎(chǔ)上利用EFGA不斷搜索當(dāng)前競爭環(huán)境下的最優(yōu)個(gè)體,得到無沖突的最優(yōu)路徑集合,并在保證AUV與障礙、AUV間均不發(fā)生碰撞的條件下,為每臺AUV規(guī)劃路徑長度最優(yōu)的航行路徑,解決了標(biāo)準(zhǔn)遺傳算法、A算法等單路徑規(guī)劃方法無法充分利用可行空間規(guī)劃多條路徑的問題,達(dá)到縮短AUV集群的航行時(shí)間的目的。

4.4.2 編隊(duì)航行方式

為了進(jìn)一步驗(yàn)證MAPP方法解決AUV在形成不同規(guī)模的編隊(duì)隊(duì)形時(shí)的路徑規(guī)劃問題的可行性,在圖10所示環(huán)境空間中基于相對復(fù)雜系數(shù)的粒度劃分原則分別進(jìn)行柵格粒度為1 m、0.66 m、1 m的柵格空間建模,并利用表1中EFGA-13～EFGA-15算法分別對無編隊(duì)、形成三機(jī)三角編隊(duì)、形成六機(jī)三角編隊(duì)的AUV集群進(jìn)行路徑規(guī)劃,AUV集群規(guī)模取12,AUV航行速度取1 m/s,AUV間安全距離取1 m,AUV編隊(duì)與障礙間安全距離取0.5 m,編隊(duì)間安全距離取2 m。分別進(jìn)行100次仿真后,取典型路徑規(guī)劃結(jié)果如圖12所示,統(tǒng)計(jì)數(shù)據(jù)如表6所示。

圖12 AUV編隊(duì)集群路徑規(guī)劃典型求解結(jié)果Fig.12 Typical results of AUV formation swarm path planning

表6 基于EFGA-13～EFGA-15的AUV編隊(duì)集群路徑規(guī)劃結(jié)果

由圖12可見,在圖12(a)所示無編隊(duì)情形下,AUV可以通過較為狹隘的區(qū)域,在環(huán)境可行空間充裕的情況下,規(guī)劃數(shù)量較多的路徑可以達(dá)到減少AUV集群航行時(shí)間的目的。在圖12(b)所示形成三機(jī)三角編隊(duì)情形下,AUV編隊(duì)由于需要保持一定的隊(duì)形,隊(duì)形規(guī)模限制了AUV不能通過狹隘區(qū)域,因此通過EFGA算法的隱性基因?qū)崿F(xiàn)對路徑寬度的調(diào)節(jié)。同時(shí)受環(huán)境所限,此時(shí)EFGA規(guī)劃的路徑長度有所增大。在圖12(c)所示形成六機(jī)三角編隊(duì)情形下,AUV編隊(duì)隊(duì)形尺寸進(jìn)一步增大,AUV編隊(duì)僅能通過寬闊區(qū)域,所需路徑寬度也相應(yīng)增大,此時(shí)EFGA規(guī)劃的最短路徑長度進(jìn)一步增大,且受環(huán)境所限,僅存在一條最短路徑,此時(shí)AUV航行方案只能采取逐個(gè)編隊(duì)依次前行方式。

通過分析表6統(tǒng)計(jì)數(shù)據(jù)可知,無編隊(duì)情形下AUV集群行進(jìn)時(shí)間最短,這是由于EFGA算法充分利用了環(huán)境空間中的狹隘通道求解出3條無碰撞的最優(yōu)路徑,有利于基于當(dāng)量路徑長度規(guī)劃得到航行時(shí)間最短的AUV集群航行方案。在形成三機(jī)三角編隊(duì)情形下,原始路徑長度有所增大,相應(yīng)的AUV集群行進(jìn)時(shí)間有所增加。在形成六機(jī)三角編隊(duì)情形下,AUV集群行進(jìn)時(shí)間最大,這是由于環(huán)境中僅存在一條寬度足夠的最短路徑,AUV編隊(duì)只能采取逐個(gè)編隊(duì)依次前行的方式,不能充分利用環(huán)境空間中的狹隘通道。

上述分析表明,本文提出的MAPP方法不僅能解決常規(guī)的無編隊(duì)AUV集群最優(yōu)路徑規(guī)劃問題,通過隱性基因?qū)β窂綄挾冗M(jìn)行調(diào)節(jié),還可以在保證柵格空間建模精度的情況下,根據(jù)實(shí)際AUV集群的編隊(duì)需求,求解不同路徑數(shù)量和不同路徑寬度的AUV編隊(duì)集群最優(yōu)路徑規(guī)劃問題,解決了標(biāo)準(zhǔn)遺傳算法、A算法等單路徑規(guī)劃方法難以滿足AUV編隊(duì)集群對更為高效的多路徑航行方式、與不同集群規(guī)模相匹配的可調(diào)路徑寬度需求的問題,達(dá)到提高AUV集群在不同應(yīng)用情形下求解最優(yōu)路徑規(guī)劃問題能力的目的。

5 結(jié) 論

MAPP是水下無人集群航行控制中至關(guān)重要的一環(huán),本文針對AUV集群路徑規(guī)劃問題,提出了EFGA,并在此基礎(chǔ)上設(shè)計(jì)了一種MAPP方法。具體工作如下:

(1) 提出了基于編隊(duì)規(guī)模和基于相對復(fù)雜系數(shù)的兩種柵格粒度劃分方法,并在此基礎(chǔ)上對顯性基因和隱性基因進(jìn)行了定義,通過柵格建模、顯性基因和隱性基因?qū)崿F(xiàn)了對智能體與障礙、智能體間不發(fā)生碰撞條件的描述。

(2) 將基因適應(yīng)度項(xiàng)引入適應(yīng)度函數(shù),實(shí)現(xiàn)對路徑長度和路徑重合度的綜合評價(jià),并在精英個(gè)體和精英族系的基礎(chǔ)上,針對多路徑規(guī)劃問題提出了精英族系選擇策略和EFGA,通過隱性基因?qū)崿F(xiàn)對路徑寬度的調(diào)節(jié),同時(shí)競爭強(qiáng)度系數(shù)的引入可以實(shí)現(xiàn)對路徑重合度的有效調(diào)節(jié)。仿真結(jié)果表明,該算法具有求解無沖突的路徑集合的能力,可以為解決以同時(shí)到達(dá)為目的的路徑規(guī)劃問題提供參考。

(3) 設(shè)計(jì)了一種基于EFGA的MAPP方法。該方法根據(jù)EFGA求解的無沖突多路徑集合,根據(jù)當(dāng)量路徑長度將AUV集群合理分配到各個(gè)路徑上。通過對AUV集群路徑規(guī)劃問題的仿真驗(yàn)證,與單路徑規(guī)劃相比,該方法所得到的路徑規(guī)劃方案的AUV集群航行耗時(shí)明顯減少,且能根據(jù)不同集群規(guī)模規(guī)劃相應(yīng)寬度的最優(yōu)路徑集合,解決了單路徑規(guī)劃方法不能充分利用環(huán)境空間規(guī)劃多條可行路徑的問題和不能滿足AUV編隊(duì)對可調(diào)路徑寬度需求的問題。

值得指出的是,在競爭強(qiáng)度系數(shù)較低的情況下,EFGA所規(guī)劃的路徑存在“交叉”現(xiàn)象,降低了算法的收斂速率,進(jìn)一步研究可以考慮在適應(yīng)度函數(shù)中引入交叉懲罰項(xiàng)或優(yōu)化交叉算子以避免此現(xiàn)象的發(fā)生。