摘 要： "考慮到在多機(jī)器人巡邏任務(wù)中，待訪問(wèn)節(jié)點(diǎn)的重要程度存在差異是一種普遍現(xiàn)象，針對(duì)多數(shù)巡邏算法沒(méi)有考慮節(jié)點(diǎn)重要程度的不同，導(dǎo)致所有節(jié)點(diǎn)的空閑時(shí)間趨于一致，從而造成重要節(jié)點(diǎn)訪問(wèn)頻次不足、普通節(jié)點(diǎn)過(guò)度訪問(wèn)的問(wèn)題，提出了一種基于節(jié)點(diǎn)重要度的分布式巡邏策略以?xún)?yōu)化節(jié)點(diǎn)訪問(wèn)頻率、降低全局平均空閑時(shí)間。 機(jī)器人計(jì)算周?chē)?jié)點(diǎn)空閑時(shí)間與重要度，在線(xiàn)決策目標(biāo)節(jié)點(diǎn)，估計(jì)到達(dá)目標(biāo)節(jié)點(diǎn)的時(shí)刻，并且將訪問(wèn)目標(biāo)與估計(jì)到達(dá)時(shí)刻告知附近的同伴；為了避免某些節(jié)點(diǎn)被過(guò)度訪問(wèn)，在邊緣節(jié)點(diǎn)的被訪問(wèn)頻率低于最小訪問(wèn)頻率時(shí)提高邊緣節(jié)點(diǎn)的重要度，使得機(jī)器人可以盡快訪問(wèn)該點(diǎn)。最后，通過(guò)仿真分析機(jī)器人數(shù)量、環(huán)境變化、重要度等因素對(duì)機(jī)器人完成持續(xù)巡邏任務(wù)的影響。結(jié)果表明，重要度大的節(jié)點(diǎn)被訪問(wèn)次數(shù)明顯增加；在巡邏環(huán)境與機(jī)器人數(shù)量相同的前提下，該算法的異常值較少且平均空閑時(shí)間較小，多機(jī)器人持續(xù)巡邏性能表現(xiàn)較好。

關(guān)鍵詞： "節(jié)點(diǎn)重要度； 分布式； 多機(jī)器人系統(tǒng)； 持續(xù)巡邏

中圖分類(lèi)號(hào)： "TP242 """文獻(xiàn)標(biāo)志碼： A

文章編號(hào)： "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 引言

多機(jī)器人巡邏是指為了監(jiān)視或者保護(hù)特定環(huán)境的變化情況，使用多個(gè)機(jī)器人不斷地前往該特定環(huán)境的一種任務(wù)形式［1］。多機(jī)器人巡邏在現(xiàn)實(shí)生活中有著廣泛的應(yīng)用，例如監(jiān)控［2］、偵測(cè)、排雷等軍事領(lǐng)域或者檢測(cè)火災(zāi)以及危險(xiǎn)物質(zhì)的泄露。評(píng)價(jià)標(biāo)準(zhǔn)一般為整個(gè)環(huán)境節(jié)點(diǎn)的平均空閑時(shí)間最小和機(jī)器人系統(tǒng)的平均通勤時(shí)間最小。

在研究初期，大部分研究工作主要是針對(duì)集中式策略展開(kāi)的［3］，隨著應(yīng)用場(chǎng)景逐漸變得復(fù)雜化，研究重心開(kāi)始向分布式的多機(jī)器人系統(tǒng)轉(zhuǎn)變。在集中式系統(tǒng)中，所有機(jī)器人都連接到中央服務(wù)器，每個(gè)機(jī)器人將收集其本地信息并將此數(shù)據(jù)傳輸?shù)街醒敕?wù)器；該系統(tǒng)的缺點(diǎn)主要是對(duì)服務(wù)器的功能依賴(lài)性，因?yàn)榉?wù)器功能的失敗將導(dǎo)致整個(gè)系統(tǒng)崩潰［4］。而分布式機(jī)制系統(tǒng)中每個(gè)機(jī)器人都帶有數(shù)量不一的傳感器，通過(guò)傳感器來(lái)收集每個(gè)機(jī)器人周?chē)沫h(huán)境信息并進(jìn)行相應(yīng)的數(shù)據(jù)分析和計(jì)算，最后達(dá)到整體效果，整個(gè)過(guò)程并沒(méi)有整體或者全局的概念，所以分布式策略具有更好的容錯(cuò)性和可擴(kuò)展性［5］。

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

在之前的研究結(jié)果中，每個(gè)節(jié)點(diǎn)的重要程度是相同的［13］，這與現(xiàn)實(shí)環(huán)境不符。一方面，在實(shí)際環(huán)境中本來(lái)就有重要節(jié)點(diǎn)和次要節(jié)點(diǎn)的區(qū)分，例如在交通運(yùn)輸領(lǐng)域，有重要的交通樞紐，還有連接較少的邊緣站，當(dāng)重要節(jié)點(diǎn)連接在一起時(shí)就構(gòu)成了重要區(qū)域；另一方面，在外部條件發(fā)生改變時(shí)，節(jié)點(diǎn)甚至區(qū)域的重要度也會(huì)發(fā)生變化，例如發(fā)生火災(zāi)時(shí)，著火地點(diǎn)成為優(yōu)先考慮的節(jié)點(diǎn)，重要度也隨之增加。本文綜合節(jié)點(diǎn)的空閑時(shí)間和重要程度，提出了一種基于節(jié)點(diǎn)重要度不同的多機(jī)器人分布式巡邏策略。

1 問(wèn)題描述

1.1 分布式實(shí)現(xiàn)

每個(gè)機(jī)器人的決策由信息共享和行為決策兩部分組成。包含信息共享的協(xié)同決策過(guò)程如圖1所示。信息共享與行為決策可以分離，如圖2所示，在信息共享階段，機(jī)器人通過(guò)自身的觀測(cè)和通信獲取信息，組成自己的本地知識(shí)庫(kù)，然后將信息與其他機(jī)器人通信，機(jī)器人的通信行為通過(guò)影響團(tuán)隊(duì)其他成員的本地庫(kù)從而影響整個(gè)團(tuán)隊(duì)的信息分布情況，最終實(shí)現(xiàn)一個(gè)較好的信息覆蓋；在行為決策階段，輸入為自身的本地知識(shí)庫(kù)，輸出為機(jī)器人的行為決策，使得機(jī)器人團(tuán)隊(duì)可以更好地完成任務(wù)。圖3為機(jī)器人通信拓?fù)鋱D，每個(gè)機(jī)器人與自己相鄰最近的同伴進(jìn)行雙向通信。

1.2 環(huán)境建模

巡邏環(huán)境用無(wú)向拓?fù)鋱D來(lái)表示，記為 G=（V，E） ，其中 V={v 1，v 2，…，v n} 為頂點(diǎn)集， E={e i，j} 為邊的集合。在本文中，考慮用 m 個(gè)機(jī)器人 R={r 1，r 2，…，r m} 訪問(wèn) n 個(gè)頂點(diǎn)來(lái)實(shí)現(xiàn)巡邏任務(wù)。

由實(shí)際情況可知，當(dāng)環(huán)境中節(jié)點(diǎn)所連接的邊的數(shù)量越多，則該點(diǎn)越重要。環(huán)境中節(jié)點(diǎn)初始重要度可用 α 來(lái)表示，根據(jù)節(jié)點(diǎn)鄰接的邊數(shù)來(lái)分級(jí)確定。在巡邏過(guò)程中，為了避免地圖上存在長(zhǎng)時(shí)間未訪問(wèn)的節(jié)點(diǎn)，當(dāng)節(jié)點(diǎn)的被訪問(wèn)頻率為全局最低時(shí)，可依據(jù)附加重要度 β 來(lái)提高該點(diǎn)的重要度，使機(jī)器人盡快訪問(wèn)該點(diǎn)。則頂點(diǎn) v i 的綜合重要度為

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

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

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

則 ω min= min {ω i，i∈（1，n）} 為節(jié)點(diǎn)的最小被訪問(wèn)頻率。

在巡邏策略研究中，為了評(píng)估巡邏算法的性能，節(jié)點(diǎn)的空閑時(shí)間是一個(gè)較為重要的衡量標(biāo)準(zhǔn)［5］?？臻e時(shí)間表示機(jī)器人團(tuán)隊(duì)對(duì)同一頂點(diǎn)的連續(xù)兩次訪問(wèn)的時(shí)間之差。若頂點(diǎn) v i∈V 在 ti k 時(shí)刻被機(jī)器人訪問(wèn)，則頂點(diǎn) v i 的瞬時(shí)空閑時(shí)間為

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

其中： k 表示頂點(diǎn) v i 從巡邏開(kāi)始到 ti k時(shí)刻被訪問(wèn)的次數(shù)，ti k-1表示頂點(diǎn)v i 上一次被機(jī)器人訪問(wèn)的時(shí)刻。則頂點(diǎn) v i在ti k 時(shí)刻的平均空閑時(shí)間為

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

拓?fù)鋱D G=（V，E） 的全局平均空閑時(shí)間［14］為

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

巡邏任務(wù)開(kāi)始時(shí)所有頂點(diǎn)的空閑時(shí)間設(shè)為0。在巡邏過(guò)程中，另一個(gè)重要的衡量標(biāo)準(zhǔn)為機(jī)器人的總巡邏面積與環(huán)境面積之比，即

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

其中： S 為環(huán)境面積， s i 為單個(gè)機(jī)器人的巡邏面積，顯然 ηlt;1 。

每個(gè)機(jī)器人根據(jù)周?chē)鷻C(jī)器人的信息共享以及自身的本地觀測(cè)來(lái)計(jì)算節(jié)點(diǎn)的空閑時(shí)間，同時(shí)考慮頂點(diǎn)的不確定度來(lái)確定下一個(gè)要訪問(wèn)的節(jié)點(diǎn)。

2 基于節(jié)點(diǎn)重要度不同的分布式巡邏策略

本文考慮已知環(huán)境下機(jī)器人的巡邏效果，因此，整個(gè)環(huán)境的拓?fù)鋱D以及節(jié)點(diǎn)的初始重要度作為基本信息存儲(chǔ)于每個(gè)機(jī)器人的數(shù)據(jù)庫(kù)中。巡邏決策時(shí)，每個(gè)機(jī)器人計(jì)算與所在節(jié)點(diǎn)相鄰的節(jié)點(diǎn)的空閑時(shí)間，結(jié)合考慮節(jié)點(diǎn)的重要程度，然后確定擬訪問(wèn)的下一個(gè)節(jié)點(diǎn)。

在機(jī)器人周?chē)?jié)點(diǎn)中，如果存在某一點(diǎn)的空閑時(shí)間為0，表示該點(diǎn)在巡邏開(kāi)始后還未被機(jī)器人訪問(wèn)，因此機(jī)器人優(yōu)先訪問(wèn)這類(lèi)節(jié)點(diǎn)。當(dāng)空閑時(shí)間為0的節(jié)點(diǎn)只有一個(gè)時(shí)，選擇該節(jié)點(diǎn)作為下一節(jié)點(diǎn)。當(dāng)空閑時(shí)間為0的節(jié)點(diǎn)多余一個(gè)時(shí)，選擇重要度較大的節(jié)點(diǎn)作為擬訪問(wèn)節(jié)點(diǎn)，即

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

而當(dāng)周?chē)?jié)點(diǎn)的空閑時(shí)間均不為0時(shí)，機(jī)器人 r 確定下一個(gè)訪問(wèn)頂點(diǎn) v j 的效用函數(shù) U（v j，t） 為

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

若某一節(jié)點(diǎn) v j 同時(shí)被兩個(gè)或者多個(gè)機(jī)器人確定為下一個(gè)目標(biāo)點(diǎn)，此時(shí)機(jī)器人在彼此的通信范圍內(nèi)。機(jī)器人計(jì)算各自距離目標(biāo)節(jié)點(diǎn)的距離，記為 dist（r m） ，則機(jī)器人 r m 到達(dá)節(jié)點(diǎn) v j 的時(shí)間 t j m 為

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

其中： vel 表示機(jī)器人的速度， t 為當(dāng)前時(shí)刻。

如果 t j m 均不相等，機(jī)器人到達(dá)節(jié)點(diǎn) v j 的時(shí)間不同，即機(jī)器人之間不存在干擾，則機(jī)器人依次訪問(wèn)該節(jié)點(diǎn)；如果存在兩個(gè)或者多個(gè)機(jī)器人 t j m 相等，則兩個(gè)機(jī)器人同時(shí)到達(dá)節(jié)點(diǎn) v j ，那么從節(jié)點(diǎn) v j 開(kāi)始，兩個(gè)機(jī)器人將作出相同的決策，訪問(wèn)相同的節(jié)點(diǎn)，造成了資源的浪費(fèi)。為了避免出現(xiàn)這種情況，此時(shí)效用函數(shù) 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） 表示機(jī)器人當(dāng)前所在節(jié)點(diǎn)的空閑時(shí)間。

為了考慮邊緣節(jié)點(diǎn)，避免訪問(wèn)區(qū)域過(guò)于集中在重要節(jié)點(diǎn)附近，則在巡邏周期 [0，T] 內(nèi)，若某一節(jié)點(diǎn) v j 的被訪問(wèn)頻率等于最小被訪問(wèn)頻率，則提高 v j 的附加重要度，即

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

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

使得機(jī)器人可以盡快訪問(wèn)該點(diǎn)。

綜上可知，本文所提出的巡邏策略中，機(jī)器人選擇效用函數(shù)最大值的頂點(diǎn)作為目標(biāo)訪問(wèn)點(diǎn)，在計(jì)算效用函數(shù)的過(guò)程中，考慮了下一節(jié)點(diǎn)的重要度（importance of nodes）。本文巡邏策略簡(jiǎn)稱(chēng)為NDI，其偽代碼如下所示：

基于節(jié)點(diǎn)重要度不同的分布式巡邏算法

initialization """""""http:// 初始化空閑時(shí)間表，訪問(wèn)頻率表

while true do

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

γ j=（α j+β j） ； """""""""http://計(jì)算鄰居節(jié)點(diǎn)的綜合重要度

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

//計(jì)算鄰居節(jié)點(diǎn)的空閑時(shí)間

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

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

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:// 考慮邊緣節(jié)點(diǎn)

β j=α j ；

else

β j=0 ；

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

// 選擇效用函數(shù)最大的鄰居節(jié)點(diǎn)作為訪問(wèn)節(jié)點(diǎn)

end for

publish intention message （v j+1） ； "http:// 機(jī)器人發(fā)布目標(biāo)點(diǎn)信息

move to vertex "v j+1 "to "r ； """""http:// 機(jī)器人向目標(biāo)點(diǎn)移動(dòng)

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

publish message of arrival "v j+1 ； """"http:// 發(fā)布到達(dá)信息

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

update "ω min ； """"""""""""http:// 更新最小訪問(wèn)頻率

end while

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

end while

end

3 仿真實(shí)驗(yàn)及結(jié)果分析

為了更好地檢驗(yàn)算法性能，在ROS環(huán)境中進(jìn)行仿真實(shí)驗(yàn)。本文在兩種巡邏場(chǎng)景圖中測(cè)試所提出的算法，如圖4所示，藍(lán)色的圓圈為環(huán)境當(dāng)中的節(jié)點(diǎn)（參見(jiàn)電子版）。這兩個(gè)拓?fù)鋱D具有不同的代數(shù)連通性，即 λ ，顯然，Cumberland地圖的連通性比Grid地圖的差［14］。表1描述了兩個(gè)拓?fù)鋱D的具體細(xì)節(jié)。

根據(jù)地圖中每個(gè)節(jié)點(diǎn)相鄰節(jié)點(diǎn)的數(shù)量，將兩個(gè)拓?fù)鋱D中的各個(gè)節(jié)點(diǎn)的初始重要度分為0.3、0.6和1，初始重要度為1表示節(jié)點(diǎn)鄰接邊數(shù)最多，0.3表示最少，如表2和3所示。基于上述巡邏環(huán)境拓?fù)鋱D，在機(jī)器人數(shù)量分別為4、8、12時(shí)進(jìn)行仿真實(shí)驗(yàn)。在實(shí)驗(yàn)過(guò)程中機(jī)器人的平均速度為1 m/s，巡邏半徑為3 m，每組仿真實(shí)驗(yàn)持續(xù)1 h。

為了分析不同重要度節(jié)點(diǎn)的訪問(wèn)頻率，分別在時(shí)間 t =1000 s、2000 s、3000 s時(shí)統(tǒng)計(jì)重要度不同的節(jié)點(diǎn)的平均訪問(wèn)次數(shù)，結(jié)果如表4和5所示。由表4、5可知，重要度較高的節(jié)點(diǎn)平均訪問(wèn)次數(shù)較高，重要度較低的節(jié)點(diǎn)平均訪問(wèn)次數(shù)較低，在巡邏時(shí)間較短時(shí)，有部分節(jié)點(diǎn)的被訪問(wèn)次數(shù)為0，但隨著迭代次數(shù)的增加，邊緣節(jié)點(diǎn)的被訪問(wèn)頻率會(huì)增加。

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

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

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

4 結(jié)束語(yǔ)

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

之后的工作將考慮節(jié)點(diǎn)重要度改變時(shí)如何被機(jī)器人盡快的獲??；仿真環(huán)境中入侵者模型的描述；如何提高檢測(cè)入侵者的概率；入侵者被檢測(cè)到之后機(jī)器人系統(tǒng)的重構(gòu)等問(wèn)題。

參考文獻(xiàn)：

［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］ 袁國(guó)棟，李宗剛，杜亞江，等.基于Voronoi和虛擬力的多機(jī)器人持續(xù)監(jiān)控研究［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，F(xiàn)arges 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，F(xiàn)ranchi 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］ 趙云濤，李宗剛，杜亞江.基于最大空閑時(shí)間的分布式巡邏機(jī)器人數(shù)量?jī)?yōu)化［J］.模式識(shí)別與人工智能，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.