韓宇星， 丁剛毅， 柴作鴻

(1.北京理工大學(xué) 軟件學(xué)院， 北京 100081； 2.天津工業(yè)大學(xué) 電氣工程與自動化學(xué)院， 天津 300387)

0 引言

智能巡檢在工業(yè)、民用、國防、軍事領(lǐng)域有著重要的應(yīng)有價值[1-4]，例如，對軍事管轄區(qū)內(nèi)的營房、軍械庫、保密地點以及其他監(jiān)控地點等均需要進行周期性或不定時的巡檢作業(yè)[5-6]。由于軍事任務(wù)的特殊性，對智能巡檢系統(tǒng)的快速響應(yīng)以及執(zhí)行效率提出了更高要求[7]。為巡檢機器人(巡檢車)規(guī)劃最優(yōu)的巡檢路線是提高巡檢效率的關(guān)鍵技術(shù)問題之一[8-9]。目前，許多智能優(yōu)化算法均可用于求解機器人巡檢路線優(yōu)化問題[10-11]。例如，對于小規(guī)模的路線優(yōu)化問題，可采用模擬退火、神經(jīng)網(wǎng)絡(luò)等方法進行優(yōu)化求解[12-14]，而對于大規(guī)模路線優(yōu)化問題，可采用遺傳算法、粒子群算法、蟻群算法等并行優(yōu)化計算方法進行求解[15-18]。其中，蟻群算法采用信息素正反饋的原理實現(xiàn)并行優(yōu)化計算，具有收斂速度快、全局尋優(yōu)能力強等特點，在各類路線優(yōu)化問題的求解中獲得了良好的應(yīng)用效果[19-20]。不過，目前路線優(yōu)化通常針對單機器人巡檢問題開展研究，即在給定的巡檢區(qū)域內(nèi)，為單一的巡檢機器人進行路線優(yōu)化。但在實際應(yīng)用中，當(dāng)巡檢點較多或巡檢區(qū)域較大時，為了盡快完成巡檢任務(wù)，往往采用多機器人共同協(xié)作完成巡檢任務(wù)，即由多個機器人同時對區(qū)域內(nèi)的巡檢點進行檢測，當(dāng)所有巡檢點都被檢測一次后，巡檢任務(wù)才最終完成。目前對于此類巡檢路線優(yōu)化問題研究較少，常用方法是基于地圖分割的巡檢路線優(yōu)化方法[21]，即將包括全部巡檢點的地圖劃分成若干區(qū)域，每個機器人獨立負責(zé)完成一個區(qū)域內(nèi)的巡檢任務(wù)，當(dāng)全部機器人均完成指定區(qū)域內(nèi)的巡檢任務(wù)后，最終的巡檢任務(wù)才完成。這樣，多機器人的路線優(yōu)化問題又可轉(zhuǎn)化為傳統(tǒng)的單機器人路線優(yōu)化問題進行求解。不過，這類問題的巡檢效率不僅與每個機器人的路線優(yōu)化有關(guān)，還與地圖分割方式有關(guān)。但對于大規(guī)模巡檢問題，由于巡檢節(jié)點分布的復(fù)雜性，很難按照先驗知識進行合理的地圖劃分。例如，常用基于等巡檢點數(shù)量的劃分或基于等巡檢面積的劃分，都無法保證劃分結(jié)果的全局優(yōu)化性能，造成有些區(qū)域機器人很快完成巡檢任務(wù)而處于閑置狀態(tài)，而個別區(qū)域長時間無法完成巡檢任務(wù)導(dǎo)致整體巡檢耗時過長。因此，由于巡檢任務(wù)劃分不均衡導(dǎo)致巡檢機器人不能充分利用，是降低巡檢效率的重要因素。

為此，本文提出可應(yīng)用于多機器人協(xié)同巡檢路線優(yōu)化的改進蟻群優(yōu)化算法，該算法可對多機器人巡檢任務(wù)實現(xiàn)巡檢區(qū)域的均衡劃分，提高巡檢機器人的利用率，減少巡檢整體任務(wù)量，提升巡檢系統(tǒng)的執(zhí)行效率。

1 協(xié)同巡檢路線優(yōu)化

1.1 問題描述

設(shè)給定的軍事巡檢區(qū)內(nèi)，共有N個巡檢節(jié)點{n1,n2,…,nN}，使用M個巡檢機器人{m1,m2,…,mM}協(xié)同巡檢，各機器人對應(yīng)的運行速度為{v1,v2,…,vM}，當(dāng)所有節(jié)點都完成一次巡檢時任務(wù)完成。其中，巡檢機器人的起始位置固定，對巡檢終點位置不做要求，即不要求巡檢機器人重新回到起始位置。此時最優(yōu)巡檢方案可表示為下列優(yōu)化問題的求解：

J=min{max{ti=Li/vi|i=1,2,…,M}}，

(1)

式中：J為優(yōu)化指標；ti為機器人mi的巡檢耗時；Li為機器人mi的巡檢路線。

如果所有機器人的速度相同，則該巡檢問題可簡化為如下路線優(yōu)化問題：

J=min{max{Li|i=1,2,…,M}}.

(2)

對于此問題，通常可采用基于地圖分割的方法進行路線優(yōu)化，即將巡檢范圍分為M個區(qū)域，每個巡檢機器人負責(zé)一個區(qū)域的巡檢作業(yè)，然后對各巡檢區(qū)單獨進行路線優(yōu)化。不過，由于巡檢節(jié)點分布的復(fù)雜性以及各區(qū)域路線優(yōu)化的隨機性，這種方法無法保證地圖分割時巡檢任務(wù)分配的均衡性，同時，由于各個機器人獨立巡檢，缺少協(xié)同配合，造成不同機器人完成巡檢作業(yè)的時間差距較大，導(dǎo)致部分機器人利用不充分，從而降低整體巡檢效率。

1.2 協(xié)同蟻群優(yōu)化算法

在傳統(tǒng)蟻群算法中，每個人工蟻都擁有一個禁忌表，用于避免巡檢節(jié)點的重復(fù)搜索，人工蟻之間通過路線上留存的信息素進行信息交互，實現(xiàn)路線的全局優(yōu)化，但這只能為單一機器人巡檢進行路線優(yōu)化。為了解決多機器人協(xié)同巡檢問題，本文所提出的協(xié)同蟻群優(yōu)化算法中，每個巡檢機器人都擁有一個蟻群，并采用共享禁忌表方式實現(xiàn)不同蟻群中人工蟻之間的信息共享，用于完成巡檢任務(wù)的全局優(yōu)化。人工蟻群及共享禁忌表的分布如表1所示。表1中P為人工蟻的數(shù)量。

表1 人工蟻群與共享禁忌表

表1中每一列為一個蟻群，每個巡檢機器人都擁有一個由P個人工蟻構(gòu)成的蟻群，例如機器人mi的蟻群為{ai,1,ai,2,…,ai,P}，因此，全部人工蟻的數(shù)量為M×P. 表1中最后一列為各個蟻群中的人工蟻所擁有的共享禁忌表，例如，第j行的所有人工蟻共同擁有共享禁忌表Tj. 另外，每個人工蟻均有一個代價表，用于累計當(dāng)前該人工蟻所付出的尋優(yōu)代價。協(xié)同蟻群優(yōu)化算法的尋優(yōu)過程可具體描述如下：

步驟1按照表1初始化M個蟻群，其中，每個蟻群中包含P個人工蟻，ai,j表示蟻群i中的第j個人工蟻，i=1,2,…,M，j=1,2,…,P. 每個人工蟻均擁有一個許可表和一個代價表，例如，Ai,j和Ci,j分別為人工蟻ai,j的許可表和代價表。Tj為M個蟻群中的人工蟻{a1,j,a2,j,…,aM,j}所共同擁有的共享禁忌表。最大迭代次數(shù)設(shè)為S，當(dāng)前迭代次數(shù)設(shè)為s=1.

步驟2清空所有的共享禁忌表Tj和代價表Ci, j，將所有節(jié)點置入每個人工蟻ai, j的許可表Ai, j中。

步驟3每個蟻群的人工蟻均放置在對應(yīng)巡檢機器人的初始節(jié)點上，即第j個蟻群的人工蟻均放置在第j個機器人的初始節(jié)點上。

步驟4將全部機器人初始節(jié)點從每個Ai, j中移出，并置入Tj中。

步驟5在各節(jié)點間的路線上初始化信息素濃度為隨機小數(shù)據(jù)。

步驟6將表1中的每行人工蟻組成一個協(xié)同尋優(yōu)小組，例如，第j行的人工蟻{a1,j,a2,j,…,aM,j}組成第j個協(xié)同尋優(yōu)小組，該小組尋優(yōu)過程如下：

從表2中可以看出，隨著磨礦細度的增加，無論是一段選別還是二段選別，精礦品位均逐漸增加，弱磁選與強磁選的鐵綜合回收率僅略有下降。根據(jù)生產(chǎn)指標要求，精礦鐵品位必須達到62%以上，因此，綜合考慮選擇一段磨礦細度-0.07 4 mm占72.96%，二段磨礦細度-0.045 mm占74.58%。此時試驗綜合指標為：精礦產(chǎn)率51.41%、鐵品位62.61%、回收率88.12%，尾礦鐵品位8.92%。

1)每個人工蟻ai,j將當(dāng)前所在節(jié)點置入代價表Ci, j中。

2)計算每個人工蟻ai, j的代價表Ci, j中的當(dāng)前代價值ci, j，并求得具有當(dāng)前最小代價值ck, j=min{ci,j,i=1,2,…,M}的人工蟻ak, j，ak,j為第j個協(xié)同尋優(yōu)小組中的第k個人工蟻，其當(dāng)前代價值最小。其中，代價值ci, j的計算方法為

(3)

式中：Li,j為代價表Ci, j中所存儲節(jié)點的路線長度。

3)設(shè)具有最小代價的人工蟻ak, j當(dāng)前位于節(jié)點h，則t時刻從節(jié)點h向節(jié)點l的轉(zhuǎn)移概率ph, l為

(4)

式中：α和β為作用強度參數(shù)；τh,l為節(jié)點h與節(jié)點l之間的信息素濃度；τh,q為節(jié)點h與節(jié)點q之間的信息素濃度；ηh,l為節(jié)點h與節(jié)點l之間的啟發(fā)式信息；ηh,q為節(jié)點h與節(jié)點q之間的啟發(fā)式信息，

(5)

dh,l為節(jié)點h與節(jié)點l之間的距離。

4)將人工蟻ak, j移至按照轉(zhuǎn)移概率選中的新節(jié)點上，并將該節(jié)點從許可表Ai, j中移出，加入到代價表Ci, j和共享禁忌表Tj中。

5)若禁忌表Tj中包含了全部節(jié)點，則第j行的人工蟻所組成的協(xié)同尋優(yōu)小組完成本次優(yōu)化；否則返回2繼續(xù)優(yōu)化，直到所有節(jié)點全部置入共享禁忌表Tj中。

步驟7若所有尋優(yōu)小組完成尋優(yōu)任務(wù)，則更新全部路線上的信息素濃度：

τh,l(t)=(1-ρ)τh,l(t)+Δτh,l，

(6)

式中：ρ為揮發(fā)系數(shù)；Δτh, l為節(jié)點h與節(jié)點l之間路線上的信息素增量，

(7)

(8)

Li,j為人工蟻ai,j當(dāng)前尋優(yōu)路線長度，Q為一個正常數(shù)。

步驟8s=s+1，如果迭代次數(shù)達到最大迭代次數(shù)，即s=S，則結(jié)束優(yōu)化，否則返回步驟2繼續(xù)下一次優(yōu)化。

傳統(tǒng)蟻群算法中，每只人工蟻按照預(yù)定規(guī)則獨立完成巡檢路線的優(yōu)化搜索，人工蟻之間缺少有效的協(xié)同機制，無法求解多機器人協(xié)同巡檢的路線優(yōu)化問題。改進蟻群算法中設(shè)置了共享禁忌表，為不同蟻群之間的人工蟻提供了信息共享機制，可實現(xiàn)不同蟻群之間的信息傳遞。而且，算法中引入了代價競爭機制，即同一優(yōu)化小組中，當(dāng)前優(yōu)化代價最小的人工蟻優(yōu)先獲得路線搜索權(quán)，由此建立了蟻群之間的協(xié)同合作機制，因此協(xié)同蟻群優(yōu)化算法可應(yīng)用于多機器人協(xié)同巡檢的路線優(yōu)化問題求解。

2 仿真實驗

為驗證協(xié)同蟻群優(yōu)化方法的有效性，將其應(yīng)用于多機器人協(xié)同巡檢的路線優(yōu)化問題求解中。采用TSP數(shù)據(jù)集作為巡檢測試數(shù)據(jù)，TSP公開數(shù)據(jù)集的網(wǎng)址為：http:∥elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/index.html，設(shè)巡檢機器人數(shù)量為4. 由于多機器人巡檢問題的復(fù)雜性，當(dāng)機器人初始位置不同時，優(yōu)化結(jié)果也不同。這里設(shè)定機器人的初始位置分別位于地圖的4個角，并假設(shè)各機器人的移動速度相同，均為1 m/s. 分別針對eil51、eil76、kroa100、krob150和kroa200共5組數(shù)據(jù)進行系統(tǒng)巡檢路線優(yōu)化，圖1～圖5分別給出了采用協(xié)同蟻群優(yōu)化方法和基于地圖分割的蟻群優(yōu)化算法求得的巡檢路線優(yōu)化結(jié)果。

圖1 eil51路線尋優(yōu)結(jié)果Fig.1 Optimized results of eil51 route

圖2 eil76路線尋優(yōu)結(jié)果Fig.2 Optimized results of eil76 route

從實驗結(jié)果可見，由于蟻群算法具有較好的全局尋優(yōu)能力，基于地圖分割的方法能夠根據(jù)給定區(qū)域內(nèi)巡檢節(jié)點的分布情況確定出合理的巡檢路線。但地圖分割的合理性對于整體尋優(yōu)性能影響很大，由于節(jié)點數(shù)量眾多，造成巡檢問題較為復(fù)雜，因此很難確定出最佳的地圖分割方案。而本文協(xié)同蟻群優(yōu)化算法在路線優(yōu)化過程中逐漸確定出各巡檢機器人的巡檢區(qū)域，也就是巡檢區(qū)域的劃分過程包含在路線優(yōu)化過程內(nèi)，因此能夠根據(jù)巡檢節(jié)點的整體分布給出符合全局優(yōu)化的最佳巡檢方案，以此提高巡檢效率。

表2給出了上述巡檢結(jié)果的具體路線數(shù)值。表2中，4個蟻群分別為4個機器人進行路線尋優(yōu)，所得路線最長的蟻群所對應(yīng)的巡檢時間為最終巡檢任務(wù)所需時間。從實驗結(jié)果可見，上述5個協(xié)同優(yōu)化問題中，基于協(xié)同蟻群優(yōu)化算法的最終巡檢時間均優(yōu)于基于地圖分割的蟻群優(yōu)化算法所得巡檢時間。

尋優(yōu)性能具體分析如表3所示。由表3可見，隨著巡檢節(jié)點數(shù)量的增加，協(xié)同蟻群優(yōu)化算法的耗時明顯小于基于地圖分割的蟻群優(yōu)化算法，因此巡檢效率也可得到明顯提升。兩種方法所得機器人的耗時均值相差并不大，但與基于地圖分割的蟻群優(yōu)化算法相比，協(xié)同蟻群優(yōu)化算法所得各機器人耗時的標準差明顯變小，最大空閑時間也明顯變小，說明各機器人所承擔(dān)的巡檢任務(wù)量較為均衡。另外，協(xié)同蟻群優(yōu)化算法中機器人耗時均值均略小于基于地圖分割的蟻群優(yōu)化算法，也說明協(xié)同蟻群優(yōu)化算法能夠通過合理劃分巡檢區(qū)域，獲得更優(yōu)的巡檢方案來減少協(xié)同巡檢總體任務(wù)量，從而進一步提高全局巡檢優(yōu)化性能。

圖3 kroa100路線尋優(yōu)結(jié)果Fig.3 Optimized results of kroa100 route

圖5 kroa200路線尋優(yōu)結(jié)果Fig.5 Optimized results of kroa200 route

表4給出了巡檢機器人平均利用率及最大閑置率的性能指標。由表4可見，與基于地圖分割的蟻群優(yōu)化算法相比，協(xié)同蟻群優(yōu)化算法中機器人的平均利用率得到了明顯提高，最大閑置率則明顯降低，進一步說明各機器人能夠得到充分利用，有效提高了整體巡檢效率。

表4 巡檢機器人利用率

3 結(jié)論

針對多機器人協(xié)同巡檢問題，本文提出了改進的協(xié)同蟻群優(yōu)化算法，將巡檢區(qū)域的劃分過程包含在路線優(yōu)化過程中，從而能夠為機器人進行合理的巡檢區(qū)域劃分，由此提高了全局巡檢效率。實驗結(jié)果表明，對于大規(guī)模巡檢優(yōu)化問題，協(xié)同蟻群優(yōu)化算法能夠給出更加合理的巡檢方案，從而可有效提升系統(tǒng)的整體巡檢效率。與基于地圖分割的蟻群優(yōu)化算法相比，整體巡檢量有所下降，機器人空閑時間縮短，利用率得到提高，巡檢效率得到提升。