基于Petri网的扫地机器人路径设计分析

胡源，王丽丽，刘祥伟

（安徽理工大学 数学与大数据学院，安徽淮南 232001）

近年来，科学技术的不断进步与发展，扫地机器人的功能也日益完善，但是由于现代房间住房内部环境的复杂性，导致了扫地机器人难以完整记录室内环境，因此如何设计机器人的清扫路径是整个设计系统的重点。

Petri网的行为轮廓理论是以合理的自由选择petri网为基础，从过程行为角度建模，使得Petri网模型间的行为关系具体化、数字化，直观的刻画了行为间的内部关系[1]，对服务的交互和组合能从过程行为角度上得到解决。构建流程模型[1]能够清晰地表现出业务行为的逻辑性和有序性，建模原理则给出了建模语言所需的形式化的程序。文献[3]给出了在扫地机器人工作时，如何寻找内层非障碍点的方法建议。文献[4]提出了在满足室内环境全覆盖的情况下，如何规划扫地机器人的路径问题想法。文献[5]给出了在业务流程建模时，将一个建模目标的多个输入模型根据模型相关性合并成一个复杂的综合模型，以及子模型的实现。文献[6]介绍了一个利用组合性的方法检测Petri网可达性。文献[8]给出了在业务流程建模时，将一个建模目标的多个输入模型根据模型相关性合并成一个复杂的综合模型，建模者可以观察到输入模型间的共性和不同之处，以及子模型的实现，从而能更深一步的服务于建模目标。文献[9]给出了在业务流程建模时，将一个建模目标的多个输入模型根据模型相关性合并成一个复杂的综合模型，建模者可以观察到输入模型间的共性和不同之处，以及子模型的实现，从而能更深一步的服务于建模目标。

本文基于Petri网和行为轮廓的思想，从过程行为角度进行建模，提出了扫地机器人路径系统模型的设计分析。为了使得机器人在清扫环境系统中更方便快捷的达到环境全覆盖，并且针对其在打扫过程中碰到路面障碍的情况，结合Petri网中的行为关系分析流程模型，使其达到适用性和一致性。

1 基本概念

下面仅介绍流程模型Petri网的定义及其可达性，阐述了行为轮廓的相关定义。

定义1[1]（流程模型Petri网）一个流程模型Petri网PM=(P,T,F,C,s,e)是一个六元组，满足以下条件：

（1）P是有限库所集，T是有限活动变迁集；

（2）P≠∅,T≠∅且P⋂T=∅；

（3）F⊆(P×T)⋃(T×P)表示 PN 的流关系且(P⋃T,F)是强连通图；

（4）dom(F)⋃cod(F)=P⋃T,

其中

dom(F)={x∈P⋃T|∃y∈P⋃T,(x,y∈F)} ；cod(F)={x∈P⋃T|∃y∈P⋃T,(y,x)∈F}。

（5）C={and,xor,or}是流程网的结构类型；

（6）M0是网的初始标识，Mf是网的终止标识，且Mf是死标识；

（7）s∈T是开始活动变迁，e∈T是终止活动变迁。

则称该网为流程模型Petri网。

在此定义上，定义了网的前集和网的后集。

定 义 2[2]（变 迁 发 生 规 则）一 个 四 元 组PN=( )P,T;F,M0称为Petri网，并具有下面的变迁发生规则

（1）变迁t∈T具有发生权，当且仅当对∀p∈·t:M(p)≥1，记作M[t＞；

（2）在标识M下能使的变迁t经发生后，得到一个新的标识M′，记作M[t＞M′，则有

定 义 3[6]（ 可 达 性 ） 已 知 Petri网PN=(P,T;F,M)，如果存在t∈T，使M[t＞M′，则称M′为从M直接可达的。如果存在变迁序列t1,t2,…,tk和标识序列M1,M2,…,Mk使得

则称Mk为从M可达的。从M可达的一切标识的集合记为R( )M。

图1 可达性模型

定义4[9]（行为轮廓）设是一个网，初始标识为M0。对任给的变迁对满足下面关系；

（1）若t1≻t2且t2⊁t1，则称严格序关系，记作t1→t2；

（2）若t1⊁t2且t2≻t1，则称严格逆序关系，记作t1→-1t2；

（3）若t1⊁t2且t2⊁t1，则称排他关系，记作t1//t2；

（4）若t1≻t2且t2≻t1，则称交叉序关系，记作t1×t2；

2 基于Petri网的扫地机器人路径系统的模型建立

本部分首先基于Petri网建立扫地机器人路径设置模型，其次分析该模型中活动间的相互关系并分析该模型的结构，完善机器人的路径系统，使得其能够更好地完成清洁室内的工作。目前来说，扫地机器人以螺旋式行动来进行清扫的方式是效率最高的，它在避免了重复行走路径的同时，也能够有效的遍历所有的区域达到完成各个区域的清扫目的。但是机器人在以螺旋模式行动的途中，若是在途中碰到了较大形状的障碍物，如桌椅，抑或是宠物等物体时，便会中断它的行动路线[7]。所以，在螺旋行动中加入避开障碍物的算法，如绕开障碍物后再返回原路径。下面就此方法提基于Petri网的模型建立，使得机器人可以在陌生的环境中完成自身的清扫任务。然后根据建立的模型，用Java进行仿真演示以验证模型。

图2 扫地机器人路径的Petri网模型

对房间进行模块化分层，清洁机器人按右螺旋方式对房间进行清扫，假定房间分为51*51矩阵，最外层200个点记为1（起始点记为0），第二层196个点记为2，以此类推，最中间点记为26。若房间大小改变，按此方法类似进行标记分层。

通过模型的运行可以直观的看出活动之间的关系。在机器人行进至障碍物时，首先会判断该障碍物为墙壁或一般阻碍物，然后返回判断信息并根据返回的信息决定下一步行动方式。若为墙壁则转变方向继续前行执行清扫，若为一般阻碍物则寻找内层紧邻点，通过移动至内层紧邻点再返回到外层阻碍物后一点继续之前的路径执行清扫，直至这一层清扫完毕再运行至内一层重复上述工作。下面以迹的方式给出分析：给出如下变迁序列：

当机器人以螺旋方式行动清扫时，会对已清扫后的位置进行标记，当外层清扫完毕后，会移动至内层重复进行螺旋式清扫，即为路径σ=σ1。

若机器人判断无内层且所经过区域全部已标记，则机器人便完成清扫[4]，其路径为σ=σ1σ2σ3。

下面用Java来进行模拟实验，以验证其有效性。部分核心代码如下：

表1 图2变迁符号的含义

图3 房间内部环境设置

图3所显示的为未清扫之前房间内部环境图部分，房间障碍物及垃圾随机产生。清扫结果如图4所示。

图4 清扫完成后室内环境部分

运行结果显示完成清扫后，地面已无垃圾，且机器人避开了所有的障碍物。

3 结束语

本文基于Petri网构建了扫地机器人的一种路径设置模型，其中包含了并发关系、排他关系及顺序关系的流程，根据Petri网的变迁发生规则及其可达性和行为轮廓等基本性质，通过增加相应的结构变迁对其进行设计。构建的模型包括顺序关系的流程图及具有排他关系的变迁发生序列，使模型应用更加全面，也体现了该模型在实际应用中的适用性。

未来关于路径设计建模优化还有许多问题去研究，需要基于Petri网及其行为轮廓的相关性质分析其模型优化的一致性和合理性。