基于異構(gòu)無人系統(tǒng)的水渠網(wǎng)絡(luò)自主巡檢路徑規(guī)劃

陳 洋 李 贏 華鐵丹 邱 權(quán)

(1.武漢科技大學(xué)冶金自動化與檢測技術(shù)教育部工程研究中心, 武漢 430081;2.武漢科技大學(xué)機(jī)器人與智能系統(tǒng)研究院, 武漢 430081;3.北京石油化工學(xué)院人工智能研究院, 北京 102617)

0 引言

引水渠是水利工程中的重要渠道構(gòu)筑物,大型的水利工程建設(shè)周期長,工況復(fù)雜,為了保障施工安全,保證引水渠能正常運作,需要展開定期或者不定期的巡檢工作。傳統(tǒng)的水渠檢測需要技術(shù)人員沿著水渠行走,并手動測量和標(biāo)記受損區(qū)域,其工作量大、效率低。因此,引入無人機(jī)和無人車異構(gòu)系統(tǒng)代替人工檢測,可以提高水渠檢測的效率,也可以為防汛應(yīng)急搶險、河道岸線違法等水利行業(yè)監(jiān)管監(jiān)察提供強(qiáng)有力的技術(shù)支撐。

目前,無人機(jī)和無人車組成的無人系統(tǒng)在諸多領(lǐng)域有著廣泛的應(yīng)用,如包裹投遞[1]、自動駕駛[2]、軍事行動[3]、火災(zāi)探測[4]等。無人機(jī)有著視野大、飛行速度快的優(yōu)勢,可以到達(dá)其它設(shè)備難以到達(dá)的區(qū)域,不足之處是載荷量小、續(xù)航時間有限,而無人車載荷量大、續(xù)航能力強(qiáng)的特點正好彌補(bǔ)了無人機(jī)的短板,二者結(jié)合構(gòu)成的異構(gòu)無人系統(tǒng)擁有廣闊的應(yīng)用前景。

有關(guān)無人機(jī)和無人車協(xié)作的兩級路由問題,最先起源于MURRAY等[5]在2015年提出的飛行輔助旅行商問題(Flying sidekick traveling salesman problem, FSTSP),該問題由一輛無人車和一架無人機(jī)組成異構(gòu)系統(tǒng),無人機(jī)在最大飛行距離限制下,每次飛行只能運送一個包裹,不訪問目標(biāo)節(jié)點的時候,無人機(jī)會被卡車運到下一個地點。為了使無人機(jī)工作效率更高,LUO等[6]和LIU等[7]在FSTSP模型上進(jìn)行了改進(jìn),使無人機(jī)一次能訪問多個目標(biāo)點,并把改進(jìn)后的模型應(yīng)用于偵察任務(wù)中。WU等[8]在允許無人機(jī)一次訪問多個目標(biāo)點的基礎(chǔ)上優(yōu)化了目標(biāo)點的訪問順序。

另一類改進(jìn)著重考慮了地面道路的情況,對無人車進(jìn)行約束。BOOTH等[9]考慮了不同速度限制的路段,從道路網(wǎng)絡(luò)的地圖開始,將道路網(wǎng)絡(luò)按單元網(wǎng)格的方式進(jìn)行離散化,并生成最終的路由圖,該路由圖允許無人機(jī)通過與無人車的匯合重新充電。HAM等[10]先固定無人車的路徑后,再為無人機(jī)規(guī)劃飛行路徑。CHEN等[11]考慮了地面路網(wǎng)約束的同時允許無人機(jī)一次訪問多個目標(biāo)點,并且考慮無人車和無人機(jī)的匯合問題。

異構(gòu)機(jī)器人的路徑規(guī)劃可以分為局部路徑規(guī)劃和全局路徑規(guī)劃。局部路徑規(guī)劃是機(jī)器人之間實時位置信息共享,根據(jù)新環(huán)境規(guī)劃出躲避障礙物的路徑的方法。局部路徑規(guī)劃方法中有虛擬力場算法[12]、人工勢場法[13]、動態(tài)窗口法[14]等。而全局路徑規(guī)劃是在已知完整地圖環(huán)境的情況下規(guī)劃一條已知起點和終點的最優(yōu)路徑,常見的算法包括Dijkstra算法[15]、蟻群算法[16]、遺傳算法[17]等。全局算法會因為地圖過大導(dǎo)致搜索時間過長。

目前,在農(nóng)業(yè)領(lǐng)域中已經(jīng)應(yīng)用啟發(fā)式算法解決許多實際問題。VAHDANJOO等[18]采用模擬退火的元啟發(fā)式算法,解決了在田間放置農(nóng)作物捆堆的最佳位置和每個位置放置捆堆的最優(yōu)數(shù)量的問題。在非結(jié)構(gòu)化的果園環(huán)境中,LIN等[19]利用基于深度強(qiáng)化學(xué)習(xí)的快速魯棒無碰撞路徑規(guī)劃方法預(yù)測無障礙路徑。郝琨等[20]提出基于改進(jìn)避障策略和雙優(yōu)化蟻群算法(Double optimization ant colony algorithm,DOACO)的路徑規(guī)劃方法。

采用無人機(jī)對水渠進(jìn)行巡檢具有視野開闊、響應(yīng)迅速、巡檢周期短等優(yōu)點。其飛行高度可根據(jù)現(xiàn)場要求進(jìn)行設(shè)置,水渠的圖像信息通過機(jī)載攝像機(jī)采集后實時傳輸至地面工作站,然后借助用戶端人機(jī)界面軟件實現(xiàn)多種多樣的巡檢功能,例如,發(fā)現(xiàn)水渠阻塞和構(gòu)筑體破損、分析水面藻類生長情況等。在針對水渠巡檢的研究中,DENG等[21]采用多無人機(jī)多無人車的系統(tǒng)分別完成水渠巡檢工作,但該研究沒有考慮無人機(jī)的重復(fù)巡檢路徑問題。ABBAS等[22]采用深度卷積神經(jīng)網(wǎng)絡(luò)實時規(guī)劃無人機(jī)的巡檢路徑,但沒有考慮無人機(jī)的能耗約束,且整個系統(tǒng)魯棒性不高。針對湖泊巡檢問題,YANES等[23]考慮了多個地面車輛之間的任務(wù)分配問題,并且每臺車輛的巡檢路徑都是一條閉合回路,該研究把巡檢區(qū)域離散成目標(biāo)點,對各個目標(biāo)點的重要性進(jìn)行約束,但由于無人車的速度相對較小,這種僅由無人車組成的同構(gòu)系統(tǒng)相比無人機(jī)和無人車組成的異構(gòu)系統(tǒng)在執(zhí)行巡檢任務(wù)時效率更低。

以上研究都是從無人機(jī)或無人車訪問目標(biāo)點的角度考慮路徑規(guī)劃問題,而本文在已知全局地圖環(huán)境的情況下,從訪問目標(biāo)邊的角度解析水渠巡檢中無人系統(tǒng)路徑規(guī)劃問題,可以避免因無人機(jī)的起降過程而忽略需要檢測的邊。由于受水渠網(wǎng)絡(luò)和地面網(wǎng)路雙重約束的影響,求解無人車和無人機(jī)的路徑問題變得異常困難,針對此問題,首先考慮水渠網(wǎng)絡(luò)約束,建立帶度約束的邊分割模型,將水渠網(wǎng)絡(luò)劃分為若干個子區(qū)域,得到無人機(jī)在水渠網(wǎng)絡(luò)上的最優(yōu)巡檢區(qū)域。然后,結(jié)合地面路網(wǎng)約束,建立以巡檢任務(wù)完成時間最小為目標(biāo)函數(shù)的路徑規(guī)劃模型,最后用遺傳算法求解無人系統(tǒng)整體的最優(yōu)路徑。

1 水渠巡檢路徑規(guī)劃模型

1.1 問題描述

水渠檢測任務(wù)由一架無人機(jī)和一輛無人車組成的無人系統(tǒng)完成。假設(shè)無人機(jī)在水渠網(wǎng)絡(luò)正上方飛行執(zhí)行巡檢任務(wù),一次能夠持續(xù)飛行的最大距離為L,飛行速度恒定為va。假設(shè)無人車的能量足夠多,以恒定速度vg在地面道路網(wǎng)絡(luò)上行駛。由于無人機(jī)的續(xù)航能力有限,每完成一個子區(qū)域的巡檢任務(wù)后,無人機(jī)便需要返回與無人車匯合,并進(jìn)行補(bǔ)能操作(充電或更換電池)。所有目標(biāo)子區(qū)域檢測完成后,無人機(jī)和無人車一起回到終點。本文圍繞路網(wǎng)中無人系統(tǒng)的路徑規(guī)劃問題,主要研究以下兩個方面:①在已知水渠網(wǎng)絡(luò),以及無人機(jī)一次持續(xù)飛行的最大距離的前提下,將地圖離散化后,建立帶度約束的邊分割模型,求解該模型后,得到無人機(jī)單次飛行巡檢的子區(qū)域。②結(jié)合地面網(wǎng)絡(luò)、無人機(jī)和地面車匯合時間和無人機(jī)的能耗等約束,建立無人系統(tǒng)路徑規(guī)劃模型,并使用遺傳算法求解得到最優(yōu)的整體路徑。

1.2 拓?fù)涞貓D

為了方便描述,將圖1a所示的武漢市某地區(qū)部分水渠和道路地圖轉(zhuǎn)為如圖1b所示的無向拓?fù)鋱D,其中,水渠網(wǎng)絡(luò)用G=(V,E)表示,V為水渠離散化后節(jié)點的集合,節(jié)點個數(shù)為M。DM×M為頂點的度矩陣(頂點的度表示每個節(jié)點和它相連邊的個數(shù))。E為水渠路網(wǎng)上邊集合。水渠的邊被離散化為權(quán)重已知的均勻線段e∈E,邊的條數(shù)用e0表示,LE為水渠圖中所有邊的總長。

圖1 某地區(qū)水渠網(wǎng)絡(luò)和道路網(wǎng)絡(luò)

道路網(wǎng)絡(luò)為G′=(V′,E′),其中V′為地面路網(wǎng)上節(jié)點的集合,節(jié)點個數(shù)為N,E′為道路網(wǎng)絡(luò)上的邊,與水渠的邊類似,也被離散化為各個均等且權(quán)重已知的線段。

1.3 研究思路

本文先將待巡檢的水渠網(wǎng)絡(luò)劃分為若干子圖,再確定各個子圖的最優(yōu)訪問順序,以及無人機(jī)的運動路徑。研究框圖如圖2所示。對這2個部分分別建立優(yōu)化模型并分別求解,使得無人機(jī)在巡檢每個子圖時都是連續(xù)進(jìn)行不需要補(bǔ)能,并且使完成巡檢任務(wù)的總時間達(dá)到最短。

圖2 研究框圖

1.4 水渠網(wǎng)絡(luò)分割

定義邏輯矩陣W∈RS×e0,其中W=[wse],wse∈{0,1}為邏輯矩陣W中的元素,表示水渠網(wǎng)絡(luò)中的邊e∈E是否在子圖s中,wse=0表示邊e不在子圖s中,wse=1表示邊e存在子圖s中。定義常量de表示邊e的實際長度;常量Lmin、Lmax為子圖區(qū)域長度的上下界。在水渠網(wǎng)絡(luò)G中,每條邊都要被分配到相應(yīng)的子圖,且每條邊有且只能被分配一次,由此建立約束1

(1)

由于無人機(jī)有能耗限制,每個子圖的大小應(yīng)該滿足無人機(jī)最大續(xù)航距離限制,由此建立約束2

(2)

式中k——調(diào)節(jié)參數(shù),0

約束式(2)中,k為調(diào)節(jié)參數(shù),表示預(yù)留無人機(jī)起降能耗,其值可根據(jù)實際地圖大小和無人機(jī)一次飛行最大距離調(diào)節(jié)。

定義邏輯矩陣X∈RS×N,其中X=[xsi],二值變量xsi∈{0,1}為邏輯矩陣X中的元素,表示水渠網(wǎng)絡(luò)中的節(jié)點i∈V是否在子圖s中,xsi=0表示節(jié)點i不在子圖s中,xsi=1表示節(jié)點i存在于子圖s中[21]。建立約束3和約束4保證邊與邊之間的連通性

(3)

xsi+xsj-2wse[i,j]≥0

(4)

式中wse表示邊和節(jié)點關(guān)系的表達(dá)形式,下標(biāo)e[i,j]表示如果選擇邊e,則i和j為邊e的兩個端點。

考慮到實際水渠路網(wǎng)中節(jié)點的度一般小于等于4(水渠分叉口一般為十字口或人字口),為了減少無人機(jī)重復(fù)飛行路徑,即對度大于2的節(jié)點進(jìn)行約束

(5)

式中deg(i′)表示求取節(jié)點i′的度的函數(shù)。約束式(5)保證度大于2且小于等于4的節(jié)點至少被劃分到2個子圖中,以此保證每個子圖為直線段或由直線段組成的折線段。

為了使每個子圖的大小均衡,構(gòu)造優(yōu)化問題

(6)

1.5 路徑規(guī)劃建模

通過求解優(yōu)化問題式(6),可以獲得水渠網(wǎng)絡(luò)的每個子圖實際長度矩陣,假設(shè)為T=[T1,T2,…,TS]。假設(shè)各個子圖端點坐標(biāo)集合(訪問順序)矩陣為H∈RS×4,其中每一行都儲存著兩個端點的坐標(biāo)。由于無人機(jī)在各個子圖上飛行檢測時不進(jìn)行補(bǔ)能操作,但每個子圖訪問完后,無人車需要在地面路網(wǎng)上選擇最優(yōu)的地點與其匯合。根據(jù)飛行安全要求,要使無人機(jī)和無人車同時到達(dá)匯合點,或者無人車比無人機(jī)先到達(dá)匯合點。接下來,對無人機(jī)訪問子圖順序進(jìn)行優(yōu)化,優(yōu)化的目標(biāo)是使無人車和無人機(jī)完成檢測任務(wù)的總時間最小。

針對上述異構(gòu)機(jī)器人巡檢路徑規(guī)劃問題提出以下假設(shè):①忽略無人機(jī)垂直起降高度,假設(shè)無人機(jī)和無人車均在二維平面上移動。②假設(shè)無人車的能量無限多,并且隨時可為無人機(jī)補(bǔ)充能量。③忽略無人機(jī)補(bǔ)能時間消耗。

(1)子圖訪問順序建模

(7)

(8)

(9)

其中Oij=1表示原來的子圖i被調(diào)整為第j個訪問。約束式(8)表示每個子圖僅被訪問一次,約束式(9)表示優(yōu)化后的子圖訪問順序中,每個子圖仍只被訪問一次。

(2)子圖內(nèi)巡檢路徑訪問方向建模

(3)無人機(jī)起降點選擇及無人機(jī)起降過程建模

無人機(jī)每巡檢完一個子圖區(qū)域,都需要在路網(wǎng)的降落點與無人車匯合,進(jìn)行充電或者更換電池。選擇合適的無人機(jī)起降點是無人機(jī)實現(xiàn)安全起降的前提。找到了最佳起降點也就同時確定了無人機(jī)的起降過程。假設(shè)道路網(wǎng)絡(luò)離散后的坐標(biāo)矩陣為Z∈RN×2,1～N代表每個坐標(biāo)的編號。定義無人機(jī)起飛點邏輯矩陣α∈RS×N和無人機(jī)著陸邏輯矩陣β∈RS×N[11],αsi=1表示無人機(jī)選擇路網(wǎng)節(jié)點i飛往子圖s,βsj=1表示無人機(jī)完成子圖s的檢測任務(wù)后前往路網(wǎng)端點j。需滿足約束

(10)

(11)

(s=1,2,…,S;γs∈{0,1})

(12)

(s=1,2,…,S;γs∈{0,1})

(13)

式中αsi——矩陣α的元素

βsj——矩陣β的元素

Zq——道路網(wǎng)路第q行坐標(biāo)

Zv——道路網(wǎng)路第v行坐標(biāo)

Fs——第s個子圖中的方向

Ts——第s個子圖的長度

Osj——矩陣O的元素,表示第s個子圖的訪問順序為j

αsq——第s個子圖原本的訪問順序

αsq——矩陣α的元素,表示第s個子圖中起飛點為q的元素

βsv——矩陣β的元素,表示第s個子圖中降落點為v的元素

約束式(10)表示每個子圖有且僅有一個起飛點。約束式(11)表示每個子圖有且僅有一個降落點。約束式(12)表示無人機(jī)起降過程經(jīng)過的距離和巡檢該子圖的總距離不能超過無人機(jī)一次飛行的最大距離,其中OsjTs表示第s個子圖的總長度,Fs表示無人機(jī)的巡檢方向。約束式(13)表示無人車比無人機(jī)先到達(dá)或同時到達(dá)匯合點,不等式(13)的左邊表示無人機(jī)到達(dá)匯合點的時間,右邊表示無人車到達(dá)匯合點的時間。Zj表示地面路網(wǎng)坐標(biāo)矩陣中的第j行,即具體坐標(biāo)值。

確定無人機(jī)的起降點和子圖的訪問順序后,通過Floyd算法計算出無人車在每兩個節(jié)點間行駛的最短路徑,即可得到無人車路徑。

完成整個巡檢任務(wù)的時間包括兩部分:無人機(jī)巡檢各子圖區(qū)域的飛行時間、無人機(jī)由無人車運載一起運動的時間。其中,無人機(jī)總飛行距離為

(s=1,2,…,S;γs∈{0,1})

(14)

式中fa——無人機(jī)總飛行距離,km

定義基地坐標(biāo)為B∈R1×2,無人車運載無人機(jī)的總移動距離為

(s=1,2,…,S;γs∈{0,1})

(15)

式中fg——無人車運載無人機(jī)距離,km

根據(jù)以上分析,以完成整個巡檢任務(wù)的總時間為代價,該路徑規(guī)劃問題可以轉(zhuǎn)換為

(16)

2 基于遺傳算法的兩步求解方法

本文采用兩步法求解該路徑規(guī)劃問題,算法流程如圖3所示。①將無人機(jī)待檢測區(qū)域進(jìn)行劃分,得到各個子圖的長度即無人機(jī)的飛行長度集合T,以及各個子圖的端點集合H。無人機(jī)對各子圖巡檢時,除了飛行方向有兩種可能的選擇外,飛行路徑基本確定。②使用改進(jìn)的遺傳算法,優(yōu)化各子圖的巡檢順序、無人機(jī)在路網(wǎng)上的起降位置[25],以及無人機(jī)巡檢各子圖時的飛行方向,使整體完成檢測任務(wù)的時間達(dá)到最小。

圖3 水渠巡檢路徑規(guī)劃算法流程圖

遺傳算法是一類借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)搜索算法。遺傳算法遵循優(yōu)勝劣汰原則,從初始種群出發(fā),經(jīng)過選擇、交叉、變異等遺傳算子迭代操作后,得到優(yōu)化后的種群,從而得到滿足目標(biāo)的最優(yōu)個體。

2.1 編碼

編碼是遺傳算法中的關(guān)鍵問題之一。本文設(shè)計的編碼方式如圖4所示,分別對無人機(jī)起飛點、無人機(jī)降落點、無人機(jī)訪問子圖端點的順序、子圖訪問方向進(jìn)行4位編碼。

圖4 編碼

圖4第1行為子圖編號,編號為1,2,…,S。第2行為子圖端點坐標(biāo)的編號,每子圖對應(yīng)2個端點,由之前模型(6)求解得到。第3行為無人機(jī)在道路網(wǎng)絡(luò)上選擇的起飛點坐標(biāo)編號。第4行為無人機(jī)在道路網(wǎng)絡(luò)上選擇的降落點坐標(biāo)編號。第5行為各子圖的訪問順序的排列。第6行為無人機(jī)訪問各個子圖時的訪問方向的選擇。要求得無人機(jī)和無人車的最優(yōu)訪問路線,即求第3～6行中每個元素的值。

2.2 適應(yīng)度函數(shù)

利用約束的違反量構(gòu)造懲罰函數(shù)設(shè)計適應(yīng)度函數(shù)[23]。懲罰函數(shù)式為

(s=1,2,…,S;γs∈{0,1})

(17)

(s=1,2,…,S;γs∈{0,1})

(18)

式中p1——無人機(jī)能耗懲罰函數(shù)

p2——無人系統(tǒng)協(xié)同懲罰函數(shù)

式(17)表示若無人機(jī)訪問子圖完整過程時的時間大于無人機(jī)一次飛行最大距離允許的時間,則給予懲罰;式(18)表示若無人機(jī)比無人車提前到達(dá)匯合點,則給予懲罰。

為了減少無人車在巡檢過程中的重復(fù)路徑,假設(shè)無人車重復(fù)路徑長度為lg,懲罰系數(shù)為λ3,則新個體引入違反量后總代價為

(19)

式中fn——違反量總代價

lg——無人車重復(fù)路徑長度,km

λ1、λ2、λ3——違反量懲罰系數(shù)

懲罰系數(shù)越大,違反量可以被越快地消除,但是函數(shù)可能過快收斂到局部最優(yōu)值,由于fn的值越小越接近最優(yōu)解,因此適應(yīng)度函數(shù)設(shè)置為ft=1/fn。

2.3 選擇算子

采用輪盤賭法對每次生成的種群中的個體進(jìn)行選擇,參與下一輪的迭代。適應(yīng)度越大的個體被選擇的概率越大,第i個個體被選擇的概率為

(20)

式中p(i)——第i個個體被選擇概率

ft(i)——個體適應(yīng)度

K——種群規(guī)模

2.4 交叉算子

采用單點交叉法對染色體中代表各子圖訪問順序的S個基因片段進(jìn)行交叉,即對子圖訪問順序進(jìn)行隨機(jī)變換,交叉算子操作方法如圖5所示。每組染色體片段表示一個子圖的信息,其中第3位基因代表當(dāng)前子圖的訪問順序。采取單點交叉方法對子圖的訪問順序進(jìn)行交換,從而增加種群中得到最優(yōu)子圖訪問順序個體的概率。

圖5 兩條染色體交叉示例

2.5 自適應(yīng)變異算子

無人機(jī)在靠近水渠子圖端點的路網(wǎng)上選擇合適的位置作為起降點。本文通過染色體變異的方式,對起降點進(jìn)行隨機(jī)選擇。起降點的選擇范圍需考慮無人機(jī)的最大允許能耗,通過式(12)、(13)對無人機(jī)起飛點和降落點的選擇范圍進(jìn)行約束。在這兩組范圍內(nèi),分別對染色體的前兩位基因進(jìn)行變異,變異方式如圖6a所示。采取這種方式對無人機(jī)的起降點選擇范圍增加限制,保證變異后的染色體仍滿足約束。

圖6 單條染色體變異示例

此外,在染色體的第4位基因,即子圖訪問方向,通過變異方式改變子圖的訪問方向,以避免陷入局部最優(yōu),如圖6b所示?；蛑?和1表示無人機(jī)訪問子圖進(jìn)入時相反的兩個方向。

遺傳算法在前期的迭代過程中,通過染色體的變異改善解的搜索空間,防止陷入局部最優(yōu),增加了優(yōu)良個體產(chǎn)生的可能性。而在迭代過程后期,種群的整體適應(yīng)度趨于穩(wěn)定,此時較高的變異概率會降低算法的收斂速度。為了解決上述問題,本文將變異概率與當(dāng)前迭代次數(shù)結(jié)合,提出一種自適應(yīng)變異算子,使算法在迭代前期采用較大的變異概率,而在迭代后期采用較小的變異概率。變異概率計算式為

(21)

g——當(dāng)前迭代次數(shù)

θ——下降系數(shù)

3 仿真分析與比較

3.1 參數(shù)初始化

為驗證所提出的模型,根據(jù)已知目標(biāo)區(qū)域的水渠和地面地圖,在Matlab 2018b中進(jìn)行仿真,計算機(jī)配置為:AMD Ryzen 5 5600H with Radeon Graphics,3.30 GHz,安裝內(nèi)存為16.0 GB。

離散后的水渠路網(wǎng)G由36個頂點和35條邊組成,總長度為15.87 km;地面路網(wǎng)G′由156個節(jié)點和174條邊組成。仿真時的地面基站編號可根據(jù)實際應(yīng)用中基站的選址位置進(jìn)行調(diào)整。1.4節(jié)的圖分割模型參數(shù)如表1所示。遺傳算法參數(shù)設(shè)置如表2所示,其中Ng為最大迭代次數(shù)、Ps為選擇概率、Pc為交叉概率。

表1 圖分割及路徑規(guī)劃模型參數(shù)

表2 遺傳算法參數(shù)

3.2 水渠網(wǎng)絡(luò)子圖分割結(jié)果

針對優(yōu)化模型(6),使用CVX工具箱[26]對其進(jìn)行求解。圖7為s0=7的圖分割結(jié)果,即水渠網(wǎng)絡(luò)圖被分割成7個長度均勻的子圖,各個子圖間都有重復(fù)分配的節(jié)點,以保證每個子圖的連通,每個子圖的長度如表3所示,均低于無人機(jī)最大飛行距離L。

表3 子圖長度

圖7 分割為7個區(qū)域的水渠網(wǎng)絡(luò)

3.3 無人系統(tǒng)路徑規(guī)劃仿真結(jié)果

根據(jù)基地選址位置不同,無人機(jī)和無人車的路徑規(guī)劃得到的結(jié)果實際可以分為3種:①無人車載著無人機(jī)從基地出發(fā)并且返回。②當(dāng)?shù)?個訪問的區(qū)域離基地近時,無人機(jī)直接從基地出發(fā)訪問第1個子圖,無人車單獨前往2號端點。③當(dāng)無人機(jī)巡檢完最后1個子圖還有多余能量時,無人機(jī)直接返回基地,無人車獨自從14號端點返回基地。以下對這3類仿真結(jié)果進(jìn)行具體分析。

3.3.1無人車載著無人機(jī)從基地出發(fā)與返回(仿真1)

當(dāng)基地編號為128時,求解得到的無人機(jī)路徑圖和無人車路徑如圖8所示。圖8a中不同顏色的實線表示無人機(jī)訪問各個子區(qū)域時的巡檢路徑,不同顏色的虛線部分則對應(yīng)相應(yīng)的子區(qū)域無人機(jī)的起降路徑。圖8b中帶箭頭的線段為無人車在路網(wǎng)上行駛的路徑,不帶箭頭的線段為無人車搭載無人機(jī)從當(dāng)前子圖前往下一個子圖的路徑。

圖8 無人車搭載無人機(jī)出發(fā)和返回路徑

圖8中的序號1～14代表地面路網(wǎng)上訪問起飛降落點的順序,按編號從小到大的順序進(jìn)行訪問,其中,起降點編號的顏色與對應(yīng)子圖顏色相同。如圖8b所示,無人車搭載無人機(jī)從基地出發(fā),沿橘色直線路徑行駛到達(dá)1號起飛點,到達(dá)1號起飛點后,如圖8a所示,無人機(jī)從1號起飛點沿著紫色虛線前往第1個子圖區(qū)域進(jìn)行區(qū)域巡檢,巡檢完后再沿著虛線路徑飛往2號降落點。與此同時,無人車沿著圖8b所示的紫色帶箭頭線段勻速前往2號端點,在2號端點和無人機(jī)匯合。與此相似,無人系統(tǒng)前往第2個巡檢區(qū)域進(jìn)行巡檢,無人車搭載無人機(jī)沿 圖8b所示的橘色直線路徑從2號端點前往3號端點,到達(dá)3號端點后無人機(jī)沿著圖8a紫色路徑對第2個子圖區(qū)域進(jìn)行巡檢,此時無人車沿著圖8b的紫色帶箭頭的路徑前往4號匯合點與無人機(jī)匯合。以此類推,完成7個子區(qū)域的巡檢后,無人車搭載無人機(jī)從14號端點沿著橘色直線路徑回到基站。

在仿真實驗中,加入違反無人機(jī)能量約束懲罰、無人車和無人機(jī)匯合時間約束懲罰,以此確保無人機(jī)的能量能夠完成整個巡檢任務(wù)。同時加入無人車重復(fù)路徑的懲罰,最終獲得的最優(yōu)路徑中僅包括少量重復(fù)的路徑節(jié)點。圖9為遺傳算法執(zhí)行過程中代價函數(shù)fn的迭代曲線,迭代到293代時,算法獲得最優(yōu)解。算法結(jié)束時,無人車行駛路徑總長度為25.33 km,其中包括重復(fù)路徑1.70 km,約占6.7%,運行總時間為48 min。無人機(jī)飛行總時間為26.53 min。

圖9 包含懲罰項的總代價fn

3.3.2無人機(jī)直接從基地出發(fā)(仿真2)

當(dāng)基地編號為154時,此時基地與第1個巡檢區(qū)域較近,無人機(jī)可以直接從基地出發(fā)飛行到第1個巡檢區(qū)域,與3.3.1節(jié)的仿真相比,無人車載著無人機(jī)出發(fā)的路徑不再存在,如圖10所示,當(dāng)無人機(jī)直接從基地起飛前往第1個子圖區(qū)域巡檢時,無人車空載沿著湖藍(lán)色帶箭頭路徑直接行駛到2號端點與無機(jī)匯合。在無人機(jī)巡檢完最后1個子圖后,與無人車在14號端點匯合后,沿著橘色直線從14號端點回到基地,返回時的路徑與仿真1相似。此時無人車行駛路徑總長度為31.68 km,其中包括重復(fù)路徑4.74 km,約占15%,運行總時間為59 min。無人機(jī)飛行總時間為28.51 min。

圖10 無人機(jī)直接從基地出發(fā)時無人車路徑

3.3.3無人機(jī)直接返回基地(仿真3)

當(dāng)基地編號為55時,此時無人機(jī)在巡檢完最后1個子圖區(qū)域后能量充足,可以直接返回基地,與仿真1的區(qū)別在于無人機(jī)訪問最后1個子圖時無人車的路徑,如圖11所示,無人機(jī)巡檢完最后紅色區(qū)域直接返回基地,而無人車直接沿著紅色帶箭頭的路徑回到基地。此時無人車行駛路徑總長度為24.34 km,其中包括重復(fù)路徑1.95 km,約占8%,運行總時間為48 min。無人機(jī)飛行總時間為27.56 min。

圖11 無人機(jī)直接回到基地時無人車的路徑

綜上所述,由于基地的選址位置不同,無人系統(tǒng)路徑規(guī)劃會有3種不同的結(jié)果。仿真實驗表明,在基地選址不同的情況下,本文模型都能在滿足無人機(jī)能耗約束、訪問順序約束、無人機(jī)起降點約束的情況下規(guī)劃出一條較好的巡檢路線。按照人工步行巡檢速度2 km/h計算,在不考慮人員休息和路徑重復(fù)的情況下,完成圖8所示水渠網(wǎng)絡(luò)巡檢至少需要476 min,因此,本文提出的無人系統(tǒng)的巡檢速度是人工巡檢的8.4～9.8倍。以上多組實驗結(jié)果說明本文所提方法具備有效性和通用性,能夠規(guī)劃出不同情形下無人機(jī)、無人車協(xié)作巡檢路徑,保證任務(wù)完成時間最優(yōu)。

4 結(jié)論

(1)對無人系統(tǒng)在水渠巡檢中的實際應(yīng)用進(jìn)行了研究,針對巡檢區(qū)域一般面積大、道路網(wǎng)絡(luò)復(fù)雜、無人機(jī)續(xù)航能力受限等實際情況,提出了一種可行的路徑規(guī)劃方案。

(2)考慮實際水渠網(wǎng)絡(luò)中通常沒有交叉處超過4個分叉口的情況,針對度為1～4的節(jié)點進(jìn)行了約束,建立了圖分割優(yōu)化模型,并用CVX工具箱對該模型進(jìn)行求解,以某水渠巡檢區(qū)域為例,得到了最優(yōu)的7個子圖。

(3)建立了無人系統(tǒng)在雙重網(wǎng)絡(luò)約束下的路徑長度優(yōu)化模型。為符合實際,考慮了無人機(jī)的能量約束、無人車和無人機(jī)匯合時間約束、道路網(wǎng)絡(luò)對無人車運動的約束等,使用遺傳算法對無人車和無人機(jī)路徑進(jìn)行求解。在給出的巡檢案例中,無人車載著無人機(jī)從基地出發(fā)并返回基地的最優(yōu)任務(wù)完成時間為48 min。按人工步行速度2 km/h計算,無人系統(tǒng)的巡檢速度為人工巡檢的8.4～9.8倍。