復(fù)雜環(huán)境下多機(jī)器人協(xié)同覆蓋搜索路徑規(guī)劃

史萬(wàn)慶， 黃鴻柳， 蔣林利

(1.商丘學(xué)院計(jì)算機(jī)工程學(xué)院，河南 商丘 476000； 2.廣西科技師范學(xué)院實(shí)驗(yàn)實(shí)訓(xùn)中心，廣西 來(lái)賓 546000)

0 引言

近年來(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)證了所提算法的有效性。

1 多機(jī)器人覆蓋性問(wè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)的路徑。

2 協(xié)同覆蓋搜索路徑規(guī)劃

2.1 傳感器部署

傳感器部署問(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)部署向量。

2.2 改進(jìn)的K-means均值聚類(lèi)和區(qū)域劃分反饋機(jī)制

完成傳感器部署求解后，可得到一系列傳感器部署點(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)=||

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)

2.3 基于旅行商的路徑規(guī)劃

旅行商問(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)得到期望的解。

3 仿真實(shí)驗(yàn)與分析

開(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。

3.1 傳感器部署

首先，需引進(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

3.2 傳感器部署點(diǎn)的聚類(lèi)結(jié)果

使用改進(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

3.3 子區(qū)域的路徑規(guī)劃

由于目標(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

3.4 復(fù)雜區(qū)域仿真結(jié)果

為驗(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)有限制，具有較高的魯棒性。

3.5 不同算法平均覆蓋率對(duì)比

為了驗(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)樵诤笃谑Ｓ辔锤采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)越性。

4 結(jié)論

針對(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)于其他兩種算法性能。