一种基于离散时间一致性理论的多机器人分布式巡逻算法

张鹏超 李宗刚

摘 要：在多机器人巡逻任务中，由于通信距离的限制，单个机器人很难获得全局信息。然而，现有的大多数多机器人分布式巡逻算法都要求每个机器人获得其巡逻区域的全局信息进行决策。因此，考虑到通信半径约束和局部信息约束，为了通过相邻机器人之间的交互完成巡逻任务，基于离散时间一致性理论提出了两种巡逻算法。算法1使用全局信息进行决策，算法2基于离散时间一致性理论实现局部信息对全局信息的预测进行决策。通过模拟器Stage对所提算法与对比算法在不同机器人数量、通信半径、地图环境下进行了对比。实验验证了所提出的基于局部信息的分布式多机器人巡逻算法具有与原算法类似的特性和性能，能够使机器人在没有全局信息的情况下判断全局状态，并基于邻居之间的协商完成巡逻任务。

关键词：巡逻；多机器人系统；分布式协同；离散时间一致性

中图分类号：TP242   文献标志码：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 引言

多机器人巡逻问题（MRPP）是指多个机器人在目标区域内或周围移动，以保护或监督目标区域，达到安全目的的活动［1］。多机器人巡逻应用广泛，例如城市安保巡逻、边境巡逻、海岸线巡逻、化工厂集群安保巡逻［2］、森林火灾预防巡逻等。通常，巡逻可以分为常规巡逻和对抗巡逻两类［1］，常规巡逻指的是通过频繁到访目标区域内部以掌握该区域，对抗巡逻旨在通过检测入侵者来保护目标区域。

常规巡逻问题广泛研究的算法有两种类型：a）集中式算法。如图1所示，其中要么存在一个中央控制器，要么每个机器人都可以获得全局信息并独立决策。集中式算法易于应用，适用于小规模巡逻任务。但是受中央控制器宕机和全局信息获取的影响较大，因此鲁棒性较差。b）分布式算法。如图2所示，每个机器人收集周围的环境信息并与邻居进行交换，即每个机器人只使用局部信息来作出决策。分布式算法具有更好的可扩展性和容错性，适用于大规模巡逻任務。出于本文的研究目的，仅将分布式算法的文献总结如下。

现有的分布式多机器人巡逻算法主要包括反应式策略、基于学习的方法和基于拍卖的方法。反应式策略是指每个机器人选择效用值最高的邻居节点作为目标节点。因此，通常采用拓扑图对环境进行建模。效用函数和评价标准可以通过空闲时间［3］、平均空闲时间［4，5］、全局平均最大空闲时间［6］、节点重要度［7］、期望空闲时间［8］、周围邻居的意图［9］、不确定度［10］等因素来构建。评价指标采用空闲时间、不确定度等因素构造。但是，现有反应策略大都采用将到达和意图信息发送给所有其他机器人的方式。因为每个机器人都需要拿到全局信息，所以不是完全的分布式策略。基于学习的方法通过积累历史经验帮助机器人适应动态环境。文献［9，11］提出了GBS、SEBS和CBLS算法，以贝叶斯算法实现机器人的学习，并通过空闲时间对算法进行评估。全局信息（包括到达信息和意图信息）通过无线自组织网络（MANET）发布和传输。仿真分析了不同通信故障率对巡逻效果的影响。然而没有考虑通信距离和机器人具体位置因素。基于长短期记忆网络的RLPM是在集中式算法HPCC上训练的，并在机器人之间没有通信的情况下工作。虽然RLPM算法不需要全局信息就可以实现接近于被学习的原始算法的性能，但是需要对特定地图和算法进行大量的训练。在基于拍卖的方法中，每个节点都被视为一个要分配的任务。每个机器人独立地求解其投标值并同所有其他机器人完成竞标以判断是否将竞标节点加入任务清单［12，13］。DTAP和EDCP都要求每个机器人将投标值发送给所有其他机器人进行投标，以确定是否将投标节点添加到其任务列表中。因为竞标过程中需要将出价信息发送到所有其他机器人，所以其集群大小和巡逻范围受到了限制，算法不是完全的分布式巡逻算法。

综上所述，现有文献中的大多数分布式巡逻算法虽然实现了线上自主决策，但是大都需要所有其他机器人的信息来作出决策，也就是说巡逻问题是基于全局信息来解决的。随着机器人规模的增加和巡逻范围的扩大，机器人在有限的硬件资源下传输、获取、存储全局信息的难度随之上升［14］。多机器人系统的通信要求、存储要求和计算要求也随着机器人数量的提高而提高，导致系统成本升高。因此有必要研究基于机器人自身局部信息的完全分布式的巡逻算法。例如对于有限通信范围内考虑连通性保持因素的巡逻算法研究［15～17］。一致性算法使得机器人在没有全局信息的情况下只需要相邻机器人之间的协商，就能够达成状态信息的一致。一致性算法在分布式多機器人系统协同控制中的理论优势使得设计基于局部信息的多机器人分布式巡逻算法成为可能。

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

a）建立了机器人之间的关系拓扑描述；

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

c）提出了一种基于局部信息的完全分布式巡逻算法，使得机器人通过邻居间通信协商、自身局部信息存储、局部信息计算求解完成巡逻任务。

1 问题描述

考虑用多个移动机器人对给定环境进行巡逻，实现对环境状态变化的实时监控。由于所考虑环境的结构特征已知，故采用无向图G1（V1，E1）对环境进行建模。其中顶点集V1={v1，v2，…，vn}表示在环境中所选取的若干关键节点，边集E1={eij}表示节点之间所存在的路径，如图3所示。顶点vi的相邻点的集合称为顶点vi的邻居，记为NG1（vi），NG1（vi）={vq∈V1：ei，q∈E1}。从而所考虑巡逻问题可视为多机器人通过合作对顶点集的遍历。

多机器人之间的关系也采用图G2（V2，E2）表示，其中V2={r1，r2，…，rm}表示用于巡逻的机器人，E2={cij}表示机器人之间的关系。当cij=1时，机器人ri可以接收到机器人rj的信息，反之不能。机器人ri相邻机器人的集合称为机器人ri的邻居，记为NG2（ri），NG2（ri）={rq∈V：ci，q∈E}。所有机器人在巡逻任务开始前已知拓扑地图G1（V1，E1），并建立了初始关系G2（V2，E2）。

本文将机器人之间的关系G2（V2，E2）分为基于固定拓扑的关系和基于距离的关系两种类型。前者通过固定机器人之间的关系实现固定的拓扑结构，后者预先设计机器人的通信半径，通过机器人的移动实现关系变化。本文在分析中采用固定关系分析机器人关系对巡逻效果的影响，在实验中考虑通信半径实现的关系变化，每个机器人具有相同的通信半径。

需要说明的是，多个机器人能否实现对环境的有效巡逻，取决于多机器人系统获取、传递并利用环境信息的方式。现有文献中，机器人到达目标节点后，向所有其他机器人广播巡逻节点到达信息、目标巡逻节点信息等其他信息。每个机器人在进行决策时所使用信息均为巡逻环境所有节点的信息。也就是说，巡逻问题的解决是基于全局信息解决全局问题。考虑到单个机器人难以获取全局信息的情况，有必要设计一种基于局部信息和邻居间的通信的完全分布式巡逻算法。

利用一致性理论在局部信息估计全局信息的理论基础，选取合适的状态信息和一致性算法，能够实现完全分布式巡逻算法。总的来说，一致性理论有以下三个好处：a）随时都可以获得最新的协商结果，而不需要判断所获取的全局信息是否完整；b）保密性和扩展性较好，因为协商信息是邻居机器人之间相互协商的结果，而且是局部信息，受群体中单个机器人的影响小；c）能够在巡逻算法中考虑通信半径等实际因素，从而建立机器人之间的关系。因此，本文将一致性理论作为理论依据。

由于被协商的状态量与时间无关，采用离散时间一致性理论建立协同算法。离散时间一致性理论的迭代公式为

其中：xki代表机器人i第k次协商的状态信息和协商变量。通过设计不同的函数f实现不同的一致性。如果所有机器人的状态最终趋于一致，则称达成了离散时间一致性，如式（2）所示。

因此，本文研究了如何基于离散时间一致性理论实现邻居机器人之间的协商行为。从而实现了一种基于局部信息和通信半径约束的分布式巡逻算法。

所提算法的评价包括巡逻效果的评价以及一致性算法的协商效率两个部分。通过空闲时间评价多机器人常规巡逻的巡逻效果。顶点vi在t时刻的瞬时空闲时间定义如式（3）所示。

Ivi（t）=t－tlast（3）

其中：tlast表示顶点最近一次被访问的时刻。顶点vi在t时刻的平均空闲时间定义如式（4）所示。

此外，定义了全图空闲时间标准差IGstddev、全图空闲时间最大值IGmax。用干扰率Ifrate（每分钟的干扰次数）评价两个机器人距离过近产生的冲突。

多机器人系统离散时间一致性算法的协商效果通常用协商次数k评价。首先定义机器人ri第k次协商的收敛误差εki如式（6）所示。

当收敛误差εki在误差限Δ以内时称协商收敛，如下所示。对应的协商次数称为收敛协商次数kconv。

|εki|<Δ（7）

结合巡逻算法和一致性算法，机器人可以通过局部信息来解决全局问题。本文感兴趣的是通过邻居机器人之间的通信来建立一个完全分布式的多机器人巡逻算法。问题陈述如下：

考虑使用多个机器人G2（V2，E2）对目标区域G1（V1，E1）进行巡逻。机器人关系G2由通信半径约束R形成，每个机器人只能得到相邻机器人的局部信息。目标是设计一种完全分布式巡逻算法，使机器人团队以局部信息、局部决策和局部执行完成巡逻任务。

2 基于离散时间一致性理论的分布式巡逻算法

根据基于一致性算法的分布式多机器人协同控制设计思路，构建算法需要两步：a）设计一个具有全局信息的集中式策略；b）基于一致性算法将全局信息转换为局部信息，建立分布式算法［18］。

因此，本文从离散时间一致性算法的实现、集中式多机器人巡逻算法和分布式多机器人巡逻算法三个方面描述所建立的分布式巡逻算法。

2.1 离散时间一致性算法

2.1.1 离散时间一致性算法

根据最终收敛一致状态值的不同，一致性可分为平均一致、最大一致、最小一致等［19］。

平均一致指的是收敛值为各个机器人初始值的平均值，采用文献［20］提出的离散时间一致性算法，其形式如下：

其中：p［k］ij为第k次迭代的信息权重。式（8）可写成矩阵形式，如式（9）所示。

其中：L［k］是拉普拉斯矩阵，它表示第k次協商时机器人之间的关系。当机器人之间的关系由无向图表示时收敛条件有两个［20～22］。首先，机器人之间的关系拓扑是连通的或联合连通的。其次，ε∈（0，1/dmax），dmax=maxilii表示图G2的最大出度。dmax也表示机器人的通信对象上限，即机器人的通信对象越多，系数ε越小，收敛越慢。

最大一致指的是收敛值为各个机器人初始值的最大值。离散时间一致性迭代形式如下：

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次协商时的邻接矩阵。当机器人之间存在信息交换时aij=1，否则aij=0。经过多次协商，所有协商变量即可收敛到最大值。类似地，可以收敛到所有机器人初始状态的最小值。

2.1.2 离散时间一致性算法实现

在现实过程中，巡逻机器人之间的关系与其空间位置密切相关，需要考虑其关系的变化。当两个机器人很接近时，它们应该能够直接建立关系。为了使机器人之间完成信息交换，给每一次迭代预留单位时间ΔT，定义为单位协商时间。单位协商时间的大小通常与多机器人系统的通信状况和计算能力相关。此外，迭代计算时刻由独立于机器人的壁钟时间决定，通过网络获得、判断和校正壁钟时间。因此，将机器人迭代计算时刻序列定义为tk=k×ΔT（k=1，2，…）。

基于上述过程，只要机器人在单位协商时间ΔT内完成信息交换，那么就确认机器人在该次计算中存在信息传输。这也意味着表示机器人之间关系的拓扑G2（V2，E2）在不同的ΔT内可以不同。因此，上述迭代过程能够适应机器人关系的变化。

2.1.3 重复进行的协商过程

因为节点被访问，所以需要刷新收敛值以预测最新全局信息。循环协商即以ktotal为周期指定协商次数重复进行的协商。ktotal是所有机器人已知的。每个重复的协商都被称为一个循环。当k=ktotal时，协商的状态信息达成一致，从而用于估计全局信息并重新开始一轮新的协商。

协商算法收敛的协商次数称为收敛协商次数kconv。为了确保拿到收敛值，收敛协商次数必须小于给定的协商次数，kconv

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

因为单位协商时间ΔT取决于多机器人系统的通信与计算能力，所以在具体系统中往往为一定值。减少协商次数ktotal或总协商时间ttotal能够快速获取收敛值，但是有不收敛的风险。提高协商次数ktotal或总协商时间ttotal有利于获取准确的收敛值但是协商结果刷新的速度变慢。因此需要根据实际情况综合决定ktotal与ttotal。

在重复进行的协商过程中，ktotal在任务开始前已经给定。然而，达到平均一致性所需的协商次数K1通常大于达到最大一致性所需的协商次数K2。因此，设计K1=ktotal而且K1=q×K2（q为正整数）来组合不同类型的协商结果。

为了确保所有机器人在给定的时刻执行一致性计算，即迭代时刻相等tki=tkj，同时确保完全分布。k值通过挂钟时间求取，即指定第k次协商的协商迭代时刻，如式（16）所示。

2.2 集中式多机器人巡逻算法EAIG

本节设计了一种集中式多机器人巡逻算法。当机器人到达起始节点或目标节点时，它将采用以下三步选择目标点。首先，计算该节点所有邻接节点NG1（vi）的效用度U1。然后，遍历所有其他机器人的意图节点序列It，如果存在意图节点是该节点的邻居节点，则该邻居节点效用度归零。从而得到决策用的效用度U并且避免机器人之间的冲突。最后，从邻接节点中选择效用度最高的节点作为目标节点。从而使得每个机器人基于全局信息独立在线决策。机器人在决策后也会向所有其他机器人发送到达信息和意图信息，使每个机器人获知全局信息。整个过程如图5所示。

采用期望平均空闲时间和期望瞬时空闲时间构造效用函数。基于瞬时空闲时间定义，期望瞬时空闲时间定义为

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

其中：cost代表前往目标点的距离；VEL代表机器人的平均速度。

根据平均空闲时间定义，用访问次数表示如下：

其中：ttotal表示机器人总计巡逻时间。用Δtexception表示机器人宕机、充电等行为所占的时间，那么ttotal可以表示为

ttotal=t－t0－Δtexception（19）

其中：t0代表顶点第一次被访问的时刻，也代表机器人的启动时刻。定义期望平均空闲时间如下：

期望瞬时空闲时间和期望平均空闲时间反映了机器人未选择顶点vi作为目标点时可能发生的平均空闲时间和瞬时空闲时间。因此机器人倾向于前往潜在空闲时间更高的目标点。效用值U1表示为

其中：U1为大于零的正数；α，β为比例因子。

采用意图信息避免两个机器人访问同一个节点，减小机器人之间的冲突，得到最终决策用的效用度U。当机器人ri的意图节点为vj时，Itri=vj，反之Itrivj。当一带机器人的其中一个对某节点存在意图时，其向所有巡逻机器人发布意图信息Itri=vj。当其他机器人收到该信息后，其在决策时将该节点效用度归零。由于效用度是由期望平均空闲时间和期望瞬时空闲时间构造的大于零的值，所以邻居机器人会选择其余节点作为目标节点，避免了两个机器人之间的潜在冲突。机器人ri存储着所有其他机器人的意图节点序列It={Itr1=vi1 Itr2=vi2 … Itrm=vim}，简记为It={vi1 vi2 … vim}。用于决策的机器人ri对邻居节点vi的效用值U最终表示为

本文所提的集中式巡逻算法称为基于全局信息的期望平均空闲和期望瞬时空闲算法（expected average idleness and expected idleness of global information，EAIG），算法伪代码如下所示。

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

2.3 分布式多机器人巡逻算法EAIL-C

2.3.1 算法描述

基于上述离散时间一致性算法的实现和集中式多机器人巡逻算法EAIG建立完全分布式多机器人巡逻算法。与EAIG的不同点有两个：a）机器人随时都在同邻居机器人进行协商以刷新收敛信息，替代了到达目标节点时向所有机器人的广播行为;b）决策所用的信息是局部信息而不是全局信息。机器人的协商过程和决策过程是相互关联的两个过程，整个过程如图6所示。

在协商过程中，当k=0时，机器人通过本地信息初始化其协商值。用列向量表示所有的协商值，并设计在一条协商消息中。在每个单位协商时间ΔT期间，此协商消息是唯一的。协商消息将向邻居机器人多次广播，等待一致性迭代计算。然后通过离散时间一致性计算得到下一个单位协商时间更新的协商值和收敛值。最后，在k=ktotal时刷新协商结果并储存在收敛值中。当需要进行决策时，机器人基于收敛的协商信息对全局信息进行估计，采用估计信息替代全局信息并计算效用值。与EAIG类似，机器人从邻接节点中选择效用值最大的节点作为目标点。

EAIG的全局信息和EAIL-C中基于协商信息预估的全局信息对比于表1中。协商信息预估全局信息的过程见下节。

式（23）～（27）与式（17）～（22）类似，设计了分布式多机器人巡逻算法EAIL-C计算各节点效用值的公式。与EAIG的决策逻辑相同，效用值最高的邻居节点将成为目标节点。

采用最近一次访问时刻估计值替代基于全局信息的最近一次访问时刻，期望瞬时空闲时间定义为

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

采用节点访问次数估计值替代节点总访问次数，平均空闲时间表示为

定义期望平均空闲时间如下：

效用值U1如式（26）所示，一般情况下，U1为大于零的正数。

采用节点意图估计值序列Itest替代每个机器人的意图序列It。机器人ri对节点vj的二元的意图估计值Itesti_j，简记为Itestj。当Itestj=1时，存在机器人对该节点的访问意图。当Itestj=0时，没有机器人计划访问该节点。当一带机器人的其中一个对某节点存在意图时，其意图协商信息通过邻居机器人之间的相互协商影响到这一带的所有机器人的协商信息，并进一步影响到这一带机器人对全局信息的预估值Itestj。当其余机器人根据协商信息预估值判断该节点时，该节点的效用度归零。由于其他节点的效用度大于零，所以机器人不再选择该节点作为目标节点，避免了机器人之间的潜在冲突。机器人存储并通过协商信息预估着整张地图所有节点的意图估计序列Itest={Itestv1 Itestv2 … Itestvn}。该估计序列由协商信息估计得到并经由协商过程不断刷新，与机器人数量无关，是局部信息。用于决策的机器ri对邻居节点vj的效用值U最终表示如下：

上述完全分布式巡逻算法称为基于局部信息的期望平均空闲和期望瞬时空闲的算法，简称为EAIL-C（expected average idleness and expected idleness of local information-cycled negotiation）。该算法的伪代码如算法2所示。一致性协商包括时间检查程序（time check）、一致性消息发布程序（publish consensus message）、一致性消息接收程序（receive consensus message）和节点到达程序（goal reached）。时间检查过程在给定时间通过ROS挂钟时间回调来计算新的协商值，而另外两个过程用于信息传输。巡逻行为包含在节点到达程序中，当机器人到达一个节点时被触发。

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

2.3.2 协商信息设计与全局信息预估

本节介绍了协商过程和估计全局信息的过程。鉴于固定拓扑能够可重复地描述信息的协商过程，本节示意图中机器人之间的关系均由固定拓扑描述，如图7所示。

为了预估EAIG的全局信息，设计机器人ri对节点vj的协商信息。EAIL-C的协商信息初始值、协商值、收敛值如表2所示。其中，协商信息初始值由每个机器人根据自身的节点访问情况赋值。经过一致性计算得到协商值，协商完成后保存收敛值。每当机器人需要决策时，基于协商值和收斂值计算全局信息的估计值。

采用最大一致性协商K2次得到机器人最近一次访问节点的时刻tlastj的收敛值t_delastj。机器人之间的协商过程如图8所示，用收敛值代表预估的最近访问时刻，即testj=t_delastj。

当节点vj是机器人ri的目标节点时Itj=1，否则Itj=0。采用平均一致性协商K2次获取节点意图收敛值Itcoj，易知，0≤Itcoj≤1。当且仅当Itdej=0并且Itcoj=0时没有机器人计划访问该节点。从而通过式（28）得到估计的意图信息Itestj。最大一致性也在这里有效。协商过程如图9所示。

采用平均一致性协商K1次得到节点vj的访问次数kj的收敛值kdej，kdej反映了节点的平均访问次数。然而，平均一致性协商需要更多的协商时间来获得节点访问次数的收敛值，而在协商期间节点可能被访问。这将导致协商值无法及时刷新。因此，有必要设计一个辅助协商变量以估计更新的全局信息，即设计一种基于收敛协商和趋势协商相结合的双重协商策略。结合收敛协商和趋势协商的价值，准确地估计全局信息。设计节点访问次数趋势ktrj作为机器人ri关于节点vj的协商变量，表示在协商期间节点是否被访问。在一轮kj协商初始化之后，如果机器人ri访问节点vj，那么ktrj=1，否则ktrj=0。采用平均一致性协商K2次获取节点访问次数趋势收敛值ktrdej。与Itcoj和Itdej类似，节点是否被访问是由ktrcoj和ktrdej来确定。因为节点访问趋势不能反映多次访问，例如在同一协商中访问了节点两次，所以协商周期ttotal需满足

ttotal

其中：Imin表示最小空闲时间。

为了结合kdej和ktrdej，需要估计机器人数量。机器人ri的协商变量mi_k表示机器人rk是否存在于协商中，通过式（30）初始化。采用平均一致性协商K2次获取协商值mcoi_k，最大一致性也可以通过收敛值mdei_k是否等于0判断机器人rk是否参与了协商。进而可以由式（31）得到参与协商的机器人数量mi。

其中：「·表示向上取整。因此，机器人数量的协商过程如圖10所示。

因此节点访问次数由式（32）估计，节点访问次数的协商过程如图11所示。

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

2.3.3 信息协商中的延迟

离散时间一致算法的实现过程具有延迟效应，包括延迟开始和延迟结束。以意向协商为例，如图12（a）所示，当机器人4计划访问节点0并在第566.2 s以1初始化其Itco4_0时，其邻居的协商信息依次受到影响，需要3个单位协商时间（0.6 s）才能影响到最远的邻居1号机器人Itco1_0。即Itco1_0在第566.8 s时受到影响。考虑到协商值会周期性初始化，实际延迟可能会更长。当两个机器人同时到达相邻的目标节点时，延迟开始会导致两个机器人选择与目标节点相同的节点，从而导致冲突。另一方面，如图12（b）所示，当意图信息在第584.2 s消失后，延迟效应阻止了协商意图在第585.2 s前返回到零。延迟结束阻止机器人选择刚刚被另一个机器人访问的节点，从而对计划的路径造成影响。由于机器人的冲突，延迟开始的影响远远超过延迟结束。所以，应尽量避免延迟开始。

解决延迟协商意图引起冲突的一种可能的解决方案是将邻居意图和协商意图结合起来。其原因是，机器人选择了一个相邻的节点作为目标节点，因此该潜在的冲突机器人位于其目标节点的相邻节点上。只要机器人的通信半径能够覆盖相邻节点的相邻节点，它就可以直接与潜在的冲突机器人通信，获取它们的本地意图信息。

另一方面，考虑到跟随行为的风险，不能不考虑邻居意图而单独使用协商意图。跟随行为意味着两个机器人总是一个接一个作出相同的选择，导致巡逻效果降低。其原因在于，邻居离开某节点的局部意图是准确的，而邻居刚刚访问该节点的信息是延迟的。因此，跟随者机器人不知道这个节点刚刚被访问，并且总是用相同的决策信息作出与前一个机器人相同的选择。当机器人之间的关系固定，如图7所示，且地图拓扑的各边长度相等时，跟随问题变得更加明显，特别是在机器人1和4之间。通信半径内邻居间的通信使得可能冲突的两个机器人之间产生了直接的意图信息交互，提高了意图传输的速度，从而解决了协商信息延迟的问题。当机器人进行决策时，如果协商信息指示目标节点存在访问意图（Itestj=1），或者接收到邻居机器人意图访问该节点的信息，那么机器人的效用值归零，不会将该节点作为目标节点。

3 仿真实验与结果

仿真实验的目的是通过模拟一个真实的环境从而比较不同的多机器人巡逻算法，并确认EAIL-C是否具有与EAIG相似的特性。文献［23］设计了基于ROS和Stage的patrolling_sim功能包以进行多机器人巡逻策略的仿真开发验证，不断添加新的巡逻算法并更新平台。功能包采用ROS开源导航包进行导航，可直接部署在基于ROS的机器人上实现应用。本文基于patrolling_sim功能包添加了EAIG、EAIL-C两个新算法并对相关文件进行了修改以适应算法，从而验证算法，并同功能包已有算法进行对比。以ROS移动机器人为对象模拟实际环境应用场景进行相关仿真实验。

3.1 仿真设置

采用两种地图（cumberland和grid）对巡逻算法进行评价对比，如图13和表3所示，在实验开始前地图及其拓扑已知，其中，grid地图连通性更好且所有节点之间的距离相等。

考虑到机器人之间的关系变化，基于通信半径约束确定机器人之间的关系。虽然较低的通信半径意味着对巡逻机器人的要求较低，但应考虑邻居的意图以避免发生冲突。因此机器人的通信半径应至少覆盖到邻居节点的邻居节点。不同地图的实验通信半径Rset应大于最小值Rmin，如表4所示。

基于通信半径建立了两种机器人关系。第一个名为EAIL-C1，机器人只使用协商信息，因为当两个机器人基于通信半径建立关系时，延迟启动引起的冲突与固定拓扑相比并不明显。第二个名为EAIL-C2，同时考虑了通信半径以内的邻居意图和协商意图，以最大程度减少冲突。一个固定的拓扑结构有利于满足一致性的收敛条件。因此，本文认为由固定拓扑所描述的机器人之间的关系是基于通信半径的交换拓扑的弱化，在实验中不考虑固定拓扑。

另外：a）EAIL-C1只采用协商信息进行决策；b）EAIL-C2采用协商信息以及通信半径以内的邻居意图信息共同决策。

采用四个机器人进行实验，机器人的平均速度VEL取值1 m/s。算法参数设置为：α=1、β=1、ε=1/5、K1=35、K2=5。每组仿真实验持续1 h并重复三次。在通过方差分析检验（ANOVA）的条件下，为每个算法选择三个仿真结果。各算法的p值均大于0.1，表示相同分布的概率较高。采用监控节点收集信息和求解评价指标。

用于对比的算法包括SEBS、DTAP，这两种算法都可以反映EAIG和EAIL-C的特性。算法对比如表5所示。

3.2 巡逻过程及巡逻算法对比

多机器人巡逻过程如图14所示，图中四个机器人在各自执行巡逻任务。通过记录单个机器人巡逻过程中的位置，绘制其1 h轨迹图，如图15所示。

cumberland地图的实验结果如表6所示，EAIG算法的全图空闲时间平均值IGavg均介于SEBS和DTAP之间，接近于SEBS。而EAIG的全图空闲时间标准差IGstddev、全图空闲时间最大值IGmax大于SEBS和DTAP。EAIL-C继承了EAIG的算法特性，它的平均空闲时间略有增加，但总体上与EAIG处于同一水平。由于协商信息的延迟效应，EAIL-C1和EIAL-C2的干扰率均略高于EAIG。在邻居意图的影响下，EAIL-C2的干扰率低于EAIL-C1。

grid地图的结果如表7所示，EAIG的全局平均空闲时间IGavg优于DTAP，略优于SEBS。EAIG的全图空闲时间标准差、全图空闲时间最大值与SEBS和DTAP处于同一水平。因此，EAIG的性能优于SEBS和DTAP。因为grid地图的连通性比cumberland地图更好，所以grid地图的干扰率比cumberland高，其性能受到的影响更大。EAIL-C1和EAIL-C2的全局平均空閑时间IGavg与EAIG的水平相同。EAIL-C1和EAIL-C2的空闲时间标准差IGstddev和最大空闲时间IGmax均高于EAIG，而EAIL-C2的性能优于EAIL-C1，这是由于EAIL-C2具有更准确的意图信息，带来更低的干扰率和更好的性能。总体来说，EAIL-C的巡逻效果与EAIG非常接近。

使用箱线图分析不同节点的平均空闲时间，如图16、17所示。在cumberland和grid地图中，SEBS的平均空闲时间都低于DTAP，但存在许多异常值。DTAP以增加节点的平均空闲时间为代价减少了异常值。EAIG在保持了较低的平均值水平的基础上异常值较少，因此节点的平均空闲时间表现更好。同时，EAIL-C具有与EAIG相似的特征，而EAIL-C2在grid地图的表现优于EAIL-C1。

综上所述，在本地信息和邻居协作的支持下，EAIL-C取得了与EAIG相似的性能。避免了全局信息，并考虑了通信约束。当地图的拓扑连通度较低时，EAIL-C就可以基本反映EAIG的算法特征，并在一定程度上取代原算法EAIG。当图的拓扑连通性较高时，EAIL-C的干扰率越高。在通信半径内邻居的局部意图的帮助下，EAIL-C2取得了比EAIL-C1更稳定的巡逻效果。

3.3 一致性算法的性能确认

一致性算法的收敛性对性能起着重要作用。因此，本节使用cumberland地图中EAIL-C1的数据来确定其收敛性。本小节分析了协商K2次的意图信息和协商K1次的节点访问次数。

机器人并不总是能保持完全的连接。机器人之间连边的数量对收敛结果有不可否认的影响，因此，监控节点每秒钟记录一次每个机器人的位置。不同数量的连接边对应的时间比例如表8所示，大约30%的时间有3条或更多的边，这意味着这四个机器人保持完全连接，可以准确地估计全局信息。大约35%的时间里，有两条边，即两个或三个机器人连接起来，它们的信息被用来估计全局信息。

意图协商是趋势协商，其目标是确定协商值是否等于零，并估计对应的全局信息。通过在每个单位协商时间ΔT处存储估计的全局信息和真实的全局信息并进行比较，确认所估计的意图是否准确。估计的全局意图Itestj受到信息协商延迟和机器人之间关系的影响。结果显示，94.32%的数据与全局信息一致，如表9所示。这超过了准确估计全局信息的时间35%。原因是单个节点超过85%的时间是没有机器人访问的意图的。

节点访问次数的协商是收敛协商，其目标是得到收敛值kdej。收敛性受到一致性收敛速度和机器人之间关系的影响。当k=K1时计算kconvi_j，以检查协商收敛情况，如式（33）所示。

如果kconvi_j< 0.25，则认为它是收敛的。结果表明，95%的协商满足收敛条件，如表10所示。

3.4 不同机器人数量和通信距离下的性能验证

本节对EAIL-C2算法进行进一步性能验证。考虑2，4，6，8四种机器人数量进行对比。考虑避免冲突的最小通信半径、覆盖全图的最大通信半径以及介于两者之间的通信半径。grid地图对12 m、24 m、36 m三种通信半径进行对比，cumberland地图对16 m、40 m、64 m三种通信半径进行对比，其余参数与上节仿真设置相同。考虑grid、cumberland两种地图环境。

图18、19分别展示了SEBS、DTAP、EAIG和EAIL-C2算法在grid和cumberland两种地图中的全图空闲时间平均值IGavg和标准差IGstddev随时间的变化，其在1 500 s以内稳定。因此，本节仿真时间为60 min。每组仿真实验至少重复3次，取其平均值进行对比。

grid地图的结果如表11、12所示。其中，表11对比了EAIL-C2在不同机器人数量和通信半径条件下的巡逻效果。在同一通信半径下，随着机器人数量的提升，全图平均空闲时间、全图空闲时间标准差下降，机器人之间的干扰率上升。全图空闲时间最大值在机器人数量为2时出现。因此，机器人数量对巡逻效果有重要作用。而随着机器人通信半径的增加，全图平均空闲时间、全图空闲时间标准差、机器人之间的干扰率没有明显区别。因此，算法EAIL-C2受通信半径的影响较小。

表12展示了不同机器人数量下对比算法的评价指标。在不同机器人数量下，EAIG和EAIL-C2的全局平均空闲时间均优于DTAP，接近于SEBS。随着机器人数量的增加，各个算法的全图空闲时间标准差随之下降。在干扰率方面，随着机器人数量的增加，机器人之间的干扰率不断上升。相比之下，SEBS的干扰率上升明显，而DTAP、EAIG、EAIL-C2基本处于同一水平。EAIL-C2的干扰率高于原算法EAIG。因此，EAIL-C2在各个条件下的评价指标均略弱于基于全局信息的EAIG算法，但差距不大。

EAIL-C2在cumberland地图的实验结果如表13所示，机器人数量对实验结果的影响大于通信半径的影响。在同一通信半径下，随着机器人数量的提升，全图平均空闲时间、全图空闲时间标准差下降，机器人之间的干扰率上升。全图空闲时间最大值出现在机器人数量为2时，随着机器人数量的增加呈现递减趋势。而随着机器人通信半徑的增加，全图平均空闲时间、全图空闲时间标准差、机器人之间的干扰率没有明显区别。因此，算法EAIL-C2受通信半径的影响较小。

表14展示了对比算法的评价指标。在不同机器人数量下，EAIG和EAIL-C2的全局平均空闲时间均优于DTAP，略弱于SEBS。EAIG和EAIL-C2的全图空闲时间标准差大于SEBS和DTAP。随着机器人数量的增加，所有算法的全图平均空闲时间、全图空闲时间标准差下降，机器人之间的干扰率上升。最大干扰率出现在八个机器人的SEBS算法中，而EAIG的干扰率介于DTAP和SEBS之间。EAIL-C2的干扰率高于EAIG，其余指标和EAIG接近，基本处于同一水平。

图20展示了不同机器人数量和不同通信半径下的各个节点的平均空闲时间箱线图。在grid地图中，SEBS的平均空闲时间都低于DTAP，但存在许多异常值。EAIG的平均值接近于SEBS，同时异常值较低。因此节点的平均空闲时间表现更好。同时，EAIL-C在不同半径下具有与EAIG相似的分布。在cumberland地图中，EAIG的效果介于SEBS和DTAP之间，接近于SEBS，其异常值同样较少。EAIL-C2的效果与EAIG类似，受通信半径影响较小。

综上所述，EAIG相比DTAP具有更低的平均空闲时间，相比SEBS异常值更少，具有一定优势。EAIL-C具有和EAIG类似的算法特点，能够基本达到EAIG的算法性能。

4 结束语

本文采用离散时间一致的方法实现了完全分布式多机器人巡逻算法EAIL-C，并与原有的集中式巡逻算法EAIG等巡逻算法进行了比较。算法考虑了通信半径和局部信息的约束条件。在每个周期中都可以获得最新的协商结果，并且协商信息独立于特定的机器人。机器人之间的关系会根据通信半径和机器人位置的变化而变化。采用仿真器Stage对算法进行了仿真和比较，验证了所提算法EAIL-C具有与原算法EAIG相似的特性和性能。EAIL-C算法为后续实现更大规模的机器人集群提供了思路，所提出的趋势协商和收敛协商的协商方法可以扩展到其他集中式巡逻算法，以实现完全分布。所提算法适用于巡逻范围大且通信半径有限的情况。例如：森林火灾实时监控、海洋污染防控、边境线巡逻等。

在未来的多机器人分布式巡逻算法的研究中，可以考虑以下两个方向：采用更优秀的离散时间一致性算法来加速协商速度，这意味着更低的Ktotal；综合考虑机器人的位置和通信半径、机器人之间的关系维持和巡逻任务的完成，设计出与实际情况关联更紧密的完全分布式巡逻算法。

参考文献：

［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］武丽霞. 多机器人系统分布式巡逻算法设计及实验验证［D］. 兰州： 兰州交通大学，2019. （Wu Lixia. Distributed patrol algorithm design and experimental verification for multi-robot system［D］. Lanzhou： Lanzhou Jiaotong University，2019.）

［5］史天伊. 多机器人系统巡逻分布式算法研究［D］. 兰州： 兰州交通大学，2021. （Shi Tianyi. Research on distributed patrol algorithm of multi-robot system［D］.Lanzhou：Lanzhou Jiaotong University，2021.）

［6］赵云涛，李宗刚，杜亚江. 基于最大空闲时间的分布式巡逻机器人数量优化［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］霍耀彦，李宗刚，高溥. 基于节点重要度的多机器人分布式巡逻策略［J］. 计算机应用研究，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］王通，黄攀峰，董刚奇. 启发式多无人机协同路网持续监视轨迹规划［J］. 航空学报，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，Fabila-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］紀良浩，王慧维，李华青. 分布式多智能体网络一致性协调控制理论［M］. 北京： 科学出版社，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，Farinelli 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.