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

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

0 引言

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

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

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

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

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

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

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

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

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

1.1 問(wèn)題描述

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

1.2 拓?fù)涞貓D

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

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

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

1.3 研究思路

本文先將待巡檢的水渠網(wǎng)絡(luò)劃分為若干子圖,再確定各個(gè)子圖的最優(yōu)訪(fǎng)問(wèn)順序,以及無(wú)人機(jī)的運(yùn)動(dòng)路徑。研究框圖如圖2所示。對(duì)這2個(gè)部分分別建立優(yōu)化模型并分別求解,使得無(wú)人機(jī)在巡檢每個(gè)子圖時(shí)都是連續(xù)進(jìn)行不需要補(bǔ)能,并且使完成巡檢任務(wù)的總時(shí)間達(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的實(shí)際長(zhǎng)度;常量Lmin、Lmax為子圖區(qū)域長(zhǎng)度的上下界。在水渠網(wǎng)絡(luò)G中,每條邊都要被分配到相應(yīng)的子圖,且每條邊有且只能被分配一次,由此建立約束1

(1)

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

(2)

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

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

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

(3)

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

(4)

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

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

(5)

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

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

(6)

1.5 路徑規(guī)劃建模

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

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

(1)子圖訪(fǎng)問(wèn)順序建模

(7)

(8)

(9)

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

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

(3)無(wú)人機(jī)起降點(diǎn)選擇及無(wú)人機(jī)起降過(guò)程建模

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

(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個(gè)子圖中的方向

Ts——第s個(gè)子圖的長(zhǎng)度

Osj——矩陣O的元素,表示第s個(gè)子圖的訪(fǎng)問(wèn)順序?yàn)閖

αsq——第s個(gè)子圖原本的訪(fǎng)問(wèn)順序

αsq——矩陣α的元素,表示第s個(gè)子圖中起飛點(diǎn)為q的元素

βsv——矩陣β的元素,表示第s個(gè)子圖中降落點(diǎn)為v的元素

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

確定無(wú)人機(jī)的起降點(diǎn)和子圖的訪(fǎng)問(wèn)順序后,通過(guò)Floyd算法計(jì)算出無(wú)人車(chē)在每?jī)蓚€(gè)節(jié)點(diǎn)間行駛的最短路徑,即可得到無(wú)人車(chē)路徑。

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

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

(14)

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

定義基地坐標(biāo)為B∈R1×2,無(wú)人車(chē)運(yùn)載無(wú)人機(jī)的總移動(dòng)距離為

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

(15)

式中fg——無(wú)人車(chē)運(yùn)載無(wú)人機(jī)距離,km

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

(16)

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

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

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

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

2.1 編碼

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

圖4 編碼

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

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

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

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

(17)

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

(18)

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

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

式(17)表示若無(wú)人機(jī)訪(fǎng)問(wèn)子圖完整過(guò)程時(shí)的時(shí)間大于無(wú)人機(jī)一次飛行最大距離允許的時(shí)間,則給予懲罰;式(18)表示若無(wú)人機(jī)比無(wú)人車(chē)提前到達(dá)匯合點(diǎn),則給予懲罰。

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

(19)

式中fn——違反量總代價(jià)

lg——無(wú)人車(chē)重復(fù)路徑長(zhǎng)度,km

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

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

2.3 選擇算子

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

(20)

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

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

K——種群規(guī)模

2.4 交叉算子

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

圖5 兩條染色體交叉示例

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

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

圖6 單條染色體變異示例

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

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

(21)

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

θ——下降系數(shù)

3 仿真分析與比較

3.1 參數(shù)初始化

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

離散后的水渠路網(wǎng)G由36個(gè)頂點(diǎn)和35條邊組成,總長(zhǎng)度為15.87 km;地面路網(wǎng)G′由156個(gè)節(jié)點(diǎn)和174條邊組成。仿真時(shí)的地面基站編號(hào)可根據(jù)實(shí)際應(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é)果

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

表3 子圖長(zhǎng)度

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

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

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

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

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

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

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

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

圖9 包含懲罰項(xiàng)的總代價(jià)fn

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

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

圖10 無(wú)人機(jī)直接從基地出發(fā)時(shí)無(wú)人車(chē)路徑

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

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

圖11 無(wú)人機(jī)直接回到基地時(shí)無(wú)人車(chē)的路徑

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

4 結(jié)論

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

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

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