白耀文，杜亞江，李宗剛

(1.蘭州交通大學(xué)機(jī)電工程學(xué)院，甘肅 蘭州 730070；2.蘭州交通大學(xué)機(jī)器人研究所，甘肅 蘭州 730070)

1 引言

多機(jī)器人巡邏是指為了保護(hù)或監(jiān)控指定區(qū)域，多個(gè)機(jī)器人頻繁前往或通過(guò)該區(qū)域的行為，廣泛應(yīng)用于環(huán)境監(jiān)控、信息收集、入侵監(jiān)測(cè)及其他安全領(lǐng)域。多機(jī)器人巡邏策略主要有2種：集中式巡邏策略和分布式巡邏策略。2種巡邏策略都廣泛應(yīng)用于安防和服務(wù)等領(lǐng)域。目前多機(jī)器人巡邏研究主要集中在分布式巡邏策略，其巡邏性能主要由節(jié)點(diǎn)訪問(wèn)頻率和空閑時(shí)間來(lái)衡量[1]。

在多機(jī)器人巡邏策略研究初期，研究方向主要集中在對(duì)集中式巡邏策略的研究，即多個(gè)機(jī)器人收集環(huán)境信息并將其傳遞給中央機(jī)器人，中央機(jī)器人通過(guò)一定的數(shù)據(jù)處理后指導(dǎo)機(jī)器人運(yùn)動(dòng)。Machado等人[2]提出了認(rèn)知協(xié)同策略，核心為在巡邏過(guò)程中上位機(jī)知道所有節(jié)點(diǎn)的信息，其選擇共享空閑值最大的節(jié)點(diǎn)，使其成為機(jī)器人的下一個(gè)目標(biāo)節(jié)點(diǎn)，同時(shí)避免將同一個(gè)節(jié)點(diǎn)分配給多個(gè)機(jī)器人,然后利用尋路技術(shù)，機(jī)器人可以實(shí)現(xiàn)從當(dāng)前位置到目標(biāo)節(jié)點(diǎn)的自主移動(dòng)。

隨著多機(jī)器人巡邏策略研究的深入，研究人員發(fā)現(xiàn)傳統(tǒng)的集中式巡邏算法在面對(duì)復(fù)雜多變的環(huán)境時(shí)具有較大的局限性。當(dāng)環(huán)境信息發(fā)生變化或者中央機(jī)器人受到入侵時(shí)[3]，集中式巡邏算法無(wú)法及時(shí)進(jìn)行策略調(diào)整，難以完成巡邏任務(wù)。Portugal等人[4]提出了基于貝葉斯決策的分布式多機(jī)器人巡邏算法，該算法基于貝葉斯數(shù)學(xué)模型，通過(guò)建立獎(jiǎng)勵(lì)函數(shù)和效用函數(shù)來(lái)對(duì)機(jī)器人的下一個(gè)目標(biāo)興趣點(diǎn)進(jìn)行選擇。由于該算法具有較強(qiáng)的靈活性，它可以很好地解決傳統(tǒng)預(yù)先定義巡邏算法中其確定性本質(zhì)帶來(lái)的潛在可入侵危險(xiǎn)。在此基礎(chǔ)上，Portugal等人[5]針對(duì)分布式多機(jī)器人巡邏中的容錯(cuò)性和可拓展性提出了2種算法，即貪婪貝葉斯策略GBS(Greedy Bayesian strategy)和狀態(tài)交換貝葉斯策略SEBS(State Exchange Bayesian Strategy)。貪婪貝葉斯策略的思想是機(jī)器人按照自己的決策并結(jié)合效用函數(shù)，在每個(gè)階段找到局部最優(yōu)選擇，進(jìn)而完成指定區(qū)域的巡邏任務(wù)。SEBS是GBS的延伸，在GBS的基礎(chǔ)上引入了概率質(zhì)量函數(shù)(1/2幾何序列)，將機(jī)器人數(shù)量這一因素加入到機(jī)器人的決策過(guò)程中，在一定程度上減少了機(jī)器人之間的沖突，因而在性能上優(yōu)于GBS。但是，當(dāng)環(huán)境信息或機(jī)器人數(shù)量發(fā)生變化時(shí)，這2種算法的性能會(huì)受到很大的影響。因此，Portugal等人[6]在GBS的基礎(chǔ)上提出了并行貝葉斯策略CBLS(Concurrent Bayesian Learning Strategy)算法,該算法考慮了不同先驗(yàn)概率的情況，并在決策過(guò)程中引入了機(jī)器人第2步前視頂點(diǎn)的空閑時(shí)間，結(jié)合自適應(yīng)學(xué)習(xí)來(lái)靈活調(diào)整機(jī)器人決策，使各個(gè)機(jī)器人可以很好適應(yīng)復(fù)雜多變的環(huán)境。Farinelli等人[7]提出了2種動(dòng)態(tài)任務(wù)分配方法：貪婪的基線方法DTA-G(Dynamic Task Assignment-Greedy)和以市場(chǎng)為基礎(chǔ)的基于連續(xù)單物品拍賣(mài)的方法DTAP(Dynamic Task Assignment Patrolling)。DTAG將地圖節(jié)點(diǎn)的瞬時(shí)空閑時(shí)間引入到?jīng)Q策過(guò)程中，通過(guò)效用函數(shù)指導(dǎo)機(jī)器人運(yùn)動(dòng)，且每次決策只給每個(gè)機(jī)器人指定一個(gè)巡邏節(jié)點(diǎn)。而DTAP通過(guò)給每個(gè)機(jī)器人指定一個(gè)巡邏節(jié)點(diǎn)集，來(lái)避免機(jī)器人巡邏路徑的交叉，減少多機(jī)器人間的相互干擾，進(jìn)而提高巡邏效率。實(shí)驗(yàn)結(jié)果表明，DTAP在多連通地圖中的巡邏性能優(yōu)于DTAG的。趙云濤等人[8]提出了一種基于平均最大空閑時(shí)間EGMI(Estimated Global Maximum Idleness)的巡邏算法,該算法將巡邏地圖的全局平均最大空閑時(shí)間引入到?jīng)Q策過(guò)程中，根據(jù)最大空閑時(shí)間的大小估算在特定巡邏環(huán)境中完成巡邏任務(wù)所需要的機(jī)器人數(shù)量，進(jìn)而得知完成巡邏所需的最優(yōu)機(jī)器人數(shù)量。EGMI算法在機(jī)器人數(shù)量?jī)?yōu)化上有著很好的應(yīng)用，但當(dāng)機(jī)器人巡邏數(shù)量發(fā)生變化時(shí)，其巡邏效果可能會(huì)受到較大影響。

綜上所述，在復(fù)雜多變的巡邏環(huán)境中，上述巡邏算法并不總是能達(dá)到巡邏效果最優(yōu)。本文在全局平均空閑時(shí)間的基礎(chǔ)上，提出了基于多步長(zhǎng)的分布式巡邏算法MSLA(Multi-Step Length Algorithm)，通過(guò)考慮機(jī)器人前視節(jié)點(diǎn)，即目標(biāo)節(jié)點(diǎn)鄰居的平均空閑時(shí)間和節(jié)點(diǎn)個(gè)數(shù)來(lái)縮短巡邏系統(tǒng)的全局平均空閑時(shí)間，使其更能適用于機(jī)器人數(shù)量較多時(shí)的巡邏情況，最終達(dá)到改善巡邏效果的目的。

2 問(wèn)題描述

在給定環(huán)境中通過(guò)一組數(shù)量為m的機(jī)器人R=(R1,R2,…，Rm)進(jìn)行巡邏，每個(gè)機(jī)器人都已知所要巡邏環(huán)境中的巡邏節(jié)點(diǎn)，則可以得到機(jī)器人的無(wú)向?qū)Ш綀DG=(V,E)，使得機(jī)器人可以評(píng)估巡邏環(huán)境的拓?fù)浣Y(jié)構(gòu)。V0和Vi為地圖上的巡邏節(jié)點(diǎn)，所有節(jié)點(diǎn)構(gòu)成集合V，記為V={V0,…,Vi,Vj,…,Vn}，E表示相鄰節(jié)點(diǎn)連接形成的邊集合，表示各個(gè)節(jié)點(diǎn)的連通性，這些邊可提供機(jī)器人通行且互不相交，其中將某一節(jié)點(diǎn)相鄰的鄰居節(jié)點(diǎn)稱(chēng)為該節(jié)點(diǎn)的前視節(jié)點(diǎn)。節(jié)點(diǎn)V0和Vi間的路徑長(zhǎng)度記為l0,i，節(jié)點(diǎn)的重要度分別記為e0和ei。

為了評(píng)價(jià)不同算法的性能，引入一個(gè)合適的評(píng)判標(biāo)準(zhǔn)是非常重要的。傳統(tǒng)的評(píng)價(jià)標(biāo)準(zhǔn)主要有：空閑時(shí)間[9]、訪問(wèn)頻率[10]和機(jī)器人運(yùn)動(dòng)的距離等。本文引入節(jié)點(diǎn)空閑時(shí)間，即節(jié)點(diǎn)被連續(xù)訪問(wèn)的時(shí)間間隔，通過(guò)將目標(biāo)節(jié)點(diǎn)和前視節(jié)點(diǎn)的平均空閑時(shí)間引入到效用函數(shù)中來(lái)提高機(jī)器人決策的合理性。規(guī)定機(jī)器人通信半徑有限，不能進(jìn)行通信全覆蓋，只能與相鄰的個(gè)別機(jī)器人進(jìn)行雙向通信[11]。圖1和圖2是以自建地圖Lab為例的路徑拓?fù)鋱D和通信拓?fù)鋱D。為簡(jiǎn)化起見(jiàn)，圖中巡邏節(jié)點(diǎn)Vi均簡(jiǎn)記為i，后文各圖也按照類(lèi)似方法處理，不再另作說(shuō)明。

Figure 1 Lab path topology圖1 Lab路徑拓?fù)鋱D

Figure 2 Lab communication topology圖2 Lab通信拓?fù)鋱D

在行為決策階段，每個(gè)機(jī)器人與自己相鄰最近的伙伴進(jìn)行雙向通信，如圖2所示。輸入為當(dāng)前的本地信息，輸出為機(jī)器人的行為策略，所巡邏環(huán)境的信息和機(jī)器人的決策算法直接影響著多機(jī)器人的巡邏效果。為了評(píng)價(jià)巡邏算法的性能，本文將全局平均空閑時(shí)間作為評(píng)判標(biāo)準(zhǔn)引入到算法決策過(guò)程中。

記機(jī)器人當(dāng)前所在節(jié)點(diǎn)為V0點(diǎn)，機(jī)器人R1第k次訪問(wèn)節(jié)點(diǎn)Vi的空閑時(shí)間如式(1)所示：

IVi(tk)=tk-tk-1

(1)

其中，tk表示機(jī)器人R1在第k次訪問(wèn)節(jié)點(diǎn)Vi的時(shí)刻，所得到的空閑時(shí)間可以?xún)?chǔ)存在該機(jī)器人中，故得到節(jié)點(diǎn)Vi在當(dāng)前時(shí)刻的平均空閑時(shí)間如式(2)所示:

(2)

(3)

其中,n表示巡邏區(qū)域中的節(jié)點(diǎn)總數(shù)。全局平均空閑時(shí)間越短，說(shuō)明每個(gè)節(jié)點(diǎn)的安全度越高，即巡邏效率越好。

3 基于多步長(zhǎng)的分布式巡邏算法

為了提高多機(jī)器人巡邏過(guò)程中的效率，本文提出了一種基于節(jié)點(diǎn)平均空閑時(shí)間的多步長(zhǎng)分布式巡邏算法。其決策過(guò)程如下：當(dāng)機(jī)器人R1處在節(jié)點(diǎn)V0時(shí)，通過(guò)信息交互采集環(huán)境信息及其他機(jī)器人所傳遞的信息，對(duì)該數(shù)據(jù)進(jìn)行處理，通過(guò)特定的效用函數(shù)來(lái)指導(dǎo)該機(jī)器人運(yùn)動(dòng)到相應(yīng)目標(biāo)點(diǎn)。

假設(shè)機(jī)器人R1處在V0節(jié)點(diǎn)上，則其到達(dá)下一個(gè)相鄰節(jié)點(diǎn)Vi的時(shí)間可表示為式(4)：

(4)

其中，l0,i為節(jié)點(diǎn)V0到節(jié)點(diǎn)Vi的路徑長(zhǎng)度，c為巡邏機(jī)器人的速度，這里規(guī)定每個(gè)機(jī)器人速度相同。在多機(jī)器人巡邏過(guò)程中節(jié)點(diǎn)重要度集合為e={e0,e1,…，en}。巡邏節(jié)點(diǎn)的重要度通常是由人們的先驗(yàn)經(jīng)驗(yàn)和巡邏場(chǎng)所已有的巡邏數(shù)據(jù)相結(jié)合來(lái)確定的，因此巡邏節(jié)點(diǎn)重要度的大小設(shè)置具有很大的不確定性。但總體而言，當(dāng)目標(biāo)節(jié)點(diǎn)在巡邏場(chǎng)所中越重要或該目標(biāo)節(jié)點(diǎn)發(fā)生盜竊、安全事故等情況的概率越高，則該巡邏節(jié)點(diǎn)的重要度就越大。在本文中，假設(shè)每個(gè)節(jié)點(diǎn)的重要度恒定不變，則機(jī)器人從節(jié)點(diǎn)V0到節(jié)點(diǎn)Vi的弧強(qiáng)度θ0,i如式(5)所示：

(5)

注意，θ0,i≠θi,0。則機(jī)器人第1步的效用函數(shù)為：

(6)

若機(jī)器人只考慮第1步目標(biāo)節(jié)點(diǎn)，可能會(huì)導(dǎo)致機(jī)器人運(yùn)動(dòng)的不均勻和相互干擾，進(jìn)而影響巡邏效率，故本文引入第2步節(jié)點(diǎn)集，即前視節(jié)點(diǎn)集。將節(jié)點(diǎn)V0在Vi方向上的前視節(jié)點(diǎn)集記為VNG,i={Vh,Vj,…，Vp}，則其相對(duì)應(yīng)的前視節(jié)點(diǎn)集的平均空閑時(shí)間如式(7)所示：

(7)

其中，z為節(jié)點(diǎn)V0在Vi方向上前視節(jié)點(diǎn)的數(shù)量。則V0節(jié)點(diǎn)相應(yīng)的第2步效用函數(shù)如式(8)所示：

(8)

(9)

(10)

其中,β表示前視節(jié)點(diǎn)數(shù)量與其中機(jī)器人數(shù)量的比值；φ為當(dāng)前節(jié)點(diǎn)V0在Vi方向上前視節(jié)點(diǎn)中的機(jī)器人數(shù)量；ω為第1步效用函數(shù)在整體效用函數(shù)中所占的權(quán)重，該參數(shù)可以根據(jù)巡邏地圖中節(jié)點(diǎn)的分布情況進(jìn)行適當(dāng)調(diào)節(jié)，但總體來(lái)說(shuō)該參數(shù)設(shè)置要大于0.5。因?yàn)橄噜徆?jié)點(diǎn)的環(huán)境信息總是可靠和最新的，而當(dāng)機(jī)器人到達(dá)目標(biāo)節(jié)點(diǎn)時(shí)，前視節(jié)點(diǎn)集中的環(huán)境節(jié)點(diǎn)信息可能會(huì)發(fā)生改變。

如果有2個(gè)及2個(gè)以上的機(jī)器人與目標(biāo)節(jié)點(diǎn)Vi相鄰，則在當(dāng)前tk時(shí)刻節(jié)點(diǎn)Vi的效用函數(shù)為:

(11)

式(11)中，當(dāng)節(jié)點(diǎn)V0的前視節(jié)點(diǎn)上有1個(gè)或多個(gè)機(jī)器人時(shí)，機(jī)器人在尋找目標(biāo)點(diǎn)Vi時(shí)要考慮前視節(jié)點(diǎn)數(shù)量與其中機(jī)器人數(shù)量的比值β。β越小，說(shuō)明該前視節(jié)點(diǎn)集中機(jī)器人的密度越大，可以很好地巡邏該區(qū)域，因而機(jī)器人R1在進(jìn)行決策時(shí)對(duì)前視節(jié)點(diǎn)考慮越少。

如果只有1個(gè)機(jī)器人去競(jìng)逐節(jié)點(diǎn)Vi，則在當(dāng)前tk時(shí)刻節(jié)點(diǎn)Vi的效用函數(shù)為：

(12)

式(12)表示當(dāng)節(jié)點(diǎn)V0的前視節(jié)點(diǎn)中沒(méi)有機(jī)器人時(shí)，機(jī)器人R1在選擇目標(biāo)節(jié)點(diǎn)時(shí)對(duì)前視節(jié)點(diǎn)考慮較多。只有2步節(jié)點(diǎn)相結(jié)合才能縮短節(jié)點(diǎn)的全局平均空閑時(shí)間，進(jìn)而改善機(jī)器人的巡邏效果。

通過(guò)式(11)和式(12)可以計(jì)算出在上述2種情況下目標(biāo)節(jié)點(diǎn)的效用函數(shù)，機(jī)器人可通過(guò)效用函數(shù)的大小來(lái)對(duì)目標(biāo)節(jié)點(diǎn)進(jìn)行選擇。目標(biāo)節(jié)點(diǎn)的效用函數(shù)值越大，表明該目標(biāo)節(jié)點(diǎn)越需要機(jī)器人去訪問(wèn)。機(jī)器人通過(guò)效用函數(shù)來(lái)選取合適的目標(biāo)節(jié)點(diǎn)，可以減少機(jī)器人數(shù)量較多時(shí)所產(chǎn)生的相互干擾，進(jìn)而縮短巡邏區(qū)域的全局平均空閑時(shí)間，最終達(dá)到提高巡邏效率的目的。

在此將執(zhí)行巡邏任務(wù)的算法簡(jiǎn)稱(chēng)為MSLA,其偽代碼如算法1所示。

算法1基于多步長(zhǎng)的分布式巡邏算法

1 Initialization;

2whiletruedo

3forallVi∈Vdo

9ifφ=0then

11else

13endif

14Vi←argmax(U(Vi,tk))；

15endfor

16 publish intention messageVi；

17 move to vertexVi;

18whileone of robot reachedVido

19 publish message to the other robots as arrivingVi；

20 update idleness (V)；

21endwhile

22Vi←Vi+1;

23endwhile

24end

在巡邏過(guò)程中，機(jī)器人通過(guò)信息交互來(lái)收集巡邏節(jié)點(diǎn)的環(huán)境信息，并計(jì)算出各個(gè)節(jié)點(diǎn)的空閑時(shí)間，進(jìn)而得到當(dāng)前時(shí)刻節(jié)點(diǎn)的平均空閑時(shí)間，然后將節(jié)點(diǎn)平均空閑時(shí)間引入到效用函數(shù)中，結(jié)合節(jié)點(diǎn)數(shù)量和節(jié)點(diǎn)重要度計(jì)算出每個(gè)環(huán)境巡邏節(jié)點(diǎn)的效用函數(shù)，最后比較機(jī)器人相鄰節(jié)點(diǎn)的各個(gè)效用函數(shù)大小。若某一相鄰節(jié)點(diǎn)的效用函數(shù)最大，說(shuō)明該目標(biāo)節(jié)點(diǎn)最需要機(jī)器人去訪問(wèn)，則機(jī)器人根據(jù)結(jié)果指導(dǎo)自己向該點(diǎn)移動(dòng)。當(dāng)機(jī)器人到達(dá)目標(biāo)節(jié)點(diǎn)后，該機(jī)器人將到達(dá)信息發(fā)送給其他機(jī)器人(對(duì)應(yīng)算法第19行)，而后更新當(dāng)前巡邏節(jié)點(diǎn)信息(對(duì)應(yīng)算法第20行)，多種信息依次傳遞給各個(gè)機(jī)器人，多機(jī)器人會(huì)根據(jù)所收集的環(huán)境信息獨(dú)立決策，進(jìn)而完成巡邏任務(wù)。

4 仿真實(shí)驗(yàn)

為了驗(yàn)證本文所提巡邏算法的有效性，在ROS(Robot Operating System)環(huán)境下搭建多機(jī)器人巡邏仿真平臺(tái)multi_robot_patrol來(lái)對(duì)算法性能進(jìn)行測(cè)試，而后通過(guò)和現(xiàn)有算法進(jìn)行對(duì)比來(lái)分析本文算法的優(yōu)劣性。在仿真過(guò)程中，機(jī)器人在二維地圖的基礎(chǔ)上使用ROS導(dǎo)航和定位系統(tǒng)，并結(jié)合算法完成機(jī)器人路徑自主規(guī)劃，同時(shí)避免多個(gè)機(jī)器人在移動(dòng)中發(fā)生碰撞。

仿真使用了Example和Grid 2種二維仿真地圖來(lái)驗(yàn)證算法的可行性，其環(huán)境拓?fù)鋱D如圖3所示。

Figure 3 Topology of simulation experiment environment圖3 仿真實(shí)驗(yàn)環(huán)境拓?fù)鋱D

表1為2種仿真地圖拓?fù)鋱D信息。當(dāng)采用數(shù)量為4，8，12的Turtlebot3機(jī)器人時(shí)，在上述2種仿真地圖上進(jìn)行算法驗(yàn)證，仿真通過(guò)multi_robot_patrol仿真平臺(tái)進(jìn)行實(shí)驗(yàn)，同時(shí)進(jìn)行數(shù)據(jù)記錄。仿真中，多機(jī)器人移動(dòng)速度均為1 m/s，每組仿真實(shí)驗(yàn)持續(xù)半小時(shí)。

Table 1 Topological information of simulation maps表1 仿真圖拓?fù)湫畔?/p>

Table 2 Simulation results in Example map表2 在Example仿真地圖中的仿真結(jié)果 s

Table 3 Simulation results in Grid map表3 在Grid仿真地圖中的仿真結(jié)果 s

本文分別選取機(jī)器人數(shù)量為4,8,12的巡邏結(jié)果進(jìn)行數(shù)據(jù)分析。圖4通過(guò)繪制箱線圖分別對(duì)機(jī)器人不同數(shù)量和不同環(huán)境中的節(jié)點(diǎn)空閑時(shí)間進(jìn)行了統(tǒng)計(jì)分析。在該實(shí)驗(yàn)中，箱線圖中所繪制的矩形框表示空閑時(shí)間的集中區(qū)域，矩形框越小，表明使用該算法所得到的節(jié)點(diǎn)空閑時(shí)間越集中，圖中上下2條短黑線分別表示非異?？臻e時(shí)間的最大值和最小值，而矩形框中的長(zhǎng)實(shí)線表示節(jié)點(diǎn)空閑時(shí)間的中值,可以看出空閑時(shí)間的離散程度，黑色小圈表示空閑時(shí)間的異常值。

由圖4可知，當(dāng)機(jī)器人數(shù)量為4時(shí)，各算法的節(jié)點(diǎn)空閑時(shí)間較為分散，且全局平均空閑時(shí)間較長(zhǎng)，隨著機(jī)器人數(shù)量的增加，各算法的空閑時(shí)間慢慢收斂，全局平均空閑時(shí)間也逐漸縮短。當(dāng)機(jī)器人數(shù)量為8時(shí)，在Example和Grid仿真地圖中，相較于其他幾種算法，MSLA的矩形框較低，且矩形框較小，說(shuō)明該算法在機(jī)器人數(shù)量為8時(shí)具有較短的空閑時(shí)間和較好的收斂性，因而更加高效，更加穩(wěn)定。當(dāng)機(jī)器人數(shù)量繼續(xù)增加時(shí)，從箱線圖中可以看出，MSLA相較于其他幾種算法同樣保持著較短的空閑時(shí)間和較好的收斂性，因此可以看出在同一環(huán)境中巡邏時(shí)，當(dāng)機(jī)器人數(shù)量較多時(shí)，MSLA的巡邏效果優(yōu)于其他幾種算法的。

Figure 5 Convergence of for five algorithms in Grid map 圖5 5種算法在Grid仿真地圖中的和收斂性

為了分析MSLA隨著機(jī)器人數(shù)量的增加巡邏性能的變化情況，本文在Example和Grid仿真地圖中，通過(guò)仿真平臺(tái)對(duì)機(jī)器人數(shù)量進(jìn)行改變來(lái)對(duì)巡邏效果進(jìn)行分析，分析結(jié)果如圖6所示。

Figure 6 Patrol effect of five algorithms with different robot numbers圖6 5種算法在機(jī)器人數(shù)量不同時(shí)的巡邏效果

由圖6可知，隨著機(jī)器人數(shù)量的增加，各巡邏算法的全局平均空閑時(shí)間逐漸縮短，表示巡邏性能逐漸提高，但隨著機(jī)器人數(shù)量的逐漸飽和，其機(jī)器人之間的干擾逐漸增大，影響了算法的巡邏性能，反而會(huì)導(dǎo)致巡邏性能降低。從全局平均空閑時(shí)間曲線趨勢(shì)可以看出，相較于其他算法，MSLA的全局平局空閑時(shí)間曲線在機(jī)器人數(shù)量較多時(shí)仍然可以保持在較小的數(shù)值范圍內(nèi)，表明該算法在機(jī)器人數(shù)量較多時(shí)其巡邏性能優(yōu)于其他算法的。以圖6a為例，當(dāng)機(jī)器人數(shù)量達(dá)到8后，隨著機(jī)器人數(shù)量的增加，MSLA的全局平均空閑時(shí)間仍保持在較小的數(shù)值范圍內(nèi)，且沒(méi)有隨機(jī)器人干擾的增加出現(xiàn)上升趨勢(shì)，反觀其他幾種算法，在機(jī)器人數(shù)量達(dá)到8后全局平均空閑時(shí)間有上升趨勢(shì)，且整體大于MSLA的平均空閑時(shí)間。在圖6b中，雖然MSLA的全局平均空閑時(shí)間曲線也存在一些波動(dòng)，但相較于其他算法的曲線趨勢(shì)，MSLA的整體全局平均空閑時(shí)間仍保持在較小數(shù)值水平，且在機(jī)器人數(shù)量為12時(shí)，有著最短的全局平均空閑時(shí)間，此時(shí)多機(jī)器人系統(tǒng)巡邏性能較好。

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

本文針對(duì)多機(jī)器人巡邏問(wèn)題，提出了一種基于多步長(zhǎng)的多機(jī)器人分布式巡邏算法MSLA，通過(guò)將多步長(zhǎng)巡邏節(jié)點(diǎn)信息引入到機(jī)器人決策過(guò)程中，從而縮短節(jié)點(diǎn)全局平均空閑時(shí)間。在ROS環(huán)境下的實(shí)驗(yàn)結(jié)果表明，該算法在機(jī)器人數(shù)量較少時(shí)沒(méi)有明顯的團(tuán)隊(duì)優(yōu)勢(shì)，但隨著機(jī)器人數(shù)量增加，該算法在巡邏過(guò)程中所表現(xiàn)出來(lái)的優(yōu)勢(shì)越來(lái)越明顯。當(dāng)機(jī)器人數(shù)量較多時(shí)，從實(shí)驗(yàn)結(jié)果可以看出，MSLA所得到的全局平均空閑時(shí)間和全局空閑時(shí)間標(biāo)準(zhǔn)差都較小，說(shuō)明該算法在完成巡邏任務(wù)的同時(shí)，具有較好的巡邏效率和穩(wěn)定性。在后期工作中，將嘗試考慮多機(jī)器人巡邏過(guò)程中通信延遲對(duì)巡邏效果的影響，進(jìn)而對(duì)本文所提算法進(jìn)行進(jìn)一步完善。