复合Petri网的主从式多智能体通信建模方法*

王帅辉，袁 杰

(新疆大学电气工程学院,新疆 乌鲁木齐 830047)

1 引言

近年来，多智能体系统研究成为热点[1-4]，多智能体系统通过多个同构或异构的智能体进行协同配合，从而完成单一智能体不易或无法完成的工作[5]。其中主从式智能体的协同应用已成为当前热点，在诸多领域发挥着越来越重要的作用[6-8]。而主从式智能体之间的通信问题，作为保障其协同作业的决定因素之一，正成为制约其进一步发展的关键因素。

在当前多智能体系统，特别是主从式多智能体系统的通信领域，MAS(Multi Agent System)面临着因频繁的消息交换和短缺的计算资源造成的消息处理的滞后问题,以及因保障通信鲁棒性而造成通信硬件的成本高昂等问题[9,10]，影响着系统响应的实时性甚至稳定性。主流研究方向是要求在连续时间下对多智能体进行控制，然而实际环境的通信信号一般为离散的，文献[11]改善了离散工况下的一致性，从而减少了通信负担；通信的网络拓扑结构一般使用图论方法进行研究，其结构的不同决定着系统整体的稳定性;文献[12]通过改变其拓扑结构提高了通信效率；文献[13,14]通过减少智能体的通信信息长度提高了系统的通信效率；文献[15]通过给机器人减少适配微控制器，降低了硬件成本；此外，从通信协议、通信方式等方面考虑，学者们也提出了相关理论方法去完善通信处理的过程[16]。然而，随着智能体的数量进一步增加以及面临动态开放的外部环境，MAS的计算资源被大量无用、不可靠消息制约，并且伴随着高昂的通信硬件成本问题，使之成为多智能体协同领域应用发展的一个制约点。

Petri网PN(Petri Net)是针对离散并行系统建模的一种重要工具，特别在表达复杂逻辑方面，具有巨大的优势[17,18]。因此，本文在主从式多智能体系统的通信领域引入Petri网模型。基于主从式多智能体通信的资源特征，尝试对Petri网的库所属性进行定义，建立相应的Petri网处理模型。并且在此基础上，构建基于主从式多智能体编队的实验场景进行模型验证，结果实现了编队的通信过程，表明Petri网可以对主从式多智能体系统通信建模处理、对消息的通信可靠性提供保证，并能缓解通信消息对系统计算资源的压力。

2 基于Petri网的主从式智能体通信

2.1 主从式智能体通信

在主从式多智能体中，消息分为智能体可识别消息(高优先级消息和一般消息)和智能体不可识别消息(错误消息，包括噪声和空消息)，其中一般消息又分为与高优先级无关消息(如状态消息)和与高优先级相关消息(高优先级消息的后续消息,如回复消息)，本文分别以状态消息和回复消息代称。若同时接收到多种消息，4种消息处理优先级为：高优先级消息>回复消息>状态消息>错误消息。

2.2 Petri网的相关定义

为了能够有效解决主从式智能体的通信问题，使用Petri网(PN)对其建模处理，为了更好地理解Petri网的建模方法，以下给出了Petri网的相关定义[19]：

Petri网由式(1)所示的5元组进行描述：

PN={P,T,I,O,M}

(1)

其中,P={p1,p2,…,pk}表示库所的有限集，k表示系统的库所总数；T={t1,t2,…,tl}表示变迁的有限集，l表示系统的变迁总数；且P∩T=∅。I:T×P→{0,1}为输入函数，定义从P到T的有向弧的集合，弧定义为引发变迁激发的库所条件；O:P×T→{0,1}为输出函数，定义从T到P的有向弧的集合,F=T×P∪P×T。令：

K:P→{1,2,3,…}∪{∞}为PN的容量函数；

W:F→{1,2,3,…}为PN的权函数；

M:P→{1,2,3,…}为容量函数K允许的标识。

令X=P∪T，X为PN网的元素集，则：

∀x∈X,·x={y|y∈X∧(y,x)∈F}

(2)

∀x∈X,x·={y|y∈X∧(x,y)∈F}

(3)

其中，·x称为x的前集，x·称为x的后集。

禁止弧：定义为在Petri网的输入侧，始端连接库所、尾端连接变迁的弧，其尾端的小圆圈表示对当前弧进行取反操作。即如果禁止弧所连接的库所的资源数量(token)大于或等于其弧的权重，禁止弧所连接的变迁将被禁止激发。

t(I不含禁止弧)在M的激发条件是：

{∀p∈·t:M(p)≥W(p,t)}∧{∀p∈t·:M(p)+W(p,t)≤K(p)}

t(I含禁止弧)在M的激发条件是：

{∀p∈·t:M(p)=0}∧{∀p∈t·:M(p)+W(p,t)≤K(p)}

定义变迁t的激发事实发生函数：

activation(t)=1,t∈T

(4)

否则：

activation(t)=0,t∈T

(5)

2.3 多智能体通信PN元模型

在主从式智能体的通信问题中，定义库所中的token表示状态消息(消息特征状态和通信的触发状态)或行为消息(表示通信的处理过程消息)，分别储存在状态库所和行为库所中；定义状态库所pst∈P，行为库所pac∈P。Petri网的激发过程都是瞬时完成的，从一种M态激发为另一种M态，但在通信问题中，为了表示消息收发的一定时间过程，定义时滞库所pti∈P。即有：

p=pti∨pst∨pac,p∈P

(6)

令M′为t激发后的标识，称为M的后继态。对于状态库所pst，其后继态根据环境确定。例如：pst表示发送高优先级消息请求库所(状态库所)，当系统有发送高优先级消息请求时：

M′(pst)=1

(7)

否则：

M′(pst)=0

(8)

对于行为库所pac的标识函数，其后继态为：

(9)

时滞库所pti标识函数的后继态和时间因子有关，引入时间因子常量time_pti≥0，其值依赖于使用场景。时滞库所pti的标识函数为M(pti,time_pti),定义其后继态如下所示：

M′(pti,time_pti)=M(pac)，

{M(pac)

(10)

M′(pti,time_pti)=M′(pac),

{M(pac)

(11)

M′(pti,time_pti)=M′(pac),

{M(pac)>M′(pac)}∧{tim(pti)

(12)

M′(pti,time_pti)=M′(pac),

{M(pac)>M′(pac)}∧{tim(pti)≥time_pti}

(13)

M′(pti,time_pti)=M(pac),

M(pac)=M′(pac)

(14)

其中，tim(pti)定义为时间函数，由pti所在变迁激发时开始计时，函数更新规则为：

timnew(pti)=tim(pti)×max(activation(t),0)

(15)

引入时间因子常量time_pti后，行为库所和状态库所的时间因子常量恒为零。此时，时滞库所pti的标识更新需要大于时间因子常量time_pti，则此时t的激发条件应满足：

t(I不含禁止弧)在M的激发条件是：

{∀p∈·t:M(p)≥W(p,t)}∧

{∀p∈t·:M(p)+W(p,t)≤K(p)}∧

{∀pti∈t·:tim(pti)≥time_pti}

(16)

t(I含禁止弧)在M的激发条件是：

{∀p∈·t:M(p)=0}∧

{∀p∈t·:M(p)+W(p,t)≤K(p)}∧

{∀pti∈t·:tim(pti)≥time_pti}

(17)

Petri网的图形描述如下所示：使用弧表示引发变迁处理的消息条件，使用圆表示库所p，使用点表示token，使用矩形表示变迁。当容量函数相对于资源数是无穷时，即K:P→{∞}，当容量函数相对于资源数是有限时，即K:P→{1,2,3,…}；本文模型权函数取值为1，即W:F→{1}，图中省略不写。图1和图2分别展示了可视化的2种激发过程。

Figure 1 Petri nets firing process without forbidden arcs

Figure 2 Petri nets firing process with forbidden arcs

3 主从式MAS通信建模

根据主从式多智能体通信特征，本节分别建立了高优先级消息、一般消息和通信异常处理的PN模型，并进行了相关分析。表1列出了本文后续所用库所的含义。

3.1 高优先级消息的PN模型

在主从式多智能体通信中，高优先级消息属于发布频率小，但重要度高的消息，采用“发送-回复”方式保障其消息通信的可靠性；为了减少不必要的计算资源冗余，高优先级消息的安全保障机制采用“发送者负责制”(高优先级消息通信过程的可靠性由发送者承担，接收者不承担其回复消息的可靠性)，同时，针对智能体通信的高频性，智能体在信息处理期间可以执行其它突发消息，以满足消息处理的并行特点。针对高优先级消息建立如图3所示的PN模型。

Table 1 Meaning of the places

Figure 3 PN model of high priority message

为理解此PN模型原理，以当前行为为“发送完高优先级消息等待回复过程” 为例进行解释说明。其中，pti5和pac7存在token，分别表示目前执行行为是“消息识别”及存在的事实为“高优先级消息处理”。pti5为时滞库所，经过时间time_pti完成1次消息的接收识别后，分别可能识别到回复消息、高优先级消息、状态消息和错误类消息(分别由pac9、pst11和pst12的不同token组合表示)。若要完成本次消息处理，变迁t7必须要被激发。由图3可知，变迁t7激发的条件是:pti5、pac7、pst11和pst12必须存在token，同时库所pac9不能存在token。其物理意义为:当前等待回复过程时，同时检测到4个事实“进行消息识别”(pti5)、“进行高优先级消息处理”(pac7)、“正确消息”(pst11)和“回复消息”(pst12)存在，“高优先级消息标志”(pac9)不存在时，则通信状态转移到“空闲态”(pac8)。另外，接收到其它3类信息时，处理后进入消息的循环接收，直到满足2.3节的通信异常处理PN模型的相关条件或接收到正确的回复消息，从而完成处理过程。pst0容量函数K=∞，消息相对于库所容量是无穷的，即保证智能体同时面对多个消息时，消息能及时进入智能体的处理队列。psc4的容量函数K=1，则保证了消息每次必须处理完成后，智能体才会接收下一个消息，除非这个消息被取消，即保证了消息的可靠性。禁止弧的加入保证了消息并行处理时不会陷入死锁。

3.2 一般消息的PN模型

对于一般消息，智能体必须及时处理，以便快速做出响应；除了响应可识别消息外，智能体还必须处理由于外界环境不可靠导致的噪声。为了保证高优先级消息处理的快速性，此时消息接收的优先级要低于2.1节模型的优先级。建立一般消息的PN模型如图4所示。

Figure 4 PN model of general message

对于一般消息的发送，智能体要针对不同类型的消息发送冲突，设置消息优先级，保障消息处理顺序，实现消息通信的事件驱动(pti0、pti10和pti13)；同时，为了适应多智能体中消息的定时发送，发送状态消息库所设置为时滞库所，在M(pst13)=1的条件下，实现了消息通信的时间驱动(t15)。比较图3和图4可知，完成1次一般消息的发送需要激发变迁t15；而完成1次高优先级消息的发送至少需要激发变迁t0、t1和t7。同时，为了避免高优先级消息和一般消息的资源占用冲突引起死锁，变迁t10加入了含禁止弧的库所pti7。

3.3 通信异常处理PN模型

建立应急处理PN模型如图5所示。在实际场景通信中，受外界因素影响，智能体之间存在消息通信失败的可能。此时在通信异常处理模型中，智能体根据pst3是否赋值token决定重发次数以及重发失败后的系统应急处理，进而决定是否定时重发(t2)，避免通信死锁，保证消息通信的可靠性。

Figure 5 PN model of communication exception processing

4 主从式MAS通信模型验证

4.1 实验验证平台

主从式多移动机器人的硬件平台由3辆智能小车组成，实验过程如图6所示，其中，Master代表主机，Slaver代表从机。每辆小车分别采用ATK-ESP8266模块进行通信，该模块采用串口(LVTTL)与其他串口设备通信，通过内置的TCP/IP协议栈，实现串口与WIFI之间的转换，完成无线通信；其中主智能体小车工作在服务器模式，从智能体小车工作在客户端模式。

Figure 6 Experimental verification process

采用Arduino R3处理器进行实验来验证本文模型，消息的收发通过内部中断进行；利用Arduino IDE的带时间戳的串口监视器，采集串口通信实时收发的状态量(为了使状态量可视化明显，消息的收发有部分时间延迟)，收集整理消息日志数据，得到实验数据。

4.2 模型验证

对于3.1节中高优先级消息的PN模型，验证结果如图7a所示，其中横坐标取值来源于Arduino IDE中带时间戳的串口监视器，单位为s；纵坐标是智能体消息通信的状态量，各状态量之间的排列顺序呈并列关系。主智能体和从智能体的数据分别在2台主机的Arduino IDE中生成，因此当一台主机接收到消息的同时，另一台主机消息状态按空闲态处理。

Figure 7 Verification state diagrams of different priority PN models

图7a验证了主智能体和从智能体分别发送高优先级消息响应过程。具体状态响应过程为:主智能体发送高优先级消息→从智能体接收高优先级消息→从智能体发送回复消息→主智能体接收回复消息，此时主智能体通信完成；从智能体发送高优先级消息→主智能体接收高优先级消息→主智能体发送回复消息→从智能体接收回复消息，此时从智能体通信完成。

对于3.2节中一般消息的PN模型，验证结果如图7b所示。可以看出在大约816.6 s时，从智能体在事件驱动状态库所pst13=1下，开始通信任务：从机发送状态消息→主机接收状态消息，随后在时间驱动下，从机定时2 s发送其状态消息给主机；直到事件驱动状态状态库所pst13=0，即大约820.9 s时完成通信任务。

4.3 主从式MAS的通信综合模型

为了对上述模型进行综合验证，在高优先级消息、一般消息和通信异常处理的Petri网模型基础上，构建了主从式MAS的综合PN通信模型；引入多移动小车编队实物场景，完成主智能体引导行走，从智能体等距跟随的任务。

Figure 8 Communication model of master-slaver multi-agent PN

4.4 多移动小车编队通信验证

图9所示为模型在高优先级消息处理期间，并行处理突发消息的实验结果。图9a中设定为主机发送高优先级消息后，从机同时有发送高优先级消息请求和回复消息的处理请求。从机处理顺序为高优先级消息>回复消息。图9b中设定为主机发送高优先级消息后，从机同时有发送状态消息请求和回复消息的处理请求。从机处理顺序为回复消息>状态消息。对于其它复合类回复消息，处理过程类似。

Figure 9 Compound messages processing

图10中设定为主机发送高优先级消息，从机设定回复主智能体不能识别的消息，即错误消息；主机应急故障处理设置为3次重发失效后进入空闲态，即放弃此次任务执行。在图10a中，从机设置为发送2次错误消息，再发送正确回复消息；图10b中，从机设置为无限次发送错误消息，主机在接收到3次错误类消息后，进入了故障处理状态，实现了异常先处理原则。

Figure 10 Verification states of communication exception handling in PN model

图11所示为智能体接收到噪声等错误消息时的处理过程，此过程中噪声是由智能体从机发送的，主机接收后丢弃。图12所示为在Petri网模型的支持下，完成多移动小车编队的实际运行图。

Figure 11 Error messages processing

Figure 12 Partial operational states

在此实验平台上，通过简单的WIFI通信模块，Petri网模型实现了对消息的通信管理，并且具有一定的鲁棒性，在软件层面实现了通信管理，从而减少了对昂贵通信模块的依赖。通过消息分类，将包括噪声、空消息等的错误类消息、一般类消息和高优先级类消息分类处理，阻止错误类消息进入智能体的计算过程，减少一般类消息占用高优先级类消息的处理通道的概率，从而达到缓解通信压力，提高智能体的通信响应速度，最终节省智能体的计算资源的目的。

5 结束语

本文针对当前主从式多智能体系统通信领域的硬件成本高、计算资源占用大等问题，利用Petri网理论，提出了主从式多智能体的通信模型。该模型可以从软件方面对主从式多智能体的消息提供保障处理，降低对通信硬件的依赖。根据不同优先级的消息，基于主从式多智能体通信的资源特征，将 Petri网划分为状态库所、行为库所和时滞库所，并且关联了变迁被激发后库所的生效时间；建立了高优先级消息、一般消息和通信异常处理的Petri网模型。实验表明了该Petri网模型的有效性。在此基础上，构建了主从式多智能体Petri网的综合通信模型；在多智能体编队的任务场景下进行了验证。验证的结果说明该模型可以处理不同类别消息，缓解了通信消息对系统计算资源的压力，最终达到提高智能体计算资源处理速度的目的。