陳改霞，葉蕭然

（河南理工大學(xué)鶴壁工程技術(shù)學(xué)院，河南 鶴壁 458030）

0 引言

無人船的智能控制十分關(guān)鍵，其核心是避障路線規(guī)劃設(shè)計(jì)，避障路線規(guī)劃效果是判斷無人船智能航行水平的重要依據(jù)[1-2]。無人船避障路線規(guī)劃是以航行環(huán)境建模為前提，通過智能優(yōu)化算法實(shí)現(xiàn)無人船最佳避障路線的設(shè)計(jì)[3-4]。隨著技術(shù)手段的不斷革新及智能化水平的提高，各種智能算法被引入到避障路線規(guī)劃中，實(shí)現(xiàn)無人船航行效率與避障能力的大幅提升。

李清亮等[5]為使無人船能夠安全航行于含有障礙物的水域環(huán)境，在障礙物區(qū)域標(biāo)記的基礎(chǔ)上，采用最優(yōu)時(shí)間控制目標(biāo)函數(shù)描述無人船避障問題，通過控制參數(shù)優(yōu)化和時(shí)間尺度變換對(duì)優(yōu)化問題求解，再基于精確罰函數(shù)實(shí)現(xiàn)各狀態(tài)約束的處理，從而實(shí)現(xiàn)無人船航跡規(guī)劃和自動(dòng)避障。但是該算法求解難度較高，優(yōu)化參數(shù)的選取對(duì)無人船避障路線規(guī)劃效果影響較大。呂進(jìn)鋒等[6]通過在海圖上進(jìn)行節(jié)點(diǎn)設(shè)置與擴(kuò)充，完成路徑網(wǎng)絡(luò)圖的建立后，采用改進(jìn)和聲算法實(shí)現(xiàn)無人船避障路線優(yōu)化，該算法會(huì)因障礙物節(jié)點(diǎn)位置改變而使規(guī)劃的避障路線不可行，且規(guī)劃路線無法滿足最短要求。蟻群算法是可實(shí)現(xiàn)全局路徑規(guī)劃的智能優(yōu)化算法，通過正反饋機(jī)制指引路徑規(guī)劃問題逐步向最優(yōu)解逼近，具備強(qiáng)大的魯棒性能。因此，本文設(shè)計(jì)復(fù)雜開放水域的無人船避障路線蟻群規(guī)劃算法，保證全局收斂效率，同時(shí)規(guī)劃出具有較少拐點(diǎn)、路徑最短的避障路線。

1 無人船避障路線蟻群規(guī)劃算法

1.1 復(fù)雜開放水域障礙物柵格化處理

依據(jù)無人船半徑對(duì)復(fù)雜開放水域環(huán)境中的障礙物作膨脹處理后，將障礙物所在柵格填充完整，保證無人船在復(fù)雜開放水域航行過程不發(fā)生碰撞。障礙物柵格化處理如圖1 所示。

圖1 障礙物的柵格化處理Fig.1 Grid processing of obstacles

改進(jìn)蟻群算法通過對(duì)各柵格中心點(diǎn)進(jìn)行查詢，實(shí)現(xiàn)無人船避障路線規(guī)劃。

1.2 蟻群算法

蟻群算法是一種智能優(yōu)化算法，其設(shè)計(jì)靈感源于螞蟻覓食行為[8]，螞蟻在尋找食物時(shí)，會(huì)將一種特殊物質(zhì)分泌在其食物搜索路徑中，完成一段時(shí)間搜索后，距離相對(duì)較小的搜索路徑上含有的信息素含量較高，其他螞蟻將按照信息素高的路徑繼續(xù)搜索。

螞蟻在覓食時(shí)，將搜索節(jié)點(diǎn)的信息素含量以及啟發(fā)信息作為依據(jù)，完成后續(xù)搜索節(jié)點(diǎn)的確定。對(duì)于第k只螞蟻，由節(jié)點(diǎn)i移動(dòng)到節(jié)點(diǎn)j的轉(zhuǎn)移概率為：

式中：kallow為可供該螞蟻移動(dòng)的所有節(jié)點(diǎn)集合；在t時(shí)間點(diǎn)下，τij(t) 為節(jié)點(diǎn)i與節(jié)點(diǎn)j的連接路徑上的信息素濃度；ρij(t) 表示啟發(fā)函數(shù)，通過 ρij(t)計(jì)算得到，dij為節(jié)點(diǎn)i至節(jié)點(diǎn)j的距離，dij與成反比例關(guān)系，當(dāng)dij取最小值，可達(dá)到最大；參數(shù) α用于描述螞蟻搜索路徑中信息素濃度的重要程度，通過參數(shù)β可實(shí)現(xiàn)搜索路徑中啟發(fā)信息重要程度的描述。

螞蟻覓食過程中分泌的信息素具有揮發(fā)性，蟻群中各螞蟻均執(zhí)行完搜索任務(wù)后，將對(duì)各搜索路徑上的信息素濃度進(jìn)行調(diào)整，公式為：

其中：λ表示揮發(fā)因子，決定了信息素的揮發(fā)速度，其值較大，信息素可易揮發(fā)，通過 λ可實(shí)現(xiàn)螞蟻搜索路徑信息素濃度的調(diào)節(jié)，以防止信息素持續(xù)累積；?τij表示對(duì)于搜索路徑ij，全部螞蟻在其上留下的信息素濃度大?。槐硎疚浵?k在其上殘留的信息素濃度大小，可通過下式對(duì)其進(jìn)行求解：

式中：Q表示對(duì)于螞蟻k，其執(zhí)行一次搜索任務(wù)分泌的信息素?cái)?shù)量，其值取常數(shù)；Lk表示搜索路徑總長。

1.3 基于改進(jìn)蟻群算法的無人船避障路線規(guī)劃

1.3.1 啟發(fā)信息的改進(jìn)

將無人船受到的勢場信息融入到啟發(fā)信息中，實(shí)現(xiàn)啟發(fā)信息的改進(jìn)處理，確保螞蟻沿著合力方向執(zhí)行搜索任務(wù)。勢場合力啟發(fā)信息通過下式進(jìn)行描述：

其中：C為常數(shù)，其值大于0；Ftol表示勢場合力，其與螞蟻可能搜索路徑所成角度表示為θ。此種狀況下，螞蟻更傾向沿較小 θ方向進(jìn)行后續(xù)搜索節(jié)點(diǎn)的選取。將無人船行駛環(huán)境勢場信息融入到啟發(fā)信息中，對(duì)提高無人船避障水平具有重要意義。

將 ρs(t) 與 ρij(t)相乘即可確定考慮勢場信息與距離信息的啟發(fā)信息，計(jì)算公式為：

在人工勢場法中，當(dāng)目標(biāo)節(jié)點(diǎn)引力與障礙物斥力相同時(shí)，勢場合力將等于0，將獲得一個(gè)局部最小值，為避免無人船避障路線規(guī)劃陷入局部最小問題，將勢場力融入到蟻群算法自身啟發(fā)信息中，可確保無人船在勢場合力等于0 時(shí)，也能實(shí)現(xiàn)最優(yōu)避障路線規(guī)劃。

1.3.2 信息素濃度增量優(yōu)化

對(duì)各搜索路徑上的信息素濃度進(jìn)行優(yōu)化處理，提高無人船避障路線規(guī)劃效果，其計(jì)算公式為：

其中，信息素濃度的高低通過Q?反映。

通過設(shè)計(jì)的信息素濃度增量優(yōu)化，可對(duì)螞蟻搜索路徑上的信息素濃度高低進(jìn)行自主更新，以提高無人船全局最佳避障路線收斂效率。δ>ε條件下，信息素濃度隨著 δ值的增大而提高，這有利于提升無人船避障路線規(guī)劃效率；δ ≤ε 條件下，Ln,k與Lmin之差越小，信息素?fù)]發(fā)性越高，可防止無人船避障路線規(guī)劃陷入局部最優(yōu)解。

1.3.3 狀態(tài)轉(zhuǎn)移概率的改進(jìn)

應(yīng)用蟻群算法對(duì)無人船避障路線進(jìn)行規(guī)劃時(shí)，容易陷入局部最優(yōu)困局，這是由于螞蟻在后續(xù)移動(dòng)節(jié)點(diǎn)選取時(shí)，一旦其處于凹型障礙環(huán)境或無新節(jié)點(diǎn)可選，就會(huì)停在原處不動(dòng)。本文對(duì)狀態(tài)轉(zhuǎn)移概率進(jìn)行優(yōu)化處理，通過引入穩(wěn)定因子S j，避免無人船避障路線規(guī)劃陷入局部最優(yōu)困局。優(yōu)化后的狀態(tài)轉(zhuǎn)移概率公式為：

式中：對(duì)于節(jié)點(diǎn)j，Tj為與其鄰近的柵格總量；Oj為其附近障礙物柵格總量；γ為穩(wěn)定因子參數(shù)。

2 實(shí)驗(yàn)分析

以航行于復(fù)雜開放水域的某無人船為實(shí)驗(yàn)對(duì)象，對(duì)無人船航行環(huán)境進(jìn)行建模，獲得30×30 柵格地圖，航行環(huán)境中的障礙物用灰色柵格標(biāo)記。在上述環(huán)境采用本文算法對(duì)無人船避障路線進(jìn)行規(guī)劃，分析本文算法的避障性能。無人船航行環(huán)境建模結(jié)果如圖2 所示。

圖2 復(fù)雜開放水域航行環(huán)境建模結(jié)果Fig.2 Modeling results of complex open water navigation environment

蟻群算法性能的優(yōu)劣直接影響無人船避障路線規(guī)劃效果，啟發(fā)參數(shù) α反映了搜索路徑上信息素濃度對(duì)螞蟻路徑選擇的影響，參數(shù) β體現(xiàn)了啟發(fā)函數(shù)對(duì)螞蟻路徑選擇的重要性。采用本文算法對(duì)復(fù)雜開放水域環(huán)境下的無人船避障路線進(jìn)行規(guī)劃，并將算法改進(jìn)前路線規(guī)劃結(jié)果作為對(duì)比，通過分析不同 α、β取值下的最優(yōu)路徑長度差異，驗(yàn)證本文算法的避障效果，實(shí)驗(yàn)結(jié)果如圖3 和圖4 所示。

圖3 啟發(fā)參數(shù) α對(duì)無人船避障路線規(guī)劃效果影響Fig.3 Influence of heuristic parameters on the planning effect of ship obstacle avoidance routes

圖4 啟發(fā)參數(shù) β對(duì)無人船避障路線規(guī)劃效果影響Fig.4 Influence of heuristic parameters on the planning effect of ship obstacle avoidance routes

可知，啟發(fā)參數(shù) α、β的取值對(duì)無人船避障路線規(guī)劃效果具有直接影響，隨著參數(shù) α、β的不斷增大，無人船避障路線長度大體呈先減小后微弱增大趨勢變化，當(dāng)α=1、β=4時(shí)，本文算法確定的無人船避障路線最短；改進(jìn)前算法在 α=1.2、β=5.5時(shí)可獲得最短避障路線，但避障路線長度始終高于改進(jìn)后。實(shí)驗(yàn)結(jié)果表明，將勢場信息引入到啟發(fā)信息中，實(shí)現(xiàn)蟻群算法的改進(jìn)，可有效提升無人船避障路線規(guī)劃效果，獲得更短規(guī)劃路徑。

在圖2 航行環(huán)境下，無人船航行初始點(diǎn)為A，航行目標(biāo)點(diǎn)為B，將本文算法應(yīng)用到無人船避障路線規(guī)劃中，通過對(duì)算法改進(jìn)前后的避障路線規(guī)劃結(jié)果以及收斂曲線進(jìn)行對(duì)比分析，驗(yàn)證本文算法的應(yīng)用性，實(shí)驗(yàn)結(jié)果如圖5 和圖6 所示。

圖5 算法改進(jìn)前后避障路線規(guī)劃結(jié)果對(duì)比分析Fig.5 Comparative analysis of obstacle avoidance route planning results before and after algorithm improvement

圖6 改進(jìn)前后算法性能對(duì)比分析Fig.6 Comparative analysis of algorithm performance before and after improvement

可知，隨著迭代次數(shù)的不斷增加，算法改進(jìn)前后的收斂曲線均呈現(xiàn)出不斷降低的發(fā)展趨勢，本文算法經(jīng)過50 次迭代即可實(shí)現(xiàn)最佳路徑長度曲線的快速收斂，改進(jìn)前算法需要100 次迭代方能達(dá)到穩(wěn)定狀態(tài)，且迭代前期曲線波動(dòng)起伏較大，曲線平滑性差。改進(jìn)前算法的避障路線規(guī)劃結(jié)果中存在更多的拐點(diǎn)，路線曲折、避障路線更長。采用本文算法規(guī)劃設(shè)計(jì)的無人船避障路線平整度高、避障路線長度降低了40.39%，拐點(diǎn)數(shù)降低了60%。

3 結(jié)語

以航行于復(fù)雜開放水域的無人船為實(shí)驗(yàn)對(duì)象，在分析蟻群算法性能影響因素的基礎(chǔ)上，通過對(duì)比分析改進(jìn)前后無人船避障路線規(guī)劃結(jié)果研究本文算法的優(yōu)越性。實(shí)驗(yàn)結(jié)果表明：

1）蟻群規(guī)模為80，啟發(fā)參數(shù) α、β分別為1 和4 時(shí)，設(shè)計(jì)的無人船避障路線最短。

2）本文算法可實(shí)現(xiàn)無人船避障路線規(guī)劃，設(shè)計(jì)的避障路線長度比改進(jìn)前降低了40.39%、拐點(diǎn)數(shù)減少60%。