基于多步長的多機器人分布式巡邏算法研究*

白耀文，杜亞江，李宗剛

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

1 引言

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

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

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

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

2 問題描述

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

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

Figure 1 Lab path topology圖1 Lab路徑拓撲圖

Figure 2 Lab communication topology圖2 Lab通信拓撲圖

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

記機器人當前所在節(jié)點為V0點，機器人R1第k次訪問節(jié)點Vi的空閑時間如式(1)所示：

IVi(tk)=tk-tk-1

(1)

其中，tk表示機器人R1在第k次訪問節(jié)點Vi的時刻，所得到的空閑時間可以儲存在該機器人中，故得到節(jié)點Vi在當前時刻的平均空閑時間如式(2)所示:

(2)

(3)

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

3 基于多步長的分布式巡邏算法

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

假設機器人R1處在V0節(jié)點上，則其到達下一個相鄰節(jié)點Vi的時間可表示為式(4)：

(4)

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

(5)

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

(6)

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

(7)

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

(8)

(9)

(10)

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

如果有2個及2個以上的機器人與目標節(jié)點Vi相鄰，則在當前tk時刻節(jié)點Vi的效用函數(shù)為:

(11)

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

如果只有1個機器人去競逐節(jié)點Vi，則在當前tk時刻節(jié)點Vi的效用函數(shù)為：

(12)

式(12)表示當節(jié)點V0的前視節(jié)點中沒有機器人時，機器人R1在選擇目標節(jié)點時對前視節(jié)點考慮較多。只有2步節(jié)點相結合才能縮短節(jié)點的全局平均空閑時間，進而改善機器人的巡邏效果。

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

在此將執(zhí)行巡邏任務的算法簡稱為MSLA,其偽代碼如算法1所示。

算法1基于多步長的分布式巡邏算法

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

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

4 仿真實驗

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

仿真使用了Example和Grid 2種二維仿真地圖來驗證算法的可行性，其環(huán)境拓撲圖如圖3所示。

Figure 3 Topology of simulation experiment environment圖3 仿真實驗環(huán)境拓撲圖

表1為2種仿真地圖拓撲圖信息。當采用數(shù)量為4，8，12的Turtlebot3機器人時，在上述2種仿真地圖上進行算法驗證，仿真通過multi_robot_patrol仿真平臺進行實驗，同時進行數(shù)據(jù)記錄。仿真中，多機器人移動速度均為1 m/s，每組仿真實驗持續(xù)半小時。

Table 1 Topological information of simulation maps表1 仿真圖拓撲信息

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

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

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

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

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

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

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

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

5 結束語

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