一種基于云機器人的綜合管廊智能巡檢調度算法

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

（長安大學，陜西 西安 710064）

0 引言

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

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

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

1 機器人調度的數學模型

在對管廊巡檢技術設計時，管廊各巡檢區(qū)域將由不同的機器人不間斷地往復巡檢，預計每10 km管廊采用30個機器人以1～3 m/s速度巡檢。正常工作時，巡檢機器人在自己的區(qū)域以一定速度往復巡檢；當管廊內部發(fā)生燃氣泄漏或火災等情況、需要機器人定點監(jiān)測或機器人損壞時，當前機器人停在原地不動，而該機器人負責的區(qū)域需要由左右兩側臨近的機器人來承擔，此時我們對巡檢機器人建立調度模型。

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

其約束條件如下：

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

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

2 適用的調度算法比較

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

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

式中：f——粒子實時的目標函數值；favg——當前所有粒子平均值；fmin——當前所有粒子最小目標函數值[11]。

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

3 改進的調度算法

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

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

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

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

（2）計算各粒子適應度值。

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

（4）根據式（8）更新慣性權重。

（5）用粒子適應度值和個體極值比較，將適應度值更好的更新為當前最好位置。用粒子的適應度值和全局極值比較，將適應度值更好的更新為全局最好位置。

（6）將PSO算法得到的個體作為GA的初始種群，對其進行交叉、變異操作。

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

4 仿真分析

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

表1 PSO的參數設置Tab.1 Parameter settings of PSO

表2 AWPSO的參數設置Tab.2 Parameter settings of AWPSO

表3 AWPSO-GA的參數設置Tab.3 Parameter settings of AWPSO-GA

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

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

圖1示出PSO, AWPSO和AWPSO-GA算法尋優(yōu)結果?？梢园l(fā)現，PSO, AWPSO和AWPSO-GA算法分別在迭代57次、49次和22次后達到最優(yōu)，其中AWPSO-GA算法迭代次數最少；3種算法最優(yōu)解分別為tmin=149.110 8 s，tmin=143.073 7 s，tmin=141.147 8 s。圖2示出采用AWPSO-GA算法所求得的最優(yōu)時間對應的小車重新分配的巡檢區(qū)間長度。

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

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

通過對比尋優(yōu)結果圖的3條曲線可以看出：AWPSO的收斂速度稍高于PSO的，得到的巡檢最小時間也相比PSO的短；相比AWPSO和PSO，AWPSOGA收斂速度更快，巡檢調度所用的最小時間更短。這說明改進的混合算法對求解最小化管廊巡檢機器人耗時最長的巡檢時間問題更有效。

5 結語

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