周熙煒，尚 宵，尚新娟，閆茂德，王發(fā)發(fā)

（長(zhǎng)安大學(xué)，陜西 西安 710064）

0 引言

地下綜合管廊，又稱(chēng)“共同溝”，擔(dān)負(fù)著輸送介質(zhì)、能量和傳輸信息的功能，是城市的“生命線(xiàn)”。采用綜合管廊的建設(shè)方式，能合理、有效地利用城市地下空間，科學(xué)地敷設(shè)各類(lèi)市政管線(xiàn)，有利于管廊內(nèi)部的運(yùn)維。隨著人工智能及機(jī)器人技術(shù)的不斷發(fā)展，基于巡檢機(jī)器人移動(dòng)監(jiān)測(cè)的技術(shù)方案應(yīng)運(yùn)而生；但受自身存儲(chǔ)空間等因素的影響，機(jī)器人不能及時(shí)更新信息，降低了系統(tǒng)的實(shí)時(shí)性能，故提出使用云機(jī)器人來(lái)解決上述問(wèn)題。云機(jī)器人是“機(jī)器人+物聯(lián)網(wǎng)+云計(jì)算”技術(shù)結(jié)合的新型應(yīng)用，借助云端強(qiáng)大的并行計(jì)算能力、存儲(chǔ)和通信資源，可以把巡檢機(jī)器人本體的數(shù)據(jù)處理、規(guī)劃、決策及協(xié)作等復(fù)雜計(jì)算功能“卸載”到云平臺(tái)，機(jī)器人本體僅需保留最基本的傳感器、執(zhí)行器和處理單元來(lái)完成一些高實(shí)時(shí)性作業(yè)，以減小機(jī)器人體積、降低功耗、延長(zhǎng)航程，從而解決制約機(jī)器人應(yīng)用的系統(tǒng)復(fù)雜度高、智力水平低和可靠性差等問(wèn)題。

云機(jī)器人的路徑規(guī)劃與調(diào)度算法一直受到研究學(xué)者們的廣泛關(guān)注。ASORO實(shí)驗(yàn)室采用Hadoop分布式系統(tǒng)構(gòu)架，建立了云計(jì)算基礎(chǔ)設(shè)施并生成3D環(huán)境模型，從而支持機(jī)器人進(jìn)行即時(shí)定位與地圖構(gòu)建[1]；Arumugam R等人[2]利用Hadoop計(jì)算群和ROS系統(tǒng)提出了DavinCi軟件框架，將云計(jì)算應(yīng)用在服務(wù)機(jī)器人中；趙連翔等人[3]將云計(jì)算的理念運(yùn)用到機(jī)器人遙控操作上，設(shè)計(jì)了機(jī)器人云操作平臺(tái)。Kenendy博士和Eberhart博士于1995年首次提出粒子群優(yōu)化算法（particle swarm optimization, PSO）[4]，該算法已被廣泛應(yīng)用到函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練及模糊控制系統(tǒng)等多個(gè)領(lǐng)域。文獻(xiàn)[5-7]分別對(duì)PSO算法進(jìn)行了改進(jìn)，并應(yīng)用其解決了復(fù)雜的非凸/非線(xiàn)性電力系統(tǒng)經(jīng)濟(jì)負(fù)荷分配問(wèn)題、BP（back propagation）神經(jīng)網(wǎng)絡(luò)短時(shí)交通流預(yù)測(cè)和障礙環(huán)境下機(jī)器人的路徑規(guī)劃問(wèn)題。

管廊巡檢機(jī)器人在特殊管隧環(huán)境下工作，國(guó)內(nèi)外的研究文獻(xiàn)中對(duì)于管廊的巡檢調(diào)度問(wèn)題探究較少，但對(duì)于礦山、車(chē)間及物流等機(jī)器人調(diào)度問(wèn)題的研究常見(jiàn)諸文獻(xiàn)。文獻(xiàn)[8]提出引入多智能體技術(shù)（Multi-Agent），運(yùn)用GA-ANFIS（遺傳算法-自適應(yīng)模糊神經(jīng)系統(tǒng)）算法并采用黑板通信模式建立智能化的露天礦山生產(chǎn)調(diào)度系統(tǒng)。文獻(xiàn)[9]利用禁忌搜索算法來(lái)規(guī)劃并解決有限等待制造單元的雙小車(chē)調(diào)度線(xiàn)路最優(yōu)解問(wèn)題。魏文義等人提出的三段運(yùn)行方式行車(chē)調(diào)度方案可提升車(chē)輛的運(yùn)輸效率、減小車(chē)輛的候車(chē)概率[10]。本文針對(duì)管廊運(yùn)營(yíng)瞬發(fā)量和緩發(fā)量災(zāi)害，提出了一種改進(jìn)的自適應(yīng)權(quán)重粒子群-遺傳混合優(yōu)化算法，以提高管廊內(nèi)管線(xiàn)泄漏源檢測(cè)的實(shí)時(shí)性。

1 機(jī)器人調(diào)度的數(shù)學(xué)模型

在對(duì)管廊巡檢技術(shù)設(shè)計(jì)時(shí)，管廊各巡檢區(qū)域?qū)⒂刹煌臋C(jī)器人不間斷地往復(fù)巡檢，預(yù)計(jì)每10 km管廊采用30個(gè)機(jī)器人以1～3 m/s速度巡檢。正常工作時(shí)，巡檢機(jī)器人在自己的區(qū)域以一定速度往復(fù)巡檢；當(dāng)管廊內(nèi)部發(fā)生燃?xì)庑孤┗蚧馂?zāi)等情況、需要機(jī)器人定點(diǎn)監(jiān)測(cè)或機(jī)器人損壞時(shí)，當(dāng)前機(jī)器人停在原地不動(dòng)，而該機(jī)器人負(fù)責(zé)的區(qū)域需要由左右兩側(cè)臨近的機(jī)器人來(lái)承擔(dān)，此時(shí)我們對(duì)巡檢機(jī)器人建立調(diào)度模型。

各機(jī)器人之間不可翻越，假設(shè)需要定點(diǎn)監(jiān)測(cè)或損壞的機(jī)器人不發(fā)生在端點(diǎn)處，否則將有一側(cè)成為死區(qū)而無(wú)法被監(jiān)測(cè)。建立機(jī)器人調(diào)度的目標(biāo)函數(shù)，即巡檢一次耗時(shí)最長(zhǎng)的機(jī)器人其巡檢時(shí)間的最小值：

其約束條件如下：

式中：n——巡檢機(jī)器人的數(shù)量，本文中n=30；xi——機(jī)器人i巡檢的區(qū)域長(zhǎng)度；vi——機(jī)器人i的巡檢速度；Ti——機(jī)器人i的調(diào)度時(shí)間；D——發(fā)生災(zāi)害點(diǎn)的機(jī)器人距離巡檢最左端的距離長(zhǎng)度（將機(jī)器人從左到右依次進(jìn)行從小到大的編號(hào)）；k——災(zāi)害點(diǎn)機(jī)器人的標(biāo)號(hào)；ai——機(jī)器人i的加速度；vmax——機(jī)器人運(yùn)行的最大速度；v0——機(jī)器人在巡檢區(qū)域端點(diǎn)處的速度。

約束條件中，式（2）是對(duì)每個(gè)機(jī)器人巡檢區(qū)域長(zhǎng)度的約束；式（3）和式（4）是災(zāi)害點(diǎn)到巡檢總長(zhǎng)度左端點(diǎn)的距離和巡檢總長(zhǎng)度；式（5）是災(zāi)害點(diǎn)處機(jī)器人不分配巡檢區(qū)域；式（6）是機(jī)器人i的加速度，離災(zāi)害點(diǎn)最近的左右兩個(gè)機(jī)器人加速度均為3 m/s2，兩側(cè)機(jī)器人的加速度依次遞減0.1 m/s2；式（7）是重新劃分巡檢區(qū)域時(shí)，機(jī)器人在巡檢區(qū)間里先加速、再勻速、最后減速的過(guò)程由運(yùn)動(dòng)學(xué)公式得到機(jī)器人i巡檢一次所用的時(shí)間，在巡檢區(qū)間端點(diǎn)處的速度均為0，勻速運(yùn)動(dòng)時(shí)速度為3 m/s。

2 適用的調(diào)度算法比較

在管廊巡檢調(diào)度系統(tǒng)中，機(jī)器人通過(guò)本體攜帶的感知單元與RFID路標(biāo)等輔助定位技術(shù)結(jié)合，與上位機(jī)進(jìn)行實(shí)時(shí)信息交流；一旦檢測(cè)到泄漏源，即可精確定位到災(zāi)害點(diǎn)處的位置信息，確定災(zāi)害點(diǎn)處實(shí)時(shí)監(jiān)測(cè)的機(jī)器人的標(biāo)號(hào)，然后重新分配該機(jī)器人左右兩側(cè)的巡檢區(qū)域。管廊巡檢調(diào)度系統(tǒng)對(duì)算法的實(shí)時(shí)性要求較高，適用的算法包括PSO算法與遺傳算法（genetic algorithm，GA）。PSO算法與GA算法在種群多樣性、收斂速度和全局尋優(yōu)能力上有互補(bǔ)性，二者相結(jié)合可提高算法的整體性能。

PSO中每個(gè)粒子代表一個(gè)機(jī)器人在一段區(qū)域內(nèi)的巡檢長(zhǎng)度，算法得到的優(yōu)化極值為巡檢一次巡檢耗時(shí)最長(zhǎng)的機(jī)器人巡檢時(shí)間的最小值。有些學(xué)者提出權(quán)重會(huì)根據(jù)粒子位置的變化而動(dòng)態(tài)改變的觀(guān)點(diǎn)。根據(jù)全局最優(yōu)點(diǎn)的距離調(diào)整算法，對(duì)PSO采用非線(xiàn)性動(dòng)態(tài)慣性權(quán)重系數(shù)，使得算法能夠自適應(yīng)更新權(quán)值，慣性權(quán)重隨粒子目標(biāo)函數(shù)值的改變而改變，而慣性權(quán)重的改變有利于增加粒子的尋優(yōu)能力。慣性權(quán)重ω的表達(dá)式如下：

式中：f——粒子實(shí)時(shí)的目標(biāo)函數(shù)值；favg——當(dāng)前所有粒子平均值；fmin——當(dāng)前所有粒子最小目標(biāo)函數(shù)值[11]。

GA算法先初始化一個(gè)種群，按照生物進(jìn)化的原理根據(jù)適應(yīng)度大小挑選出好的個(gè)體，然后通過(guò)交叉、變異操作得到代表新的解集的種群。PSO算法和GA算法相同點(diǎn)為：兩者均屬于仿生類(lèi)全局優(yōu)化算法，在解空間內(nèi)隨機(jī)產(chǎn)生初始種群，然后在全局解空間適應(yīng)性好的部分集中搜索，但是在解決高維問(wèn)題時(shí)易陷入局部最優(yōu)。不同之處在于：PSO算法的粒子均保存自己歷史最優(yōu)解信息，且粒子按照位置和速度更新公式來(lái)更新自己，具有一定方向；而GA算法會(huì)隨著種群的破壞而丟失以前的信息，交叉和變異操作都是隨機(jī)操作，沒(méi)有確定的方向。

3 改進(jìn)的調(diào)度算法

采用GA算法可有效地求解優(yōu)化問(wèn)題，但不論是交叉還是變異操作，都缺乏明確的導(dǎo)向性，因此其對(duì)空間最優(yōu)解的逼近能力不強(qiáng)。PSO算法的速度與位置更新公式讓粒子有很強(qiáng)的導(dǎo)向性，空間尋優(yōu)能力很強(qiáng)，但容易陷入局部最優(yōu)[12]。結(jié)合GA算法的極強(qiáng)探索精度和求變功能、在解空間全局尋優(yōu)的優(yōu)勢(shì)[13]和PSO中粒子的強(qiáng)導(dǎo)向性，本文提出一種自適應(yīng)權(quán)重的PSO算法（adaptive weight particle swarm optimization, AWPSO）和GA算法相結(jié)合的混合算法（AWPSO-GA算法）。

首先隨機(jī)初始化粒子群以及粒子的初始位置和速度，計(jì)算每個(gè)粒子的適應(yīng)度值。接著粒子進(jìn)行AWPSO算法流程，以單次飛行得到的個(gè)體極值的1.5倍為半徑，作為GA初始種群的取值范圍；再通過(guò)GA的交叉、變異操作，得到經(jīng)過(guò)2次篩選、擁有遺傳算法最優(yōu)解的粒子。最后用GA得到的最優(yōu)解替換AWPSO算法中適應(yīng)度最低個(gè)體，這樣在一次大的迭代中可以得到具有飛行方向和遺傳算法優(yōu)點(diǎn)的適應(yīng)度較高的個(gè)體，以此來(lái)增加算法尋優(yōu)效率并避免某一個(gè)算法的局限性。

本文所提的AWPSO-GA算法具體步驟如下：

（1）初始化粒子種群。群體規(guī)模為N，粒子的取值范圍[-xmax,xmax]，粒子的速度范圍[-vmax,vmax]，最大權(quán)重為ωmax，最小權(quán)重為ωmin，最大迭代次數(shù)I，交叉概率Pc，變異概率Pm。

（2）計(jì)算各粒子適應(yīng)度值。

（3）根據(jù)速度和位置公式更新粒子的速度和位置。

（4）根據(jù)式（8）更新慣性權(quán)重。

（5）用粒子適應(yīng)度值和個(gè)體極值比較，將適應(yīng)度值更好的更新為當(dāng)前最好位置。用粒子的適應(yīng)度值和全局極值比較，將適應(yīng)度值更好的更新為全局最好位置。

（6）將PSO算法得到的個(gè)體作為GA的初始種群，對(duì)其進(jìn)行交叉、變異操作。

（7）判斷是否滿(mǎn)足終止條件（最大迭代次數(shù)）。如果否，將得到的新粒子種群返回到步驟（2）；如果是，則輸出最優(yōu)解。

4 仿真分析

假設(shè)災(zāi)害點(diǎn)位置在7.50 km處，即在第23個(gè)巡檢機(jī)器人監(jiān)控區(qū)域監(jiān)測(cè)到的災(zāi)害點(diǎn)，對(duì)其左右兩側(cè)機(jī)器人巡檢區(qū)域進(jìn)行異常動(dòng)態(tài)分配。利用PSO，AWPSO及本文所提的AWPSO-GA算法分別進(jìn)行仿真實(shí)驗(yàn)，得到重新劃分的區(qū)間長(zhǎng)度和機(jī)器人巡檢一次耗時(shí)最長(zhǎng)機(jī)器人巡檢時(shí)間的最小值。各算法的參數(shù)設(shè)置分別如表1～表3所示，其中c1和c2為加速度常數(shù)。

表1 PSO的參數(shù)設(shè)置Tab.1 Parameter settings of PSO

表2 AWPSO的參數(shù)設(shè)置Tab.2 Parameter settings of AWPSO

表3 AWPSO-GA的參數(shù)設(shè)置Tab.3 Parameter settings of AWPSO-GA

對(duì)上述3種算法分別進(jìn)行了25次仿真實(shí)驗(yàn)，得到以迭代次數(shù)為橫坐標(biāo)、函數(shù)適應(yīng)值為縱坐標(biāo)的尋優(yōu)結(jié)果圖，并用表4記錄了求解巡檢一次最短時(shí)間的結(jié)果。

表4 3種算法結(jié)果比較Tab. 4 Results comparison of the three algorithms

圖1示出PSO, AWPSO和AWPSO-GA算法尋優(yōu)結(jié)果。可以發(fā)現(xiàn)，PSO, AWPSO和AWPSO-GA算法分別在迭代57次、49次和22次后達(dá)到最優(yōu)，其中AWPSO-GA算法迭代次數(shù)最少；3種算法最優(yōu)解分別為tmin=149.110 8 s，tmin=143.073 7 s，tmin=141.147 8 s。圖2示出采用AWPSO-GA算法所求得的最優(yōu)時(shí)間對(duì)應(yīng)的小車(chē)重新分配的巡檢區(qū)間長(zhǎng)度。

圖1 3種算法尋優(yōu)結(jié)果Fig. 1 Optimization results of the three algorithms

圖2 機(jī)器人重分配巡檢區(qū)域的長(zhǎng)度Fig. 2 Length of the inspection area distributed by robot

通過(guò)對(duì)比尋優(yōu)結(jié)果圖的3條曲線(xiàn)可以看出：AWPSO的收斂速度稍高于PSO的，得到的巡檢最小時(shí)間也相比PSO的短；相比AWPSO和PSO，AWPSOGA收斂速度更快，巡檢調(diào)度所用的最小時(shí)間更短。這說(shuō)明改進(jìn)的混合算法對(duì)求解最小化管廊巡檢機(jī)器人耗時(shí)最長(zhǎng)的巡檢時(shí)間問(wèn)題更有效。

5 結(jié)語(yǔ)

本文以城市地下管廊巡檢的機(jī)器人調(diào)度耗時(shí)最長(zhǎng)的時(shí)間最小化為目標(biāo)函數(shù)，采用PSO，AWPSO和AWPSO-GA算法分別對(duì)模型進(jìn)行了優(yōu)化求解。仿真結(jié)果表明，本文提出的AWPSO-GA算法尋優(yōu)效果更好、迭代次數(shù)少，滿(mǎn)足巡檢調(diào)度實(shí)時(shí)性的要求。目前，國(guó)內(nèi)外云機(jī)器人在地下綜合管廊中的應(yīng)用研究尚處空白，本文所建立的調(diào)度模型立足于實(shí)踐、可行性強(qiáng)，其研究工作對(duì)地下管廊的運(yùn)營(yíng)和維護(hù)有著重要的意義。對(duì)于管廊巡檢中存在的各種非線(xiàn)性因素，如機(jī)器人定位精度、傳感器靈敏度和誤報(bào)率等，會(huì)對(duì)系統(tǒng)的運(yùn)維帶來(lái)擾動(dòng)，本文后續(xù)將開(kāi)展更多的研究工作。