韓宇星， 丁剛毅， 柴作鴻

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

0 引言

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

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

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

1.1 問(wèn)題描述

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

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

(1)

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

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

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

(2)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(3)

式中：Li,j為代價(jià)表Ci, j中所存儲(chǔ)節(jié)點(diǎn)的路線長(zhǎng)度。

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

(4)

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

(5)

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

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

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

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

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

(6)

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

(7)

(8)

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

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

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

2 仿真實(shí)驗(yàn)

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

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

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

尋優(yōu)性能具體分析如表3所示。由表3可見(jiàn)，隨著巡檢節(jié)點(diǎn)數(shù)量的增加，協(xié)同蟻群優(yōu)化算法的耗時(shí)明顯小于基于地圖分割的蟻群優(yōu)化算法，因此巡檢效率也可得到明顯提升。兩種方法所得機(jī)器人的耗時(shí)均值相差并不大，但與基于地圖分割的蟻群優(yōu)化算法相比，協(xié)同蟻群優(yōu)化算法所得各機(jī)器人耗時(shí)的標(biāo)準(zhǔn)差明顯變小，最大空閑時(shí)間也明顯變小，說(shuō)明各機(jī)器人所承擔(dān)的巡檢任務(wù)量較為均衡。另外，協(xié)同蟻群優(yōu)化算法中機(jī)器人耗時(shí)均值均略小于基于地圖分割的蟻群優(yōu)化算法，也說(shuō)明協(xié)同蟻群優(yōu)化算法能夠通過(guò)合理劃分巡檢區(qū)域，獲得更優(yōu)的巡檢方案來(lái)減少協(xié)同巡檢總體任務(wù)量，從而進(jìn)一步提高全局巡檢優(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給出了巡檢機(jī)器人平均利用率及最大閑置率的性能指標(biāo)。由表4可見(jiàn)，與基于地圖分割的蟻群優(yōu)化算法相比，協(xié)同蟻群優(yōu)化算法中機(jī)器人的平均利用率得到了明顯提高，最大閑置率則明顯降低，進(jìn)一步說(shuō)明各機(jī)器人能夠得到充分利用，有效提高了整體巡檢效率。

表4 巡檢機(jī)器人利用率

3 結(jié)論

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