一種基于離散時(shí)間一致性理論的多機(jī)器人分布式巡邏算法

張鵬超 李宗剛

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

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

中圖分類號(hào)：TP242?? 文獻(xiàn)標(biāo)志碼：A??? 文章編號(hào)：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ī)器人巡邏問(wèn)題（MRPP）是指多個(gè)機(jī)器人在目標(biāo)區(qū)域內(nèi)或周圍移動(dòng)，以保護(hù)或監(jiān)督目標(biāo)區(qū)域，達(dá)到安全目的的活動(dòng)［1］。多機(jī)器人巡邏應(yīng)用廣泛，例如城市安保巡邏、邊境巡邏、海岸線巡邏、化工廠集群安保巡邏［2］、森林火災(zāi)預(yù)防巡邏等。通常，巡邏可以分為常規(guī)巡邏和對(duì)抗巡邏兩類［1］，常規(guī)巡邏指的是通過(guò)頻繁到訪目標(biāo)區(qū)域內(nèi)部以掌握該區(qū)域，對(duì)抗巡邏旨在通過(guò)檢測(cè)入侵者來(lái)保護(hù)目標(biāo)區(qū)域。

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

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

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

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

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

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

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

1 問(wèn)題描述

考慮用多個(gè)移動(dòng)機(jī)器人對(duì)給定環(huán)境進(jìn)行巡邏，實(shí)現(xiàn)對(duì)環(huán)境狀態(tài)變化的實(shí)時(shí)監(jiān)控。由于所考慮環(huán)境的結(jié)構(gòu)特征已知，故采用無(wú)向圖G1（V1，E1）對(duì)環(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}。從而所考慮巡邏問(wèn)題可視為多機(jī)器人通過(guò)合作對(duì)頂點(diǎn)集的遍歷。

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

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

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

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

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

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

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

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

Ivi（t）=t－tlast（3）

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

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

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

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

|εki|<Δ（7）

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

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

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

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

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

2.1 離散時(shí)間一致性算法

2.1.1 離散時(shí)間一致性算法

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

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

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

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

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

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é)商時(shí)的鄰接矩陣。當(dāng)機(jī)器人之間存在信息交換時(shí)aij=1，否則aij=0。經(jīng)過(guò)多次協(xié)商，所有協(xié)商變量即可收斂到最大值。類似地，可以收斂到所有機(jī)器人初始狀態(tài)的最小值。

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

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

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

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

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

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

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

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

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

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

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

本節(jié)設(shè)計(jì)了一種集中式多機(jī)器人巡邏算法。當(dāng)機(jī)器人到達(dá)起始節(jié)點(diǎn)或目標(biāo)節(jié)點(diǎn)時(shí)，它將采用以下三步選擇目標(biāo)點(diǎn)。首先，計(jì)算該節(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)。從而使得每個(gè)機(jī)器人基于全局信息獨(dú)立在線決策。機(jī)器人在決策后也會(huì)向所有其他機(jī)器人發(fā)送到達(dá)信息和意圖信息，使每個(gè)機(jī)器人獲知全局信息。整個(gè)過(guò)程如圖5所示。

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

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

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

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

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

ttotal=t－t0－Δtexception（19）

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

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

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

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

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

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

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

2.3.1 算法描述

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

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

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

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

采用最近一次訪問(wèn)時(shí)刻估計(jì)值替代基于全局信息的最近一次訪問(wèn)時(shí)刻，期望瞬時(shí)空閑時(shí)間定義為

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

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

定義期望平均空閑時(shí)間如下：

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

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

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

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

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

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

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

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

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

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

ttotal

其中：Imin表示最小空閑時(shí)間。

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

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

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

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

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

離散時(shí)間一致算法的實(shí)現(xiàn)過(guò)程具有延遲效應(yīng)，包括延遲開(kāi)始和延遲結(jié)束。以意向協(xié)商為例，如圖12（a）所示，當(dāng)機(jī)器人4計(jì)劃訪問(wèn)節(jié)點(diǎn)0并在第566.2 s以1初始化其Itco4_0時(shí)，其鄰居的協(xié)商信息依次受到影響，需要3個(gè)單位協(xié)商時(shí)間（0.6 s）才能影響到最遠(yuǎn)的鄰居1號(hào)機(jī)器人Itco1_0。即Itco1_0在第566.8 s時(shí)受到影響。考慮到協(xié)商值會(huì)周期性初始化，實(shí)際延遲可能會(huì)更長(zhǎng)。當(dāng)兩個(gè)機(jī)器人同時(shí)到達(dá)相鄰的目標(biāo)節(jié)點(diǎn)時(shí)，延遲開(kāi)始會(huì)導(dǎo)致兩個(gè)機(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ī)器人選擇剛剛被另一個(gè)機(jī)器人訪問(wèn)的節(jié)點(diǎn)，從而對(duì)計(jì)劃的路徑造成影響。由于機(jī)器人的沖突，延遲開(kāi)始的影響遠(yuǎn)遠(yuǎn)超過(guò)延遲結(jié)束。所以，應(yīng)盡量避免延遲開(kāi)始。

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

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

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

3.1 仿真設(shè)置

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

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

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

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

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

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

3.2 巡邏過(guò)程及巡邏算法對(duì)比

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

在未來(lái)的多機(jī)器人分布式巡邏算法的研究中，可以考慮以下兩個(gè)方向：采用更優(yōu)秀的離散時(shí)間一致性算法來(lái)加速協(xié)商速度，這意味著更低的Ktotal；綜合考慮機(jī)器人的位置和通信半徑、機(jī)器人之間的關(guān)系維持和巡邏任務(wù)的完成，設(shè)計(jì)出與實(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è)計(jì)及實(shí)驗(yàn)驗(yàn)證［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］趙云濤，李宗剛，杜亞江. 基于最大空閑時(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.）

［7］霍耀彥，李宗剛，高溥. 基于節(jié)點(diǎn)重要度的多機(jī)器人分布式巡邏策略［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ā)式多無(wú)人機(jī)協(xié)同路網(wǎng)持續(xù)監(jiān)視軌跡規(guī)劃［J］. 航空學(xué)報(bào)，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.