室內(nèi)環(huán)境下基于拓撲連接圖的全覆蓋搜索算法

周 捷,施曉東,樂 意,朱 峰

(中國電子科技集團公司第二十八研究所, 江蘇 南京 210007)

1 引言

覆蓋路徑規(guī)劃(coverage path planning,CPP)是確定一條路徑,該路徑通過一個區(qū)域或感興趣的體積的所有點,同時避免障礙[1-2]。這一任務是許多機器人應用的組成部分,如真空清洗機器人、油漆機器人、自主水下機器人創(chuàng)建圖像馬賽克、排雷機器人、割草機、自動收割機、窗戶清潔工和復雜結(jié)構(gòu)的檢查[3-4]。CPP要遵循一定的規(guī)則,機器人/無人車不走重復的路徑;在覆蓋目標區(qū)域的同時應避開所有的障礙物;要將任務區(qū)域全部覆蓋;遵循一定的運動模式;覆蓋過程中走的路徑盡量短。

無人機(unmanned aerial vehicle,UAV)由于其快速靈巧的特點經(jīng)常應用于山地、野外以及城市環(huán)境中的搜索、監(jiān)視、偵察、跟蹤等任務。對目標的偵察監(jiān)視以及跟蹤任務的前提是對任務區(qū)域進行搜索,直到發(fā)現(xiàn)目標,才會觸發(fā)后續(xù)的任務流程。所以,UAV對任務區(qū)域快速高效地全覆蓋起著至關重要的作用。

城市環(huán)境對UAV執(zhí)行搜索、監(jiān)視、偵察等任務會產(chǎn)生各種各樣不同程度的影響。城市環(huán)境又分為室外環(huán)境和室內(nèi)環(huán)境。城市室外環(huán)境,高樓林立樹木繁多,車輛行人不斷運動,而且運動雜亂無章毫無規(guī)律可尋。這就會對UAV的運動產(chǎn)生極大的威脅。例如,高樓和樹木的存在會對UAV的視覺產(chǎn)生遮擋,運動中的車輛和行人可視為UAV的動態(tài)障礙物等。同理,復雜狹小的城市室內(nèi)環(huán)境對UAV執(zhí)行搜索、監(jiān)視、偵察等任務也會產(chǎn)生影響。首先,室內(nèi)通道狹窄,加上UAV有一定的安全距離,UAV在室內(nèi)環(huán)境飛行并不是暢通無阻的;其次,室內(nèi)通道大部分由門連接,門的開關狀態(tài)對于UAV來說存在著極大的不確定性;然后,室內(nèi)空間狹小結(jié)構(gòu)復雜遮擋嚴重,對UAV的視覺能力也會產(chǎn)生一定的衰減。所以,針對室內(nèi)環(huán)境下UAV的研究就顯得尤為重要。

室內(nèi)環(huán)境下UAV在執(zhí)行任務之前,首先需要對任務區(qū)域進行劃分和分解,對于分解得到的任務子區(qū)域進行有效的、安全的任務分配,UAV對于得到的子任務內(nèi)容進行路徑規(guī)劃,最終UAV前往各個任務區(qū)域執(zhí)行相應的搜索、偵察等任務[5-6]。

本文重點對室內(nèi)環(huán)境下無人機全覆蓋搜索任務展開研究。由于室內(nèi)特殊的環(huán)境結(jié)構(gòu),以及各個房間之間的連通性,首先對室內(nèi)環(huán)境提取出房間之間的拓撲連通圖,將各個房間抽象成一個個的點,則可以將問題轉(zhuǎn)化為一個旅行商問題(traveling salesman problem,TSP)[7-8],優(yōu)先解決TSP問題,規(guī)劃出對各個房間的訪問序列,由于各個房間之間不是全部互相連通的,所以規(guī)劃出訪問序列之后根據(jù)連通性來評價此訪問序列的可行性,并確定最終訪問順序,最后對每個房間進行全覆蓋搜索。

2 問題分析

2.1 問題描述

復雜室內(nèi)環(huán)境下UAV對于任務區(qū)域的全覆蓋搜索問題可以進行如下建模:給定n架異構(gòu)無人機Ui,i=1,…,n,因為UAV搭載的傳感器種類不同,所以UAV的工作能力也不同,對給定的任務區(qū)域P執(zhí)行搜索、偵察等任務,使得對于任務區(qū)域盡可能大的覆蓋,也就是盡可能多地完成任務,也要保證UAV規(guī)劃出來的路徑?jīng)]有重復,盡可能快速。分析此問題的特性發(fā)現(xiàn)使用雙層的思想對此問題進行求解最合適。

首先,將室內(nèi)的任務場景以房間為單位劃分為一個個子任務,根據(jù)每個子任務的區(qū)域大小不同以及房間內(nèi)部的連通關系,對無人機的第一層路徑即各個房間的訪問順序進行規(guī)劃,當UAV進入房間執(zhí)行全覆蓋搜索任務時,再規(guī)劃UAV在房間內(nèi)部的全覆蓋搜索路徑。如圖1所示為無人機的任務區(qū)域,黃色方格為門的位置,黑色條狀區(qū)域為墻,黑色矩形為障礙物或威脅區(qū)域。

室內(nèi)環(huán)境下UAV的全覆蓋問題框架如圖2所示,首先,對任務場景進行預處理,以房間為單位對室內(nèi)的整體場景進行分解將任務區(qū)域P劃分成n個不相重疊的子區(qū)域P1,…,Pn,然后通過室內(nèi)各個房間門的分布情況構(gòu)建拓撲連接關系將子區(qū)域P1,…,Pn進行連接;然后,將子區(qū)域P1,…,Pn抽象為一個個點,需要確認對抽象出來的點的訪問順序,則此問題可建模為TSP問題模型,利用蟻群優(yōu)化算法(ant colony optimization,ACO)進行求解求得訪問順序,當進入每個房間時UAV切換到全覆蓋搜索模式,進入此模式時,UAV需要規(guī)劃搜索的方向和全覆蓋搜索的路徑點以及飛行的高度,合適的飛行高度有利于UAV的傳感器的探測范圍wi達到最大,從而減少由于對搜索區(qū)域產(chǎn)生的疊加導致的UAV能耗的浪費,直到遍歷完所有的任務區(qū)域。

圖2 全覆蓋問題框架

2.2 算法描述

為便于討論,并結(jié)合實際全覆蓋搜索、偵察問題進行以下假設:①UAV勻速進行搜索;②子任務以房間為單位進行劃分;③不考慮門的開關狀態(tài),默認門的狀態(tài)都為開,即可連通;④UAV的初始位置為已知的。

合理的性能評估與任務區(qū)域分配將使得UAV整體執(zhí)行任務的效能最大,即UAV協(xié)同執(zhí)行任務的代價最小[9]。所以,建立UAV全覆蓋搜索任務代價模型可以很好地檢測性能評估方法和區(qū)域分配方法是否有效。

UAV在執(zhí)行全覆蓋搜索任務的過程中要付出的代價包括UAV飛行路徑代價、油耗以及執(zhí)行偵察任務的時間代價。并且約束有油耗不能超過UAV的最大載油量,偵察時間不能超過傳感器的最大工作時間。

針對問題的特性對ACO算法進行如下兩點改進,一是引入自適應參數(shù)調(diào)整機制,目的是提高算法搜索初期尋優(yōu)速度;有效的擺脫局部最優(yōu)的情況;二是引入雙向搜索機制,目的是為了加快搜尋最優(yōu)解的速度。

綜合以上UAV的代價和約束條件,可以將UAV室內(nèi)全覆蓋搜索、偵察任務的數(shù)學模型進行總結(jié),如下如公式(1)所示:

(1)

模型求解的結(jié)果為優(yōu)化的無人機任務區(qū)域分配面積百分比,使得多UAV任務執(zhí)行代價最小。比較模型求解得出的區(qū)域面積分配百分比與基于性能評估的任務區(qū)域分配百分比之間的差異,以及所對應的多UAV任務執(zhí)行代價之間的差異,可以分析基于性能評估的任務區(qū)域分配方法的有效性。

2.3 傳感器探測范圍

對于執(zhí)行偵察任務的無人機,其執(zhí)行任務的效果很大程度決定于載荷的能力,即無人機機載傳感器的性能。傳感器的能力通?？梢杂脗鞲衅鞯奶綔y范圍w來表示。如圖3所示,當無人機以固定的高度水平飛行時,公式(2)描述了機載傳感器的地面探測范圍w

圖3 無人機的傳感器探測區(qū)域

圖4 全覆蓋游走模式

w=2·H·tanγ[cosα+sinαtan(π/2-α-β)]

(2)

其中,H為UAV的飛行高度,α為傳感器的安裝角,角度β和γ的取值與傳感器性能相關,由傳感器的視場角和焦距決定。所以,不同焦距下,傳感器的視場角也有差異,β和γ的取值也不相同,所以傳感器對于地面探測區(qū)域范圍也不同。當H固定時,β和γ取值越大,w值越大。

2.4 全覆蓋搜索模式

在CPP問題中,最優(yōu)的覆蓋路線是基于來回的路線或螺旋形的路線[10-11]。

如圖所示4,沿著任務區(qū)域的長邊進行搜索需要最小的匝數(shù),減少轉(zhuǎn)彎的次數(shù),因此可以最小化總能耗。

3 基于拓撲地圖的全覆蓋搜索算法

基于拓撲地圖的全覆蓋搜索算法主要分為以下三個步驟:首先,將先驗的室內(nèi)地圖柵格化;其次,結(jié)合拓撲地圖信息將抽象出來的TSP問題進行求解,并對求得的訪問序列進行可行性驗證;最后,按照第二步求得的訪問順序依次遍歷各個房間,并在各個房間內(nèi)部進行全覆蓋搜索。

3.1 拓撲地圖的構(gòu)建

為了方便無人機進行快速搜索,首先需要對室內(nèi)不規(guī)則的障礙物進行擴展處理,處理后得到規(guī)則的四邊形,處理效果示意圖如圖5所示,藍色為障礙物區(qū)域,處理后的效果如周圍的矩形所示。

圖5 障礙物處理規(guī)則

對無人機執(zhí)行全覆蓋任務的建筑物內(nèi)部房間進行標號,R1-R8代表8個房間,黃色區(qū)域代表連接房間的門,如圖6中標號1-12所示。

表1 房間中心點坐標

圖6 室內(nèi)結(jié)構(gòu)標號示意圖

根據(jù)重心法規(guī)則可得到每個房間的中心點,提取出來的R1-R8的坐標點如下表所示,將中心點抽象為一個個節(jié)點,以便于利用這些節(jié)點進行TSP問題的求解。

根據(jù)房間之間的連通性,對室內(nèi)環(huán)境進行處理,建立拓撲連接關系,如圖7所示,紅色節(jié)點代表房間標號,連線代表這兩個房間之間可連通。

圖7 拓撲連接圖

3.2 TSP問題的求解

旅行商問題是圖論中一個經(jīng)典的組合優(yōu)化問題。經(jīng)典的TSP可以描述為:一個商品推銷員要去若干個城市推銷商品,該推銷員從一個城市出發(fā),需要經(jīng)過所有城市一次并且僅一次之后,回到出發(fā)城市。那么他應如何選擇在城市之間的行程路線,以使他走過的總路程最短。從圖論的角度來看,該問題其實就是在一個賦權的無向圖中,去找一個哈密爾頓回路,并且使得該回路的總權值最小。

本文同理需要無人機遍歷所有的房間,盡量不要重復,在可通行的情況下以保證走過的路徑盡量短。利用ACO求解抽象出來的TSP問題,對所求得的訪問序列利用房間之間的連通性判斷序列是否可行。

3.3 全覆蓋搜索

如圖8所示,從上述TSP規(guī)劃的結(jié)果來看,首先從R3房間出發(fā),經(jīng)過R2、R1等最終在R5結(jié)束搜索任務,以R3為例首先進行小規(guī)模仿真,如圖9所示為房間R3全覆蓋之后的效果示意圖。

圖8 拓撲路線圖

圖9 房間R3全覆蓋效果示意圖

4 仿真驗證

在已建立好的地圖上,首先根據(jù)房間之間的連通關系建立拓撲連接圖,再根據(jù)一系列各個房間的中心點來規(guī)劃訪問順序,并用建立好的拓撲連接圖來評價訪問順序的可行性。當進入每個節(jié)點時,即進入每個房間時,先進行全覆蓋搜索,再進入下一個訪問節(jié)點進行全覆蓋搜索,直到遍歷完所有的房間節(jié)點,如圖10所示,為室內(nèi)環(huán)境下全覆蓋搜索示意圖,綠點處為起點,紅點處為重點。

圖10 室內(nèi)環(huán)境下全覆蓋效果示意圖

5 結(jié)束語

本文以室內(nèi)無人機全覆蓋搜索為背景,使用基于拓撲地圖的全覆蓋搜索算法,結(jié)合室內(nèi)存在障礙物、各個房間之間的連通性以及拓撲關系等多維信息進行模擬仿真。雖然前期對建筑物室內(nèi)結(jié)構(gòu)進行了拓撲關系的構(gòu)建,房間中心點的選取,卻極大地保障了規(guī)劃的訪問順序的可靠性和可行性。