張鵬超 李宗剛

摘 要：在多機(jī)器人巡邏任務(wù)中，由于通信距離的限制，單個機(jī)器人很難獲得全局信息。然而，現(xiàn)有的大多數(shù)多機(jī)器人分布式巡邏算法都要求每個機(jī)器人獲得其巡邏區(qū)域的全局信息進(jìn)行決策。因此，考慮到通信半徑約束和局部信息約束，為了通過相鄰機(jī)器人之間的交互完成巡邏任務(wù)，基于離散時間一致性理論提出了兩種巡邏算法。算法1使用全局信息進(jìn)行決策，算法2基于離散時間一致性理論實現(xiàn)局部信息對全局信息的預(yù)測進(jìn)行決策。通過模擬器Stage對所提算法與對比算法在不同機(jī)器人數(shù)量、通信半徑、地圖環(huán)境下進(jìn)行了對比。實驗驗證了所提出的基于局部信息的分布式多機(jī)器人巡邏算法具有與原算法類似的特性和性能，能夠使機(jī)器人在沒有全局信息的情況下判斷全局狀態(tài)，并基于鄰居之間的協(xié)商完成巡邏任務(wù)。

關(guān)鍵詞：巡邏；多機(jī)器人系統(tǒng)；分布式協(xié)同；離散時間一致性

中圖分類號：TP242?? 文獻(xiàn)標(biāo)志碼：A??? 文章編號：1001-3695（2024）05-027-1470-10

doi： 10.19734/j.issn.1001-3695.2023.08.0421

Distributed patrol algorithm for multi-robot systems based on discrete-time consensus theory

Abstract：In the multi-robot patrol task， it is difficult for a single robot to obtain global information due to the limitation of the communication distance. However， most existing multi-robot distributed patrol algorithms require each robot to obtain global information of its patrol area for decision-making. Therefore， this paper addressed on the communication radius constrain and the local information constrain to completes patrol tasks through the interaction between neighbor robots， and proposed two solution algorithms based on discrete-time consensus theory. Algorithm 1 used global information for decision-making. Algorithm 2 used discrete-time consensus theory to predict and make decisions based on local information. Through the simulator Stage， the proposed algorithm and the comparison algorithm were simulated and compared under different robot numbers， communication radii and map environments. The simulation verifies that the proposed fully distributed multi-robot patrol algorithm based on local information has similar characteristics and performance to the original algorithm， enabling robots to judge the global state without global information and complete patrol tasks based on the negotiation between neighbors.

Key words：patrolling; autonomous multi-robot system; distributed coordination; discrete-time consensus theory

0 引言

多機(jī)器人巡邏問題（MRPP）是指多個機(jī)器人在目標(biāo)區(qū)域內(nèi)或周圍移動，以保護(hù)或監(jiān)督目標(biāo)區(qū)域，達(dá)到安全目的的活動［1］。多機(jī)器人巡邏應(yīng)用廣泛，例如城市安保巡邏、邊境巡邏、海岸線巡邏、化工廠集群安保巡邏［2］、森林火災(zāi)預(yù)防巡邏等。通常，巡邏可以分為常規(guī)巡邏和對抗巡邏兩類［1］，常規(guī)巡邏指的是通過頻繁到訪目標(biāo)區(qū)域內(nèi)部以掌握該區(qū)域，對抗巡邏旨在通過檢測入侵者來保護(hù)目標(biāo)區(qū)域。

常規(guī)巡邏問題廣泛研究的算法有兩種類型：a）集中式算法。如圖1所示，其中要么存在一個中央控制器，要么每個機(jī)器人都可以獲得全局信息并獨(dú)立決策。集中式算法易于應(yīng)用，適用于小規(guī)模巡邏任務(wù)。但是受中央控制器宕機(jī)和全局信息獲取的影響較大，因此魯棒性較差。b）分布式算法。如圖2所示，每個機(jī)器人收集周圍的環(huán)境信息并與鄰居進(jìn)行交換，即每個機(jī)器人只使用局部信息來作出決策。分布式算法具有更好的可擴(kuò)展性和容錯性，適用于大規(guī)模巡邏任務(wù)。出于本文的研究目的，僅將分布式算法的文獻(xiàn)總結(jié)如下。

現(xiàn)有的分布式多機(jī)器人巡邏算法主要包括反應(yīng)式策略、基于學(xué)習(xí)的方法和基于拍賣的方法。反應(yīng)式策略是指每個機(jī)器人選擇效用值最高的鄰居節(jié)點(diǎn)作為目標(biāo)節(jié)點(diǎn)。因此，通常采用拓?fù)鋱D對環(huán)境進(jìn)行建模。效用函數(shù)和評價標(biāo)準(zhǔn)可以通過空閑時間［3］、平均空閑時間［4，5］、全局平均最大空閑時間［6］、節(jié)點(diǎn)重要度［7］、期望空閑時間［8］、周圍鄰居的意圖［9］、不確定度［10］等因素來構(gòu)建。評價指標(biāo)采用空閑時間、不確定度等因素構(gòu)造。但是，現(xiàn)有反應(yīng)策略大都采用將到達(dá)和意圖信息發(fā)送給所有其他機(jī)器人的方式。因為每個機(jī)器人都需要拿到全局信息，所以不是完全的分布式策略。基于學(xué)習(xí)的方法通過積累歷史經(jīng)驗幫助機(jī)器人適應(yīng)動態(tài)環(huán)境。文獻(xiàn)［9，11］提出了GBS、SEBS和CBLS算法，以貝葉斯算法實現(xiàn)機(jī)器人的學(xué)習(xí)，并通過空閑時間對算法進(jìn)行評估。全局信息（包括到達(dá)信息和意圖信息）通過無線自組織網(wǎng)絡(luò)（MANET）發(fā)布和傳輸。仿真分析了不同通信故障率對巡邏效果的影響。然而沒有考慮通信距離和機(jī)器人具體位置因素?；陂L短期記憶網(wǎng)絡(luò)的RLPM是在集中式算法HPCC上訓(xùn)練的，并在機(jī)器人之間沒有通信的情況下工作。雖然RLPM算法不需要全局信息就可以實現(xiàn)接近于被學(xué)習(xí)的原始算法的性能，但是需要對特定地圖和算法進(jìn)行大量的訓(xùn)練。在基于拍賣的方法中，每個節(jié)點(diǎn)都被視為一個要分配的任務(wù)。每個機(jī)器人獨(dú)立地求解其投標(biāo)值并同所有其他機(jī)器人完成競標(biāo)以判斷是否將競標(biāo)節(jié)點(diǎn)加入任務(wù)清單［12，13］。DTAP和EDCP都要求每個機(jī)器人將投標(biāo)值發(fā)送給所有其他機(jī)器人進(jìn)行投標(biāo)，以確定是否將投標(biāo)節(jié)點(diǎn)添加到其任務(wù)列表中。因為競標(biāo)過程中需要將出價信息發(fā)送到所有其他機(jī)器人，所以其集群大小和巡邏范圍受到了限制，算法不是完全的分布式巡邏算法。

綜上所述，現(xiàn)有文獻(xiàn)中的大多數(shù)分布式巡邏算法雖然實現(xiàn)了線上自主決策，但是大都需要所有其他機(jī)器人的信息來作出決策，也就是說巡邏問題是基于全局信息來解決的。隨著機(jī)器人規(guī)模的增加和巡邏范圍的擴(kuò)大，機(jī)器人在有限的硬件資源下傳輸、獲取、存儲全局信息的難度隨之上升［14］。多機(jī)器人系統(tǒng)的通信要求、存儲要求和計算要求也隨著機(jī)器人數(shù)量的提高而提高，導(dǎo)致系統(tǒng)成本升高。因此有必要研究基于機(jī)器人自身局部信息的完全分布式的巡邏算法。例如對于有限通信范圍內(nèi)考慮連通性保持因素的巡邏算法研究［15～17］。一致性算法使得機(jī)器人在沒有全局信息的情況下只需要相鄰機(jī)器人之間的協(xié)商，就能夠達(dá)成狀態(tài)信息的一致。一致性算法在分布式多機(jī)器人系統(tǒng)協(xié)同控制中的理論優(yōu)勢使得設(shè)計基于局部信息的多機(jī)器人分布式巡邏算法成為可能。

基于以上分析，本文做了以下工作：

a）建立了機(jī)器人之間的關(guān)系拓?fù)涿枋觯?/p>

b）提出了一種基于全局信息的巡邏算法；

c）提出了一種基于局部信息的完全分布式巡邏算法，使得機(jī)器人通過鄰居間通信協(xié)商、自身局部信息存儲、局部信息計算求解完成巡邏任務(wù)。

1 問題描述

考慮用多個移動機(jī)器人對給定環(huán)境進(jìn)行巡邏，實現(xiàn)對環(huán)境狀態(tài)變化的實時監(jiān)控。由于所考慮環(huán)境的結(jié)構(gòu)特征已知，故采用無向圖G1（V1，E1）對環(huán)境進(jìn)行建模。其中頂點(diǎn)集V1={v1，v2，…，vn}表示在環(huán)境中所選取的若干關(guān)鍵節(jié)點(diǎn)，邊集E1={eij}表示節(jié)點(diǎn)之間所存在的路徑，如圖3所示。頂點(diǎn)vi的相鄰點(diǎn)的集合稱為頂點(diǎn)vi的鄰居，記為NG1（vi），NG1（vi）={vq∈V1：ei，q∈E1}。從而所考慮巡邏問題可視為多機(jī)器人通過合作對頂點(diǎn)集的遍歷。

多機(jī)器人之間的關(guān)系也采用圖G2（V2，E2）表示，其中V2={r1，r2，…，rm}表示用于巡邏的機(jī)器人，E2={cij}表示機(jī)器人之間的關(guān)系。當(dāng)cij=1時，機(jī)器人ri可以接收到機(jī)器人rj的信息，反之不能。機(jī)器人ri相鄰機(jī)器人的集合稱為機(jī)器人ri的鄰居，記為NG2（ri），NG2（ri）={rq∈V：ci，q∈E}。所有機(jī)器人在巡邏任務(wù)開始前已知拓?fù)涞貓DG1（V1，E1），并建立了初始關(guān)系G2（V2，E2）。

本文將機(jī)器人之間的關(guān)系G2（V2，E2）分為基于固定拓?fù)涞年P(guān)系和基于距離的關(guān)系兩種類型。前者通過固定機(jī)器人之間的關(guān)系實現(xiàn)固定的拓?fù)浣Y(jié)構(gòu)，后者預(yù)先設(shè)計機(jī)器人的通信半徑，通過機(jī)器人的移動實現(xiàn)關(guān)系變化。本文在分析中采用固定關(guān)系分析機(jī)器人關(guān)系對巡邏效果的影響，在實驗中考慮通信半徑實現(xiàn)的關(guān)系變化，每個機(jī)器人具有相同的通信半徑。

需要說明的是，多個機(jī)器人能否實現(xiàn)對環(huán)境的有效巡邏，取決于多機(jī)器人系統(tǒng)獲取、傳遞并利用環(huán)境信息的方式。現(xiàn)有文獻(xiàn)中，機(jī)器人到達(dá)目標(biāo)節(jié)點(diǎn)后，向所有其他機(jī)器人廣播巡邏節(jié)點(diǎn)到達(dá)信息、目標(biāo)巡邏節(jié)點(diǎn)信息等其他信息。每個機(jī)器人在進(jìn)行決策時所使用信息均為巡邏環(huán)境所有節(jié)點(diǎn)的信息。也就是說，巡邏問題的解決是基于全局信息解決全局問題?？紤]到單個機(jī)器人難以獲取全局信息的情況，有必要設(shè)計一種基于局部信息和鄰居間的通信的完全分布式巡邏算法。

利用一致性理論在局部信息估計全局信息的理論基礎(chǔ)，選取合適的狀態(tài)信息和一致性算法，能夠?qū)崿F(xiàn)完全分布式巡邏算法?？偟膩碚f，一致性理論有以下三個好處：a）隨時都可以獲得最新的協(xié)商結(jié)果，而不需要判斷所獲取的全局信息是否完整；b）保密性和擴(kuò)展性較好，因為協(xié)商信息是鄰居機(jī)器人之間相互協(xié)商的結(jié)果，而且是局部信息，受群體中單個機(jī)器人的影響??；c）能夠在巡邏算法中考慮通信半徑等實際因素，從而建立機(jī)器人之間的關(guān)系。因此，本文將一致性理論作為理論依據(jù)。

由于被協(xié)商的狀態(tài)量與時間無關(guān)，采用離散時間一致性理論建立協(xié)同算法。離散時間一致性理論的迭代公式為

其中：xki代表機(jī)器人i第k次協(xié)商的狀態(tài)信息和協(xié)商變量。通過設(shè)計不同的函數(shù)f實現(xiàn)不同的一致性。如果所有機(jī)器人的狀態(tài)最終趨于一致，則稱達(dá)成了離散時間一致性，如式（2）所示。

因此，本文研究了如何基于離散時間一致性理論實現(xiàn)鄰居機(jī)器人之間的協(xié)商行為。從而實現(xiàn)了一種基于局部信息和通信半徑約束的分布式巡邏算法。

所提算法的評價包括巡邏效果的評價以及一致性算法的協(xié)商效率兩個部分。通過空閑時間評價多機(jī)器人常規(guī)巡邏的巡邏效果。頂點(diǎn)vi在t時刻的瞬時空閑時間定義如式（3）所示。

Ivi（t）=t－tlast（3）

其中：tlast表示頂點(diǎn)最近一次被訪問的時刻。頂點(diǎn)vi在t時刻的平均空閑時間定義如式（4）所示。

此外，定義了全圖空閑時間標(biāo)準(zhǔn)差I(lǐng)Gstddev、全圖空閑時間最大值IGmax。用干擾率Ifrate（每分鐘的干擾次數(shù)）評價兩個機(jī)器人距離過近產(chǎn)生的沖突。

多機(jī)器人系統(tǒng)離散時間一致性算法的協(xié)商效果通常用協(xié)商次數(shù)k評價。首先定義機(jī)器人ri第k次協(xié)商的收斂誤差εki如式（6）所示。

當(dāng)收斂誤差εki在誤差限Δ以內(nèi)時稱協(xié)商收斂，如下所示。對應(yīng)的協(xié)商次數(shù)稱為收斂協(xié)商次數(shù)kconv。

|εki|<Δ（7）

結(jié)合巡邏算法和一致性算法，機(jī)器人可以通過局部信息來解決全局問題。本文感興趣的是通過鄰居機(jī)器人之間的通信來建立一個完全分布式的多機(jī)器人巡邏算法。問題陳述如下：

考慮使用多個機(jī)器人G2（V2，E2）對目標(biāo)區(qū)域G1（V1，E1）進(jìn)行巡邏。機(jī)器人關(guān)系G2由通信半徑約束R形成，每個機(jī)器人只能得到相鄰機(jī)器人的局部信息。目標(biāo)是設(shè)計一種完全分布式巡邏算法，使機(jī)器人團(tuán)隊以局部信息、局部決策和局部執(zhí)行完成巡邏任務(wù)。

2 基于離散時間一致性理論的分布式巡邏算法

根據(jù)基于一致性算法的分布式多機(jī)器人協(xié)同控制設(shè)計思路，構(gòu)建算法需要兩步：a）設(shè)計一個具有全局信息的集中式策略；b）基于一致性算法將全局信息轉(zhuǎn)換為局部信息，建立分布式算法［18］。

因此，本文從離散時間一致性算法的實現(xiàn)、集中式多機(jī)器人巡邏算法和分布式多機(jī)器人巡邏算法三個方面描述所建立的分布式巡邏算法。

2.1 離散時間一致性算法

2.1.1 離散時間一致性算法

根據(jù)最終收斂一致狀態(tài)值的不同，一致性可分為平均一致、最大一致、最小一致等［19］。

平均一致指的是收斂值為各個機(jī)器人初始值的平均值，采用文獻(xiàn)［20］提出的離散時間一致性算法，其形式如下：

其中：p［k］ij為第k次迭代的信息權(quán)重。式（8）可寫成矩陣形式，如式（9）所示。

其中：L［k］是拉普拉斯矩陣，它表示第k次協(xié)商時機(jī)器人之間的關(guān)系。當(dāng)機(jī)器人之間的關(guān)系由無向圖表示時收斂條件有兩個［20～22］。首先，機(jī)器人之間的關(guān)系拓?fù)涫沁B通的或聯(lián)合連通的。其次，ε∈（0，1/dmax），dmax=maxilii表示圖G2的最大出度。dmax也表示機(jī)器人的通信對象上限，即機(jī)器人的通信對象越多，系數(shù)ε越小，收斂越慢。

最大一致指的是收斂值為各個機(jī)器人初始值的最大值。離散時間一致性迭代形式如下：

x［k+1］i=max（a［k］i1×x［k］1，…，a［k］im×x［k］m） ?i=1，…，m（13）

x［k+1］i=max（A［k］×x［k］i） i=1，…，m（14）

其中：A［k］代表第k次協(xié)商時的鄰接矩陣。當(dāng)機(jī)器人之間存在信息交換時aij=1，否則aij=0。經(jīng)過多次協(xié)商，所有協(xié)商變量即可收斂到最大值。類似地，可以收斂到所有機(jī)器人初始狀態(tài)的最小值。

2.1.2 離散時間一致性算法實現(xiàn)

在現(xiàn)實過程中，巡邏機(jī)器人之間的關(guān)系與其空間位置密切相關(guān)，需要考慮其關(guān)系的變化。當(dāng)兩個機(jī)器人很接近時，它們應(yīng)該能夠直接建立關(guān)系。為了使機(jī)器人之間完成信息交換，給每一次迭代預(yù)留單位時間ΔT，定義為單位協(xié)商時間。單位協(xié)商時間的大小通常與多機(jī)器人系統(tǒng)的通信狀況和計算能力相關(guān)。此外，迭代計算時刻由獨(dú)立于機(jī)器人的壁鐘時間決定，通過網(wǎng)絡(luò)獲得、判斷和校正壁鐘時間。因此，將機(jī)器人迭代計算時刻序列定義為tk=k×ΔT（k=1，2，…）。

基于上述過程，只要機(jī)器人在單位協(xié)商時間ΔT內(nèi)完成信息交換，那么就確認(rèn)機(jī)器人在該次計算中存在信息傳輸。這也意味著表示機(jī)器人之間關(guān)系的拓?fù)銰2（V2，E2）在不同的ΔT內(nèi)可以不同。因此，上述迭代過程能夠適應(yīng)機(jī)器人關(guān)系的變化。

2.1.3 重復(fù)進(jìn)行的協(xié)商過程

因為節(jié)點(diǎn)被訪問，所以需要刷新收斂值以預(yù)測最新全局信息。循環(huán)協(xié)商即以ktotal為周期指定協(xié)商次數(shù)重復(fù)進(jìn)行的協(xié)商。ktotal是所有機(jī)器人已知的。每個重復(fù)的協(xié)商都被稱為一個循環(huán)。當(dāng)k=ktotal時，協(xié)商的狀態(tài)信息達(dá)成一致，從而用于估計全局信息并重新開始一輪新的協(xié)商。

協(xié)商算法收斂的協(xié)商次數(shù)稱為收斂協(xié)商次數(shù)kconv。為了確保拿到收斂值，收斂協(xié)商次數(shù)必須小于給定的協(xié)商次數(shù)，kconv

ttotal=ktotal×ΔT， tconv=kconv×ΔT（15）

因為單位協(xié)商時間ΔT取決于多機(jī)器人系統(tǒng)的通信與計算能力，所以在具體系統(tǒng)中往往為一定值。減少協(xié)商次數(shù)ktotal或總協(xié)商時間ttotal能夠快速獲取收斂值，但是有不收斂的風(fēng)險。提高協(xié)商次數(shù)ktotal或總協(xié)商時間ttotal有利于獲取準(zhǔn)確的收斂值但是協(xié)商結(jié)果刷新的速度變慢。因此需要根據(jù)實際情況綜合決定ktotal與ttotal。

在重復(fù)進(jìn)行的協(xié)商過程中，ktotal在任務(wù)開始前已經(jīng)給定。然而，達(dá)到平均一致性所需的協(xié)商次數(shù)K1通常大于達(dá)到最大一致性所需的協(xié)商次數(shù)K2。因此，設(shè)計K1=ktotal而且K1=q×K2（q為正整數(shù)）來組合不同類型的協(xié)商結(jié)果。

為了確保所有機(jī)器人在給定的時刻執(zhí)行一致性計算，即迭代時刻相等tki=tkj，同時確保完全分布。k值通過掛鐘時間求取，即指定第k次協(xié)商的協(xié)商迭代時刻，如式（16）所示。

2.2 集中式多機(jī)器人巡邏算法EAIG

本節(jié)設(shè)計了一種集中式多機(jī)器人巡邏算法。當(dāng)機(jī)器人到達(dá)起始節(jié)點(diǎn)或目標(biāo)節(jié)點(diǎn)時，它將采用以下三步選擇目標(biāo)點(diǎn)。首先，計算該節(jié)點(diǎn)所有鄰接節(jié)點(diǎn)NG1（vi）的效用度U1。然后，遍歷所有其他機(jī)器人的意圖節(jié)點(diǎn)序列It，如果存在意圖節(jié)點(diǎn)是該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，則該鄰居節(jié)點(diǎn)效用度歸零。從而得到?jīng)Q策用的效用度U并且避免機(jī)器人之間的沖突。最后，從鄰接節(jié)點(diǎn)中選擇效用度最高的節(jié)點(diǎn)作為目標(biāo)節(jié)點(diǎn)。從而使得每個機(jī)器人基于全局信息獨(dú)立在線決策。機(jī)器人在決策后也會向所有其他機(jī)器人發(fā)送到達(dá)信息和意圖信息，使每個機(jī)器人獲知全局信息。整個過程如圖5所示。

采用期望平均空閑時間和期望瞬時空閑時間構(gòu)造效用函數(shù)?；谒矔r空閑時間定義，期望瞬時空閑時間定義為

Iviexp（t）=t－tlast+cost/VEL（17）

其中：cost代表前往目標(biāo)點(diǎn)的距離；VEL代表機(jī)器人的平均速度。

根據(jù)平均空閑時間定義，用訪問次數(shù)表示如下：

其中：ttotal表示機(jī)器人總計巡邏時間。用Δtexception表示機(jī)器人宕機(jī)、充電等行為所占的時間，那么ttotal可以表示為

ttotal=t－t0－Δtexception（19）

其中：t0代表頂點(diǎn)第一次被訪問的時刻，也代表機(jī)器人的啟動時刻。定義期望平均空閑時間如下：

期望瞬時空閑時間和期望平均空閑時間反映了機(jī)器人未選擇頂點(diǎn)vi作為目標(biāo)點(diǎn)時可能發(fā)生的平均空閑時間和瞬時空閑時間。因此機(jī)器人傾向于前往潛在空閑時間更高的目標(biāo)點(diǎn)。效用值U1表示為

其中：U1為大于零的正數(shù)；α，β為比例因子。

采用意圖信息避免兩個機(jī)器人訪問同一個節(jié)點(diǎn)，減小機(jī)器人之間的沖突，得到最終決策用的效用度U。當(dāng)機(jī)器人ri的意圖節(jié)點(diǎn)為vj時，Itri=vj，反之Itrivj。當(dāng)一帶機(jī)器人的其中一個對某節(jié)點(diǎn)存在意圖時，其向所有巡邏機(jī)器人發(fā)布意圖信息Itri=vj。當(dāng)其他機(jī)器人收到該信息后，其在決策時將該節(jié)點(diǎn)效用度歸零。由于效用度是由期望平均空閑時間和期望瞬時空閑時間構(gòu)造的大于零的值，所以鄰居機(jī)器人會選擇其余節(jié)點(diǎn)作為目標(biāo)節(jié)點(diǎn)，避免了兩個機(jī)器人之間的潛在沖突。機(jī)器人ri存儲著所有其他機(jī)器人的意圖節(jié)點(diǎn)序列It={Itr1=vi1 Itr2=vi2 … Itrm=vim}，簡記為It={vi1 vi2 … vim}。用于決策的機(jī)器人ri對鄰居節(jié)點(diǎn)vi的效用值U最終表示為

本文所提的集中式巡邏算法稱為基于全局信息的期望平均空閑和期望瞬時空閑算法（expected average idleness and expected idleness of global information，EAIG），算法偽代碼如下所示。

算法1 基于全局信息的期望平均空閑和期望瞬時空閑的算法

2.3 分布式多機(jī)器人巡邏算法EAIL-C

2.3.1 算法描述

基于上述離散時間一致性算法的實現(xiàn)和集中式多機(jī)器人巡邏算法EAIG建立完全分布式多機(jī)器人巡邏算法。與EAIG的不同點(diǎn)有兩個：a）機(jī)器人隨時都在同鄰居機(jī)器人進(jìn)行協(xié)商以刷新收斂信息，替代了到達(dá)目標(biāo)節(jié)點(diǎn)時向所有機(jī)器人的廣播行為;b）決策所用的信息是局部信息而不是全局信息。機(jī)器人的協(xié)商過程和決策過程是相互關(guān)聯(lián)的兩個過程，整個過程如圖6所示。

在協(xié)商過程中，當(dāng)k=0時，機(jī)器人通過本地信息初始化其協(xié)商值。用列向量表示所有的協(xié)商值，并設(shè)計在一條協(xié)商消息中。在每個單位協(xié)商時間ΔT期間，此協(xié)商消息是唯一的。協(xié)商消息將向鄰居機(jī)器人多次廣播，等待一致性迭代計算。然后通過離散時間一致性計算得到下一個單位協(xié)商時間更新的協(xié)商值和收斂值。最后，在k=ktotal時刷新協(xié)商結(jié)果并儲存在收斂值中。當(dāng)需要進(jìn)行決策時，機(jī)器人基于收斂的協(xié)商信息對全局信息進(jìn)行估計，采用估計信息替代全局信息并計算效用值。與EAIG類似，機(jī)器人從鄰接節(jié)點(diǎn)中選擇效用值最大的節(jié)點(diǎn)作為目標(biāo)點(diǎn)。

EAIG的全局信息和EAIL-C中基于協(xié)商信息預(yù)估的全局信息對比于表1中。協(xié)商信息預(yù)估全局信息的過程見下節(jié)。

式（23）～（27）與式（17）～（22）類似，設(shè)計了分布式多機(jī)器人巡邏算法EAIL-C計算各節(jié)點(diǎn)效用值的公式。與EAIG的決策邏輯相同，效用值最高的鄰居節(jié)點(diǎn)將成為目標(biāo)節(jié)點(diǎn)。

采用最近一次訪問時刻估計值替代基于全局信息的最近一次訪問時刻，期望瞬時空閑時間定義為

Ivi exp（t）=t－testj+cost/VEL（23）

采用節(jié)點(diǎn)訪問次數(shù)估計值替代節(jié)點(diǎn)總訪問次數(shù)，平均空閑時間表示為

定義期望平均空閑時間如下：

效用值U1如式（26）所示，一般情況下，U1為大于零的正數(shù)。

采用節(jié)點(diǎn)意圖估計值序列Itest替代每個機(jī)器人的意圖序列It。機(jī)器人ri對節(jié)點(diǎn)vj的二元的意圖估計值Itesti_j，簡記為Itestj。當(dāng)Itestj=1時，存在機(jī)器人對該節(jié)點(diǎn)的訪問意圖。當(dāng)Itestj=0時，沒有機(jī)器人計劃訪問該節(jié)點(diǎn)。當(dāng)一帶機(jī)器人的其中一個對某節(jié)點(diǎn)存在意圖時，其意圖協(xié)商信息通過鄰居機(jī)器人之間的相互協(xié)商影響到這一帶的所有機(jī)器人的協(xié)商信息，并進(jìn)一步影響到這一帶機(jī)器人對全局信息的預(yù)估值Itestj。當(dāng)其余機(jī)器人根據(jù)協(xié)商信息預(yù)估值判斷該節(jié)點(diǎn)時，該節(jié)點(diǎn)的效用度歸零。由于其他節(jié)點(diǎn)的效用度大于零，所以機(jī)器人不再選擇該節(jié)點(diǎn)作為目標(biāo)節(jié)點(diǎn)，避免了機(jī)器人之間的潛在沖突。機(jī)器人存儲并通過協(xié)商信息預(yù)估著整張地圖所有節(jié)點(diǎn)的意圖估計序列Itest={Itestv1 Itestv2 … Itestvn}。該估計序列由協(xié)商信息估計得到并經(jīng)由協(xié)商過程不斷刷新，與機(jī)器人數(shù)量無關(guān)，是局部信息。用于決策的機(jī)器ri對鄰居節(jié)點(diǎn)vj的效用值U最終表示如下：

上述完全分布式巡邏算法稱為基于局部信息的期望平均空閑和期望瞬時空閑的算法，簡稱為EAIL-C（expected average idleness and expected idleness of local information-cycled negotiation）。該算法的偽代碼如算法2所示。一致性協(xié)商包括時間檢查程序（time check）、一致性消息發(fā)布程序（publish consensus message）、一致性消息接收程序（receive consensus message）和節(jié)點(diǎn)到達(dá)程序（goal reached）。時間檢查過程在給定時間通過ROS掛鐘時間回調(diào)來計算新的協(xié)商值，而另外兩個過程用于信息傳輸。巡邏行為包含在節(jié)點(diǎn)到達(dá)程序中，當(dāng)機(jī)器人到達(dá)一個節(jié)點(diǎn)時被觸發(fā)。

算法2 基于局部信息的期望平均空閑和期望瞬時空閑的算法

2.3.2 協(xié)商信息設(shè)計與全局信息預(yù)估

本節(jié)介紹了協(xié)商過程和估計全局信息的過程。鑒于固定拓?fù)淠軌蚩芍貜?fù)地描述信息的協(xié)商過程，本節(jié)示意圖中機(jī)器人之間的關(guān)系均由固定拓?fù)涿枋?，如圖7所示。

為了預(yù)估EAIG的全局信息，設(shè)計機(jī)器人ri對節(jié)點(diǎn)vj的協(xié)商信息。EAIL-C的協(xié)商信息初始值、協(xié)商值、收斂值如表2所示。其中，協(xié)商信息初始值由每個機(jī)器人根據(jù)自身的節(jié)點(diǎn)訪問情況賦值。經(jīng)過一致性計算得到協(xié)商值，協(xié)商完成后保存收斂值。每當(dāng)機(jī)器人需要決策時，基于協(xié)商值和收斂值計算全局信息的估計值。

采用最大一致性協(xié)商K2次得到機(jī)器人最近一次訪問節(jié)點(diǎn)的時刻tlastj的收斂值t_delastj。機(jī)器人之間的協(xié)商過程如圖8所示，用收斂值代表預(yù)估的最近訪問時刻，即testj=t_delastj。

當(dāng)節(jié)點(diǎn)vj是機(jī)器人ri的目標(biāo)節(jié)點(diǎn)時Itj=1，否則Itj=0。采用平均一致性協(xié)商K2次獲取節(jié)點(diǎn)意圖收斂值Itcoj，易知，0≤Itcoj≤1。當(dāng)且僅當(dāng)Itdej=0并且Itcoj=0時沒有機(jī)器人計劃訪問該節(jié)點(diǎn)。從而通過式（28）得到估計的意圖信息Itestj。最大一致性也在這里有效。協(xié)商過程如圖9所示。

采用平均一致性協(xié)商K1次得到節(jié)點(diǎn)vj的訪問次數(shù)kj的收斂值kdej，kdej反映了節(jié)點(diǎn)的平均訪問次數(shù)。然而，平均一致性協(xié)商需要更多的協(xié)商時間來獲得節(jié)點(diǎn)訪問次數(shù)的收斂值，而在協(xié)商期間節(jié)點(diǎn)可能被訪問。這將導(dǎo)致協(xié)商值無法及時刷新。因此，有必要設(shè)計一個輔助協(xié)商變量以估計更新的全局信息，即設(shè)計一種基于收斂協(xié)商和趨勢協(xié)商相結(jié)合的雙重協(xié)商策略。結(jié)合收斂協(xié)商和趨勢協(xié)商的價值，準(zhǔn)確地估計全局信息。設(shè)計節(jié)點(diǎn)訪問次數(shù)趨勢ktrj作為機(jī)器人ri關(guān)于節(jié)點(diǎn)vj的協(xié)商變量，表示在協(xié)商期間節(jié)點(diǎn)是否被訪問。在一輪kj協(xié)商初始化之后，如果機(jī)器人ri訪問節(jié)點(diǎn)vj，那么ktrj=1，否則ktrj=0。采用平均一致性協(xié)商K2次獲取節(jié)點(diǎn)訪問次數(shù)趨勢收斂值ktrdej。與Itcoj和Itdej類似，節(jié)點(diǎn)是否被訪問是由ktrcoj和ktrdej來確定。因為節(jié)點(diǎn)訪問趨勢不能反映多次訪問，例如在同一協(xié)商中訪問了節(jié)點(diǎn)兩次，所以協(xié)商周期ttotal需滿足

ttotal

其中：Imin表示最小空閑時間。

為了結(jié)合kdej和ktrdej，需要估計機(jī)器人數(shù)量。機(jī)器人ri的協(xié)商變量mi_k表示機(jī)器人rk是否存在于協(xié)商中，通過式（30）初始化。采用平均一致性協(xié)商K2次獲取協(xié)商值mcoi_k，最大一致性也可以通過收斂值mdei_k是否等于0判斷機(jī)器人rk是否參與了協(xié)商。進(jìn)而可以由式（31）得到參與協(xié)商的機(jī)器人數(shù)量mi。

其中：「·表示向上取整。因此，機(jī)器人數(shù)量的協(xié)商過程如圖10所示。

因此節(jié)點(diǎn)訪問次數(shù)由式（32）估計，節(jié)點(diǎn)訪問次數(shù)的協(xié)商過程如圖11所示。

Itcoj、ktrcoj和mcoi_k只需要確定收斂值是否等于零，因此最大一致性和平均一致性都有效。

2.3.3 信息協(xié)商中的延遲

離散時間一致算法的實現(xiàn)過程具有延遲效應(yīng)，包括延遲開始和延遲結(jié)束。以意向協(xié)商為例，如圖12（a）所示，當(dāng)機(jī)器人4計劃訪問節(jié)點(diǎn)0并在第566.2 s以1初始化其Itco4_0時，其鄰居的協(xié)商信息依次受到影響，需要3個單位協(xié)商時間（0.6 s）才能影響到最遠(yuǎn)的鄰居1號機(jī)器人Itco1_0。即Itco1_0在第566.8 s時受到影響。考慮到協(xié)商值會周期性初始化，實際延遲可能會更長。當(dāng)兩個機(jī)器人同時到達(dá)相鄰的目標(biāo)節(jié)點(diǎn)時，延遲開始會導(dǎo)致兩個機(jī)器人選擇與目標(biāo)節(jié)點(diǎn)相同的節(jié)點(diǎn)，從而導(dǎo)致沖突。另一方面，如圖12（b）所示，當(dāng)意圖信息在第584.2 s消失后，延遲效應(yīng)阻止了協(xié)商意圖在第585.2 s前返回到零。延遲結(jié)束阻止機(jī)器人選擇剛剛被另一個機(jī)器人訪問的節(jié)點(diǎn)，從而對計劃的路徑造成影響。由于機(jī)器人的沖突，延遲開始的影響遠(yuǎn)遠(yuǎn)超過延遲結(jié)束。所以，應(yīng)盡量避免延遲開始。

解決延遲協(xié)商意圖引起沖突的一種可能的解決方案是將鄰居意圖和協(xié)商意圖結(jié)合起來。其原因是，機(jī)器人選擇了一個相鄰的節(jié)點(diǎn)作為目標(biāo)節(jié)點(diǎn)，因此該潛在的沖突機(jī)器人位于其目標(biāo)節(jié)點(diǎn)的相鄰節(jié)點(diǎn)上。只要機(jī)器人的通信半徑能夠覆蓋相鄰節(jié)點(diǎn)的相鄰節(jié)點(diǎn)，它就可以直接與潛在的沖突機(jī)器人通信，獲取它們的本地意圖信息。

另一方面，考慮到跟隨行為的風(fēng)險，不能不考慮鄰居意圖而單獨(dú)使用協(xié)商意圖。跟隨行為意味著兩個機(jī)器人總是一個接一個作出相同的選擇，導(dǎo)致巡邏效果降低。其原因在于，鄰居離開某節(jié)點(diǎn)的局部意圖是準(zhǔn)確的，而鄰居剛剛訪問該節(jié)點(diǎn)的信息是延遲的。因此，跟隨者機(jī)器人不知道這個節(jié)點(diǎn)剛剛被訪問，并且總是用相同的決策信息作出與前一個機(jī)器人相同的選擇。當(dāng)機(jī)器人之間的關(guān)系固定，如圖7所示，且地圖拓?fù)涞母鬟呴L度相等時，跟隨問題變得更加明顯，特別是在機(jī)器人1和4之間。通信半徑內(nèi)鄰居間的通信使得可能沖突的兩個機(jī)器人之間產(chǎn)生了直接的意圖信息交互，提高了意圖傳輸?shù)乃俣?，從而解決了協(xié)商信息延遲的問題。當(dāng)機(jī)器人進(jìn)行決策時，如果協(xié)商信息指示目標(biāo)節(jié)點(diǎn)存在訪問意圖（Itestj=1），或者接收到鄰居機(jī)器人意圖訪問該節(jié)點(diǎn)的信息，那么機(jī)器人的效用值歸零，不會將該節(jié)點(diǎn)作為目標(biāo)節(jié)點(diǎn)。

3 仿真實驗與結(jié)果

仿真實驗的目的是通過模擬一個真實的環(huán)境從而比較不同的多機(jī)器人巡邏算法，并確認(rèn)EAIL-C是否具有與EAIG相似的特性。文獻(xiàn)［23］設(shè)計了基于ROS和Stage的patrolling_sim功能包以進(jìn)行多機(jī)器人巡邏策略的仿真開發(fā)驗證，不斷添加新的巡邏算法并更新平臺。功能包采用ROS開源導(dǎo)航包進(jìn)行導(dǎo)航，可直接部署在基于ROS的機(jī)器人上實現(xiàn)應(yīng)用。本文基于patrolling_sim功能包添加了EAIG、EAIL-C兩個新算法并對相關(guān)文件進(jìn)行了修改以適應(yīng)算法，從而驗證算法，并同功能包已有算法進(jìn)行對比。以ROS移動機(jī)器人為對象模擬實際環(huán)境應(yīng)用場景進(jìn)行相關(guān)仿真實驗。

3.1 仿真設(shè)置

采用兩種地圖（cumberland和grid）對巡邏算法進(jìn)行評價對比，如圖13和表3所示，在實驗開始前地圖及其拓?fù)湟阎?，其中，grid地圖連通性更好且所有節(jié)點(diǎn)之間的距離相等。

考慮到機(jī)器人之間的關(guān)系變化，基于通信半徑約束確定機(jī)器人之間的關(guān)系。雖然較低的通信半徑意味著對巡邏機(jī)器人的要求較低，但應(yīng)考慮鄰居的意圖以避免發(fā)生沖突。因此機(jī)器人的通信半徑應(yīng)至少覆蓋到鄰居節(jié)點(diǎn)的鄰居節(jié)點(diǎn)。不同地圖的實驗通信半徑Rset應(yīng)大于最小值Rmin，如表4所示。

基于通信半徑建立了兩種機(jī)器人關(guān)系。第一個名為EAIL-C1，機(jī)器人只使用協(xié)商信息，因為當(dāng)兩個機(jī)器人基于通信半徑建立關(guān)系時，延遲啟動引起的沖突與固定拓?fù)湎啾炔⒉幻黠@。第二個名為EAIL-C2，同時考慮了通信半徑以內(nèi)的鄰居意圖和協(xié)商意圖，以最大程度減少沖突。一個固定的拓?fù)浣Y(jié)構(gòu)有利于滿足一致性的收斂條件。因此，本文認(rèn)為由固定拓?fù)渌枋龅臋C(jī)器人之間的關(guān)系是基于通信半徑的交換拓?fù)涞娜趸?，在實驗中不考慮固定拓?fù)洹?/p>

另外：a）EAIL-C1只采用協(xié)商信息進(jìn)行決策；b）EAIL-C2采用協(xié)商信息以及通信半徑以內(nèi)的鄰居意圖信息共同決策。

采用四個機(jī)器人進(jìn)行實驗，機(jī)器人的平均速度VEL取值1 m/s。算法參數(shù)設(shè)置為：α=1、β=1、ε=1/5、K1=35、K2=5。每組仿真實驗持續(xù)1 h并重復(fù)三次。在通過方差分析檢驗（ANOVA）的條件下，為每個算法選擇三個仿真結(jié)果。各算法的p值均大于0.1，表示相同分布的概率較高。采用監(jiān)控節(jié)點(diǎn)收集信息和求解評價指標(biāo)。

用于對比的算法包括SEBS、DTAP，這兩種算法都可以反映EAIG和EAIL-C的特性。算法對比如表5所示。

3.2 巡邏過程及巡邏算法對比

多機(jī)器人巡邏過程如圖14所示，圖中四個機(jī)器人在各自執(zhí)行巡邏任務(wù)。通過記錄單個機(jī)器人巡邏過程中的位置，繪制其1 h軌跡圖，如圖15所示。

cumberland地圖的實驗結(jié)果如表6所示，EAIG算法的全圖空閑時間平均值IGavg均介于SEBS和DTAP之間，接近于SEBS。而EAIG的全圖空閑時間標(biāo)準(zhǔn)差I(lǐng)Gstddev、全圖空閑時間最大值IGmax大于SEBS和DTAP。EAIL-C繼承了EAIG的算法特性，它的平均空閑時間略有增加，但總體上與EAIG處于同一水平。由于協(xié)商信息的延遲效應(yīng)，EAIL-C1和EIAL-C2的干擾率均略高于EAIG。在鄰居意圖的影響下，EAIL-C2的干擾率低于EAIL-C1。

grid地圖的結(jié)果如表7所示，EAIG的全局平均空閑時間IGavg優(yōu)于DTAP，略優(yōu)于SEBS。EAIG的全圖空閑時間標(biāo)準(zhǔn)差、全圖空閑時間最大值與SEBS和DTAP處于同一水平。因此，EAIG的性能優(yōu)于SEBS和DTAP。因為grid地圖的連通性比cumberland地圖更好，所以grid地圖的干擾率比cumberland高，其性能受到的影響更大。EAIL-C1和EAIL-C2的全局平均空閑時間IGavg與EAIG的水平相同。EAIL-C1和EAIL-C2的空閑時間標(biāo)準(zhǔn)差I(lǐng)Gstddev和最大空閑時間IGmax均高于EAIG，而EAIL-C2的性能優(yōu)于EAIL-C1，這是由于EAIL-C2具有更準(zhǔn)確的意圖信息，帶來更低的干擾率和更好的性能?？傮w來說，EAIL-C的巡邏效果與EAIG非常接近。

使用箱線圖分析不同節(jié)點(diǎn)的平均空閑時間，如圖16、17所示。在cumberland和grid地圖中，SEBS的平均空閑時間都低于DTAP，但存在許多異常值。DTAP以增加節(jié)點(diǎn)的平均空閑時間為代價減少了異常值。EAIG在保持了較低的平均值水平的基礎(chǔ)上異常值較少，因此節(jié)點(diǎn)的平均空閑時間表現(xiàn)更好。同時，EAIL-C具有與EAIG相似的特征，而EAIL-C2在grid地圖的表現(xiàn)優(yōu)于EAIL-C1。

綜上所述，在本地信息和鄰居協(xié)作的支持下，EAIL-C取得了與EAIG相似的性能。避免了全局信息，并考慮了通信約束。當(dāng)?shù)貓D的拓?fù)溥B通度較低時，EAIL-C就可以基本反映EAIG的算法特征，并在一定程度上取代原算法EAIG。當(dāng)圖的拓?fù)溥B通性較高時，EAIL-C的干擾率越高。在通信半徑內(nèi)鄰居的局部意圖的幫助下，EAIL-C2取得了比EAIL-C1更穩(wěn)定的巡邏效果。

3.3 一致性算法的性能確認(rèn)

一致性算法的收斂性對性能起著重要作用。因此，本節(jié)使用cumberland地圖中EAIL-C1的數(shù)據(jù)來確定其收斂性。本小節(jié)分析了協(xié)商K2次的意圖信息和協(xié)商K1次的節(jié)點(diǎn)訪問次數(shù)。

機(jī)器人并不總是能保持完全的連接。機(jī)器人之間連邊的數(shù)量對收斂結(jié)果有不可否認(rèn)的影響，因此，監(jiān)控節(jié)點(diǎn)每秒鐘記錄一次每個機(jī)器人的位置。不同數(shù)量的連接邊對應(yīng)的時間比例如表8所示，大約30%的時間有3條或更多的邊，這意味著這四個機(jī)器人保持完全連接，可以準(zhǔn)確地估計全局信息。大約35%的時間里，有兩條邊，即兩個或三個機(jī)器人連接起來，它們的信息被用來估計全局信息。

意圖協(xié)商是趨勢協(xié)商，其目標(biāo)是確定協(xié)商值是否等于零，并估計對應(yīng)的全局信息。通過在每個單位協(xié)商時間ΔT處存儲估計的全局信息和真實的全局信息并進(jìn)行比較，確認(rèn)所估計的意圖是否準(zhǔn)確。估計的全局意圖Itestj受到信息協(xié)商延遲和機(jī)器人之間關(guān)系的影響。結(jié)果顯示，94.32%的數(shù)據(jù)與全局信息一致，如表9所示。這超過了準(zhǔn)確估計全局信息的時間35%。原因是單個節(jié)點(diǎn)超過85%的時間是沒有機(jī)器人訪問的意圖的。

節(jié)點(diǎn)訪問次數(shù)的協(xié)商是收斂協(xié)商，其目標(biāo)是得到收斂值kdej。收斂性受到一致性收斂速度和機(jī)器人之間關(guān)系的影響。當(dāng)k=K1時計算kconvi_j，以檢查協(xié)商收斂情況，如式（33）所示。

如果kconvi_j< 0.25，則認(rèn)為它是收斂的。結(jié)果表明，95%的協(xié)商滿足收斂條件，如表10所示。

3.4 不同機(jī)器人數(shù)量和通信距離下的性能驗證

本節(jié)對EAIL-C2算法進(jìn)行進(jìn)一步性能驗證。考慮2，4，6，8四種機(jī)器人數(shù)量進(jìn)行對比?？紤]避免沖突的最小通信半徑、覆蓋全圖的最大通信半徑以及介于兩者之間的通信半徑。grid地圖對12 m、24 m、36 m三種通信半徑進(jìn)行對比，cumberland地圖對16 m、40 m、64 m三種通信半徑進(jìn)行對比，其余參數(shù)與上節(jié)仿真設(shè)置相同?？紤]grid、cumberland兩種地圖環(huán)境。

圖18、19分別展示了SEBS、DTAP、EAIG和EAIL-C2算法在grid和cumberland兩種地圖中的全圖空閑時間平均值IGavg和標(biāo)準(zhǔn)差I(lǐng)Gstddev隨時間的變化，其在1 500 s以內(nèi)穩(wěn)定。因此，本節(jié)仿真時間為60 min。每組仿真實驗至少重復(fù)3次，取其平均值進(jìn)行對比。

grid地圖的結(jié)果如表11、12所示。其中，表11對比了EAIL-C2在不同機(jī)器人數(shù)量和通信半徑條件下的巡邏效果。在同一通信半徑下，隨著機(jī)器人數(shù)量的提升，全圖平均空閑時間、全圖空閑時間標(biāo)準(zhǔn)差下降，機(jī)器人之間的干擾率上升。全圖空閑時間最大值在機(jī)器人數(shù)量為2時出現(xiàn)。因此，機(jī)器人數(shù)量對巡邏效果有重要作用。而隨著機(jī)器人通信半徑的增加，全圖平均空閑時間、全圖空閑時間標(biāo)準(zhǔn)差、機(jī)器人之間的干擾率沒有明顯區(qū)別。因此，算法EAIL-C2受通信半徑的影響較小。

表12展示了不同機(jī)器人數(shù)量下對比算法的評價指標(biāo)。在不同機(jī)器人數(shù)量下，EAIG和EAIL-C2的全局平均空閑時間均優(yōu)于DTAP，接近于SEBS。隨著機(jī)器人數(shù)量的增加，各個算法的全圖空閑時間標(biāo)準(zhǔn)差隨之下降。在干擾率方面，隨著機(jī)器人數(shù)量的增加，機(jī)器人之間的干擾率不斷上升。相比之下，SEBS的干擾率上升明顯，而DTAP、EAIG、EAIL-C2基本處于同一水平。EAIL-C2的干擾率高于原算法EAIG。因此，EAIL-C2在各個條件下的評價指標(biāo)均略弱于基于全局信息的EAIG算法，但差距不大。

EAIL-C2在cumberland地圖的實驗結(jié)果如表13所示，機(jī)器人數(shù)量對實驗結(jié)果的影響大于通信半徑的影響。在同一通信半徑下，隨著機(jī)器人數(shù)量的提升，全圖平均空閑時間、全圖空閑時間標(biāo)準(zhǔn)差下降，機(jī)器人之間的干擾率上升。全圖空閑時間最大值出現(xiàn)在機(jī)器人數(shù)量為2時，隨著機(jī)器人數(shù)量的增加呈現(xiàn)遞減趨勢。而隨著機(jī)器人通信半徑的增加，全圖平均空閑時間、全圖空閑時間標(biāo)準(zhǔn)差、機(jī)器人之間的干擾率沒有明顯區(qū)別。因此，算法EAIL-C2受通信半徑的影響較小。

表14展示了對比算法的評價指標(biāo)。在不同機(jī)器人數(shù)量下，EAIG和EAIL-C2的全局平均空閑時間均優(yōu)于DTAP，略弱于SEBS。EAIG和EAIL-C2的全圖空閑時間標(biāo)準(zhǔn)差大于SEBS和DTAP。隨著機(jī)器人數(shù)量的增加，所有算法的全圖平均空閑時間、全圖空閑時間標(biāo)準(zhǔn)差下降，機(jī)器人之間的干擾率上升。最大干擾率出現(xiàn)在八個機(jī)器人的SEBS算法中，而EAIG的干擾率介于DTAP和SEBS之間。EAIL-C2的干擾率高于EAIG，其余指標(biāo)和EAIG接近，基本處于同一水平。

圖20展示了不同機(jī)器人數(shù)量和不同通信半徑下的各個節(jié)點(diǎn)的平均空閑時間箱線圖。在grid地圖中，SEBS的平均空閑時間都低于DTAP，但存在許多異常值。EAIG的平均值接近于SEBS，同時異常值較低。因此節(jié)點(diǎn)的平均空閑時間表現(xiàn)更好。同時，EAIL-C在不同半徑下具有與EAIG相似的分布。在cumberland地圖中，EAIG的效果介于SEBS和DTAP之間，接近于SEBS，其異常值同樣較少。EAIL-C2的效果與EAIG類似，受通信半徑影響較小。

綜上所述，EAIG相比DTAP具有更低的平均空閑時間，相比SEBS異常值更少，具有一定優(yōu)勢。EAIL-C具有和EAIG類似的算法特點(diǎn)，能夠基本達(dá)到EAIG的算法性能。

4 結(jié)束語

本文采用離散時間一致的方法實現(xiàn)了完全分布式多機(jī)器人巡邏算法EAIL-C，并與原有的集中式巡邏算法EAIG等巡邏算法進(jìn)行了比較。算法考慮了通信半徑和局部信息的約束條件。在每個周期中都可以獲得最新的協(xié)商結(jié)果，并且協(xié)商信息獨(dú)立于特定的機(jī)器人。機(jī)器人之間的關(guān)系會根據(jù)通信半徑和機(jī)器人位置的變化而變化。采用仿真器Stage對算法進(jìn)行了仿真和比較，驗證了所提算法EAIL-C具有與原算法EAIG相似的特性和性能。EAIL-C算法為后續(xù)實現(xiàn)更大規(guī)模的機(jī)器人集群提供了思路，所提出的趨勢協(xié)商和收斂協(xié)商的協(xié)商方法可以擴(kuò)展到其他集中式巡邏算法，以實現(xiàn)完全分布。所提算法適用于巡邏范圍大且通信半徑有限的情況。例如：森林火災(zāi)實時監(jiān)控、海洋污染防控、邊境線巡邏等。

在未來的多機(jī)器人分布式巡邏算法的研究中，可以考慮以下兩個方向：采用更優(yōu)秀的離散時間一致性算法來加速協(xié)商速度，這意味著更低的Ktotal；綜合考慮機(jī)器人的位置和通信半徑、機(jī)器人之間的關(guān)系維持和巡邏任務(wù)的完成，設(shè)計出與實際情況關(guān)聯(lián)更緊密的完全分布式巡邏算法。

參考文獻(xiàn)：

［1］Huang Li，Zhou Mengchu，Hao Kuangrong，et al. A survey of multi-robot regular and adversarial patrolling［J］. IEEE/CAA Journal of Automatica Sinica，2019，6（4）： 894-903.

［2］Chen Feiran，Chen Bin，Zhu Zhengqiu，et al. A cost-beneficial area-partition-involved collaborative patrolling game in a large-scale chemical cluster［J］. Process Safety and Environmental Protection，2021，145： 71-82.

［3］Machado A，Ramalho G，Zucker J D，et al. Multi-agent patrolling： an empirical analysis of alternative architectures［J］. Lecture Notes in Computer Science，2003，2581（1）： 81-97.

［4］武麗霞. 多機(jī)器人系統(tǒng)分布式巡邏算法設(shè)計及實驗驗證［D］. 蘭州： 蘭州交通大學(xué)，2019. （Wu Lixia. Distributed patrol algorithm design and experimental verification for multi-robot system［D］. Lanzhou： Lanzhou Jiaotong University，2019.）

［5］史天伊. 多機(jī)器人系統(tǒng)巡邏分布式算法研究［D］. 蘭州： 蘭州交通大學(xué)，2021. （Shi Tianyi. Research on distributed patrol algorithm of multi-robot system［D］.Lanzhou：Lanzhou Jiaotong University，2021.）

［6］趙云濤，李宗剛，杜亞江. 基于最大空閑時間的分布式巡邏機(jī)器人數(shù)量優(yōu)化［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.）

［7］霍耀彥，李宗剛，高溥. 基于節(jié)點(diǎn)重要度的多機(jī)器人分布式巡邏策略［J］. 計算機(jī)應(yīng)用研究，2022，39（2）： 510-514. （Huo Yaoyan，Li Zonggang，Gao Pu. Distributed multi-robot patrolling stra-tegy based on importance of nodes［J］. Application Research of Computers，2022，39（2）： 510-514.）

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

［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］王通，黃攀峰，董剛奇. 啟發(fā)式多無人機(jī)協(xié)同路網(wǎng)持續(xù)監(jiān)視軌跡規(guī)劃［J］. 航空學(xué)報，2020，41（S1）： 723-753. （Wang Tong，Huang Panfeng，Dong Gangqi. Cooperation path planning of multi-UAV in road-network continuous monitoring［J］. Acta Aeronautica et Astronautica Sinica，2020，41（S1）： 723-753.）

［11］Portugal D，Rocha R P. Cooperative multi-robot patrol with Bayesian learning［J］. Autonomous Robots，2016，40（5）： 929-953.

［12］Farinelli A，Iocchi L，Nardi D. Distributed on-line dynamic task assignment for multi-robot patrolling［J］. Autonomous Robots，2017，41（6）： 1321-1345.

［13］Huang Li，Zhou Mengchu，Hao Kuangrong，et al. Multirobot cooperative patrolling strategy for moving objects［J］. IEEE Trans on Systems，Man，and Cybernetics Systems，2023，53（5）： 2995-3007.

［14］Ahmadian N，Lim G J，Torabbeigi M，et al. Smart border patrol using drones and wireless charging system under budget limitation［J］. Computers & Industrial Engineering，2022，164： 107891.

［15］Aggravi M，Sirignano G，Giordano P R，et al. Decentralized control of a heterogeneous human-robot team for exploration and patrolling［J］. IEEE Trans on Automation Science and Engineering，2022，19（4）： 3109-3125.

［16］Scherer J，Schoellig A P，Rinner B. Min-max vertex cycle covers with connectivity constraints for multi-robot patrolling［J］. IEEE Robotics and Automation Letters，2022，7（4）： 10152-10159.

［17］Caraballo L E，Diaz-banez J M，F(xiàn)abila-monroy R，et al. Stochastic strategies for patrolling a terrain with a synchronized multi-robot system［J］. European Journal of Operational Research，2022，301（3）： 1099-1116.

［18］Ren W，Beard R W. Distributed consensus in multi-vehicle cooperative control： theory and applications［M］. London： Springer-Verlag，2008.

［19］紀(jì)良浩，王慧維，李華青. 分布式多智能體網(wǎng)絡(luò)一致性協(xié)調(diào)控制理論［M］. 北京： 科學(xué)出版社，2015. （Ji Lianghao，Wang Huiwei，Li Huaqing. Multi-agent networks distributed consensus cooperative control theory［M］. Beijing： Science Press，2015.）

［20］Olfati-Saber R，Murray R M. Consensus problems in networks of agents with switching topology and time-delays［J］. IEEE Trans on Automatic Control，2004，49（9）： 1520-1533.

［21］Moreau L. Stability of multiagent systems with time-dependent communication links［J］. IEEE Trans on Automatic Control，2005，50（2）： 169-182.

［22］Ren W，Beard R W. Consensus seeking in multiagent systems under dynamically changing interaction topologies［J］. IEEE Trans on Automatic Control，2005，50（5）： 655-661.

［23］Portugal D，Iocchi L，F(xiàn)arinelli A. A ROS-based framework for simulation and benchmarking of multi-robot patrolling algorithms［M］// Koubaa A. Robot Operating System. Cham： Springer，2019： 3-28.