復雜環境下多機器人協同覆蓋搜索路徑規劃

史萬慶， 黃鴻柳， 蔣林利

(1.商丘學院計算機工程學院，河南 商丘 476000； 2.廣西科技師范學院實驗實訓中心，廣西 來賓 546000)

0 引言

近年來，多機器人協同覆蓋因具有良好的互聯互通、態勢共享、群策群力特性，在監視、偵察、勘探和檢測等領域得到廣泛應用[1]。多機器人協同覆蓋的主要目標是通過一組感知能力有限的機器人實現對目標區域的協同覆蓋搜索[2]。為保證覆蓋區域的有效性，需考慮不同區域之間的重疊、各機器人路徑長度的差異以及執行完全覆蓋的覆蓋周期等諸多因素[3]。此外，在不規則的障礙物、不規則的任務區域等復雜環境下，多機器人協同覆蓋的復雜性會大大增加[4-5]。

與單機器人覆蓋相比，多機器人協同覆蓋具有效率高、范圍廣、持續性強等優勢[6]。由于工作量的劃分，使用多個機器人協同搜索可以有效減少完成覆蓋所需的時間成本[7]。多機器人協同通過將隊友作為信標，可實現定位誤差的最小化。此外，在多機器人協同覆蓋中，若團隊的部分成員失敗，則可以由其他機器人進行補償，可有效提高協同覆蓋的魯棒性[8]。因此，基于多機器人的協同覆蓋是目標區域搜索的主要研究方向。

為提高多機器人協同覆蓋的有效性，國內外眾多學者開展了大量研究。在以往的研究中，多機器人協同覆蓋策略主要分為集中式覆蓋和分散式覆蓋兩種。針對集中式覆蓋策略，文獻[9]提出了一種線性掃描覆蓋規劃算法，讓所有機器人成排分布，從而實現對掃描區域的最大化覆蓋，但該算法在面對不規則障礙物時，機器人團隊處理能力會迅速下降；文獻[10]提出了一種分散式多邊形分解算法，將一個給定的區域分成多邊形塊，通過明確各機器人的相對能力，確定區域劃分的比例，但該方法不能使每條路線的長度達到平衡；文獻[11]提出了一種基于改進神經網絡的路徑規劃算法，該算法利用聚類算法對目標點進行分類，通過將相似的目標進行聚集后，按規則劃分到同一個集合，但聚類節點過于整齊，未考慮機器人的局限性，不能有效縮短覆蓋周期。

綜上所述，集中式覆蓋和分散式覆蓋兩種策略均不能有效處理復雜環境中的覆蓋問題，實際應用效果不佳。因此，針對具有復雜約束的多機器人協同覆蓋搜索問題，提出了一種多機器人協同覆蓋搜索路徑規劃策略。首先，在目標區域部署傳感器，以滿足覆蓋性要求；其次，通過改進的K-means聚類算法對傳感器布置點進行分類，引入反饋機制平衡每條路徑的長度，并以部署的傳感器位置為路徑點求解旅行商問題(TSP)，獲取每個機器人的封閉路徑。最后，通過仿真實驗，驗證了所提算法的有效性。

1 多機器人覆蓋性問題描述

為簡化多機器人覆蓋處理方式，對多機器人覆蓋問題做以下簡化處理：1) 將每個機器人的檢測范圍簡化為一個圓形區域，并忽略機器人運動對感知范圍的影響；2) 機器人所攜帶傳感器的位置與機器人的位置相同；3) 將給定任務區內的無障礙區域和障礙物分布情況作為先驗信息；4) 每個機器人的動態特性均相同。

在所考慮的場景中，需要使用一組機器人對搜索區域進行覆蓋，但各機器人的感知半徑和運動學約束是有限的。此外，應該盡量縮短搜索覆蓋周期，同時避免障礙物。令機器人的覆蓋半徑為ra，目標區域Rt由可到達區域Ra和障礙物區域Ro組成，且滿足Ra∩，Ro=?。圖1為目標區域的示意圖，圖中，黑色區域表示障礙物區域，無色為可達區域。為了簡化多機器人覆蓋問題，將所研究的多機器人協同覆蓋搜索問題轉化為2個子問題：1) 如何把給定區域劃分成相應數量的子區域；2) 如何獲取子區域內每個機器人的封閉路徑。

圖1 目標區域示意圖Fig.1 Sketch map of target region

對于子問題2)，可通過傳統的路徑規劃算法解決。因此，需重點研究的是如何進行區域劃分。為解決區域劃分問題，首先，需在給定區域覆蓋一定數量的傳感器點，以滿足覆蓋要求；隨后，將這些傳感器點聚類成N個聚類，即不同的子區域；最后，在得到聚類后，通過求解旅行商問題，獲得通過聚類中所有傳感器點的路徑。

2 協同覆蓋搜索路徑規劃

2.1 傳感器部署

傳感器部署問題(Sensor Deployment Problem，SDP)主要解決如何在目標區域和期望的需求中以最小數量部署傳感器。首先，目標區域被分為一系列矩形單元格，將Cf={c1,c2,…,ci，…,cm}定義為可訪問區域Ra中的單元格集合。假設S={s1,s2,…，sj,…,sn}是傳感器的集合，其中，n為傳感器的最大數量。只有當單元格的4個頂點在傳感器sj的感測范圍內，且單元格沒有被任何障礙物阻擋時，ci才被sj完全覆蓋。根據要求，Cf中的所有單元格都需要完全覆蓋。在完全覆蓋的前提下，要求規劃路徑最短，以利于縮短覆蓋周期。

設ej=(p(sj)，gj)為傳感器sj基本部署信息，其中，p(sj)為sj的位置，gj為有效標志。若sj已部署，則令gj=1，否則gj=0。因此，部署向量矩陣[e1e2…en]表示傳感器的部署情況，即傳感器部署問題的可行解決方案。

考慮傳感器配置指標，傳感器部署問題的適應度函數可表示為

f([e1e2…en])=λ1×nd+λ2×nu+λ3×ns+λ4×no

(1)

式中：nd,nu，ns和no分別表示Ra中部署的傳感器的數量、Ra中未覆蓋的單元格數量、Ra中覆蓋的單元格數量以及Ra中重疊的單元格數量；λ1，λ2，λ3，λ4為加權權重，滿足λ1>>λ2>>λ3>>λ4>>0。

yi=xif(xi)

(2)

(3)

此時，粒子的位置和速度更新為

xi,d(t+1)=xi,d(t)+vi,d(t+1)

(4)

(5)

(6)

(7)

式中：w(t)為平衡全局和局部搜索的慣性系數；c1，c2和c3為加速度常數；Pvji為第j個粒子群的速度。

c3的數學方程為

(8)

(9)

式中,m為鄰域范圍，通過運用CCPSO2算法，得到適應度函數的最小值，從而得到傳感器最優部署向量。

2.2 改進的K-means均值聚類和區域劃分反饋機制

完成傳感器部署求解后，可得到一系列傳感器部署點S={s1,s2,…,sn}，利用聚類方法對上述傳感器部署點進行分類，能夠將更接近的相鄰點劃分到同一個類中，從而實現有效的區域劃分。由于該算法原理簡單且易于實現，本文算法中使用了經典的K-means均值算法對傳感器部署點進行聚類。在K-means算法中，通常將誤差平方函數作為準則函數，如

(10)

式中：k為簇的數量；ni為第i個聚類的數據點數量；xi j為第i個簇的第j個數據點；mi為第i個聚類所有數據點的平均值，表示為

(11)

通常，K-means算法中每個聚類的初始中心均是隨機選擇的，而這也將導致不同聚類之間存在較大的差異，甚至造成無法穩定收斂。考慮區域劃分的主要特點，采用密度法確定聚類的初始中心，以防止聚類中心過于接近。

將傳感器點x在區域F中的密度定義為與x的距離不大于特定鄰域半徑r的傳感器點的數量。圖2為傳感器點x的密度示意圖，其中，傳感器點x的密度為11，即Di(r)=11。

圖2 點x的密度示意圖Fig.2 Sketch map of the density of point x

對于密度法，首先，需要選擇一個合適的鄰域半徑r來計算每個點的密度Di(r)，并將密度最大的數據點作為第1簇c1的初始中心；其次，刪除c1鄰域半徑r內的點，并將剩余數據點中密度最大的點作為第2聚類的初始中心。為了使總完成時間最短，每個子區域中的搜索周期應該盡可能保持一致。因此，可通過對距離D(x,cj)進行加權來修改K-means算法，以此代替歐幾里德距離。加權距離被作為數據點xi j和聚類ci中心之間的距離度量，即

Di(xi j,ci,wi)=||

xi j-ci||

/wi

(12)

式中,wi為簇ci中心的距離權重。因此，修正準則函數可表示為

(13)

(14)

此時，距離權重wi可更新為

wi=wi0+Δwi=wi0-k1Δli

(15)

式中：wi0為最后時刻的距離權重;k1為反饋增益，且k1> 0。

wi和Di的變化可以表示為

(16)

2.3 基于旅行商的路徑規劃

旅行商問題(Travelling Salesman Problem,TSP)是指訪問一組區域并返回起點的最短路線問題。假設Sq={s1,s2,…,sq}為行程點集，其中si(i=1,2,…,q)為行程點，q為行程點數。令Li=[li1,li2,li j,liq],(i,j=1,2,…,q)表示距離的集合，其中,li j表示傳感器si和sj之間的距離。通常，可使用歐幾里德距離計算兩個傳感器點之間的距離。當兩個傳感器點之間不存在障礙物時，傳感器之間的距離li j可表示為歐幾里德距離。當兩個傳感器之間障礙條件下，可通過使用A*算法獲得傳感器距離li j。

根據傳感器部署點集Sq，可得到q×q的總距離矩陣Dq×q=[L1L2…Lq]。假設sqi(s1,sq)={sa，sb，sc},a，b，c為[1,q]范圍內的自然數，是傳感器部署點的序列，其中,s為點集Sq的傳感器部署點。因此，以Sq和Dq×q為已知條件，可求解旅行商問題，從而在求解區域內得到期望的解。

3 仿真實驗與分析

開展仿真實驗對本文所提算法的有效性進行驗證，實驗中采用圖1所示的目標區域，該區域面積為120 m×120 m，其中,黑色區域代表障礙物，3個多邊形障礙物分布在方形區域內。將整個區域分為2 m×2 m大小的小方塊，每個機器人的傳感范圍均設定為10 m。

3.1 傳感器部署

首先，需引進一組傳感器覆蓋目標區域，以使用CCPSO2算法求解傳感器部署問題。傳感器部署的仿真結果見圖3，其中有95個傳感器用于覆蓋整個區域。

圖3(a)中，*表示傳感器的位置，○表示傳感器的檢測范圍。由圖可知，傳感器均勻地分布在目標區域，并能有效避開障礙物。圖3(b)為CCPSO2成本迭代曲線，為提高傳感器覆蓋效率，將任務區域分解為4個子區域進行覆蓋，對應為圖3(b)中的4條曲線。由圖3(b)可知，4條曲線均呈下降趨勢，分別在經過95，91，89和92次迭代后，最終穩定在4548，4830，5208和4300處。

圖3 傳感器部署仿真結果圖Fig.3 Simulation results of sensor deployment

3.2 傳感器部署點的聚類結果

使用改進的K-means算法將獲得的傳感器部署點分類到相應的聚類中。實驗中，將任務區域劃分為z個子區域，其中，z可以根據機器人的數量進行設置。此外，在每次迭代中，使用遺傳算法求解旅行商問題，以計算每個聚類簇的路徑長度，計算結果如圖4所示。

圖4 聚類計算結果圖Fig.4 Cluster results

圖5所示為當機器人的數量k分別為3，4，5時路徑長度和距離權重曲線。

圖5 路徑長度和距離權重的曲線圖Fig.5 Curves of path length and distance weight

由圖5(a)可知，當k=3，且迭代次數大于43時每個子區域中的路徑長度逐漸收斂。同樣，由圖5(c)和圖5(e)可知，當k=4,k=5時，迭代次數的收斂范圍分別為大于等于48和大于等于35，其詳細結果如表1所示。此外，圖5(b)、圖5(d)和圖5(f)給出了與反饋增益機制相匹配的距離權重曲線。

表1 每個子區域的平均路徑長度和偏差Table 1 Average path length and deviation of each sub-region

3.3 子區域的路徑規劃

由于目標區域被分為多個子區域，因此需要規劃通過每個子區域中所有傳感器點的最短閉合路徑。本文使用歐幾里德距離計算方法和A*算法獲得通過每個子區域中所有傳感器部署點的路徑。如果兩個傳感器點之間的連接沒有通過障礙物區域，則歐幾里德距離表示它們之間的實際距離，但如果連線經過障礙物區域，則用A*算法進行距離計算。各子區域路徑規劃的最終結果如圖6所示。

圖6 各子區域路徑規劃的最終結果Fig.6 Final results of path planning for each sub-region

3.4 復雜區域仿真結果

為驗證所提協同覆蓋搜索算法對具有不規則邊界和障礙物的復雜區域的適應性，運用所提算法對不規則區域內多機器人覆蓋問題進行仿真。其中，障礙物被設置為不規則的四邊形和圓形，且目標區域為不規則的六邊形，計算結果如圖7所示。

圖7 復雜區域的仿真結果Fig.7 Simulation results of complex region

由圖7可知，共有78個傳感器用于覆蓋任務區域，且所提策略可適用于更復雜的目標區域進行多機器人協同覆蓋搜索。由于每條路線的差異非常小，表明所提出算法可有效地將任務區域劃分為大致相同的子區域。

在獲得每個子區域的路徑后，機器人可通過封閉路徑在相應區域繞行，以實現協同覆蓋搜索該區域的任務，從而保證避障效果和最小化覆蓋周期。綜上所述，所提算法具有良好的復雜環境適應性，對環境的幾何形狀幾乎沒有限制，具有較高的魯棒性。

3.5 不同算法平均覆蓋率對比

為了驗證本文所提算法的性能，將本文算法與文獻[8]和文獻[10]所提算法，在目標區域和復雜區域兩種情況下進行對比實驗，計算機器人在不同運動步數下50組實驗的平均覆蓋率，如圖8所示。

圖8 3種算法下平均覆蓋率對比Fig.8 Comparison of average coverage under the three methods

從圖8可以看出，本文所提算法較文獻[8]和文獻[10]所提算法在平均覆蓋率上有明顯提升。另外，3種算法在前中期的收斂速度較快，而在后期較為平緩，主要是因為在后期剩余未覆蓋區域較少。除此之外，從平均消耗時間上來看，本文算法的平均消耗時間為27.2 s，而文獻[8]和文獻[10]所提算法分別為32.3 s和39.4 s，由此進一步表明了本文算法的優越性。

4 結論

針對復雜任務環境下多機器人協同覆蓋搜索問題，提出了一種多機器人協同覆蓋搜索路徑規劃策略，并通過仿真實驗分析得出以下結論：1) 所提算法能夠實現多機器人的任務區域劃分，能夠根據機器人的數量進行調整，減少每個子區域中各閉合路徑之間的長度差異；2) 所提算法對環境與障礙物的幾何形狀的限制較小，能夠有效適應不規則的復雜環境條件，具有較高的魯棒性；3) 與其他算法相比，本文算法平均消耗時間為27.2 s，明顯優于其他兩種算法性能。