李光輝，郭銳，田瑤瑤

（中南民族大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，武漢430074）

0 引言

如今各種垃圾長(zhǎng)期在水面堆積，嚴(yán)重影響水環(huán)境。于是如何進(jìn)行水質(zhì)監(jiān)控和垃圾清理便是一個(gè)不得不解決的問(wèn)題。

目前國(guó)內(nèi)的水面垃圾處理措施大多為人工打撈，此種方式效率低成本高危險(xiǎn)大，為解決以上問(wèn)題，目前不少學(xué)者提出了各種水面垃圾清理系統(tǒng)[1-5]。綜合起來(lái)看，前人在船體構(gòu)造、框架設(shè)計(jì)等方面已有較好解決方案，在一定程度上解決了小型水域的垃圾打撈問(wèn)題。但是也存在著需要人工操控、巡航方式過(guò)于耗能等尚未解決的問(wèn)題。

因此，在前人的研究基礎(chǔ)上，我們對(duì)智能水上機(jī)器人的巡航方式進(jìn)行優(yōu)化。通過(guò)歷史數(shù)據(jù)選取遍歷點(diǎn)，再使用蟻群算法[6-7]規(guī)劃?rùn)C(jī)器人航行的最優(yōu)路徑，在保證清潔能力的前提下減少了航行里程數(shù)，使其更加智能化。在很大程度上減少了的航行里程，使機(jī)器人更高效節(jié)能，在一定程度上解決了前人學(xué)者在此機(jī)器人研發(fā)上未解決的問(wèn)題。

1 模型建立與效率計(jì)算

首先設(shè)置水上機(jī)器人的航行環(huán)境為二維平面模型，采用柵格法建模[8]（圖1），避障方面由硬件實(shí)現(xiàn)，本文算法航行的水面為理想化的無(wú)通行障礙水面。每個(gè)單元格為水上機(jī)器人可探測(cè)垃圾的范圍。每個(gè)單元格的狀態(tài)分為三種：①環(huán)境檢測(cè)取樣點(diǎn)；②有垃圾點(diǎn)；③無(wú)垃圾點(diǎn)。在機(jī)器人航行過(guò)程中，垃圾產(chǎn)生后忽略其在水面的微小漂移。

圖1 湖面建模

在本文研究中，將單元格地圖劃分為A×A網(wǎng)格單元，假定每個(gè)柵格的單位長(zhǎng)度為a（2 倍機(jī)器人掃描半徑），機(jī)器人走過(guò)一個(gè)柵格它的移動(dòng)步數(shù)step加1。垃圾只會(huì)產(chǎn)生在柵格中，且機(jī)器人經(jīng)過(guò)該柵格時(shí)會(huì)撿到垃圾，撿垃圾不增加額外步數(shù)。

假設(shè)起點(diǎn)在(0,0)處，則一趟全圖遍歷的移動(dòng)步數(shù)：

我們?cè)O(shè)定在每次航行前產(chǎn)生垃圾數(shù)為n，垃圾產(chǎn)生范圍當(dāng)然在我們規(guī)定的地圖中。我們定義一個(gè)A×A的垃圾矩陣garbage_map，通過(guò)函數(shù)garbage_input(x,n)在該矩陣中產(chǎn)生垃圾。有一個(gè)環(huán)境因子比較重要，那就是垃圾集中區(qū)面積與總面積之比θ1。所謂垃圾集中區(qū)，就是垃圾產(chǎn)生概率較大的區(qū)域。另一個(gè)重要的參數(shù)就是垃圾集中區(qū)垃圾產(chǎn)生數(shù)與非垃圾集中區(qū)垃圾產(chǎn)生數(shù)比例θ2。這兩個(gè)參數(shù)對(duì)本文算法的性能具有較大的影響，后續(xù)會(huì)對(duì)其進(jìn)行分析。

我們定義撿到垃圾占比garbage_picked_ratio（記為γ1）和有效比例great_ratio（記為γ2）。其中，撿到垃圾占比為算法運(yùn)行結(jié)束后撿到的垃圾占投放垃圾的比例，而有效比例則等于航行中撿到垃圾的步數(shù)占總步數(shù)的比例，后續(xù)將用于衡量算法效率的指標(biāo)。假設(shè)采樣點(diǎn)為m，垃圾數(shù)為n，則一趟全圖遍歷的有效比例為：

其中，sum()為Python 函數(shù)，意在統(tǒng)計(jì)地圖中有垃圾的點(diǎn)數(shù)。

2 基于蟻群算法的學(xué)習(xí)遍歷算法

2.1 蟻群算法

蟻群算法作為一種自組織群體智能優(yōu)化算法，正反饋機(jī)理與較強(qiáng)的魯棒性使其在求解組合優(yōu)化問(wèn)題中得到廣泛地應(yīng)用[9-10]，相比于其他的路徑規(guī)劃算法[11-12]，蟻群算法的啟發(fā)式的概率搜索方式不容易陷入局部最優(yōu)，易于尋找到全局最優(yōu)解[13]。其他傳統(tǒng)的非進(jìn)化型算法如模擬退火算法[14]，會(huì)出現(xiàn)結(jié)果屬于局部最優(yōu)解而非全局最優(yōu)解的情況，相比之下蟻群算法就不會(huì)出現(xiàn)此類(lèi)情況，也就避免了其他算法中可能出現(xiàn)的搜索能力變差的情況。

蟻群算法模擬自然界中真實(shí)螞蟻的覓食行為，尋找一條從蟻巢（起始點(diǎn)）到食物源（終止點(diǎn)）的最短路徑。在尋找食物的過(guò)程中，螞蟻會(huì)在其行走路徑上釋放信息素，并根據(jù)信息素濃度大小決定下一步路徑方向。由于螞蟻傾向于選擇信息素更強(qiáng)的路徑，若某一路徑上螞蟻所釋放的信息素越多，則螞蟻選擇該路徑的可能性會(huì)越大。螞蟻在覓食過(guò)程中根據(jù)當(dāng)前節(jié)點(diǎn)與下一節(jié)點(diǎn)的距離及信息素濃度來(lái)決定下一節(jié)點(diǎn)的轉(zhuǎn)移概率為：

上式中：τij(t)為路徑ij上的信息素濃度，ηij(t)為與路徑ij相關(guān)的啟發(fā)式信息，α為信息素濃度啟發(fā)因子，β為能見(jiàn)度啟發(fā)因子，allowedk中包含螞蟻k 尚未訪(fǎng)問(wèn)過(guò)的節(jié)點(diǎn)。

式（4）中：εij為節(jié)點(diǎn)i與下一節(jié)點(diǎn)j之間的歐氏距離，若兩節(jié)點(diǎn)間的歐氏距離越短，則所對(duì)應(yīng)能見(jiàn)度啟發(fā)函數(shù)值越大，對(duì)應(yīng)轉(zhuǎn)移概率也越大。

式（5）為所有螞蟻完成一次迭代后，信息素更新方式。式中：ρ為信息素?fù)]發(fā)系數(shù)，其值越大信息素?fù)]發(fā)得越快，M為螞蟻總數(shù)，τij(t+1)為第t+1 次迭代時(shí)路徑ij上的信息素濃度，為本次迭代中螞蟻k留在路徑ij的信息素。

式（6）中：Lk為螞蟻k 完成路徑搜索后行走的總長(zhǎng)度；Q為一常數(shù)，表示螞蟻攜帶的信息素濃度因子。

2.2 遍歷點(diǎn)選取算法

使用蟻群算法對(duì)遍歷點(diǎn)進(jìn)行遍歷是再好不過(guò)。本文算法的另一個(gè)重點(diǎn)是確定遍歷點(diǎn)，使得用蟻群算法對(duì)這些點(diǎn)進(jìn)行遍歷時(shí)撿到的垃圾數(shù)較多，同時(shí)有效比例也較大。遍歷點(diǎn)由三種點(diǎn)組成：①水質(zhì)檢測(cè)點(diǎn)；②垃圾集中點(diǎn)；③隨機(jī)垃圾點(diǎn)。其中，水質(zhì)檢測(cè)點(diǎn)是用于水質(zhì)取樣檢測(cè)的，是已知點(diǎn)。垃圾集中點(diǎn)是指該湖面區(qū)域內(nèi)產(chǎn)生垃圾較為頻繁的點(diǎn)，隨機(jī)垃圾點(diǎn)則是小概率有垃圾的點(diǎn)。后兩種點(diǎn)是未知的。

本文是這樣來(lái)確定后兩種遍歷點(diǎn)的。初始化一個(gè)記憶矩陣Memory_map，其大小依然為A×A，初始化值為0。在一個(gè)陌生湖泊環(huán)境中進(jìn)行工作時(shí)，機(jī)器人在前K次工作時(shí)會(huì)對(duì)湖面進(jìn)行全圖遍歷，根據(jù)在某點(diǎn)是否撿到垃圾來(lái)更改Memory_map的權(quán)值。若該區(qū)域撿到垃圾，該點(diǎn)權(quán)值加μ，若沒(méi)有撿到，權(quán)值減去η。則根據(jù)實(shí)際情況，前K次運(yùn)行完畢后的矩陣值進(jìn)行如下更改：

假設(shè)撿到垃圾的次數(shù)為l1，未撿到為l2。

前K次運(yùn)行過(guò)后，若某點(diǎn)的記憶矩陣值大于預(yù)選閾值γ，則將其選入垃圾集中點(diǎn)。之后，通過(guò)對(duì)Memory_map[i,j]進(jìn)行排序，選擇其中前k 大的加入隨機(jī)垃圾點(diǎn)。以上三種點(diǎn)通過(guò)蟻群算法規(guī)劃路徑后進(jìn)行下一次遍歷。

假設(shè)本文算法撿到垃圾的移動(dòng)步數(shù)為get_num，其總的移動(dòng)步數(shù)假設(shè)為step_2，則其有效比例為：

雖然無(wú)法確定其值，但我們可以知道他們與各種參數(shù)的關(guān)系：

（1）預(yù)選閾值γ與k共同決定了遍歷點(diǎn)個(gè)數(shù)t_num，在一定范圍內(nèi)，get_num隨著t_num增大而增大，而step_2 也會(huì)隨著t_num增大而增大，且在一定范圍內(nèi)，step_2 增大速率大于t_num。

（2）垃圾集中區(qū)垃圾產(chǎn)生數(shù)與非垃圾集中區(qū)垃圾產(chǎn)生數(shù)比例θ2。其他參數(shù)設(shè)置合理的情況下，get_num隨著θ2增大而增大，step_2 隨著θ2增大而減小。

2.3 算法流程

基于本文提出的算法的機(jī)器人路徑規(guī)劃步驟如下：

步驟1 初始化蟻群算法中的所有參數(shù)，設(shè)置螞蟻個(gè)數(shù)M，最大迭代次數(shù)N，起終點(diǎn)位置S等。

步驟2 初始化遍歷算法參數(shù)：全圖遍歷次數(shù)K，正反饋權(quán)值μ，負(fù)反饋權(quán)值η，以及預(yù)選閾值γ等。

步驟3 進(jìn)行K次全圖遍歷。更改Memory_map的值

步驟4 根據(jù)Memory_map的值以及遍歷點(diǎn)數(shù)量k和環(huán)境監(jiān)測(cè)點(diǎn)確定遍歷點(diǎn)，使用蟻群算法進(jìn)行路徑規(guī)劃，然后進(jìn)行遍歷，遍歷過(guò)程中再次更新Memory_map的值。

步驟5 判斷是否達(dá)到最大運(yùn)行次數(shù)，若是則輸出運(yùn)行結(jié)果，否則轉(zhuǎn)向步驟4。

2.4 算法效果展示

如圖2 所示為某一次初始化的湖面，其中帶斜杠的陰影部分代表以該點(diǎn)為內(nèi)心的正方形區(qū)域內(nèi)存在垃圾（包括新產(chǎn)生的垃圾和上次未清理干凈的垃圾）。圖3 為本文算法在圖2 基礎(chǔ)上規(guī)劃的路徑（此前算法在該湖面的運(yùn)行次數(shù)已足夠充分），圓點(diǎn)為算法產(chǎn)生的遍歷點(diǎn)，連線(xiàn)部分為路徑，在路線(xiàn)上的垃圾已被打撈。

圖2 初始化的湖面

圖3 某一次垃圾打撈路線(xiàn)

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

為了驗(yàn)證學(xué)習(xí)遍歷算法的可行性與有效性，本文設(shè)定的垃圾分布在全局靜態(tài)10×10 的單元格中。在參數(shù)與環(huán)境完全相同的情況下，利用Python 分別對(duì)全圖遍歷方法，本文算法進(jìn)行仿真對(duì)比分析。

由于本文算法受垃圾集中區(qū)面積與總面積之比θ1，垃圾集中區(qū)垃圾產(chǎn)生數(shù)與非垃圾集中區(qū)垃圾產(chǎn)生數(shù)比例θ2影響，故先得到該算法在不同環(huán)境因子下的效率后再選擇不同因子下的各個(gè)效率與全圖遍歷效率相對(duì)比。

其中，蟻群算法的參數(shù)為：螞蟻規(guī)模M=50；最大迭代次數(shù)N=150；信息素啟發(fā)因子α=1；期望啟發(fā)因子β=5；信息素增加強(qiáng)度系數(shù)Q=2000；信息素蒸發(fā)系數(shù)ρ=0.1 ；本文算法中全圖遍歷趟數(shù)K=0.9×travel_time，閾值γ=c_num+5，正反饋權(quán)值μ=4，負(fù)反饋權(quán)值η=2。其他參數(shù)通過(guò)控制變量法來(lái)觀(guān)察其對(duì)本文算法各個(gè)效率的影響。

根據(jù)算法在不同參數(shù)環(huán)境中運(yùn)行的結(jié)果，我們選取了較為穩(wěn)定和具有代表性的數(shù)據(jù)，撿到垃圾比例γ1、垃圾集中區(qū)占比θ1與垃圾產(chǎn)生比例θ2關(guān)系，有效比例γ2與垃圾集中區(qū)占比θ1和垃圾產(chǎn)生比例θ2關(guān)系分別如表1、表2 所示。

表1 撿到垃圾比例、垃圾集中區(qū)占比θ1 與垃圾產(chǎn)生比例θ2關(guān)系

表2 有效比例與垃圾集中區(qū)占比θ1 和垃圾產(chǎn)生比例θ2 關(guān)系

同參數(shù)下各效率變化趨勢(shì)如圖4、圖5 所示。

圖4 θ1=0.15時(shí)各效率隨θ2 變化情況

圖5 θ2=7/3時(shí)各效率隨 θ1 變化圖

從實(shí)驗(yàn)結(jié)果中可以看出，θ1不變，撿到垃圾比例和有效比例都隨著θ2減小而減小，但總體而言θ2對(duì)有效比例影響不大。θ2不變，隨著θ1增大，撿到垃圾比例減小，少走路徑比例急劇減小，而有效比例則急劇增大?？梢钥闯?，在一定范圍內(nèi)，垃圾集中區(qū)占總面積比例θ1和垃圾產(chǎn)生比例θ2越大，本文算法有效比例越大。

我們選取遍歷次數(shù)為200 時(shí)，垃圾產(chǎn)生比例θ2=9/1，垃圾集中區(qū)占比θ1=0.15，以及垃圾產(chǎn)生比例θ27/3，垃圾集中區(qū)占比θ1=0.0 5 兩種情況與全圖遍歷的效率對(duì)比，結(jié)果如表3-表4 所示。

表3 θ1=0.05，θ2=7：3 情況下本文算法與全圖遍歷各項(xiàng)數(shù)據(jù)比較

表4 θ1=0.15，θ2=9：1情況下本文算法與全圖遍歷各項(xiàng)數(shù)據(jù)比較

表3-表4 中本文算法在不同環(huán)境下與全圖遍歷相比較，有效比例都比全圖遍歷要高許多，少走的路徑也意味著更低的能耗，但同時(shí)也能看到，全圖遍歷能撿到水面上幾乎所有的垃圾，而本文算法只能撿到80%-90%的垃圾，精度上還有待提高。

4 結(jié)語(yǔ)

本文提出的學(xué)習(xí)遍歷算法具有一定的學(xué)習(xí)能力，能夠根據(jù)歷史數(shù)據(jù)減少遍歷點(diǎn)的個(gè)數(shù)從而大大增加水上機(jī)器人工作的效率，相比于傳統(tǒng)的全圖遍歷的方法，本文的改進(jìn)從垃圾集中點(diǎn)入手，在遍歷過(guò)程中逐漸找到垃圾集中的地區(qū)，主要遍歷這些地區(qū)，適當(dāng)頻率遍歷垃圾較少出現(xiàn)的區(qū)域，從而較大改善了水上機(jī)器人的遍歷路徑，航行時(shí)間明顯得到減少，有效步數(shù)大幅度增加，具有更好的實(shí)用性。但是本文算法還需進(jìn)一步改善，算法體現(xiàn)出對(duì)垃圾集中點(diǎn)外產(chǎn)生的垃圾清理效率不高，雖可通過(guò)增加遍歷點(diǎn)個(gè)數(shù)來(lái)提高垃圾清理效率，但如此一來(lái)有效比例卻會(huì)因此下降。改善算法之后，下一步將考慮具體實(shí)物實(shí)現(xiàn)。