間歇式信息傳輸條件下無人機搜索覆蓋規劃

曹志強, 張 佳, 辛 斌

(北京理工大學自動化學院, 北京 100081)

0 引 言

單無人機從基站出發開始覆蓋環境,并將環境信息實時傳遞回基站。這種通信保持的方式能夠實現高效的信息傳輸,但是基站通信范圍有限。尤其在火災、地震、救援等場景下,通信設施癱瘓,恢復通信將會花費較長時間,或者依賴于較多硬件設施[1],造成基站等的通信范圍大大減少,無人機的運動范圍也會受到較大限制。而在間歇式信息傳輸條件下,無人機在一段時間內不與基站通信,而是覆蓋更多的區域,在經過一定時間后返回基站通信范圍并將信息傳輸回基站,之后繼續返回覆蓋路徑,完成剩余覆蓋任務,重復以上過程直到信息傳輸完畢。這種方法可以擴大無人機的工作范圍,并使無人機的運動不受通信距離的限制,更加靈活地完成任務。

間歇式信息傳輸下多智能體協作的核心問題為智能體通信位置和時刻的選取與任務規劃的耦合問題,多智能體間若長時間不通信,會導致協作效率下降,若頻繁通信則會導致運動自由受限且執行效率下降。

相關學者討論了間歇式規劃下的各種問題,Sabo等[2]在多無人機的PDP(pickup and delivery problem)中使每個無人機到各個位點采集數據,隨后返回基站的通信范圍反饋信息給基站。為了提高數據收集和反饋的效率,其采用了兩階段的啟發式方法,與最優解對比,兩種方法最多相差5%,但是其沒有考慮障礙物等約束。Kantaros等[3-4]利用了線性時序邏輯(linear-time temporal logic, LTL)對多智能體系統通過間歇性通信完成任務的問題,進行了系統性的研究,但是其更加關注任務執行效率,且只確保有關任務上的協商能夠經常進行。而最近Aragues等[5]針對不同速度和通信范圍的智能體巡邏一維度環形圖各個位點問題,以最小化重訪位點時間為目標設計了分布式算法。Scherer等[6]考慮智能體在巡邏過程中將信息通過智能體之間的間歇式通信傳輸到基站,針對傳輸時間有界建立了帶時間窗的最短路徑問題(shortest path problem with time windows, SPPTW)模型。Caraballo等[7]則討論智能體之間信息傳輸時間有界。雖然已有上述一些優秀的成果,但是間歇式信息傳輸下的覆蓋規劃相關文獻依然較少。

全覆蓋路徑規劃常運用的方法是在單元分解后計算各個單元之間的最短覆蓋路徑。經典的單元分解方法,包括Boustrophedon[8-9]、Trapezoidal分解[10]、莫爾斯分解[11]、聚類分解[12]和單側區域分割[13]等。Tung等[14]利用直接法 (direct method, DM)優化單元內的遍歷路徑,利用遺傳算法規劃各個單元間的覆蓋路徑。Cai等[15]采用A*算法求解覆蓋路徑。文獻[16-17]利用螺旋卡殼規劃 (rotating calipers path planner,RCPP)單元內路徑規劃方法和蟻群算法規劃單元間遍歷路徑。王偉等[18]利用自適應升溫的模擬退火算法優化遍歷路徑。而從智能體的模型出發,Yuan等[19]考慮無人機在覆蓋時的能量限制設置了多個加油站。Theresa等[20]考慮了機器人轉彎半徑等約束。

針對通信距離約束下的覆蓋,諸多文獻重點兼顧通信保持與覆蓋規劃,尹洋等[21]利用改進的K-means++算法劃分搜索區域,利用分布式拍賣給每個智能體分配區域。為實現連續通信,多智能體在進行分布式覆蓋探索時可以沿著通信拓撲拉普拉斯矩陣第二小特征值減小的逆梯度方向前進[22-24]。王寧等[25]設計了一種能夠在通信完全有效、局部有效以及完全失效下切換信息交互方法的信息交互與決策機制,在完成覆蓋搜索任務時能夠有效兼顧對運動目標的搜索。Banfi[26]在覆蓋探索中采用經常性通信連接方法,智能體在完成一定區域覆蓋后需要通過多跳通信傳遞信息給基站。相比Banfi,Benavides等[27]考慮了通信保持與覆蓋探索的權衡。Pei等[28]則對通信保持和覆蓋問題進行了分解,將其轉化為集覆蓋問題、Steiner樹問題和線性分配問題求解。

上述文獻較多地討論了間歇式通信下的巡邏問題,主要研究了通信保持與覆蓋的權衡,對間歇式通信下的覆蓋規劃問題討論較少,也沒有討論如何實現間歇式通信與覆蓋規劃之間的權衡。針對上述問題,本文具有以下創新點。

創新點 1針對間歇式通信與覆蓋規劃之間的權衡問題,當需要覆蓋的目標點較為分散且數量較少時,采用層次聚類方法對點集合進行聚類得到無人機每次從基站出發需要覆蓋的路徑點集合,在考慮了障礙物影響的情況下,提出了一種新的聚類距離度量方法。

創新點 2針對全區域覆蓋問題,相對于創新點1需進一步考慮覆蓋路徑的質量,要減少路徑中轉角過大的情況,對此提出一種三階段的智能優化方法。其思想是先利用文獻[17]的覆蓋路徑求解方法最小化覆蓋路徑長度,再優化覆蓋路徑上的返回到基站的位點,實現所有環境位點信息傳回基站的時間之和最小化,在降低問題求解復雜度的同時保證求解質量。

創新點 3在優化覆蓋路徑上的返回到基站的位點時,對目標函數(時間之和)進行分析,確定最優的返回次數搜索范圍,進一步遍歷得到最優往返次數的取值,此后利用整數編碼的遺傳算法優化在覆蓋路徑上的返回位點,實現解空間壓縮后的高效求解。

1 問題建模

間歇式信息傳輸條件指的是:由于無人機在返回到基站的通信范圍內時才能傳遞信息給基站,因此無人機需要往返于待訪問目標點和基站之間,這種運動方式形成了間歇信息傳輸的形式。首先,據此建立間歇式信息傳輸條件下的覆蓋規劃模型。

1.1 地理環境建模

以無人機的感知范圍半徑Rs作為離散化的分度,對待覆蓋區域進行離散化,從而實現對于地理環境的柵格化處理,并利用高程地圖對其進行描述,高程地圖的每個柵格均包含高程信息。

由于環境中時常包含著非結構化的部分,例如不規則的障礙區或禁飛區,另外地理環境對于無人機的運動影響較大,因此需要進一步處理這種非結構化的問題,本文對柵格化后的環境模型進行兩次“過濾”處理。

本文中的無人機為小型無人機,考慮到其飛行能力受限,且從安全角度出發,設置其最大飛行高度為hthreshold。若該柵格內障礙高度大于hthreshold,則該柵格被障礙占據,無法通行。

考慮地理環境在二維平面角度非規則形狀,如圖1所示,采用兩種策略進行處理。

圖1 環境建模方法Fig.1 Methods of environment modeling

圖1為柵格地圖,黃色部分為障礙,如圖1(a)所示。若柵格中心點C位置處于表示障礙的多邊形外,則判定該柵格為自由柵格;否則,如圖1(b)所示,判定其為障礙柵格。

1.2 間歇式信息傳輸下的覆蓋規劃模型

設無人機的平均移動速度大小為v,無人機初始點在基站。以無人機的感知范圍半徑Rs作為離散化的分度,對待覆蓋區域進行離散化,設環境需要覆蓋的位點集合為Tr,Tr={Tr1,Tr2,…,Tre},記作請求點集合,e表示請求點數量,在需要進行區域全覆蓋時,其表示所有自由空間(障礙物之外的空間)的請求點數量。當無人機通過運動返回基站通信范圍時,將位點信息傳回基站。假設Tr1為基站,該問題只返回兩次的問題圖示如圖2所示。

圖2 問題圖示Fig.2 Illustration of the problem

設無人機從基站Tr1出發沿著黑色實線箭頭所示路徑覆蓋區域內的各個點(以藍色五角星表示),從點a沿著藍色虛線路徑返回到基站通信范圍反饋所得信息,點a稱作返回點。之后,無人機從基站沿著紅色虛線路徑運動到點b,此時點b稱作恢復點。無人機繼續覆蓋完所有區域后從返回點c沿著黃色虛線路徑返回基站,完成所有區域覆蓋。按照上述流程,覆蓋路徑按照往返次數,分成了圖2中的兩段覆蓋路徑。

該問題的目標是讓基站盡快收集環境目標信息。設無人機從任務開始自基站出發到Tri被訪問、再到返回基站通信范圍且與基站交換Tri信息所用的時間為ti,則目標函數為

(1)

約束條件包括:

zi=1, ?i∈{1,2,…,e}

(2)

(3)

(4)

(5)

決策變量按此定義:zi表示請求點Tri是否被無人機訪問,若為1,則訪問,否則為0;pij表示無人機是否從Tri運動到Trj,若為1,則是,否則為0;ui表示無人機是否從Tri回到基站通信范圍回饋信息。

約束條件的描述為:式(2)表示每個請求點必須且僅訪問一次,無人機需要經?；氐絋r1通信范圍回饋信息。式(3)確保每個請求點的出度等于入度,從而確保無人機行駛路線的連通性。式(4)表示無人機從Tr1出發開始運動。式(5)表示無人機至少往返于基站通信范圍和覆蓋路徑一次。該問題模型由Sabo等[2]提出,本文將其推廣到覆蓋問題中。該問題相對于覆蓋規劃問題的區別在于無人機無法在覆蓋過程中與基站通信,需要經常從覆蓋區域返回到基站傳遞信息。核心難點問題和特點在于實現覆蓋規劃與信息傳輸的最優權衡。這種區別尤其體現在目標函數上,其不是最小化覆蓋路徑長度,而是最小化所有位點信息傳遞回基站的時間,若只在覆蓋完所有區域才返回基站,則會增大信息回饋時間。體現在決策變量上,不僅需要規劃覆蓋,還需要求解間歇式信息傳輸的時機。

2 問題求解方法

針對覆蓋規劃問題與返回位點選取問題的耦合問題,求解思路如圖3所示。

圖3 求解思路Fig.3 Solution idea

先對問題的情形進行分類討論,若是對區域進行全覆蓋,則先執行步驟(a),求解最短覆蓋路徑。步驟(b)、步驟(c)則以式(1)最小化為目標,優化覆蓋路徑上的返回到基站的位點;若不是對區域進行全覆蓋,即待覆蓋位點分散且較少時,則執行步驟(d),對需要覆蓋位點進行層次聚類,每個聚類包含無人機每次從基站通信范圍出發需要覆蓋的所有位點。無人機每次覆蓋完這些聚類內的點之后返回基站通信范圍。步驟(e)在得到無人機每次需要覆蓋的點集合后,需要求解遍歷這些點的覆蓋路徑。顯然,覆蓋路徑的起點為恢復點,終點為返回點。以下在第2.1節中介紹非區域全覆蓋的情形,進一步闡釋步驟(d)、步驟(e)。第2.2節中討論區域全覆蓋的情形,進一步闡釋步驟(a)～步驟(c)。

2.1 非區域全覆蓋的情形

在待訪問的請求點分布較為分散且數量較少時,Sinaga等[29]為劃分得到待搜索任務點使用K-means++聚類的方法,而Sabo等[2]則采用了層次聚類的方法,實驗結果良好。本文方法采取的步驟與Sabo等在文獻[2]中采用的步驟相同,區別在于聚類時采用的聚類之間的距離度量不同。

首先簡要說明Sabo的步驟,其主要的方法步驟為:對請求點進行層次聚類,聚類的度量是兩個請求點到基站的歐式距離之比與請求點相對基站方位的夾角,比值越接近1且夾角越接近0,則兩個請求點將會優先聚類。按照模糊推理得到唯一的最優聚類次數。模糊推理的參數則利用遺傳算法離線學習得到。在聚類完成后,需要利用智能優化方法計算每個聚類內部點遍歷的順序,在得到所有聚類和每個聚類內各個節點的訪問順序之后,將聚類分配給無人機。

上述聚類的度量沒有考慮障礙物的影響。本文對聚類的度量進行了改進。上述度量存在的問題以及改進方法如圖4所示。

圖4 Sabo的度量存在的問題Fig.4 Problem in Sabo’s measurement

圖4中黑色粗線段表示邊界或者障礙;x1和x2分別為利用Dijkstra算法求解得到的圓形節點1和節點2到基站的路徑長度;x3和x4分別為圓形節點1和節點2到基站的歐式距離,顯然兩者相近。另外,相對基站的方位夾角β也很小。按照Sabo的度量方法,顯然節點1和節點2可以聚成一類。但實際上,從節點1到節點2的路徑長度遠大于兩者之間的歐式距離,若將節點1和節點2聚成一類,無人機在遍歷該聚類時,將會行駛很長的路徑才能從節點1到達節點2,這將極大增加式(1)的目標函數值,產生較差的結果。

本文對該度量進行了改進,在求解兩個聚類Cluu、Cluv之間的距離d(Cluu,Cluv)時,設兩個節點Tri和Trj滿足Tri∈Cluu,Trj∈Cluv。在計算兩個節點i和j的距離時,采用的第一個度量αij為兩個節點i和j到基站的路徑長度(利用Dijkstra算法所得長度)yi和yj之比:

(6)

yi和yj分別對應x1和x2。設兩個節點i和j之間的路徑長度為qij,則采用的第二個度量為βij:

(7)

式(7)由余弦定理得到,βij為兩個節點相對基站方位的“廣義”夾角。在使用該度量時,顯然需要滿足如下條件:yi、yj和qij可以構成一個三角形。

若3條邊滿足最短兩邊之和大于第3邊,那么這3邊可以構成一個三角形,由于Dijkstra算法所求的距離為兩個點之間的最短距離,故易證yi、yj和qij滿足該條件,也即可以構成一個三角形。

綜上所述,yi和yj的距離度量d(Tri,Trj)為

d(Tri,Trj)=f(αij,βij)

(8)

式中:f(·)表示模糊規則。該規則的具體參數文獻[2]已經說明。最后,得到兩個聚類的距離d(Cluu,Cluv)為

(9)

對于處于基站通信范圍內的點,無人機先進行覆蓋,這樣可以較快將通信范圍內的點信息傳回基站。這些點不需要進行聚類,可直接求解最短路徑。無人機在遍歷完這些點之后,開始覆蓋位于基站通信范圍之外的點。在每次無人機覆蓋完一個聚類的點之后,需要在通信范圍內找到距離無人機返回點最近的點,無人機只需運動到該點即可將信息傳回基站。同理,在區域全覆蓋的情形下,也可采用該方法處理基站通信范圍之內和之外的點。另外,可利用Dijkstra算法求解地圖上所有位點之間的最短路徑長度。

2.2 區域全覆蓋的情形

對于區域全覆蓋的情形,此時需要覆蓋的位點分布均勻,而且區域中的點比較密集。相比于第2.1節中點較為分散的情形,需要進一步考慮無人機模型的影響。采用第2.1節中的覆蓋路徑求解方法顯然沒有對覆蓋路徑上路徑平滑程度、轉彎半徑等進行考慮(在待覆蓋點較為分散時該問題并不突出)。

對于此問題,本文提出一種三階段的優化方法,即圖3中步驟(a)～步驟(c)。針對步驟(a),先利用Boustrophedon法進行單元分解,利用智能優化方法優化單元之間和單元內的覆蓋路徑,具體步驟采用文獻[17]的方法。該文獻中求解的路徑考慮了上述因素。以下具體介紹步驟(b)基于目標函數提取最優返回次數的可能范圍和步驟(c)基于最優返回次數所處范圍的返回位點智能優化。

2.2.1 基于目標函數分析提取最優返回次數的可能范圍

在研究復雜規劃問題時,智能優化方法必須要與問題特征相結合,才能發揮更好的搜索效果。可以利用運籌學方法分析得到問題特征,但利用其對最優解的特征進行嚴格理論分析時,可能會面臨難以求解的情形。因此,本階段在對問題的目標函數進行分析時,采取的思想方法是抓住影響目標函數的主要因素,忽略不重要的因素,按此方法得到問題特征。此特征雖無法得到嚴格理論證明,但對搜索最優解仍具有一定的指導意義。

由于選取合適的返回次數將會發揮重要的作用,因此可以基于此分析目標函數,得到最優返回次數可能的范圍。

(10)

基于圖3中步驟(a)得到的覆蓋路徑,將單元之間的銜接路徑點集視作無效請求點集P,單元內部的覆蓋路徑點集視作有效請求點集Q,總點集合元素數量為

(11)

(12)

式中:M/K表示無人機一次覆蓋的點數。

(13)

綜上,現在需要完成以下目標:

(14)

對目標函數求導得到:

(15)

得到最優返回次數:

(16)

2.2.2 基于最優返回次數所處范圍的返回位點智能優化

第2.2.1節得到最優返回次數所處范圍,該階段利用此范圍先搜索最優返回次數,此后利用遺傳算法進一步優化返回位點位置。

步驟 1對由圖3中的步驟(a)得到最短的覆蓋路徑P,對其進行K*等分,設在覆蓋路徑上的分割點(或者稱為返回點)對應的序號集合為X={Xr|r={1,2,…,K*}}。

步驟 3采用均勻隨機初始化方法初始化每個個體的每個基因位:

(17)

生成Np個個體,組成種群A1。

步驟 4開始進化,利用錦標賽方法[30]從A1中選取兩個個體s1和s2。若rand小于交叉概率Pc,則隨機選取一段基因位進行交叉:

(18)

式中:h為需要交叉的位置。

步驟 5若rand小于變異概率Pm,對個體s1和s2進行變異,隨機選取一個位置m,針對基因位變異,有:

s(m)=(Xm-Δ1m)+rand·(Δ2m+Δ1m)

(19)

步驟 6將上述s1和s2作為子代種群中的成員,重復步驟4和步驟5,生成Np個子代成員。將A1中Np個個體與該Np成員合并,找到目標函數值排在前Np位的個體作為新的子代A1,用于之后的進化。

步驟 7重復步驟4～步驟6,直到輸出最優的返回位點,其偽代碼如算法1所示。

算法 1 基于遺傳算法的返回位點智能優化輸入覆蓋路徑P,最優返回次數K*輸出P上最優返回位點集合S 1將P劃分成 K*等份, 據此獲得每次的覆蓋點集合,設X={Xr|r={1,2,…,K*}}2先求初始解:設第i個個體對應的染色體為Yi={Yi1,Yi2,…,YiK*}其中染色體的每一位為Yin∈(Xn-Δ1n,Xn+Δ2n),其中的參數Δ1n=[(Xn-Xn-1)]/2,Δ2n=[(Xn+1-Xn)]/23初始化種群A1←?4For i=1:Np Do5For n=1:K* 6 Yin=(Xn-Δ1n)+rand·(Δ2n+Δ1n)7End For8 A1←A1∪Yi9End For10For u=1:Gmax Do11A2←?在A1中利用錦標賽算法和目標函數式(1)得到兩個個體s1 and s212If rand

2.3 算法時間復雜度分析

對于第2.1節中非區域全覆蓋的情形,其算法復雜度已經在文獻[2]中進行了分析,本文相對于其算法只增加利用Dijkstra算法求解地圖上所有點之間距離這一步驟,該部分的時間復雜度為O(M3),M為環境中自由位點的數量。

本文重點對區域全覆蓋的時間復雜度進行了分析,時間復雜度包含圖3中步驟(a)～步驟(c)3個階段的時間復雜度,以下的時間復雜度都是在最差情況下的結果。在步驟(a),使用了Dijkstra算法求解所有環境位點間的路徑長度,該部分的時間復雜度為O(M3)。設采用Boustrophedon法單元分解總的時間復雜度為O(M),設得到的單元數量為B。所有單元對應的多邊形最大邊數為A,則RCPP求解每個單元內覆蓋路徑的總時間復雜度為O(MA)。設置利用智能算法求解的單元迭代次數為G,單元間優化的時間復雜度為O(GB)。故步驟(a)的時間復雜度為O(M3+M+MA+GB)。

步驟(b)在計算所有點到基站的距離時直接利用步驟(a)的結果,故計算時間復雜度為O(M)。設步驟(c)遍歷搜索的次數為F。設步驟(c)進化代數為G2。步驟(c)的時間復雜度為O((G2+F)M),則總體時間復雜度為

f=O(M(2+M2+A+G2+F)+GB)

(20)

3 仿真實驗

本文的實驗環境為Windows10系統下基于C++的Qt環境,運行內存為16 GB。本文的驗證思路為:先驗證第2.1節提出的聚類距離度量方法的優越性,此后對第2.2.1節中的重要參數最優返回次數等進行調節和分析。最后,為了驗證3階段優化算法的優越性,將本文算法與前沿算法進行對比。

3.1 非區域全覆蓋方法對比

實驗采用如圖5所示的各種地圖。

圖5 實驗用地圖(非區域全覆蓋)Fig.5 Maps used in the experiment (non regional full coverage)

圖5中,黑色部分表示障礙物,綠色的柵格點集合為待訪問的點集合。設無人機的移動速度為1個單位/s。本節驗證步驟(a)覆蓋規劃算法的優越性,兩個對比算法為:① 文獻[2]中的Sabo的算法;② 結合文獻[17]的方法得到覆蓋路徑,再利用遺傳算法求解返回位點。兩個算法的對比結果如表1所示。

表1 目標函數平均值Table 1 Mean values of objective functions s

從表1可以看到,本文算法在目標函數值上顯然優于所有對比算法,本文算法采取的聚類距離度量考慮了障礙物的影響。利用Dijkstra算法求得兩個點之間的路徑長度,并以此對目標點聚類,避免相距較遠的兩個點聚成一類。針對圖5(a)的各種算法的規劃如圖6所示。

圖6 規劃結果(非區域全覆蓋)Fig.6 Planning results (non regional full coverage)

圖6中,左下角的藍色區域為基站的通信范圍(通信范圍半徑設置為3),每次的覆蓋路徑用不同顏色的曲線表示(為方便觀察,省略了無人機往返基站通信范圍的路徑)。如圖6(a)所示,本文算法中藍色曲線和紅色曲線為兩段覆蓋路徑;而圖6(b)中Sabo的算法將處于障礙物兩側的一部分點集合聚成了一類,導致一次覆蓋的路徑過長,降低了目標函數的質量;而圖6(c)則沒有利用Sabo所分析的問題特征,求解質量較差。

3.2 針對區域全覆蓋場景的參數調節

圖7 實驗用地圖(區域性全覆蓋)Fig.7 Maps used in the experiment (regional full coverage)

所得結果如表2所示。可以看到,λ值在分別取1、2、3時目標函數值相近且返回次數相近,參數在一定范圍內變化所引起的目標函數值變化并不敏感。返回次數不在該范圍內時,所得目標函數基本稍微劣于λ值為3對應的情況,而且此時返回次數與λ值為3對應的返回次數相近。經觀察,在λ=3的情形下將會取得最優的效果,而且對應的返回次數搜索范圍較小,由此可確定參數的取值。

表2 不同λ參數目標函數平均值對比Table 2 Comparison of mean values of objective functions with different λ s

3.3 區域全覆蓋對比實驗

經調研,近年來有關該問題的算法極少,本文選取的對比算法之一為Sabo的算法[2]。當環境中待訪問位點數量較少時,Sabo通過實驗驗證其算法運行所得結果的目標函數值與最優解相差不超過5%,因此可以將其作為一個有相當競爭力的對比算法。另外,采取的前沿對比算法為:利用文獻[17]的方法得到覆蓋路徑,再利用遺傳算法求解返回位點。采用圖7所示的4個地圖進行實驗,對比結果如表3所示。圖8為針對圖7(b)地圖2的各算法規劃結果,設無人機的移動速度為1個單位/s。圖8藍色區域為基站的通信范圍,本文算法和對比算法均優先覆蓋基站通信范圍內的目標點集合,即各算法在這部分點對應的目標函數值均相同,故表3中不再考慮這部分位點的目標函數值。圖8中,無人機每次的覆蓋路徑用不同顏色的曲線表示,為方便觀察,省略了無人機往返基站通信范圍的路徑。

表3 目標函數平均值對比Table 3 Comparison of mean values of objective functions s

圖8 規劃結果(區域全覆蓋)Fig.8 Planning results (regional full coverage)

從表3和圖8可以看到,Sabo的算法中將所有聚類的位點內規劃問題視作旅行商規劃問題,隨著位點數量增加,使用智能優化方法所得的目標函數值變差,而且經常容易產生轉角過大的路徑,不利于無人機飛行。

本文算法雖然存在表現上稍差的情形,即所求得的目標函數值稍遜于Sabo算法的結果,但從圖8可以看到其覆蓋路徑顯著優化,路徑較為平滑。

圖8(c)中的算法由于沒有關注問題的特征,所以所得無人機往返基站通信范圍的次數較多,導致目標函數質量下降。

以上算法消耗的時間如表4所示。

表4 算法運行時間比較Table 4 Comparison of running time consumption of different algorithms s

對比算法和本文算法都需要多次計算目標函數,這些都用到了地圖上所有點之間的距離。為減少頻繁多次計算目標函數帶來的計算壓力,需要先利用Dijkstra算法求解地圖上所有點之間的路徑長度,這一部分計算時間較長。本文算法的其他時間復雜度來自于單元分解、單元間遍歷順序計算,故分解的單元越多,計算時間越長,地圖1～地圖3單元數量較少,求解時間較短。對比算法的其他計算時間復雜度來源于點集合的層次聚類和類內點集合遍歷順序計算,因此點數量較多時計算時間偏長。

4 結 論

本文分析了間歇式通信下多智能體覆蓋問題模型,針對區域非全覆蓋和全覆蓋兩種情形進行了分類討論,針對非全覆蓋的情形提供了一種改進聚類度量的方法,充分考慮了障礙物對于聚類的影響,減少了聚類內遍歷路徑的長度。針對全覆蓋的情形,提出了三階段智能優化的方法,將覆蓋規劃問題和間歇式往返基站通信的耦合問題分解求解,每個階段都抓住了影響目標函數的關鍵參數,如步驟(a)的覆蓋路徑長度,步驟(b)的返回次數。在保證較好求解質量的同時,所得的覆蓋路徑相對于前沿算法取得了顯著改進,方便無人機進行飛行。本文重點研究了基于目標函數的問題特征分析方法,確定了關鍵特征,即最優返回參數的搜索范圍。進一步將該方法融合到智能優化的求解之中,先確定關鍵參數最優返回次數,再進一步優化其他參數的選取,從而更加高效地獲得了最優解。