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

白耀文，杜亞江，李宗剛

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

1 引言

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

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

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

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

2 問題描述

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

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

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

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

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

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

IVi(tk)=tk-tk-1

(1)

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

(2)

(3)

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

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

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

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

(4)

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

(5)

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

(6)

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

(7)

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

(8)

(9)

(10)

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

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

(11)

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

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

(12)

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

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

在此將執行巡邏任務的算法簡稱為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

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

4 仿真實驗

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

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

Figure 3 Topology of simulation experiment environment圖3 仿真實驗環境拓撲圖

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

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

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

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

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

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

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

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

5 結束語

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