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

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

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

1 引言

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

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

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

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

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

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

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

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

(1)

通常情況下，清除節(jié)點(diǎn)之間的連接用0和1進(jìn)行表達(dá)，此時(shí)待優(yōu)化參數(shù)的數(shù)量表示為n×n，清除節(jié)點(diǎn)的數(shù)量越大，待優(yōu)化參數(shù)變多，對(duì)于路徑優(yōu)化求解的難度會(huì)增加[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)編號(hào)表示為x(i)。

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

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

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

圖2 蟻群算法流程

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

(4)

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

(5)

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

(6)

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

3.2 信息素更新

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

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

(7)

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

1)蟻周

(8)

2)蟻數(shù)

(9)

3)蟻密

(10)

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

3.3 參數(shù)分析

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

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

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

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

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

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

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

期望啟發(fā)因子β對(duì)于螞蟻對(duì)目標(biāo)點(diǎn)的期望有著至關(guān)重要的影響，β的改變直接影響到螞蟻對(duì)未知路徑的感知能力。若β取值過(guò)大時(shí)，此時(shí)螞蟻對(duì)未知路徑的感知能力減弱，普遍會(huì)傾向于較短路徑，達(dá)到了算法收斂速度快的效果，同時(shí)算法也陷入局部最優(yōu)狀態(tài)；若β取值過(guò)小時(shí)，提高了算法多樣性的同時(shí)，降低了算法的收斂速度，搜索路徑質(zhì)量變好但是算法的運(yùn)行效率降低。通過(guò)上述步驟，采用蟻群算法，計(jì)算清漂船節(jié)點(diǎn)轉(zhuǎn)移概率，采用禁忌表，記錄路徑全部節(jié)點(diǎn)與障礙，對(duì)信息素進(jìn)行全局更新，分析各項(xiàng)參數(shù)對(duì)路徑規(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)平臺(tái)，進(jìn)行實(shí)驗(yàn)分析。選擇1個(gè)無(wú)障礙水面地圖和3個(gè)有障礙水面地圖進(jìn)行實(shí)驗(yàn)，分別采用所提算法、文獻(xiàn)[4]算法和文獻(xiàn)[5]算法，以路徑規(guī)劃長(zhǎng)度、路徑規(guī)劃時(shí)間、路徑規(guī)劃轉(zhuǎn)折角度為實(shí)驗(yàn)指標(biāo)進(jìn)行對(duì)比分析。其中，路徑規(guī)劃轉(zhuǎn)折角度即為路徑中全部轉(zhuǎn)折角度的總和。路徑轉(zhuǎn)折角度偏大時(shí)，清漂船的起始點(diǎn)到目標(biāo)點(diǎn)的路徑上含有較多拐點(diǎn)，會(huì)影響清漂船在作業(yè)工程中的穩(wěn)定性與安全性，作業(yè)效果較差。得到不同算法的路徑規(guī)劃長(zhǎng)度對(duì)比結(jié)果如圖3所示。

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

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

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

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

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

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

圖5 不同算法的路徑轉(zhuǎn)折角度對(duì)比結(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)樗崴惴▽?duì)水面環(huán)境進(jìn)行建模，建立了清除點(diǎn)路徑網(wǎng)絡(luò)，準(zhǔn)確分析各項(xiàng)參數(shù)，明顯減小了路徑轉(zhuǎn)折角度，確保了路徑規(guī)劃的有效性。

5 結(jié)束語(yǔ)

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