路 浩 陳 洋 吳懷宇 程 磊

1.冶金自動(dòng)化與檢測(cè)技術(shù)教育部工程研究中心，武漢，4300812.武漢科技大學(xué)機(jī)器人與智能系統(tǒng)研究院，武漢，430081

0 引言

變電站高壓線路因灰塵、老化、天氣等影響，易出現(xiàn)電力事故，因此需要定期巡視和檢測(cè)以盡早發(fā)現(xiàn)和排除安全隱患。傳統(tǒng)的人工巡檢方式存在任務(wù)繁重、效率低下、容易漏檢等諸多問(wèn)題，采用變電站巡檢機(jī)器人代替人工可以實(shí)施全自主和全天候的巡檢工作[1-2]。機(jī)器人通過(guò)搭載可見(jiàn)光相機(jī)可以對(duì)電器儀表進(jìn)行識(shí)別與自動(dòng)讀數(shù)[3]，也可通過(guò)攜帶紅外熱成像儀對(duì)輸電線路進(jìn)行測(cè)溫[4-5]，從而實(shí)時(shí)監(jiān)視線路工作狀態(tài)。然而，變電站內(nèi)待測(cè)溫目標(biāo)依賴變電設(shè)備與電線支撐桿的分布，存在數(shù)量多、分布廣、高度不一等特點(diǎn)，這給機(jī)器人巡檢帶來(lái)了巨大的挑戰(zhàn)。

機(jī)器人路徑規(guī)劃[6-7]是變電站機(jī)器人執(zhí)行巡檢任務(wù)的重要環(huán)節(jié)，機(jī)器人路徑的優(yōu)劣影響到整個(gè)巡檢任務(wù)的效率。實(shí)際應(yīng)用中，對(duì)高壓線路的巡檢通常要求機(jī)器人在路網(wǎng)中多次?？繌亩鴮?duì)若干個(gè)目標(biāo)點(diǎn)測(cè)溫。傳統(tǒng)的路徑規(guī)劃方法，如動(dòng)態(tài)規(guī)劃算法、神經(jīng)網(wǎng)絡(luò)算法、粒子群算法、遺傳算法等方法[8]為解決上述問(wèn)題提供了借鑒和基礎(chǔ)，但是仍然存在以下難以克服的困難。

(1)巡檢機(jī)器人的運(yùn)動(dòng)受到變電站道路網(wǎng)絡(luò)的約束，且巡檢?？奎c(diǎn)須位于路網(wǎng)中。

(2)機(jī)器人對(duì)目標(biāo)點(diǎn)進(jìn)行測(cè)量時(shí)自身的位姿約束。首先，因測(cè)量?jī)x器性能限制，機(jī)器人與目標(biāo)之間的距離必須在允許可行范圍之內(nèi)。其次，機(jī)器人攜帶的測(cè)量?jī)x可以調(diào)節(jié)的姿態(tài)(如云臺(tái)的各關(guān)節(jié)角)受物理約束，尤其是當(dāng)云臺(tái)的自由度數(shù)較少時(shí)，會(huì)進(jìn)一步限制機(jī)器人測(cè)量時(shí)的姿態(tài)。

(3)為了提高巡檢效率，不僅期望機(jī)器人的運(yùn)動(dòng)總路徑更短，還期望在完成所有目標(biāo)點(diǎn)測(cè)溫任務(wù)的前提下盡可能減少停靠次數(shù)，以節(jié)省時(shí)間消耗和能量消耗。由于機(jī)器人在停靠時(shí)才進(jìn)行檢測(cè)，當(dāng)目標(biāo)點(diǎn)總數(shù)一定時(shí)，減少停靠次數(shù)便意味著增加每次?？繒r(shí)需完成測(cè)溫的目標(biāo)點(diǎn)數(shù)目。因此，機(jī)器人巡檢路徑的選擇是一個(gè)多約束非線性優(yōu)化問(wèn)題。

上述困難給傳統(tǒng)的路徑規(guī)劃方法帶來(lái)了巨大的挑戰(zhàn)。在變電站巡檢機(jī)器人路徑規(guī)劃問(wèn)題中，李寧等[9]針對(duì)路徑規(guī)劃中存在的重復(fù)路徑過(guò)多、巡檢效率低等問(wèn)題，提出了改進(jìn)的A*算法與蟻群算法融合的算法，減少了重復(fù)的巡檢路徑。ZHANG[10]在柵格地圖上考慮變電站的電場(chǎng)強(qiáng)度對(duì)巡檢任務(wù)的影響，將免疫蟻群算法用于巡檢機(jī)器人的路徑規(guī)劃，用模糊神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)目標(biāo)自動(dòng)測(cè)溫，但研究?jī)H在柵格地圖中加以驗(yàn)證，沒(méi)有考慮實(shí)際路網(wǎng)的約束。

DENG等[11]利用Dijkstra算法和改進(jìn)的蟻群算法進(jìn)行路徑規(guī)劃，其研究?jī)A向于巡檢機(jī)器人的自動(dòng)實(shí)時(shí)避障，不適用于路網(wǎng)與巡檢點(diǎn)較多的情況。TANG等[12]提出了一種基于交叉熵優(yōu)化的變電站巡檢機(jī)器人啟發(fā)式路徑規(guī)劃算法，先將任務(wù)點(diǎn)分類簡(jiǎn)化，再利用交叉熵優(yōu)化算法求解最短路徑，但其任務(wù)點(diǎn)分類沒(méi)有考慮具體的路徑與巡檢?？奎c(diǎn)的制約性。陳瑤等[13]與袁佳泉等[14]根據(jù)變電站環(huán)境構(gòu)建無(wú)向圖，將模擬退火算法與蟻群算法相結(jié)合，解決了機(jī)器人多點(diǎn)位巡檢問(wèn)題，該研究依靠磁導(dǎo)航，靈活性較差。王銳等[15]基于遺傳算法研究了機(jī)器人起點(diǎn)與終點(diǎn)相同且路網(wǎng)中的巡檢?？奎c(diǎn)不相同的路徑規(guī)劃問(wèn)題。ZHANG等[16]基于無(wú)向圖結(jié)合機(jī)器人實(shí)際運(yùn)行情況，以轉(zhuǎn)彎次數(shù)和轉(zhuǎn)彎角度作為評(píng)價(jià)指標(biāo)，對(duì)Dijkstra算法加以改進(jìn)并應(yīng)用于變電站的巡檢機(jī)器人路徑規(guī)劃。上述路徑規(guī)劃均基于圖論對(duì)變電站環(huán)境地圖建模，人為給定巡檢停靠點(diǎn)進(jìn)行求解，沒(méi)有結(jié)合變電站具體測(cè)溫約束對(duì)巡檢?？奎c(diǎn)優(yōu)化。

張承模等[17]提出受巡檢類型、路徑長(zhǎng)度、時(shí)間耗費(fèi)、場(chǎng)地通過(guò)難度、機(jī)器人控制復(fù)雜度等因素影響的變電站巡檢機(jī)器人路徑規(guī)劃，但并沒(méi)有抽象出具體的約束模型，不具備普遍適用性。PETERS等[18]在無(wú)人機(jī)監(jiān)視問(wèn)題中考慮了成像時(shí)間與拍攝角度限制，將多約束問(wèn)題近似為離散圖搜索問(wèn)題，從而轉(zhuǎn)化為一個(gè)廣義的旅行商問(wèn)題，以時(shí)間最小為目標(biāo)給出了監(jiān)視路徑，雖然理論上與高壓線路巡檢有相似性，但高壓線路巡檢問(wèn)題中涉及大量的目標(biāo)點(diǎn)，將目標(biāo)區(qū)域離散化之后的離散圖搜索會(huì)顯著增加時(shí)間消耗。CHEN等[19]研究了空-地異構(gòu)機(jī)器人系統(tǒng)的路徑規(guī)劃問(wèn)題，建立了多約束優(yōu)化模型和相應(yīng)的智能求解算法，其中無(wú)人機(jī)的能量約束和變電站巡檢機(jī)器人測(cè)溫時(shí)的位姿約束在空間意義上相似，對(duì)變電站巡檢機(jī)器人路徑規(guī)劃具有一定的借鑒意義。

本文考慮實(shí)際測(cè)量時(shí)機(jī)器人自身位姿和道路環(huán)境的約束，將待優(yōu)化的路徑長(zhǎng)度和?？看螖?shù)進(jìn)行加權(quán)，從而轉(zhuǎn)化為巡檢任務(wù)所消耗的總時(shí)間，然后以總時(shí)間最小為目標(biāo)建立數(shù)學(xué)優(yōu)化模型，提出一種基于蟻群算法的路徑優(yōu)化方法。

1 路徑規(guī)劃問(wèn)題描述

巡檢機(jī)器人典型的運(yùn)行環(huán)境和測(cè)溫點(diǎn)如圖1所示。首先分析巡檢機(jī)器人運(yùn)動(dòng)的路網(wǎng)。一般情況下機(jī)器人允許在變電站道路上雙向行駛，因此可以將機(jī)器人運(yùn)動(dòng)環(huán)境構(gòu)建為無(wú)向圖G(V,E)，如圖2所示，其中，道路節(jié)點(diǎn)集V={v1,v2,…vn}，n為道路節(jié)點(diǎn)的數(shù)目。巡檢機(jī)器人的出發(fā)點(diǎn)通常為充電房位置(圖2中節(jié)點(diǎn)s0)。E表示無(wú)向邊集，如E(i,j)表示由vi和vj相連的邊。圖2中測(cè)溫點(diǎn)Tq∈T(圖1b中紅色圓內(nèi)所示的壓接線鼻子)，q=1, 2, …,NT，NT表示測(cè)溫點(diǎn)的數(shù)量。權(quán)重W∈Rn×n表示機(jī)器人通過(guò)相應(yīng)邊時(shí)經(jīng)過(guò)的距離，例如wij表示機(jī)器人從vi運(yùn)動(dòng)到vj(或反向)經(jīng)過(guò)的距離，滿足如下約束：

(a)機(jī)器人的巡檢路徑 (b)典型的待測(cè)溫點(diǎn)

圖2 機(jī)器人運(yùn)動(dòng)的路網(wǎng)與測(cè)溫點(diǎn)示意圖

(1)

為了清晰地表述本文研究的路徑規(guī)劃問(wèn)題，對(duì)機(jī)器人工作環(huán)境作以下假設(shè)：

(1)取待測(cè)目標(biāo)的幾何中心點(diǎn)為測(cè)溫點(diǎn)Tq。忽略變電站道路寬度和坡度的影響，假設(shè)道路網(wǎng)絡(luò)可以完全在二維平面中呈現(xiàn)，即假設(shè)各道路節(jié)點(diǎn)及各邊在豎直軸上的投影坐標(biāo)均為0。

(2)為了降低能量消耗，提高任務(wù)執(zhí)行效率，假設(shè)機(jī)器人在路網(wǎng)中自主選擇不重復(fù)的巡檢路線完成巡檢任務(wù)，即機(jī)器人不會(huì)經(jīng)過(guò)同一個(gè)道路節(jié)點(diǎn)或邊兩次及兩次以上(出發(fā)點(diǎn)除外)。

(3)考慮路網(wǎng)和測(cè)溫點(diǎn)位置分布的隨機(jī)性，假設(shè)任意測(cè)溫點(diǎn)附近至少存在一條路徑或邊滿足對(duì)其進(jìn)行檢測(cè)的視距約束。

假設(shè)機(jī)器人第k次?？繉?shí)施測(cè)溫時(shí)的位置sk∈E(i,j)，即處于邊E(i,j)中的某點(diǎn)，并且該次?？客瓿蓽y(cè)溫的目標(biāo)集Ts(sk)?T。k=1, 2, …,K，K表示停靠的總次數(shù)，通常K≤NT。

機(jī)器人執(zhí)行巡檢任務(wù)時(shí)首先從充電房出發(fā)，在經(jīng)過(guò)節(jié)點(diǎn)(v′1，v′2，…，v′N′)的途中依次停靠s1,s2,…,sK對(duì)各目標(biāo)點(diǎn)進(jìn)行測(cè)溫，當(dāng)完成所有檢測(cè)任務(wù)后返回s0進(jìn)行充電，即v′1=v′N′=s0，該閉環(huán)路徑記為C。測(cè)溫的準(zhǔn)確性一般取決于測(cè)溫相機(jī)的精度、環(huán)境溫度以及圖像的采集處理方法[10]。該路徑規(guī)劃問(wèn)題主要考慮測(cè)溫?cái)?shù)據(jù)采集的效率，為了獲得最小的時(shí)間消耗，要求機(jī)器人在路網(wǎng)中盡量選擇總長(zhǎng)度小且?？看螖?shù)少的路徑。因此，本文的路徑規(guī)劃問(wèn)題可以描述為如下多目標(biāo)約束優(yōu)化問(wèn)題P1：

(2)

(3)

sk∈E(i,j)vi∈C,vj∈C,?i,j

(4)

在問(wèn)題P1中，C為G的圈(cycle)，式(2)表示需要對(duì)路徑的長(zhǎng)度l(G,T,s0)進(jìn)行優(yōu)化(簡(jiǎn)記為lC)，同時(shí)對(duì)機(jī)器人的?？看螖?shù)K(G,T,s0)進(jìn)行優(yōu)化。約束式式(3)表示所有?？奎c(diǎn)的鄰域須覆蓋全部測(cè)溫點(diǎn)集。約束式式(4)表示所有?？奎c(diǎn)必須限制在機(jī)器人的巡檢路徑中。該路徑規(guī)劃問(wèn)題的目標(biāo)是獲得機(jī)器人的巡檢路徑C、各?？奎c(diǎn)位置sk，以及各?？奎c(diǎn)所對(duì)應(yīng)的測(cè)溫點(diǎn)集Ts(sk)。

2 巡檢機(jī)器人路徑規(guī)劃模型

2.1 巡檢測(cè)溫位姿約束

巡檢機(jī)器人的位姿約束包括檢測(cè)相機(jī)俯仰角約束和最大視距約束。安裝相機(jī)的云臺(tái)模型如圖3所示，可繞水平軸和豎直軸旋轉(zhuǎn)，其中，繞豎直軸旋轉(zhuǎn)范圍為(0,2π)，繞水平軸旋轉(zhuǎn)范圍為(0,θmax)，θmax表示相機(jī)受云臺(tái)結(jié)構(gòu)[20]和拍攝質(zhì)量[21]約束的最大俯仰角度，0≤θmax≤π/2。實(shí)際應(yīng)用中，測(cè)溫點(diǎn)位于高架線路上，故只需考慮俯仰角上界θmax對(duì)巡檢任務(wù)的影響。

圖3 相機(jī)云臺(tái)模型圖

為了便于分析，引入如下定義：測(cè)溫點(diǎn)約束環(huán)STi，表示機(jī)器人對(duì)Ti進(jìn)行檢測(cè)時(shí)滿足位姿約束的位置集合。設(shè)測(cè)溫儀安裝位置離地高度為H，測(cè)溫點(diǎn)Ti的坐標(biāo)為(xTi,yTi,hi)，di為機(jī)器人停靠點(diǎn)s(xs,ys, 0)與測(cè)溫點(diǎn)Ti的水平距離，如圖4所示。

圖4 測(cè)溫點(diǎn)Ti的約束環(huán)示意圖

因此，相機(jī)俯仰角度和視距須分別滿足如下約束：

(5)

(6)

(7)

其中，dmax表示相機(jī)在滿足檢測(cè)質(zhì)量要求下的最大視距。式(6)表示機(jī)器人必須在相機(jī)可視范圍內(nèi)對(duì)目標(biāo)進(jìn)行測(cè)溫。根據(jù)式(5)與式(6)，可得測(cè)溫點(diǎn)的約束環(huán)STi計(jì)算式：

(8)

上述分析表明，當(dāng)且僅當(dāng)機(jī)器人位于式(8)所示的環(huán)域STi內(nèi)時(shí),才可對(duì)Ti實(shí)現(xiàn)有效測(cè)溫。

2.2 巡檢路徑預(yù)處理

變電站機(jī)器人須從充電房s0出發(fā)完成測(cè)溫任務(wù)后再返回充電房，記機(jī)器人在路網(wǎng)中的巡檢路徑C={v′1,v′2,…,v′N′}?V，其中，v′1=v′N′=s0。組成上述路徑的邊E′=(v′i,v′i+1)?E,i=1,2,…,N′-1。該路徑總長(zhǎng)度為

(9)

?？奎c(diǎn)s可以是機(jī)器人巡檢路徑邊E′上的任意一點(diǎn)。為了方便分析，本文通過(guò)對(duì)路徑均勻插值獲得離散化路徑點(diǎn)[19]。假設(shè)相鄰兩個(gè)離散點(diǎn)的間距為IL，組成該路徑的離散點(diǎn)集為L(zhǎng)。機(jī)器人在離散化路徑中的?？奎c(diǎn)由測(cè)溫點(diǎn)約束環(huán)STi與離散路徑L的交集確定，即

(10)

2.3 目標(biāo)函數(shù)

以完成巡檢任務(wù)總時(shí)間最短為目標(biāo)，路徑規(guī)劃的目標(biāo)函數(shù)如下：

(11)

式中，λ為機(jī)器人每次?？繙y(cè)溫所消耗的時(shí)間常數(shù)；λK為執(zhí)行K次?？繙y(cè)溫所需的時(shí)間；lC/v為機(jī)器人在路徑中持續(xù)運(yùn)動(dòng)所需時(shí)間；v為機(jī)器人平均運(yùn)動(dòng)速度。

以機(jī)器人在巡檢過(guò)程中消耗的時(shí)間最短為目標(biāo)，構(gòu)建以下數(shù)學(xué)優(yōu)化模型：

s.t.式(1)、式(4)～式(10)

基于上述分析，機(jī)器人執(zhí)行任務(wù)的一個(gè)例子如圖5所示。首先，機(jī)器人從充電房s0出發(fā)沿藍(lán)色箭頭所示路徑運(yùn)動(dòng)，依次?？吭趕1對(duì)T1和T2測(cè)溫、?？吭趕2對(duì)T5測(cè)溫、?？吭趕3對(duì)T3和T4測(cè)溫，最后返回充電房。圖5中綠色區(qū)域是根據(jù)式(8)畫(huà)出的各測(cè)溫點(diǎn)約束環(huán)。機(jī)器人的部分路徑被測(cè)溫環(huán)的交集所覆蓋，用紅色線段表示，這意味機(jī)器人?？吭诩t色路徑段上任意一點(diǎn)均可完成對(duì)相應(yīng)目標(biāo)點(diǎn)的檢測(cè)。如機(jī)器人對(duì)T5測(cè)溫時(shí)有s2和s′2兩個(gè)分離的路段可供選擇。

圖5 機(jī)器人執(zhí)行任務(wù)示例俯視圖

3 求解方法

上述建立的機(jī)器人路徑規(guī)劃模型是一個(gè)復(fù)雜的多約束非線性優(yōu)化問(wèn)題，求解過(guò)程中須著重考慮解的構(gòu)建與更新方法。由于解的主要部分巡檢路徑C具有路徑節(jié)點(diǎn)數(shù)目不確定的特點(diǎn)，即解的維數(shù)不確定，而相關(guān)智能算法(包括模擬退火算法，粒子群算法與遺傳算法等)難以構(gòu)建維度不等的解，所以這些算法在迭代更新時(shí)會(huì)出現(xiàn)困難。蟻群算法通過(guò)輪盤賭與禁忌表的設(shè)計(jì)易實(shí)現(xiàn)螞蟻在路網(wǎng)中尋路構(gòu)建維度不一的初始解，同時(shí)易于將解的優(yōu)劣轉(zhuǎn)化為信息素的強(qiáng)弱來(lái)影響螞蟻的選擇，使路網(wǎng)約束與測(cè)量約束貫穿于整個(gè)求解過(guò)程，因此本文通過(guò)改進(jìn)傳統(tǒng)蟻群優(yōu)化算法進(jìn)行路徑規(guī)劃模型的求解。首先，以充電房為巡檢任務(wù)的起點(diǎn)和終點(diǎn)，采用蟻群算法獲得一條完整的巡檢路徑；其次，基于貪婪思想并結(jié)合約束條件對(duì)測(cè)溫點(diǎn)進(jìn)行聚類，計(jì)算出螞蟻路徑的?？看螖?shù)；然后，根據(jù)目標(biāo)函數(shù)將其換算為時(shí)間代價(jià)對(duì)路網(wǎng)中信息素進(jìn)行更新；最后，將上述過(guò)程反復(fù)迭代并更新全局最優(yōu)解，從而求出最優(yōu)路徑、?？奎c(diǎn)序列以及每個(gè)?？奎c(diǎn)對(duì)應(yīng)的測(cè)溫點(diǎn)集。求解流程如圖6所示。

圖6 路徑規(guī)劃求解流程

3.1 基于蟻群算法的路徑優(yōu)化

本文受文獻(xiàn)[10,19]的啟發(fā)，采用蟻群算法優(yōu)化路徑。設(shè)蟻群中螞蟻的數(shù)量為M，第m(m=1,2,…,M)只螞蟻從路網(wǎng)節(jié)點(diǎn)vi轉(zhuǎn)移到vj的概率

(12)

ηij(t)=1/wij

(13)

式中，τij(t)為t時(shí)刻邊E(i,j)上殘留信息素濃度；ηij(t)為啟發(fā)函數(shù)，表示螞蟻從節(jié)點(diǎn)vi轉(zhuǎn)移到vj的期望程度，與節(jié)點(diǎn)間距離成反比；Am為螞蟻m待訪問(wèn)的節(jié)點(diǎn)集合；α為信息素重要程度因子；β為啟發(fā)函數(shù)重要程度因子。

當(dāng)所有螞蟻完成一次循環(huán)時(shí)，根據(jù)下式進(jìn)行迭代：

(14)

(15)

式中，ρ為信息素的揮發(fā)程度，ρ∈(0,1)；Δτij，m(t)為螞蟻m在經(jīng)過(guò)的邊E(i,j)上釋放的信息素；Q為信息素釋放總量，Q為常量；fm為根據(jù)式(11)計(jì)算的螞蟻m完成任務(wù)總時(shí)間；Δτij(t)為蟻群中所有螞蟻在邊E(i,j)上釋放的信息素之和。

蟻群算法求解流程如下。

(1)初始化相關(guān)參數(shù)：螞蟻數(shù)量M、信息素重要程度因子α、啟發(fā)函數(shù)重要程度因子β、信息素的揮發(fā)程度ρ、信息素釋放總量Q、最大迭代次數(shù)tmax、機(jī)器人相機(jī)高度H、相機(jī)俯仰角度最大上限值θmax、相機(jī)最大視距dmax、機(jī)器人每次?？繙y(cè)溫所消耗的時(shí)間常數(shù)λ、機(jī)器人平均運(yùn)動(dòng)速度v、離散化路徑中相鄰離散點(diǎn)間距IL。

(2)構(gòu)建解空間。初始時(shí)刻將螞蟻放在充電房位置，每只螞蟻根據(jù)式(12)依次跳轉(zhuǎn)到隨機(jī)概率最大的下一個(gè)節(jié)點(diǎn)，直到該螞蟻回到出發(fā)點(diǎn)或者無(wú)可跳轉(zhuǎn)節(jié)點(diǎn)。所有螞蟻執(zhí)行相同操作。

(3)更新信息素。①記第m只螞蟻選擇的閉環(huán)路徑為Cm，根據(jù)式(9)計(jì)算其長(zhǎng)度lC,m(m=1,2,…,M)，同時(shí)將Cm離散化，得到路徑點(diǎn)集Lm，最后獲得Lm與第i個(gè)測(cè)溫點(diǎn)約束環(huán)STi的交集，記為Bi，m=STi∩Lm。②當(dāng)m=1時(shí)，判斷是否存在某個(gè)測(cè)溫點(diǎn)Ti使得Bi，1=?,i=1,2,…,NT,若存在，則表示螞蟻m無(wú)法完成全部巡檢任務(wù)，令完成任務(wù)總時(shí)間f1=∞；反之，對(duì)路徑Cm上的所有測(cè)溫點(diǎn)根據(jù)約束進(jìn)行聚類(將在3.2節(jié)介紹)，得出類別總數(shù)K1，將其代入式(11)計(jì)算巡檢時(shí)間代價(jià)f1。依次計(jì)算當(dāng)m=2,3,…,M時(shí)所對(duì)應(yīng)的f2,f3,…,fM值，根據(jù)式(14)和式(15)更新信息素。信息素更新流程如圖7所示。

圖7 路網(wǎng)中信息素更新流程

(4)判斷蟻群是否終止迭代。計(jì)算當(dāng)前迭代中所有螞蟻完成巡檢任務(wù)的時(shí)間消耗，同時(shí)與以前迭代中獲得的全局最優(yōu)解比較，當(dāng)存在更小的時(shí)間代價(jià)時(shí)，則更新全局最優(yōu)解。然后，判斷迭代次數(shù)是否達(dá)到最大值，若未達(dá)到，則返回步驟(2)，若達(dá)到則停止計(jì)算，輸出全局最優(yōu)解對(duì)應(yīng)的巡檢路徑C、各?？奎c(diǎn)位置sk以及各?？奎c(diǎn)所對(duì)應(yīng)的測(cè)溫點(diǎn)集Ts(sk)。

3.2 基于貪婪思想的測(cè)溫點(diǎn)聚類

在螞蟻獲得一條完整的巡檢路徑后，對(duì)測(cè)溫點(diǎn)聚類以獲得機(jī)器人在該路徑下的測(cè)溫停靠方案。聚類獲得的類別數(shù)目便是機(jī)器人的?？看螖?shù)。本文基于貪婪思想[22]將滿足測(cè)量約束的測(cè)溫點(diǎn)聚為一類，通過(guò)迭代獲得聚類結(jié)果。聚類算法流程如下：

(1)構(gòu)建待聚類的測(cè)溫點(diǎn)初始集合A=T，求螞蟻m的離散化路徑Lm與第i個(gè)測(cè)溫點(diǎn)約束環(huán)STi的交集Bi,m，i=1, 2, …,NT。

(2)計(jì)算路徑點(diǎn)集Bij,m，j>i且測(cè)溫點(diǎn)Tj∈A。集合Bij,m中離散點(diǎn)的數(shù)目Nij,m=|Bij,m|，代表了Ti與Tj的相近程度。將所有Nij，m從大到小排序，得Nij1，m≥Nij2，m≥…≥NijZ,m，其中，Z=|A|-1。路徑點(diǎn)集Bij,m計(jì)算公式為

Bij，m=Bi，m∩Bj，m

(16)

(3)如果Nij1，m=0，表示Ti與其他目標(biāo)點(diǎn)沒(méi)有共同可行的停靠路徑點(diǎn)，則將Ti單獨(dú)歸為一類，即Ts,m(sk)={Ti}，然后執(zhí)行步驟(5)計(jì)算螞蟻m剩余?？奎c(diǎn)，否則，執(zhí)行步驟(4)。

(4)如果Nij1,m>0，則路徑點(diǎn)集Bij1,m≠?。定義可行的?？柯窂郊螪ijr+1,m=Dijr,m∩Bijr+1,m，其中Dij1,m=Bij1,m，r=1, 2, …,Z。易求得

則得到?？奎c(diǎn)sk,m可完成測(cè)溫的目標(biāo)集Ts,m(sk)={Ti,Tj1,…,Tjr*}，相應(yīng)停靠區(qū)域集合的表達(dá)式為

(17)

于是根據(jù)式(10)，?？奎c(diǎn)sk,m從停靠區(qū)域集BTs,m(sk),m中任意選擇即可。

(5)從A中剔除能夠完成檢測(cè)的目標(biāo)集Ts，m(sk)，即

A=A-Ts，m(sk)

從A中選擇下一個(gè)測(cè)溫點(diǎn)執(zhí)行步驟(2)，直到A為空集時(shí)，得到螞蟻m的路徑對(duì)應(yīng)的?？奎c(diǎn)位置s1，m,s2，m,…,sK，m與其所對(duì)應(yīng)的測(cè)溫點(diǎn)集Ts，m(s1),Ts，m(s2),…，Ts，m(sK)。

(6)最后根據(jù)機(jī)器人閉環(huán)路徑C中道路節(jié)點(diǎn)的先后順序調(diào)整sk，m的順序，得到最終的s1，m,s2，m,…,sK，m與Ts，m(s1),Ts，m(s2),…，Ts，m(sK)，避免機(jī)器人在此路徑中往復(fù)運(yùn)動(dòng)。

該聚類算法的核心是將離散路徑與測(cè)溫點(diǎn)約束環(huán)的交集作為基本處理單元，以各個(gè)單元之間的交集大小來(lái)表征當(dāng)前路徑下目標(biāo)點(diǎn)之間的相近程度，從而確定是否為同一類。

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

實(shí)驗(yàn)分為簡(jiǎn)易路網(wǎng)和實(shí)際變電站路網(wǎng)兩種情況，簡(jiǎn)易路網(wǎng)下的路徑規(guī)劃結(jié)果更清晰地表明了本文方法的有效性和可行性，實(shí)際變電站路網(wǎng)下的路徑規(guī)劃結(jié)果表明實(shí)驗(yàn)方法具有良好的魯棒性。

4.1 簡(jiǎn)易路網(wǎng)下路徑規(guī)劃結(jié)果

簡(jiǎn)易路網(wǎng)由8個(gè)道路節(jié)點(diǎn)與15條道路邊組成，另外有5個(gè)測(cè)溫點(diǎn)分布于路網(wǎng)附近，經(jīng)實(shí)地勘測(cè)其高度處于7～10 m之間，充電房位置是v1，具體參數(shù)如表1所示。

表1 道路節(jié)點(diǎn)與測(cè)溫點(diǎn)

蟻群算法與機(jī)器人的相關(guān)參數(shù)如表2所示，其中蟻群算法參數(shù)對(duì)程序運(yùn)行時(shí)間與最優(yōu)解的影響已有相關(guān)研究[23-24]，機(jī)器人參數(shù)來(lái)源于工程實(shí)際。由于部分巡檢機(jī)器人的結(jié)構(gòu)限制，設(shè)相機(jī)俯仰角度的最大上限值θmax為π/3，通過(guò)更換鏡片相機(jī)的最大視距可達(dá)50 m，最佳測(cè)溫范圍為20～30 m，將dmax設(shè)為25 m。IL為0.5 m，表示路徑由間隔不超過(guò)0.5 m的離散點(diǎn)構(gòu)成。

表2 蟻群算法參數(shù)與機(jī)器人參數(shù)

采用MATLAB R2019a作為仿真平臺(tái)，仿真結(jié)果如圖8所示。圖8中藍(lán)色粗線段為機(jī)器人的最終巡檢路徑，包括兩次?？?，分別位于s1和s2。s1處的紅色線段為機(jī)器人測(cè)量目標(biāo)點(diǎn)集{T2,T4,T5}時(shí)的可?？柯范危撀范问歉鶕?jù)式(17)將測(cè)溫點(diǎn)約束環(huán)ST2、ST4、ST5與離散化路徑取交集得到的。同理可得到s2處的紅色線段，不過(guò)由于ST1內(nèi)環(huán)的限制，停靠路段被分為兩個(gè)不相連的部分，這符合機(jī)器人在ST1內(nèi)環(huán)中無(wú)法對(duì)T1測(cè)溫的實(shí)際情況。

圖8 簡(jiǎn)易路網(wǎng)路徑規(guī)劃結(jié)果

機(jī)器人最優(yōu)巡檢路線是表3中的路徑1：v1—v4—v6—v2—v1。為了分析聚類方法的準(zhǔn)確性，從螞蟻解空間中選取?？看螖?shù)不同的三條典型路徑，其中路徑3與測(cè)溫點(diǎn)約束環(huán)相交為4段不相連的部分，且除第一段對(duì)應(yīng){T1,T3}外，其余三段均單獨(dú)對(duì)應(yīng)測(cè)溫點(diǎn)，表明機(jī)器人需要在該路徑上?？?次才完成任務(wù)。路徑2分析同理，聚類結(jié)果與表3中的停靠次數(shù)一致，證明了聚類方法的準(zhǔn)確性。由圖8可知，機(jī)器人巡檢流程與表4所示的聚類結(jié)果相吻合，證明了該求解方法的可行性。由比較結(jié)果可知，時(shí)間代價(jià)最小的路徑1相比其他兩條路徑，?？奎c(diǎn)數(shù)量最少且路徑長(zhǎng)度最短。

表3 簡(jiǎn)易路網(wǎng)主要路徑對(duì)比

表4 簡(jiǎn)易路網(wǎng)最優(yōu)路徑1聚類結(jié)果

圖9給出了蟻群算法迭代過(guò)程中簡(jiǎn)易路網(wǎng)下所有螞蟻的最小時(shí)間消耗及其對(duì)應(yīng)的?？看螖?shù)和路徑長(zhǎng)度的變化曲線。其中，最小時(shí)間消耗曲線是根據(jù)時(shí)間代價(jià)式(11)將?？看螖?shù)與路徑長(zhǎng)度曲線加權(quán)得到的。迭代初期，螞蟻根據(jù)啟發(fā)函數(shù)并行搜索，隨著信息素的更新，螞蟻逐漸趨向于時(shí)間代價(jià)較小的路徑。迭代7次后，最小時(shí)間消耗曲線不再變化，說(shuō)明完成巡檢任務(wù)的時(shí)間消耗可能已達(dá)到最優(yōu)值。

圖9 簡(jiǎn)易路網(wǎng)下迭代過(guò)程中的最優(yōu)解

4.2 實(shí)際變電站路網(wǎng)中路徑規(guī)劃結(jié)果

實(shí)際路網(wǎng)實(shí)驗(yàn)基于變電站點(diǎn)云地圖數(shù)據(jù)提取[25]與實(shí)地勘測(cè)。采用16線3維激光雷達(dá)構(gòu)建的點(diǎn)云地圖俯視效果如圖10所示。該地圖清晰地展示了地圖尺寸與變電設(shè)備位置等信息，四周不規(guī)則的點(diǎn)線為變電站圍墻，墻內(nèi)黃色的點(diǎn)是電線支撐桿，紅色粗線表示構(gòu)圖過(guò)程中機(jī)器人運(yùn)動(dòng)的軌跡，相應(yīng)實(shí)物的坐標(biāo)及尺寸采用ROS(robot operating system)下的Rviz可視化平臺(tái)獲取，并結(jié)合激光測(cè)距儀實(shí)地勘測(cè)進(jìn)行矯正。

圖10 變電站點(diǎn)云地圖

由于測(cè)溫點(diǎn)通常依托電線桿集群分布，因此該仿真以電線桿的位置代替測(cè)溫點(diǎn)位置。圖10所示變電站的范圍大約為100 m×120 m，包括270個(gè)測(cè)溫點(diǎn)，根據(jù)實(shí)驗(yàn)數(shù)據(jù)建立的道路網(wǎng)絡(luò)由42個(gè)節(jié)點(diǎn)與63條邊組成。

為了進(jìn)一步確定離散化路徑中相鄰離散點(diǎn)間距IL的最優(yōu)值，選取不同值對(duì)比分析。首先排除蟻群算法中無(wú)解螞蟻的干擾，然后采用單一變量法進(jìn)行實(shí)驗(yàn)。取表5中最優(yōu)路徑C*與270個(gè)測(cè)溫點(diǎn)，選IL為0.1 m、0.2 m、…、3 m的30組參數(shù)重復(fù)進(jìn)行50次聚類實(shí)驗(yàn)，結(jié)果如圖11所示。

表5 實(shí)際路網(wǎng)主要路徑對(duì)比

圖11 參數(shù)IL對(duì)聚類算法的影響

圖11表明聚類算法的耗時(shí)會(huì)隨著IL的增大而減小，而IL增大會(huì)導(dǎo)致聚類結(jié)果中機(jī)器人?？看螖?shù)增大。為了避免錯(cuò)過(guò)最優(yōu)解且盡量縮短程序運(yùn)行時(shí)間，IL取0.2 m。其他參數(shù)如表2所示。

機(jī)器人在實(shí)際變電站路網(wǎng)中的最優(yōu)巡檢路徑如圖12中藍(lán)色粗線所示，其中符號(hào)含義與圖8相同，充電房位于節(jié)點(diǎn)v16。圖12中紅色圓是機(jī)器人停靠在s3時(shí)測(cè)溫相機(jī)的最大可視范圍，其半徑為相機(jī)最大視距dmax，星號(hào)表示目標(biāo)點(diǎn)T1、T2、…、T270的位置。由于測(cè)溫?cái)?shù)量較多，除測(cè)溫點(diǎn)集合Ts(s1)與Ts(s3)外，其他測(cè)溫點(diǎn)編號(hào)以及相應(yīng)的測(cè)溫點(diǎn)約束環(huán)均未標(biāo)出。仿真結(jié)果表明，機(jī)器人的最優(yōu)巡檢路徑從充電房v16出發(fā)，完成全部檢測(cè)任務(wù)后返回充電房，一共需?？?2次，?？奎c(diǎn)分別為s1,s2, …,s12，如圖12中紅色六角星所示。

圖12 實(shí)際路網(wǎng)下路徑規(guī)劃結(jié)果

采用本文方法得到符合約束條件的解空間，根據(jù)式(11)計(jì)算時(shí)間代價(jià)，其中時(shí)間代價(jià)最小的3條路徑如表5所示。由表5可以看出，路徑1的時(shí)間代價(jià)最小，為最優(yōu)路徑C*，路徑2的?？看螖?shù)與路徑長(zhǎng)度均大于C*，雖然路徑3的長(zhǎng)度比C*小，但?？看螖?shù)卻多于C*。由此可見(jiàn)，最優(yōu)路徑C*代表的是綜合性能最佳的巡檢方案。

最優(yōu)路徑C*的測(cè)溫點(diǎn)聚類結(jié)果如表6所示，機(jī)器人需要在該路徑上停靠12次以完成對(duì)270個(gè)目標(biāo)點(diǎn)的測(cè)溫。另外，測(cè)溫點(diǎn)集合Ts(s1)全部位于圖12中以s1為圓心的紅色圓域內(nèi)，該聚類結(jié)果與機(jī)器人在s1對(duì)Ts(s1)進(jìn)行測(cè)溫的事實(shí)相符，Ts(s3)同理。

表6 最優(yōu)路徑C*對(duì)應(yīng)的測(cè)溫點(diǎn)聚類結(jié)果

圖13為實(shí)際變電站路網(wǎng)下蟻群算法迭代過(guò)程曲線，其含義與圖9相同。迭代開(kāi)始時(shí)，螞蟻根據(jù)啟發(fā)函數(shù)尋路，由于路網(wǎng)較復(fù)雜，只有少部分螞蟻完成巡檢任務(wù)，故信息素對(duì)蟻群的影響較小，最小時(shí)間代價(jià)曲線變化不明顯；迭代7次后，螞蟻在信息素的影響下逐漸趨向于時(shí)間代價(jià)較小的路徑，迭代曲線呈下降趨勢(shì)；迭代23次后，最小時(shí)間消耗曲線逐漸收斂，與圖9相比，簡(jiǎn)易路網(wǎng)下迭代曲線先收斂，說(shuō)明曲線收斂速度隨著路網(wǎng)復(fù)雜度與測(cè)溫點(diǎn)數(shù)量的降低而加快，且允許最小時(shí)間消耗曲線下降過(guò)程中路徑長(zhǎng)度與停靠次數(shù)曲線發(fā)生振蕩，即迭代過(guò)程選擇綜合性能最佳的最優(yōu)解。

圖13 實(shí)際路網(wǎng)下迭代過(guò)程中的最優(yōu)解

在圖10所示的變電站環(huán)境中進(jìn)行測(cè)試，實(shí)驗(yàn)采用自主研制的巡檢機(jī)器人，具備室外導(dǎo)航與定位的基本功能，定位誤差為±10 cm，設(shè)導(dǎo)航最大速度為3 m/s，控制響應(yīng)周期為0.1 s，其余參數(shù)設(shè)定同表2。機(jī)器人的軟件、硬件與巡檢任務(wù)如圖14所示，可以在巡檢?？奎c(diǎn)處收集紅外圖像。

圖14 機(jī)器人巡檢系統(tǒng)

機(jī)器人從充電房出發(fā)依次通過(guò)12個(gè)紅色巡檢?？奎c(diǎn)完成任務(wù)的藍(lán)色定位軌跡如圖15所示，該軌跡與圖12中藍(lán)色最優(yōu)路徑C*相同，說(shuō)明機(jī)器人可以自主完成巡檢任務(wù)。

圖15 實(shí)際巡檢軌跡

實(shí)驗(yàn)總耗時(shí)為695 s，大于仿真耗時(shí)，機(jī)器人的巡檢路徑為402.9 m，小于仿真路徑長(zhǎng)度，原因是機(jī)器人在運(yùn)動(dòng)中，訪問(wèn)道路節(jié)點(diǎn)與導(dǎo)航避障會(huì)降低速度，增長(zhǎng)耗時(shí)，而機(jī)器人在道路節(jié)點(diǎn)處以弧線轉(zhuǎn)彎，巡檢路徑長(zhǎng)度略有減小，由于仿真中熱成像儀的視距取較小值，即使機(jī)器人位置因?qū)Ш綑C(jī)制存在±30 cm左右的誤差也不影響巡檢任務(wù)的完成。另外，機(jī)器人在巡檢任務(wù)點(diǎn)測(cè)溫時(shí)，不僅要調(diào)整云臺(tái)姿態(tài)，還應(yīng)保證自身位姿不傾斜。

5 結(jié)論

(1)將傳統(tǒng)的單一路網(wǎng)約束拓展至路網(wǎng)與測(cè)量雙約束，以時(shí)間消耗最小為目標(biāo)構(gòu)建路徑規(guī)劃模型。

(2)提出了一種基于改進(jìn)蟻群算法的路徑優(yōu)化方法，采用貪婪思想對(duì)測(cè)溫點(diǎn)聚類以確定巡檢?？奎c(diǎn)，并將聚類結(jié)果和路徑長(zhǎng)度共同用于路網(wǎng)信息素的更新。

(3)通過(guò)仿真實(shí)驗(yàn)與實(shí)測(cè)數(shù)據(jù)驗(yàn)證了本文方法的可行性和魯棒性，繼而得到機(jī)器人的最優(yōu)巡檢路徑、巡檢?？奎c(diǎn)序列以及各停靠點(diǎn)對(duì)應(yīng)的測(cè)溫點(diǎn)集，機(jī)器人實(shí)際運(yùn)行結(jié)果表明所提方法可以實(shí)現(xiàn)，能夠滿足巡檢的要求。

該路徑規(guī)劃模型還存在一些有待改進(jìn)之處，例如：如何將巡檢類型、路徑長(zhǎng)度、時(shí)間耗費(fèi)、場(chǎng)地通過(guò)難度、機(jī)器人控制復(fù)雜度等多個(gè)實(shí)際約束相結(jié)合，使模型貼近實(shí)際，更具通用性；當(dāng)機(jī)器人停靠后對(duì)多個(gè)目標(biāo)進(jìn)行測(cè)溫時(shí)，如何考慮云臺(tái)姿態(tài)調(diào)整過(guò)程的時(shí)間消耗，以進(jìn)一步減少任務(wù)執(zhí)行時(shí)間，提高巡檢的效率等。本文方法仍需進(jìn)一步完善，如蟻群算法與基于貪婪思想的聚類具有局限性，最優(yōu)解可能并非全局最優(yōu)。