史萬(wàn)慶, 黃鴻柳, 蔣林利
(1.商丘學(xué)院計(jì)算機(jī)工程學(xué)院,河南 商丘 476000; 2.廣西科技師范學(xué)院實(shí)驗(yàn)實(shí)訓(xùn)中心,廣西 來(lái)賓 546000)
近年來(lái),多機(jī)器人協(xié)同覆蓋因具有良好的互聯(lián)互通、態(tài)勢(shì)共享、群策群力特性,在監(jiān)視、偵察、勘探和檢測(cè)等領(lǐng)域得到廣泛應(yīng)用[1]。多機(jī)器人協(xié)同覆蓋的主要目標(biāo)是通過(guò)一組感知能力有限的機(jī)器人實(shí)現(xiàn)對(duì)目標(biāo)區(qū)域的協(xié)同覆蓋搜索[2]。為保證覆蓋區(qū)域的有效性,需考慮不同區(qū)域之間的重疊、各機(jī)器人路徑長(zhǎng)度的差異以及執(zhí)行完全覆蓋的覆蓋周期等諸多因素[3]。此外,在不規(guī)則的障礙物、不規(guī)則的任務(wù)區(qū)域等復(fù)雜環(huán)境下,多機(jī)器人協(xié)同覆蓋的復(fù)雜性會(huì)大大增加[4-5]。
與單機(jī)器人覆蓋相比,多機(jī)器人協(xié)同覆蓋具有效率高、范圍廣、持續(xù)性強(qiáng)等優(yōu)勢(shì)[6]。由于工作量的劃分,使用多個(gè)機(jī)器人協(xié)同搜索可以有效減少完成覆蓋所需的時(shí)間成本[7]。多機(jī)器人協(xié)同通過(guò)將隊(duì)友作為信標(biāo),可實(shí)現(xiàn)定位誤差的最小化。此外,在多機(jī)器人協(xié)同覆蓋中,若團(tuán)隊(duì)的部分成員失敗,則可以由其他機(jī)器人進(jìn)行補(bǔ)償,可有效提高協(xié)同覆蓋的魯棒性[8]。因此,基于多機(jī)器人的協(xié)同覆蓋是目標(biāo)區(qū)域搜索的主要研究方向。
為提高多機(jī)器人協(xié)同覆蓋的有效性,國(guó)內(nèi)外眾多學(xué)者開(kāi)展了大量研究。在以往的研究中,多機(jī)器人協(xié)同覆蓋策略主要分為集中式覆蓋和分散式覆蓋兩種。針對(duì)集中式覆蓋策略,文獻(xiàn)[9]提出了一種線(xiàn)性?huà)呙韪采w規(guī)劃算法,讓所有機(jī)器人成排分布,從而實(shí)現(xiàn)對(duì)掃描區(qū)域的最大化覆蓋,但該算法在面對(duì)不規(guī)則障礙物時(shí),機(jī)器人團(tuán)隊(duì)處理能力會(huì)迅速下降;文獻(xiàn)[10]提出了一種分散式多邊形分解算法,將一個(gè)給定的區(qū)域分成多邊形塊,通過(guò)明確各機(jī)器人的相對(duì)能力,確定區(qū)域劃分的比例,但該方法不能使每條路線(xiàn)的長(zhǎng)度達(dá)到平衡;文獻(xiàn)[11]提出了一種基于改進(jìn)神經(jīng)網(wǎng)絡(luò)的路徑規(guī)劃算法,該算法利用聚類(lèi)算法對(duì)目標(biāo)點(diǎn)進(jìn)行分類(lèi),通過(guò)將相似的目標(biāo)進(jìn)行聚集后,按規(guī)則劃分到同一個(gè)集合,但聚類(lèi)節(jié)點(diǎn)過(guò)于整齊,未考慮機(jī)器人的局限性,不能有效縮短覆蓋周期。
綜上所述,集中式覆蓋和分散式覆蓋兩種策略均不能有效處理復(fù)雜環(huán)境中的覆蓋問(wèn)題,實(shí)際應(yīng)用效果不佳。因此,針對(duì)具有復(fù)雜約束的多機(jī)器人協(xié)同覆蓋搜索問(wèn)題,提出了一種多機(jī)器人協(xié)同覆蓋搜索路徑規(guī)劃策略。首先,在目標(biāo)區(qū)域部署傳感器,以滿(mǎn)足覆蓋性要求;其次,通過(guò)改進(jìn)的K-means聚類(lèi)算法對(duì)傳感器布置點(diǎn)進(jìn)行分類(lèi),引入反饋機(jī)制平衡每條路徑的長(zhǎng)度,并以部署的傳感器位置為路徑點(diǎn)求解旅行商問(wèn)題(TSP),獲取每個(gè)機(jī)器人的封閉路徑。最后,通過(guò)仿真實(shí)驗(yàn),驗(yàn)證了所提算法的有效性。
為簡(jiǎn)化多機(jī)器人覆蓋處理方式,對(duì)多機(jī)器人覆蓋問(wèn)題做以下簡(jiǎn)化處理:1) 將每個(gè)機(jī)器人的檢測(cè)范圍簡(jiǎn)化為一個(gè)圓形區(qū)域,并忽略機(jī)器人運(yùn)動(dòng)對(duì)感知范圍的影響;2) 機(jī)器人所攜帶傳感器的位置與機(jī)器人的位置相同;3) 將給定任務(wù)區(qū)內(nèi)的無(wú)障礙區(qū)域和障礙物分布情況作為先驗(yàn)信息;4) 每個(gè)機(jī)器人的動(dòng)態(tài)特性均相同。
在所考慮的場(chǎng)景中,需要使用一組機(jī)器人對(duì)搜索區(qū)域進(jìn)行覆蓋,但各機(jī)器人的感知半徑和運(yùn)動(dòng)學(xué)約束是有限的。此外,應(yīng)該盡量縮短搜索覆蓋周期,同時(shí)避免障礙物。令機(jī)器人的覆蓋半徑為ra,目標(biāo)區(qū)域Rt由可到達(dá)區(qū)域Ra和障礙物區(qū)域Ro組成,且滿(mǎn)足Ra∩,Ro=?。圖1為目標(biāo)區(qū)域的示意圖,圖中,黑色區(qū)域表示障礙物區(qū)域,無(wú)色為可達(dá)區(qū)域。為了簡(jiǎn)化多機(jī)器人覆蓋問(wèn)題,將所研究的多機(jī)器人協(xié)同覆蓋搜索問(wèn)題轉(zhuǎn)化為2個(gè)子問(wèn)題:1) 如何把給定區(qū)域劃分成相應(yīng)數(shù)量的子區(qū)域;2) 如何獲取子區(qū)域內(nèi)每個(gè)機(jī)器人的封閉路徑。
圖1 目標(biāo)區(qū)域示意圖Fig.1 Sketch map of target region
對(duì)于子問(wèn)題2),可通過(guò)傳統(tǒng)的路徑規(guī)劃算法解決。因此,需重點(diǎn)研究的是如何進(jìn)行區(qū)域劃分。為解決區(qū)域劃分問(wèn)題,首先,需在給定區(qū)域覆蓋一定數(shù)量的傳感器點(diǎn),以滿(mǎn)足覆蓋要求;隨后,將這些傳感器點(diǎn)聚類(lèi)成N個(gè)聚類(lèi),即不同的子區(qū)域;最后,在得到聚類(lèi)后,通過(guò)求解旅行商問(wèn)題,獲得通過(guò)聚類(lèi)中所有傳感器點(diǎn)的路徑。
傳感器部署問(wèn)題(Sensor Deployment Problem,SDP)主要解決如何在目標(biāo)區(qū)域和期望的需求中以最小數(shù)量部署傳感器。首先,目標(biāo)區(qū)域被分為一系列矩形單元格,將Cf={c1,c2,…,ci,…,cm}定義為可訪(fǎng)問(wèn)區(qū)域Ra中的單元格集合。假設(shè)S={s1,s2,…,sj,…,sn}是傳感器的集合,其中,n為傳感器的最大數(shù)量。只有當(dāng)單元格的4個(gè)頂點(diǎn)在傳感器sj的感測(cè)范圍內(nèi),且單元格沒(méi)有被任何障礙物阻擋時(shí),ci才被sj完全覆蓋。根據(jù)要求,Cf中的所有單元格都需要完全覆蓋。在完全覆蓋的前提下,要求規(guī)劃路徑最短,以利于縮短覆蓋周期。
設(shè)ej=(p(sj),gj)為傳感器sj基本部署信息,其中,p(sj)為sj的位置,gj為有效標(biāo)志。若sj已部署,則令gj=1,否則gj=0。因此,部署向量矩陣[e1e2…en]表示傳感器的部署情況,即傳感器部署問(wèn)題的可行解決方案。
考慮傳感器配置指標(biāo),傳感器部署問(wèn)題的適應(yīng)度函數(shù)可表示為
f([e1e2…en])=λ1×nd+λ2×nu+λ3×ns+λ4×no
(1)
式中:nd,nu,ns和no分別表示Ra中部署的傳感器的數(shù)量、Ra中未覆蓋的單元格數(shù)量、Ra中覆蓋的單元格數(shù)量以及Ra中重疊的單元格數(shù)量;λ1,λ2,λ3,λ4為加權(quán)權(quán)重,滿(mǎn)足λ1>>λ2>>λ3>>λ4>>0。
yi=xif(xi) (2) (3) 此時(shí),粒子的位置和速度更新為 xi,d(t+1)=xi,d(t)+vi,d(t+1) (4) (5) (6) (7) 式中:w(t)為平衡全局和局部搜索的慣性系數(shù);c1,c2和c3為加速度常數(shù);Pvji為第j個(gè)粒子群的速度。 c3的數(shù)學(xué)方程為 (8) (9) 式中,m為鄰域范圍,通過(guò)運(yùn)用CCPSO2算法,得到適應(yīng)度函數(shù)的最小值,從而得到傳感器最優(yōu)部署向量。 完成傳感器部署求解后,可得到一系列傳感器部署點(diǎn)S={s1,s2,…,sn},利用聚類(lèi)方法對(duì)上述傳感器部署點(diǎn)進(jìn)行分類(lèi),能夠?qū)⒏咏南噜忺c(diǎn)劃分到同一個(gè)類(lèi)中,從而實(shí)現(xiàn)有效的區(qū)域劃分。由于該算法原理簡(jiǎn)單且易于實(shí)現(xiàn),本文算法中使用了經(jīng)典的K-means均值算法對(duì)傳感器部署點(diǎn)進(jìn)行聚類(lèi)。在K-means算法中,通常將誤差平方函數(shù)作為準(zhǔn)則函數(shù),如 (10) 式中:k為簇的數(shù)量;ni為第i個(gè)聚類(lèi)的數(shù)據(jù)點(diǎn)數(shù)量;xi j為第i個(gè)簇的第j個(gè)數(shù)據(jù)點(diǎn);mi為第i個(gè)聚類(lèi)所有數(shù)據(jù)點(diǎn)的平均值,表示為 (11) 通常,K-means算法中每個(gè)聚類(lèi)的初始中心均是隨機(jī)選擇的,而這也將導(dǎo)致不同聚類(lèi)之間存在較大的差異,甚至造成無(wú)法穩(wěn)定收斂??紤]區(qū)域劃分的主要特點(diǎn),采用密度法確定聚類(lèi)的初始中心,以防止聚類(lèi)中心過(guò)于接近。 將傳感器點(diǎn)x在區(qū)域F中的密度定義為與x的距離不大于特定鄰域半徑r的傳感器點(diǎn)的數(shù)量。圖2為傳感器點(diǎn)x的密度示意圖,其中,傳感器點(diǎn)x的密度為11,即Di(r)=11。 圖2 點(diǎn)x的密度示意圖Fig.2 Sketch map of the density of point x 對(duì)于密度法,首先,需要選擇一個(gè)合適的鄰域半徑r來(lái)計(jì)算每個(gè)點(diǎn)的密度Di(r),并將密度最大的數(shù)據(jù)點(diǎn)作為第1簇c1的初始中心;其次,刪除c1鄰域半徑r內(nèi)的點(diǎn),并將剩余數(shù)據(jù)點(diǎn)中密度最大的點(diǎn)作為第2聚類(lèi)的初始中心。為了使總完成時(shí)間最短,每個(gè)子區(qū)域中的搜索周期應(yīng)該盡可能保持一致。因此,可通過(guò)對(duì)距離D(x,cj)進(jìn)行加權(quán)來(lái)修改K-means算法,以此代替歐幾里德距離。加權(quán)距離被作為數(shù)據(jù)點(diǎn)xi j和聚類(lèi)ci中心之間的距離度量,即 Di(xi j,ci,wi)=|| (12) 式中,wi為簇ci中心的距離權(quán)重。因此,修正準(zhǔn)則函數(shù)可表示為 (13) (14) 此時(shí),距離權(quán)重wi可更新為 wi=wi0+Δwi=wi0-k1Δli (15) 式中:wi0為最后時(shí)刻的距離權(quán)重;k1為反饋增益,且k1> 0。 wi和Di的變化可以表示為 (16) 旅行商問(wèn)題(Travelling Salesman Problem,TSP)是指訪(fǎng)問(wèn)一組區(qū)域并返回起點(diǎn)的最短路線(xiàn)問(wèn)題。假設(shè)Sq={s1,s2,…,sq}為行程點(diǎn)集,其中si(i=1,2,…,q)為行程點(diǎn),q為行程點(diǎn)數(shù)。令Li=[li1,li2,li j,liq],(i,j=1,2,…,q)表示距離的集合,其中,li j表示傳感器si和sj之間的距離。通常,可使用歐幾里德距離計(jì)算兩個(gè)傳感器點(diǎn)之間的距離。當(dāng)兩個(gè)傳感器點(diǎn)之間不存在障礙物時(shí),傳感器之間的距離li j可表示為歐幾里德距離。當(dāng)兩個(gè)傳感器之間障礙條件下,可通過(guò)使用A*算法獲得傳感器距離li j。 根據(jù)傳感器部署點(diǎn)集Sq,可得到q×q的總距離矩陣Dq×q=[L1L2…Lq]。假設(shè)sqi(s1,sq)={sa,sb,sc},a,b,c為[1,q]范圍內(nèi)的自然數(shù),是傳感器部署點(diǎn)的序列,其中,s為點(diǎn)集Sq的傳感器部署點(diǎn)。因此,以Sq和Dq×q為已知條件,可求解旅行商問(wèn)題,從而在求解區(qū)域內(nèi)得到期望的解。 開(kāi)展仿真實(shí)驗(yàn)對(duì)本文所提算法的有效性進(jìn)行驗(yàn)證,實(shí)驗(yàn)中采用圖1所示的目標(biāo)區(qū)域,該區(qū)域面積為120 m×120 m,其中,黑色區(qū)域代表障礙物,3個(gè)多邊形障礙物分布在方形區(qū)域內(nèi)。將整個(gè)區(qū)域分為2 m×2 m大小的小方塊,每個(gè)機(jī)器人的傳感范圍均設(shè)定為10 m。 首先,需引進(jìn)一組傳感器覆蓋目標(biāo)區(qū)域,以使用CCPSO2算法求解傳感器部署問(wèn)題。傳感器部署的仿真結(jié)果見(jiàn)圖3,其中有95個(gè)傳感器用于覆蓋整個(gè)區(qū)域。 圖3(a)中,*表示傳感器的位置,○表示傳感器的檢測(cè)范圍。由圖可知,傳感器均勻地分布在目標(biāo)區(qū)域,并能有效避開(kāi)障礙物。圖3(b)為CCPSO2成本迭代曲線(xiàn),為提高傳感器覆蓋效率,將任務(wù)區(qū)域分解為4個(gè)子區(qū)域進(jìn)行覆蓋,對(duì)應(yīng)為圖3(b)中的4條曲線(xiàn)。由圖3(b)可知,4條曲線(xiàn)均呈下降趨勢(shì),分別在經(jīng)過(guò)95,91,89和92次迭代后,最終穩(wěn)定在4548,4830,5208和4300處。 圖3 傳感器部署仿真結(jié)果圖Fig.3 Simulation results of sensor deployment 使用改進(jìn)的K-means算法將獲得的傳感器部署點(diǎn)分類(lèi)到相應(yīng)的聚類(lèi)中。實(shí)驗(yàn)中,將任務(wù)區(qū)域劃分為z個(gè)子區(qū)域,其中,z可以根據(jù)機(jī)器人的數(shù)量進(jìn)行設(shè)置。此外,在每次迭代中,使用遺傳算法求解旅行商問(wèn)題,以計(jì)算每個(gè)聚類(lèi)簇的路徑長(zhǎng)度,計(jì)算結(jié)果如圖4所示。 圖4 聚類(lèi)計(jì)算結(jié)果圖Fig.4 Cluster results 圖5所示為當(dāng)機(jī)器人的數(shù)量k分別為3,4,5時(shí)路徑長(zhǎng)度和距離權(quán)重曲線(xiàn)。 圖5 路徑長(zhǎng)度和距離權(quán)重的曲線(xiàn)圖Fig.5 Curves of path length and distance weight 由圖5(a)可知,當(dāng)k=3,且迭代次數(shù)大于43時(shí)每個(gè)子區(qū)域中的路徑長(zhǎng)度逐漸收斂。同樣,由圖5(c)和圖5(e)可知,當(dāng)k=4,k=5時(shí),迭代次數(shù)的收斂范圍分別為大于等于48和大于等于35,其詳細(xì)結(jié)果如表1所示。此外,圖5(b)、圖5(d)和圖5(f)給出了與反饋增益機(jī)制相匹配的距離權(quán)重曲線(xiàn)。 表1 每個(gè)子區(qū)域的平均路徑長(zhǎng)度和偏差Table 1 Average path length and deviation of each sub-region 由于目標(biāo)區(qū)域被分為多個(gè)子區(qū)域,因此需要規(guī)劃通過(guò)每個(gè)子區(qū)域中所有傳感器點(diǎn)的最短閉合路徑。本文使用歐幾里德距離計(jì)算方法和A*算法獲得通過(guò)每個(gè)子區(qū)域中所有傳感器部署點(diǎn)的路徑。如果兩個(gè)傳感器點(diǎn)之間的連接沒(méi)有通過(guò)障礙物區(qū)域,則歐幾里德距離表示它們之間的實(shí)際距離,但如果連線(xiàn)經(jīng)過(guò)障礙物區(qū)域,則用A*算法進(jìn)行距離計(jì)算。各子區(qū)域路徑規(guī)劃的最終結(jié)果如圖6所示。 圖6 各子區(qū)域路徑規(guī)劃的最終結(jié)果Fig.6 Final results of path planning for each sub-region 為驗(yàn)證所提協(xié)同覆蓋搜索算法對(duì)具有不規(guī)則邊界和障礙物的復(fù)雜區(qū)域的適應(yīng)性,運(yùn)用所提算法對(duì)不規(guī)則區(qū)域內(nèi)多機(jī)器人覆蓋問(wèn)題進(jìn)行仿真。其中,障礙物被設(shè)置為不規(guī)則的四邊形和圓形,且目標(biāo)區(qū)域?yàn)椴灰?guī)則的六邊形,計(jì)算結(jié)果如圖7所示。 圖7 復(fù)雜區(qū)域的仿真結(jié)果Fig.7 Simulation results of complex region 由圖7可知,共有78個(gè)傳感器用于覆蓋任務(wù)區(qū)域,且所提策略可適用于更復(fù)雜的目標(biāo)區(qū)域進(jìn)行多機(jī)器人協(xié)同覆蓋搜索。由于每條路線(xiàn)的差異非常小,表明所提出算法可有效地將任務(wù)區(qū)域劃分為大致相同的子區(qū)域。 在獲得每個(gè)子區(qū)域的路徑后,機(jī)器人可通過(guò)封閉路徑在相應(yīng)區(qū)域繞行,以實(shí)現(xiàn)協(xié)同覆蓋搜索該區(qū)域的任務(wù),從而保證避障效果和最小化覆蓋周期。綜上所述,所提算法具有良好的復(fù)雜環(huán)境適應(yīng)性,對(duì)環(huán)境的幾何形狀幾乎沒(méi)有限制,具有較高的魯棒性。 為了驗(yàn)證本文所提算法的性能,將本文算法與文獻(xiàn)[8]和文獻(xiàn)[10]所提算法,在目標(biāo)區(qū)域和復(fù)雜區(qū)域兩種情況下進(jìn)行對(duì)比實(shí)驗(yàn),計(jì)算機(jī)器人在不同運(yùn)動(dòng)步數(shù)下50組實(shí)驗(yàn)的平均覆蓋率,如圖8所示。 圖8 3種算法下平均覆蓋率對(duì)比Fig.8 Comparison of average coverage under the three methods 從圖8可以看出,本文所提算法較文獻(xiàn)[8]和文獻(xiàn)[10]所提算法在平均覆蓋率上有明顯提升。另外,3種算法在前中期的收斂速度較快,而在后期較為平緩,主要是因?yàn)樵诤笃谑S辔锤采w區(qū)域較少。除此之外,從平均消耗時(shí)間上來(lái)看,本文算法的平均消耗時(shí)間為27.2 s,而文獻(xiàn)[8]和文獻(xiàn)[10]所提算法分別為32.3 s和39.4 s,由此進(jìn)一步表明了本文算法的優(yōu)越性。 針對(duì)復(fù)雜任務(wù)環(huán)境下多機(jī)器人協(xié)同覆蓋搜索問(wèn)題,提出了一種多機(jī)器人協(xié)同覆蓋搜索路徑規(guī)劃策略,并通過(guò)仿真實(shí)驗(yàn)分析得出以下結(jié)論:1) 所提算法能夠?qū)崿F(xiàn)多機(jī)器人的任務(wù)區(qū)域劃分,能夠根據(jù)機(jī)器人的數(shù)量進(jìn)行調(diào)整,減少每個(gè)子區(qū)域中各閉合路徑之間的長(zhǎng)度差異;2) 所提算法對(duì)環(huán)境與障礙物的幾何形狀的限制較小,能夠有效適應(yīng)不規(guī)則的復(fù)雜環(huán)境條件,具有較高的魯棒性;3) 與其他算法相比,本文算法平均消耗時(shí)間為27.2 s,明顯優(yōu)于其他兩種算法性能。2.2 改進(jìn)的K-means均值聚類(lèi)和區(qū)域劃分反饋機(jī)制
xi j-ci||
/wi2.3 基于旅行商的路徑規(guī)劃
3 仿真實(shí)驗(yàn)與分析
3.1 傳感器部署
3.2 傳感器部署點(diǎn)的聚類(lèi)結(jié)果
3.3 子區(qū)域的路徑規(guī)劃
3.4 復(fù)雜區(qū)域仿真結(jié)果
3.5 不同算法平均覆蓋率對(duì)比
4 結(jié)論