考慮最優(yōu)路徑的水面清漂船自主導(dǎo)航算法設(shè)計

羅春艷，李 元，殷 飛，胡宇祥

(1. 吉林農(nóng)業(yè)科技學(xué)院機(jī)械與土木工程學(xué)院，吉林 吉林 132101；2. 陜西師范大學(xué)西北國土資源研究中心，陜西 西安 710119)

1 引言

目前水面污染嚴(yán)重，清漂工作則是重中之重[1]。人工清漂船在進(jìn)行清漂作業(yè)時，需要人工持有特定工具對水面垃圾進(jìn)行處理，危險系數(shù)較高且工作效率較低，而水面清漂船可實(shí)現(xiàn)360度全回轉(zhuǎn)運(yùn)行，對目標(biāo)水域進(jìn)行自主巡航，遍歷水域進(jìn)行規(guī)劃式清掃[2-3]。然而，水面清漂船在作業(yè)過程中，航向的路徑規(guī)劃問題是保證清漂船安全作業(yè)的基礎(chǔ)，因此，水面清漂船最優(yōu)路徑規(guī)劃問題成為目前研究的熱點(diǎn)及方向。

文獻(xiàn)[4]提出基于A*算法優(yōu)化的無人水面艇路徑規(guī)劃算法，通過分析水面信息提取水面信息數(shù)據(jù)，利用柵格法對指定路徑建立搜索空間，利用坐標(biāo)方式編號處理柵格，采用A*算法優(yōu)化搜索路徑，約束轉(zhuǎn)向角，清除冗余節(jié)點(diǎn)，獲取最優(yōu)路徑，該算法提高了無人水面艇路徑規(guī)劃的安全性，但未考慮對水面環(huán)境進(jìn)行建模，導(dǎo)致路徑規(guī)劃時間較長。文獻(xiàn)[5]提出基于多方向A～*算法的無人水面艇路徑規(guī)劃算法，采用電子水面圖，根據(jù)柵格化形式，獲取水面環(huán)境信息，約束水面航行安全距離，利用A～*算法啟發(fā)函數(shù)，控制航行路徑節(jié)點(diǎn)，依據(jù)八方向搜索模式，多方向搜索路徑冗余節(jié)點(diǎn)和拐點(diǎn)，運(yùn)用路徑平滑算法，平滑處理路徑拐點(diǎn)，獲取最優(yōu)路徑，該算法能夠有效減小路徑長度，但存在路徑規(guī)劃轉(zhuǎn)折角度較大的問題。

為了解決上述算法中存在的問題，提出考慮最優(yōu)路徑的水面清漂船自主導(dǎo)航算法，該算法分析水面信息，構(gòu)建水面環(huán)境模型，形成清除點(diǎn)路徑連通網(wǎng)絡(luò)，有效分析清漂船轉(zhuǎn)移概率，縮短路徑規(guī)劃長度。采用蟻群算法，結(jié)合禁忌表記錄路徑全部節(jié)點(diǎn)與障礙，全局更新信息素，獲取水面最優(yōu)路徑規(guī)劃，減小路徑轉(zhuǎn)折角度，提高路徑規(guī)劃效率。

2 自主導(dǎo)航路徑規(guī)劃建模

水面清漂船在進(jìn)行作業(yè)時，從指定地方出發(fā)陸續(xù)到達(dá)規(guī)定的水域，有效節(jié)約燃料和節(jié)省作業(yè)時間，需合理規(guī)劃作業(yè)路線及準(zhǔn)確了解清漂船所需經(jīng)過的全部路徑節(jié)點(diǎn)，最終返回起始點(diǎn)[6-7]。面臨水面污染嚴(yán)重問題，作業(yè)過程中，水面存在較多的路徑節(jié)點(diǎn)，需利用優(yōu)化算法對清漂船的作業(yè)路徑進(jìn)行計算，對水面環(huán)境進(jìn)行建模，并可以快速、準(zhǔn)確地獲取最優(yōu)路徑。以12個清除點(diǎn)為例，構(gòu)成清除點(diǎn)路徑連通網(wǎng)絡(luò)如圖1所示。

圖1 清除點(diǎn)構(gòu)成的路徑網(wǎng)絡(luò)

將各清除點(diǎn)進(jìn)行編號，分別為a、b、c、d、e、f、g、h、i、j、k、l，兩兩清除點(diǎn)之間相連，構(gòu)成互相連通的路徑網(wǎng)絡(luò)。

假設(shè)全部清除點(diǎn)表示為n個，任意兩個清除點(diǎn)表示為γ和λ，清除點(diǎn)之間最優(yōu)距離表示為wγ，λ，且γ≠λ，γ，λ∈{1，2，…n}，兩兩清除點(diǎn)之間的距離構(gòu)成一個網(wǎng)絡(luò)矩陣，表示為W，該矩陣是對稱矩陣，且W=W′，wγ，λ=wλ，γ。網(wǎng)絡(luò)矩陣形式如下

(1)

通常情況下，清除節(jié)點(diǎn)之間的連接用0和1進(jìn)行表達(dá)，此時待優(yōu)化參數(shù)的數(shù)量表示為n×n，清除節(jié)點(diǎn)的數(shù)量越大，待優(yōu)化參數(shù)變多，對于路徑優(yōu)化求解的難度會增加[8]。編碼清除點(diǎn)的連接順序，可將路徑優(yōu)化復(fù)雜度得到降低，編碼后，形成待優(yōu)化參數(shù)變量，表示為

x=[ijk…mr]

(2)

(3)

式中，待優(yōu)化參數(shù)表示為x，且x=(x(1)，x(2)，…x(n))，清除點(diǎn)編號表示為x(i)。

3 基于蟻群的水面清漂船最優(yōu)路徑自主導(dǎo)航算法

3.1 狀態(tài)轉(zhuǎn)移概率

采用蟻群算法對清漂船路徑規(guī)劃問題進(jìn)行處理時，當(dāng)螞蟻對下一節(jié)點(diǎn)進(jìn)行選擇時，通常是采用偽隨機(jī)方式[9]進(jìn)行選擇。蟻群算法流程如圖2所示。

圖2 蟻群算法流程

首先將螞蟻向下一個節(jié)點(diǎn)轉(zhuǎn)移的概率進(jìn)行假設(shè)，表示為p，螞蟻表示為k，且k=1，2，3，…，m，螞蟻經(jīng)過一定時間后，再選取下一節(jié)點(diǎn)轉(zhuǎn)移的概率計算公式表示為：

(4)

螞蟻在對路徑進(jìn)行選擇時，會根據(jù)自身判斷與其它螞蟻經(jīng)過路徑所含有的信息素濃度來決定下一節(jié)點(diǎn)的選擇，通常情況下，螞蟻會選擇信息素含量較高的路徑[10]。首先采用禁忌表記錄螞蟻k處于該路徑所經(jīng)過的全部節(jié)點(diǎn)與障礙，定義為tabuk(k=1，2，3，…m)，其次螞蟻k在對路徑進(jìn)行選擇時全部可選節(jié)點(diǎn)的位置表示為allowedk={C-tabuk}。式(4)中，啟發(fā)函數(shù)表示為ηij(t)，其計算公式如下

(5)

式中，此時節(jié)點(diǎn)與下一節(jié)點(diǎn)之間的距離表示為D(i，j)，距離越大，啟發(fā)函數(shù)則越小，此時螞蟻會選擇該節(jié)點(diǎn)的概率則越小，并且相應(yīng)的轉(zhuǎn)移概率也會越小；若距離D(i，j)越小，啟發(fā)函數(shù)則越大，此時螞蟻的轉(zhuǎn)移概率會增加。由此可見，螞蟻選擇目標(biāo)節(jié)點(diǎn)的概率是隨著目前節(jié)點(diǎn)與下一節(jié)點(diǎn)的距離變化而變化的，即，節(jié)點(diǎn)間距離的計算公式如下

(6)

式中，xi、yi表示為此時節(jié)點(diǎn)位置的橫坐標(biāo)與縱坐標(biāo)，xj、yj表示為下一節(jié)點(diǎn)位置的橫坐標(biāo)與縱坐標(biāo)。

3.2 信息素更新

通過蟻群算法選取最優(yōu)路徑時，隨著時間的變化，會有螞蟻不斷經(jīng)過較短路徑，并且在經(jīng)過的路徑中留存信息素，隨著螞蟻經(jīng)過次數(shù)的增加，較短路徑上的信息素過高，導(dǎo)致啟發(fā)信息機(jī)制失效，螞蟻便不會再去對其它空間路徑進(jìn)行搜索，此時蟻群算法會處于局部最優(yōu)值[11]。為此，將路徑中的信息素進(jìn)行更新，每次迭代完成之后，均進(jìn)行全局信息素更新。

假設(shè)此時螞蟻處于t+n時刻，該路徑的信息素調(diào)整方式為

(7)

式中，信息素?fù)]發(fā)系數(shù)表示為ρ，信息素殘留因子表示為(1-ρ)，通常情況下，信息素?fù)]發(fā)系數(shù)的取值為0～1之間的常數(shù)。螞蟻在t時刻節(jié)點(diǎn)i到節(jié)點(diǎn)j的路徑中完成迭代后，所留下的信息素增量表示為Δτij(t)，其中k=1，2，3，…，m。螞蟻對路徑進(jìn)行搜索后，節(jié)點(diǎn)i到節(jié)點(diǎn)j的路徑中留下的全部信息素增量的總數(shù)量表示為Δτij(t)，在螞蟻進(jìn)行路徑搜索前，取值為0；信息素增加的方式有三種，分別是蟻周、蟻量和蟻密，三種模型的求解過程如下：

1)蟻周

(8)

2)蟻數(shù)

(9)

3)蟻密

(10)

式中，信息素含量高低的常量表示為Q，式(9)中，表示k只螞蟻在進(jìn)行路徑搜索后，經(jīng)過的路徑長度總和，將不同的信息素作為依據(jù)，來選擇不同的模型進(jìn)行信息更新；式(9)、式(10)是局部信息進(jìn)行更新，在螞蟻進(jìn)行每次路徑選擇后，按照此時的路徑中含有的信息素進(jìn)行更新；式(8)是全局信息進(jìn)行更新，當(dāng)螞蟻從起始點(diǎn)到達(dá)終點(diǎn)后，對全部經(jīng)過的路徑上的信息素進(jìn)行更新。

3.3 參數(shù)分析

1)螞蟻數(shù)量的影響

當(dāng)螞蟻數(shù)量m較大時，該算法在搜索路徑時，隨機(jī)性會增加，搜索的路徑質(zhì)量也較高，同時，在螞蟻對下一節(jié)點(diǎn)進(jìn)行選擇時，節(jié)點(diǎn)中的信息素會較小，而達(dá)不到有效的反饋，進(jìn)而導(dǎo)致該算法的收斂速度降低[12]。若螞蟻數(shù)量m的數(shù)值過大時，此時路徑之間的信息素差額會增加，當(dāng)螞蟻進(jìn)行選擇下一節(jié)點(diǎn)時，由于路徑之間的信息素差距過大，導(dǎo)致最終螞蟻選取的路徑節(jié)點(diǎn)較為單一，雖然此時該算法的收斂速度得到增加，運(yùn)用時間也較短，但是搜索的精密度降低了，從而會遺失多條路徑信息，陷入局部最優(yōu)解，無法有效獲取高質(zhì)量的路徑。

2)信息素?fù)]發(fā)系數(shù)的影響

由上述可知，式(7)中，若ρ取值較大，此時的啟發(fā)信息對螞蟻選擇路徑的影響會變小，進(jìn)而導(dǎo)致螞蟻對于選擇路徑的信息素濃度較低的節(jié)點(diǎn)的概率減小，失去蟻群算法的隨機(jī)性與多樣性，此時雖達(dá)到了算法的收斂速度，但是會導(dǎo)致算法陷入局部最優(yōu)，對全局路徑搜索不利。若ρ取值較小，面對復(fù)雜的路徑環(huán)境，該算法的收斂速度會降低，并且運(yùn)算速度變慢。

3)信息啟發(fā)因子的影響

信息啟發(fā)因子對于路徑選擇的影響，主要是作用于信息啟發(fā)因子會改變信息素，當(dāng)螞蟻對路徑進(jìn)行選擇時，會根據(jù)信息素的大小來改變對下一節(jié)點(diǎn)選擇的概率。若信息啟發(fā)因子α較大時，螞蟻會選擇一條信息素較高且較短的路徑，此時蟻群算法失去了搜索多樣性，并且降低了搜索路徑的質(zhì)量。若α較小時，信息啟發(fā)因子對于信息素的影響減弱，此時增加了蟻群算法的隨機(jī)性，提高了搜索路徑質(zhì)量，但面對環(huán)境復(fù)雜路徑時，蟻群算法的收斂速度會大幅度降低。

4)期望啟發(fā)因子的影響

期望啟發(fā)因子β對于螞蟻對目標(biāo)點(diǎn)的期望有著至關(guān)重要的影響，β的改變直接影響到螞蟻對未知路徑的感知能力。若β取值過大時，此時螞蟻對未知路徑的感知能力減弱，普遍會傾向于較短路徑，達(dá)到了算法收斂速度快的效果，同時算法也陷入局部最優(yōu)狀態(tài)；若β取值過小時，提高了算法多樣性的同時，降低了算法的收斂速度，搜索路徑質(zhì)量變好但是算法的運(yùn)行效率降低。通過上述步驟，采用蟻群算法，計算清漂船節(jié)點(diǎn)轉(zhuǎn)移概率，采用禁忌表，記錄路徑全部節(jié)點(diǎn)與障礙，對信息素進(jìn)行全局更新，分析各項參數(shù)對路徑規(guī)劃的影響，從而輸出高質(zhì)量的最優(yōu)路徑，實(shí)現(xiàn)水面清漂船最優(yōu)路徑自主導(dǎo)航。

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

為了驗(yàn)證考慮最優(yōu)路徑的水面清漂船自主導(dǎo)航算法的有效性和可行性，選擇MATLAB R2017a仿真軟件作為實(shí)驗(yàn)平臺，進(jìn)行實(shí)驗(yàn)分析。選擇1個無障礙水面地圖和3個有障礙水面地圖進(jìn)行實(shí)驗(yàn)，分別采用所提算法、文獻(xiàn)[4]算法和文獻(xiàn)[5]算法，以路徑規(guī)劃長度、路徑規(guī)劃時間、路徑規(guī)劃轉(zhuǎn)折角度為實(shí)驗(yàn)指標(biāo)進(jìn)行對比分析。其中，路徑規(guī)劃轉(zhuǎn)折角度即為路徑中全部轉(zhuǎn)折角度的總和。路徑轉(zhuǎn)折角度偏大時，清漂船的起始點(diǎn)到目標(biāo)點(diǎn)的路徑上含有較多拐點(diǎn)，會影響清漂船在作業(yè)工程中的穩(wěn)定性與安全性，作業(yè)效果較差。得到不同算法的路徑規(guī)劃長度對比結(jié)果如圖3所示。

圖3 不同算法的路徑規(guī)劃長度對比結(jié)果

根據(jù)圖3中數(shù)據(jù)可知，針對無障礙水面地圖，所提算法的路徑規(guī)劃長度為280m，而文獻(xiàn)[4]算法與文獻(xiàn)[5]算法的路徑規(guī)劃長度分別為360m和430m；針對有障礙水面地圖，所提算法的平均路徑規(guī)劃長度為400m，而文獻(xiàn)[4]算法與文獻(xiàn)[5]算法的平均路徑規(guī)劃長度分別為560m和600m。由此可知所提算法的路徑規(guī)劃長度較短，因?yàn)樗崴惴ㄔ趯β窂竭M(jìn)行選擇過程中，對水面環(huán)境進(jìn)行建模，構(gòu)成相互連通的清除點(diǎn)路徑網(wǎng)絡(luò)，便于對清漂船轉(zhuǎn)移概率進(jìn)行分析，可有效控制路徑搜索概率及掌握算法收斂趨勢，有效縮短路徑規(guī)劃長度。

為了驗(yàn)證所提算法的路徑規(guī)劃效率，對比不同算法的路徑規(guī)劃時間如圖4所示。

圖4 不同算法的路徑規(guī)劃時間對比結(jié)果

分析圖4中數(shù)據(jù)可知，所提算法的路徑規(guī)劃時間明顯少于文獻(xiàn)[4]算法和文獻(xiàn)[5]算法，由此可知，所提算法的路徑規(guī)劃效率較高，因?yàn)樗崴惴ㄍㄟ^對水面環(huán)境進(jìn)行建模，形成互通清除點(diǎn)路徑網(wǎng)絡(luò)，及時將路徑上的信息素進(jìn)行全局更新，從而提高船舶選擇最優(yōu)路徑的靈敏度，達(dá)到較好的運(yùn)行速度，提高了路徑規(guī)劃效率。

在此基礎(chǔ)上，進(jìn)一步對比不同算法的路徑轉(zhuǎn)折角度如圖5所示。

圖5 不同算法的路徑轉(zhuǎn)折角度對比結(jié)果

根據(jù)圖5中的數(shù)據(jù)可知，文獻(xiàn)[4]算法與文獻(xiàn)[5]算法的轉(zhuǎn)折角度均大于所提算法，證明文獻(xiàn)[4]算法與文獻(xiàn)[5]算法的船舶的穩(wěn)定系數(shù)與安全系數(shù)較低，反之，所提算法的路徑拐點(diǎn)較少，安全性能較好。因?yàn)樗崴惴▽λ姝h(huán)境進(jìn)行建模，建立了清除點(diǎn)路徑網(wǎng)絡(luò)，準(zhǔn)確分析各項參數(shù)，明顯減小了路徑轉(zhuǎn)折角度，確保了路徑規(guī)劃的有效性。

5 結(jié)束語

為提高水面清漂船自主導(dǎo)航路徑規(guī)劃效率，縮短規(guī)劃長度，減小轉(zhuǎn)折角度，提出考慮最優(yōu)路徑的水面清漂船自主導(dǎo)航算法。通過構(gòu)建水面環(huán)境模型，形成清除點(diǎn)路徑連通網(wǎng)絡(luò)。利用蟻群算法，計算清漂船節(jié)點(diǎn)轉(zhuǎn)移概率，采用禁忌表記錄路徑節(jié)點(diǎn)與障礙，全局更新信息素，分析路徑規(guī)劃影響參數(shù)，輸出高質(zhì)量最優(yōu)路徑。該算法能夠有效提高路徑規(guī)劃效率，減小路徑轉(zhuǎn)折角度，縮短路徑規(guī)劃長度，為后期清漂船工作最優(yōu)路徑規(guī)劃的研究提供了新的思路。