基于節點重要度的多機器人分布式巡邏策略

摘 要： "考慮到在多機器人巡邏任務中，待訪問節點的重要程度存在差異是一種普遍現象，針對多數巡邏算法沒有考慮節點重要程度的不同，導致所有節點的空閑時間趨于一致，從而造成重要節點訪問頻次不足、普通節點過度訪問的問題，提出了一種基于節點重要度的分布式巡邏策略以優化節點訪問頻率、降低全局平均空閑時間。 機器人計算周圍節點空閑時間與重要度，在線決策目標節點，估計到達目標節點的時刻，并且將訪問目標與估計到達時刻告知附近的同伴；為了避免某些節點被過度訪問，在邊緣節點的被訪問頻率低于最小訪問頻率時提高邊緣節點的重要度，使得機器人可以盡快訪問該點。最后，通過仿真分析機器人數量、環境變化、重要度等因素對機器人完成持續巡邏任務的影響。結果表明，重要度大的節點被訪問次數明顯增加；在巡邏環境與機器人數量相同的前提下，該算法的異常值較少且平均空閑時間較小，多機器人持續巡邏性能表現較好。

關鍵詞： "節點重要度； 分布式； 多機器人系統； 持續巡邏

中圖分類號： "TP242 """文獻標志碼： A

文章編號： "1001-3695（2022）02-028-0001-00

doi：10.19734/j.issn.1001-3695.2021.06.0301

Distributed multi-robot patrolling strategy based on importance of nodes

Huo Yaoyan1a，1b， Li Zonggang1a，1b， Gao Pu1b，2

（1.a.School of Mechanical Engineering， b.Robotics Institute， Lanzhou Jiaotong University， Lanzhou 730070， China； 2.Lanzhou Petrochemical College of Vocational Technology， Lanzhou 730060， China）

Abstract： "Considering that in the multi-robot patrol task，it is a common phenomenon that the importance of the nodes to be visited is different.In view of the fact that most patrolling algorithms don’t consider the difference in the importance of nodes，the idle time of all nodes tends to be the same，it causes the problem of insufficient access frequency of important nodes and excessive access of ordinary nodes.This paper proposed a distributed patrolling strategy based on nodes’ importance to optimize node access frequency and reduce the global average idle time.The robot calculated the idle time and importance of surrounding nodes，online decided the target node，estimated the time of reaching the target node，and informed nearby companions of the target node and estimated time of arrival.The robot increased the importance of the edge node in order to prevent some nodes from being over-visited，when the access frequency of the edge node was lower than the minimum access frequency，so that the robot could visit the node as soon as possible.Finally，this paper analyzed the influence of factors on the completion of continuous patrolling tasks of robots through simulation on the number of robots，changing environment，the importance of nodes and other factors.The results show that the number of visits to the most important nodes has increased significantly.Moreover，under the premise of the same patrolling environment and number of robots，the algorithm has fewer outliers and smaller average idle time，and the performance of multi-robot continuous patrolling is better.

Key words： "importance of nodes； distributed； multi-robot system； continuous patrolling

0 引言

多機器人巡邏是指為了監視或者保護特定環境的變化情況，使用多個機器人不斷地前往該特定環境的一種任務形式［1］。多機器人巡邏在現實生活中有著廣泛的應用，例如監控［2］、偵測、排雷等軍事領域或者檢測火災以及危險物質的泄露。評價標準一般為整個環境節點的平均空閑時間最小和機器人系統的平均通勤時間最小。

在研究初期，大部分研究工作主要是針對集中式策略展開的［3］，隨著應用場景逐漸變得復雜化，研究重心開始向分布式的多機器人系統轉變。在集中式系統中，所有機器人都連接到中央服務器，每個機器人將收集其本地信息并將此數據傳輸到中央服務器；該系統的缺點主要是對服務器的功能依賴性，因為服務器功能的失敗將導致整個系統崩潰［4］。而分布式機制系統中每個機器人都帶有數量不一的傳感器，通過傳感器來收集每個機器人周圍的環境信息并進行相應的數據分析和計算，最后達到整體效果，整個過程并沒有整體或者全局的概念，所以分布式策略具有更好的容錯性和可擴展性［5］。

分布式協調策略主要有反應策略和基于拍賣的策略。反應策略［6］是指機器人從其領域中選擇空閑時間最大的節點作為下一個節點，如果機器人之間能夠通過標志或廣播進行通信并獲得共享的空閑信息，則性能要優于非通信情況，在非通信情況下，機器人只能訪問自己的本地圖和單獨的空閑信息。Pasqualetti等人［7］將圖與環境相關聯，考慮刷新時間和等待時間作為性能標準，即分別考慮相同區域的任何兩次訪問之間的時間間隔以及通知每個機器人有關環境中發生的事件所需的時間，設計了具有最佳特性的開環軌跡，同時提出了收斂到最佳軌跡的分布式控制律。Portugal等人［8，9］提出了貪婪貝葉斯策略（greedy Bayesian strategy，GBS）和狀態交換貝葉斯策略（state exchange Bayesian strategy，SEBS）。在GBS中，機器人以最大限度地提高自身的局部增益為目的，獨立于隊友進行決策，忽略了巡邏任務的全局目標；而在SEBS中，考慮其他機器人的意圖信息，從而有效地避免了沖突，在性能和可擴展性上優于GBS?；谂馁u的方法［10］是機器人之間基于自由消息交換的協商機制的實現，Nunes等人［11］將任務分配問題融入到多機器人巡邏問題中，提出了基線貪婪算法（dynamic task assignment greedy，DTAG）和基于順序單物品拍賣算法（dynamic task assignment problem，DTAP）兩種解決方法。Portugal等人［8］比較了五種傳統巡邏算法（CR、HCR、HPCC、CGG、MSP）的優劣性，提出了被訪問節點的瞬時空閑度和平均空閑時間等概念，并以平均空閑時間為評價指標考慮了每種算法的方差及其收斂時間。趙云濤等人［12］基于全局平均最大空閑時間提出了一種分布式巡邏算法，對巡邏問題中機器人的數量進行了優化。

在之前的研究結果中，每個節點的重要程度是相同的［13］，這與現實環境不符。一方面，在實際環境中本來就有重要節點和次要節點的區分，例如在交通運輸領域，有重要的交通樞紐，還有連接較少的邊緣站，當重要節點連接在一起時就構成了重要區域；另一方面，在外部條件發生改變時，節點甚至區域的重要度也會發生變化，例如發生火災時，著火地點成為優先考慮的節點，重要度也隨之增加。本文綜合節點的空閑時間和重要程度，提出了一種基于節點重要度不同的多機器人分布式巡邏策略。

1 問題描述

1.1 分布式實現

每個機器人的決策由信息共享和行為決策兩部分組成。包含信息共享的協同決策過程如圖1所示。信息共享與行為決策可以分離，如圖2所示，在信息共享階段，機器人通過自身的觀測和通信獲取信息，組成自己的本地知識庫，然后將信息與其他機器人通信，機器人的通信行為通過影響團隊其他成員的本地庫從而影響整個團隊的信息分布情況，最終實現一個較好的信息覆蓋；在行為決策階段，輸入為自身的本地知識庫，輸出為機器人的行為決策，使得機器人團隊可以更好地完成任務。圖3為機器人通信拓撲圖，每個機器人與自己相鄰最近的同伴進行雙向通信。

1.2 環境建模

巡邏環境用無向拓撲圖來表示，記為 G=（V，E） ，其中 V={v 1，v 2，…，v n} 為頂點集， E={e i，j} 為邊的集合。在本文中，考慮用 m 個機器人 R={r 1，r 2，…，r m} 訪問 n 個頂點來實現巡邏任務。

由實際情況可知，當環境中節點所連接的邊的數量越多，則該點越重要。環境中節點初始重要度可用 α 來表示，根據節點鄰接的邊數來分級確定。在巡邏過程中，為了避免地圖上存在長時間未訪問的節點，當節點的被訪問頻率為全局最低時，可依據附加重要度 β 來提高該點的重要度，使機器人盡快訪問該點。則頂點 v i 的綜合重要度為

γ i=（α i+β i） ""（1）

初始時刻，地圖 G=（V，E） 及每個節點的綜合重要度γ已知并且被所有機器人預先知道。在目前的分布式場景中，每個機器人 r i 在到達頂點 v i 的時候與鄰域機器人交互信息，包括所訪問的節點和時刻，然后更新自己的數據庫。機器人 r i 在環境中獲得的信息為［ v i ，ti 1，…， ti k，k i ；］。其中， ti k 表示機器人第 k 次訪問頂點 v i 的時刻， k i 表示頂點 v i 的被訪問次數。則在一個巡邏周期 [0，T] 內，頂點 v i 的被訪問頻率 ω i 為

ω i=k i/T ""（2）

則 ω min= min {ω i，i∈（1，n）} 為節點的最小被訪問頻率。

在巡邏策略研究中，為了評估巡邏算法的性能，節點的空閑時間是一個較為重要的衡量標準［5］?？臻e時間表示機器人團隊對同一頂點的連續兩次訪問的時間之差。若頂點 v i∈V 在 ti k 時刻被機器人訪問，則頂點 v i 的瞬時空閑時間為

I（v i，ti k）=ti k-ti k-1 ""（3）

其中： k 表示頂點 v i 從巡邏開始到 ti k時刻被訪問的次數，ti k-1表示頂點v i 上一次被機器人訪問的時刻。則頂點 v i在ti k 時刻的平均空閑時間為

I avg （v i，ti k）= （k-1）I avg（v i，ti k-1）+I（v i，ti k） k """（4）

拓撲圖 G=（V，E） 的全局平均空閑時間［14］為

IG avg（t k）= 1 m ∑ m i=1 I avg（v i，ti k） ""（5）

巡邏任務開始時所有頂點的空閑時間設為0。在巡邏過程中，另一個重要的衡量標準為機器人的總巡邏面積與環境面積之比，即

η=∑ m i=1 s i/S ""（6）

其中： S 為環境面積， s i 為單個機器人的巡邏面積，顯然 ηlt;1 。

每個機器人根據周圍機器人的信息共享以及自身的本地觀測來計算節點的空閑時間，同時考慮頂點的不確定度來確定下一個要訪問的節點。

2 基于節點重要度不同的分布式巡邏策略

本文考慮已知環境下機器人的巡邏效果，因此，整個環境的拓撲圖以及節點的初始重要度作為基本信息存儲于每個機器人的數據庫中。巡邏決策時，每個機器人計算與所在節點相鄰的節點的空閑時間，結合考慮節點的重要程度，然后確定擬訪問的下一個節點。

在機器人周圍節點中，如果存在某一點的空閑時間為0，表示該點在巡邏開始后還未被機器人訪問，因此機器人優先訪問這類節點。當空閑時間為0的節點只有一個時，選擇該節點作為下一節點。當空閑時間為0的節點多余一個時，選擇重要度較大的節點作為擬訪問節點，即

U（v j，t）=γ j-I avg（v j，t j k） "if "I avg（v j，t j k）=0 ""（7）

而當周圍節點的空閑時間均不為0時，機器人 r 確定下一個訪問頂點 v j 的效用函數 U（v j，t） 為

U（v j，t）=I avg（v j，t j k）γ j ""（8）

若某一節點 v j 同時被兩個或者多個機器人確定為下一個目標點，此時機器人在彼此的通信范圍內。機器人計算各自距離目標節點的距離，記為 dist（r m） ，則機器人 r m 到達節點 v j 的時間 t j m 為

t j m=t+ "dist （r m） vel """（9）

其中： vel 表示機器人的速度， t 為當前時刻。

如果 t j m 均不相等，機器人到達節點 v j 的時間不同，即機器人之間不存在干擾，則機器人依次訪問該節點；如果存在兩個或者多個機器人 t j m 相等，則兩個機器人同時到達節點 v j ，那么從節點 v j 開始，兩個機器人將作出相同的決策，訪問相同的節點，造成了資源的浪費。為了避免出現這種情況，此時效用函數 U（v j，t） 為

U（v j，t）= （I avg（v j，t j k）+t j m）γ j I avg（v i，ti k） """（10）

其中： I avg（v i，ti k） 表示機器人當前所在節點的空閑時間。

為了考慮邊緣節點，避免訪問區域過于集中在重要節點附近，則在巡邏周期 [0，T] 內，若某一節點 v j 的被訪問頻率等于最小被訪問頻率，則提高 v j 的附加重要度，即

β j= "α j "if "ω j=ω min

0 "if "ω j≠ω min """"（11）

使得機器人可以盡快訪問該點。

綜上可知，本文所提出的巡邏策略中，機器人選擇效用函數最大值的頂點作為目標訪問點，在計算效用函數的過程中，考慮了下一節點的重要度（importance of nodes）。本文巡邏策略簡稱為NDI，其偽代碼如下所示：

基于節點重要度不同的分布式巡邏算法

initialization """""""http:// 初始化空閑時間表，訪問頻率表

while true do

for all "v j∈neigh（v i） "do

γ j=（α j+β j） ； """""""""http://計算鄰居節點的綜合重要度

I avg（v j，ti k）= （k-1）·I avg （v j，t j k-1）+I（v j，t j k） k "；

//計算鄰居節點的空閑時間

if "I avg（v j，t j k）=0

U（v j，t）=γ j-I avg（v j，t j k） ； ""http://計算 v j 的效用函數

else

U（v j，t）=I avg（v j，t j k）·γ j ；

end if

if "t j m1=t j m2

U（v j，t）= （I avg（v j，t j k）+t j r）·γ j I avg（v i，ti k） "；

end if

if "ω j=ω min """""""""""""http:// 考慮邊緣節點

β j=α j ；

else

β j=0 ；

v j+1←argmax（U，（v j，t）） ；

// 選擇效用函數最大的鄰居節點作為訪問節點

end for

publish intention message （v j+1） ； "http:// 機器人發布目標點信息

move to vertex "v j+1 "to "r ； """""http:// 機器人向目標點移動

while "r "reached "v j+1 "do

publish message of arrival "v j+1 ； """"http:// 發布到達信息

update idleness （v） ； """""""""http:// 更新空閑時間

update "ω min ； """"""""""""http:// 更新最小訪問頻率

end while

v i←v k+1 ； "nbsp;""""""""""""""""http:// 初始位置更新

end while

end

3 仿真實驗及結果分析

為了更好地檢驗算法性能，在ROS環境中進行仿真實驗。本文在兩種巡邏場景圖中測試所提出的算法，如圖4所示，藍色的圓圈為環境當中的節點（參見電子版）。這兩個拓撲圖具有不同的代數連通性，即 λ ，顯然，Cumberland地圖的連通性比Grid地圖的差［14］。表1描述了兩個拓撲圖的具體細節。

根據地圖中每個節點相鄰節點的數量，將兩個拓撲圖中的各個節點的初始重要度分為0.3、0.6和1，初始重要度為1表示節點鄰接邊數最多，0.3表示最少，如表2和3所示?；谏鲜鲅策壄h境拓撲圖，在機器人數量分別為4、8、12時進行仿真實驗。在實驗過程中機器人的平均速度為1 m/s，巡邏半徑為3 m，每組仿真實驗持續1 h。

為了分析不同重要度節點的訪問頻率，分別在時間 t =1000 s、2000 s、3000 s時統計重要度不同的節點的平均訪問次數，結果如表4和5所示。由表4、5可知，重要度較高的節點平均訪問次數較高，重要度較低的節點平均訪問次數較低，在巡邏時間較短時，有部分節點的被訪問次數為0，但隨著迭代次數的增加，邊緣節點的被訪問頻率會增加。

此外，隨著機器人數量的增加各個節點的被訪問次數增加，但是機器人數量的增加還會導致機器人之間干擾率上升，由圖5（c）（d）可知，當機器人從12增加為14時，節點的平均被訪問次數基本相同，增長不明顯；圖5（h）表明在Grid地圖中，機器人數量為14時不同重要度節點的平均被訪問次數趨于一致，而且低于機器人數量較小時的平均被訪問次數，機器人之間干擾程度增加，巡邏效果下降。

為了研究所提算法的有效性，將所提出的算法與GBS、DTAP、HPCC、EGMI等巡邏算法進行比較。圖6是對不同巡邏算法下不同節點的空閑時間的統計分析結果。在連通性更好的Grid地圖中，各個算法的整體平均空閑時間明顯少于Cumberland且異常值較小。當機器人數量較少時，各個算法的空閑時間較大，且異常值分布較為分散。隨著機器人數量的增加，節點的平均空閑時間有顯著降低。當機器人數量較小為4、8時，DTAP算法的節點平均空閑時間較小，隨著機器人數量的增加，該算法的空閑時間異常值明顯增多且較為分散，如圖6（a）（c）所示。HPCC算法雖然平均空閑時間表現較好，依舊存在異常值較多的問題。在Cumberland地圖中，當機器人數量為12時，EGMI節點的平均空閑時間較少，而當機器人數量為14時，本文算法與EGMI的平均空閑時間大致相當但EGMI的異常值明顯多于NDI。在Grid地圖中，NDI在機器人數量為12、14時節點空閑時間較小，表明該算法更適合機器人數量較多時的巡邏。

圖7比較了各個算法不同 η 下的全局平均空閑時間，在Cumberland中，HPCC在 η 較低時表現較好，而NDI、DTAP、GBS更適合于 η 較大的巡邏任務；而在Grid地圖中，NDI的全局平均空閑時間最低，巡邏性能較好。

4 結束語

本文考慮了不同重要度節點情況下的巡邏問題，提出了一種基于節點重要度不同的多機器人持續巡邏算法，提高了在地圖中重要程度較高、空閑時間較大的節點的訪問頻率。機器人根據當前節點的信息，根據所提出的策略選擇下一個節點，從而降低全局的平均空閑時間。然后在ROS環境中進行仿真。結果表明，本文所提出的算法相比于其他算法在節點的空閑時間下降的基礎上，重要節點上的訪問頻率要高于普通節點。由此可知，本文提出的算法更符合實際環境的需要，因此具有更佳的巡邏性能。

之后的工作將考慮節點重要度改變時如何被機器人盡快的獲??；仿真環境中入侵者模型的描述；如何提高檢測入侵者的概率；入侵者被檢測到之后機器人系統的重構等問題。

參考文獻：

［1］ "Talmor N，Agmon N.On the power and limitations of deception in multi-robot adversarial patrolling［C］//Proc of the 26th International Joint Conference on Artificial Intelligence.Palo Alto，CA：AAAI Press，2017：430-436.

［2］ 袁國棟，李宗剛，杜亞江，等.基于Voronoi和虛擬力的多機器人持續監控研究［J］.控制工程，2021， 28 （9）：1842-1849. （Yuan Guodong，Li Zonggang，Du Yajiang， et al .Research on persistent monitoring of multi-robot systems based on Voronoi and virtual force［J］. Control Engineering of China ，2021， 28 （9）：1842-1849.）

［3］ Wiandt B，Simon V，Kokuti A.Self-organized graph partitioning approach for multi-agent patrolling in generic graphs［C］//Proc of the 17th International Conference on Smart Technologies.Piscataway，NJ：IEEE Press，2017：605-610.

［4］ Othmani-Guibourg M，El Fallah-Seghrouchni A，Farges J L， et al .Multi-agent patrolling in dynamic environments［C］//Proc of IEEE International Conference on Agents.Piscataway，NJ：IEEE Press，2017：72-77.

［5］ Portugal D，Couceiro M S，Rocha R P.Applying Bayesian learning to multi-robot patrol［C］//Proc of IEEE International Symposium on Safety，Security，and Rescue Robotics.Piscataway，NJ：IEEE Press，2013.

［6］ Yan Chuanbo，Zhang Tao.Multi-robot patrol：a distributed algorithm based on expected idleness［J］. International Journal of Advanced Robotic Systems ，2016， 13 （6）： - .

［7］ Pasqualetti F，Franchi A，Bullo F.On cooperative patrolling：optimal trajectories，complexity analysis，and approximation algorithms［J］. IEEE Trans on Robotics ，2012， 28 （3）：592-606.

［8］ Portugal D，Rocha R P.Multi-robot patrolling algorithms：examining performance and scalability［J］. Advanced Robotics ，2013， 27 （5）：325-336.

［9］ Portugal D，Rocha R P.Distributed multi-robot patrol：A scalable and fault-tolerant framework［J］. Robotics and Autonomous Systems ，2013， 61 （12）：1572-1587.

［10］ Pippin C，Christensen H，Weiss L.Performance based task assignment in multi-robot patrolling［C］//Proc of the 28th Annual ACM Symposium on Applied Computing.New York：ACM Press，2013：70-76.

［11］ Nunes E，Marie M，Mitiche H， et al. "A taxonomy for task allocation problems with temporal and ordering constraints［J］. Robotics and Autonomous Systems ，2017， 90 （4）：55-70.

［12］ 趙云濤，李宗剛，杜亞江.基于最大空閑時間的分布式巡邏機器人數量優化［J］.模式識別與人工智能，2020， 33 （4）：375-382. （Zhao Yuntao，Li Zonggang，Du Yajiang.Team size optimization for distributed patrol of multi-robot systems based on maximum idle time［J］. Pattern Recognition and Artificial Intelligence ，2020， 33 （4）：375-382.）

［13］ Farinelli A，Iocchi L，Nardi D.Distributed on-line dynamic task assignment for multi-robot patrolling［J］. Auton Robot ，2017， 41 （8）：1321-1345.

［14］ Portugal D，Pippin C，Rocha R P， et al .Finding optimal routes for multi-robot patrolling in generic graphs［C］//Proc of IEEE/RSJ International Conference on Intelligent Robots and Systems.Piscataway，NJ：IEEE Press，2014：14-18.