基于混合蟻群算法的無人船航行路徑自主規(guī)劃

陳宇文，徐 照

（1. 南京工業(yè)大學(xué) 土木工程學(xué)院，江蘇 南京 210000；2. 東南大學(xué) 土木工程學(xué)院，江蘇 南京 210000）

0 引 言

無人船能在人力不可為的條件下實現(xiàn)水面和水下目標(biāo)偵察與監(jiān)視等任務(wù)[1]，是當(dāng)前水面智能體的典型代表，受到各界普遍關(guān)注。在復(fù)雜工作環(huán)境下，航行路徑規(guī)劃是無人船正常工作的基礎(chǔ)與保障[2]。

王立鵬等[3]在研究艦船路徑規(guī)劃問題過程中，以海圖為基礎(chǔ)，確定航線與陸地物標(biāo)的對應(yīng)關(guān)系，采用遺傳算法對規(guī)劃路徑進行尋優(yōu)，獲取最優(yōu)規(guī)劃路徑。該方法在目標(biāo)工作環(huán)境較為復(fù)雜的條件下，規(guī)劃結(jié)果精度無法保障。周怡等[4]在研究艦船路徑規(guī)劃問題過程中，以防碰撞為目的構(gòu)建航行路徑規(guī)劃模型，采用優(yōu)化后的DDPG 算法求解模型獲取最優(yōu)路徑。該方法在實際應(yīng)用過程中無法保障收斂速度與尋優(yōu)性能的平衡性。

針對上述問題，提出基于混合蟻群算法的無人船航行路徑自主規(guī)劃方法，獲取最優(yōu)航行路徑。

1 無人船航行路徑的自主規(guī)劃

1.1 環(huán)境建模

無人船航行路徑自主規(guī)劃之前，需先構(gòu)建無人船工作環(huán)境模型，由此能在無人船工作環(huán)境中明確哪些區(qū)域是安全區(qū)域，哪些區(qū)域為障礙物區(qū)域。設(shè)定無人船工作環(huán)境中的障礙物均處于靜止?fàn)顟B(tài)，由于柵格法描述簡單，易于實現(xiàn)，因此通過柵格法構(gòu)建工作環(huán)境模型[5]，以A 和B 分別表示安全區(qū)域與障礙物區(qū)域。以方形地圖表示無人船工作環(huán)境，柵格法中包含若干個邊長為1 的小正方形，其中白色區(qū)域和黑色區(qū)域分別為安全區(qū)域和障礙物區(qū)域。

以方便后續(xù)對無人船工作環(huán)境信息的描述為目的，由上至下、由左至右的對柵格實施編號處理。在柵格間距確定過程中的主要依據(jù)為柵格點中心位置坐標(biāo)，所以，可通過式（1）描述柵格號與無人船工作環(huán)境坐標(biāo)(x,y)間的對應(yīng)關(guān)系：

式中：ES和ceil 分別為小柵格的邊長和向上取余函數(shù)；n和MM分別為小柵格的序號和柵格的整體行數(shù)；mod為余函數(shù)。

1.2 航行路徑自主規(guī)劃數(shù)學(xué)模型

構(gòu)建無人船工作環(huán)境模型后，再構(gòu)建無人船航行路徑自主規(guī)劃的數(shù)學(xué)模型。無人船航行路徑自主規(guī)劃問題可描述為：在任意規(guī)劃空間內(nèi)，符合相應(yīng)約束條件g(γ)=0的基礎(chǔ)上，依照某一航行性能評價指標(biāo)J，規(guī)劃確定無人船的航行路徑，也就是由起始點ES至目標(biāo)點EG，同時符合相應(yīng)約束條件的一系列路徑節(jié)點Γ={ES,E1,E2,···,En,EG}。

利用式（2）能夠描述無人船航行路徑自主規(guī)劃數(shù)學(xué)模型：

式中：D和 φ分別為水動力系數(shù)和水密度；v和 ρ分別為無人船航行速度和橫截面積； φ和H分別為無人船航行路徑長度和機械效率。

約束條件如下：

1）地形與威脅約束。無人船航行過程中，為保障航行安全性，需防止與障礙物產(chǎn)生碰撞，因此設(shè)定無人船工作環(huán)境中，障礙物與危險區(qū)域均為不可穿越的區(qū)域[6]。若以R'f表示在無人船工作區(qū)域內(nèi)不可穿越區(qū)域集合，考慮無人船自身的尺寸，同時考慮規(guī)劃路徑的平滑性，需對障礙物與危險區(qū)域?qū)嵤┡蚧幚?，由此保障無人船航行的安全性。以Rf=εR'f表示通過膨化處理的集合，也就是擴大障礙物與危險區(qū)域大小，依照無人船實際尺寸可確定膨化系數(shù)。以f(x,y)表示規(guī)劃出的無人船航行路徑，由此得到約束公式描述：

2）航程上限約束。無人船內(nèi)部攜帶能量對于航行距離上限Lmax產(chǎn)生直接影響[7]，因此在無人船航行路徑自主規(guī)劃過程中需設(shè)定相關(guān)約束條件，公式描述如下：

式中，φg和δg分別為規(guī)劃路徑長度與實際航行路徑與規(guī)劃路徑的偏差。

3）轉(zhuǎn)彎角度約束。無人船航行轉(zhuǎn)彎過程中受自身機動性能影響[8]，導(dǎo)致角度受到一定限制，以 ξ 和 ?i分別表示無人船允許的最大拐角與任意拐彎角，約束條件公式描述如下：

4）路徑平滑度約束。無人船航行路徑越平滑，對自身的機動性要求越低。考慮無人船航行過程中需消耗大量能量，為路徑的平滑性能夠降低能源消耗。描述該約束條件公式為：

式中：Sk和n分別為第k 條路徑累積轉(zhuǎn)彎角度和路徑點數(shù)量；R為無人船航行路徑的最大轉(zhuǎn)彎角度；r和Smax分別為路徑內(nèi)的轉(zhuǎn)彎角度和允許的最大平滑度。

1.3 基于混合蟻群算法的模型求解

考慮蟻群算法應(yīng)用過程中存在初始階段搜索效率差、有較大概率獲取局部最優(yōu)結(jié)果等問題，將其與粒子群算法相結(jié)合，提出混合蟻群算法。針對式（2）無人船航行路徑自主規(guī)劃數(shù)學(xué)模型，采用混合蟻群算法進行求解。將由無人船航行路徑解集內(nèi)選取最優(yōu)路徑的問題描述為螞蟻搜索食物的問題，設(shè)定無人船航行路徑解集內(nèi)各解以及最優(yōu)解，分別為螞蟻搜索食物過程中路經(jīng)的城市和目標(biāo)點。

依照無人船航行路徑自主規(guī)劃的實際情況，初始化混合蟻群算法參數(shù)，設(shè)定蟻群數(shù)量與最大迭代次數(shù)分別設(shè)定為200±100 次和150±50 次，信息素?fù)]發(fā)系數(shù)與信息素增加濃度范圍分別為0.5±0.2 和5.5±4.5，信息素初始濃度范圍與啟發(fā)因子關(guān)鍵度范圍分別為55±45和5±2，信息素關(guān)鍵度范圍為5±2。

計算螞蟻個體的適應(yīng)度v，其所描述的是螞蟻種群的屬性，能夠描述螞蟻的優(yōu)劣水平，公式描述如下：

式中：w和zi分別為慣性權(quán)重與第i只螞蟻的位置；c和 ε分別為螞蟻個體學(xué)習(xí)因子和范圍為[0,1]的隨機數(shù)；pi和si分別為第i 只螞蟻個體極限與速度的第d 維分量。

螞蟻依照設(shè)定的迭代次數(shù)對無人船最優(yōu)航行路徑實施全局搜索，每實施一次搜索即完成一次迭代過程。螞蟻在搜索無人船最優(yōu)航行路徑過程中會產(chǎn)生信息素，所以每次迭代過程后就需更新搜索路徑中遺留的信息素τ(t+1)，公式描述如下：

式中： ρ 和 ?分別為啟發(fā)因子關(guān)鍵度和信息素更新系數(shù)； Δτ為與收斂次數(shù)成線性相關(guān)性的函數(shù)。

為避免目標(biāo)迭代過程中陷入局部最優(yōu)問題，對信息素上限值實施設(shè)定，公式描述如下：

式中，τmax和H分別表示信息素上限值與混沌變量。約束不同搜索路徑上的信息素濃度，令無人船最優(yōu)航行路徑搜索空間內(nèi)全部路經(jīng)均由被選擇的概率，通過式（9）更新的蟻群位置與信息素，確定當(dāng)前蟻群位置是否為個體極值，若是個體極值，就需將當(dāng)前位置與全局極值進行對比；若不是個體極值，則需返回上一過程再次確定。在滿足迭代標(biāo)準(zhǔn)后，即可終止運算過程，輸出信息濃度最高的解作為最優(yōu)解，即無人船航行路徑自主規(guī)劃的最優(yōu)路徑。

2 實驗結(jié)果

為驗證本文方法在路徑自主規(guī)劃中的應(yīng)用效果，選取某型號的無人船為研究對象，表1 為研究對象相關(guān)參數(shù)。設(shè)定研究對象的工作環(huán)境大小為24×20 km，采用本文方法對研究對象航行路徑進行自主規(guī)劃。

表1 研究對象相關(guān)參數(shù)Tab. 1 Relevant parameters of the research object

采用本文方法獲取的研究對象最優(yōu)航行路徑規(guī)劃結(jié)果，如圖1 所示。圖中，黑色方塊為研究對象工作環(huán)境中的障礙物與危險區(qū)域，白色圓形為研究對象的起始點坐標(biāo)與終點坐標(biāo)。

圖1 本文方法航行路徑自主規(guī)劃結(jié)果Fig. 1 The results of autonomous navigation path planning using the method presented in this article

分析圖1 可知，采用本文方法能夠有效構(gòu)建研究對象工作環(huán)境模型，同時通過計算能夠有效獲取研究對象最優(yōu)航行路徑，該路徑能夠有效避開全部障礙物與危險區(qū)域。

為驗證本文方法航行路徑規(guī)劃結(jié)果的優(yōu)勢性，對比采用本文方法前后研究對象的航行路徑，結(jié)果如表2所示。

表2 研究對象航行路徑對比結(jié)果Tab. 2 Comparison results of navigation paths of research subjects

分析表2 可知，采用本文方法對研究對象航行路徑進行規(guī)劃后，最優(yōu)路徑長度與采用本文方法前相比減少1.586 1 km，平均能耗降低6.4211 kJ，路徑規(guī)劃時間降低3.565 s。以上數(shù)據(jù)充分說明采用本文方法能夠有效保障研究對象航行路徑規(guī)劃的精度與實時性，降低研究對象航行能耗，保障研究對象航行過程中的經(jīng)濟性。

3 結(jié) 語

本文研究了一種基于混合蟻群算法的無人船航行路徑自主規(guī)劃方法，在工作環(huán)境模型基礎(chǔ)上構(gòu)建航行路徑規(guī)劃數(shù)學(xué)模型，并采用混合蟻群算法求解模型。實驗結(jié)果顯示，本文方法所構(gòu)建的工作環(huán)境模型較為準(zhǔn)確，所得最優(yōu)路徑規(guī)劃結(jié)果路徑最短、能耗最低。