（计算机软件与理论专业论文）基于petri网的智能机器人系统死锁检测.pdf

南京理工大学硕士学位论文基于p e t r i 网的智能机器人系统死锁检测 摘要 智能机器人是一个对外界环境高度开放的智能系统，由一系列具有独立问题 求解能力的子系统组合而成。机器人各子系统在自主地完成各自的子问题求解的同 时，在黑板的干预下互相协作、协调完成全局性的任务，从而对各种复杂的道路状 况作出实时感知和决策，实现道路跟踪、分叉、避障、越野等功能。 整个系统存在多种流程和不同的环节，为保障这一错综复杂的系统各个环节、 各个模块能正常工作，不致产生死锁、阻塞等情况，需要一种强有力的分析工具对 其进行描述、分析。 本文首先分析地面微小型智能机器人的系统结构，并构造出它的p e t r i 网模型； 然后，针对该系统自身的特点得出合适的死锁检测算法对所构造的p e t r i 网进行死 锁检测：1 、利用“可达树死锁标识检测算法”判断该p e t r i 网是否存在死锁标识、 死变迁；2 、根据所构造可达树的特点提出并实现。初始标识可达性判断算法”，检 测是否所有的可达标识均可回到初始标识。 检测结果证明，该p e t r i 网不含死锁标识、不含死变迁并且所有可达标识均可 到达初始标识，即该p e t r i 网是活性的，进一步说明该智能机器人系统不存在死锁。 关键词：智能机器人p e t r i 网死锁活性可达树死锁标识循环系统 a b s t r a c t硕士论文 a b s t r a c t i n t e l e g e n tr o b o ti sa l li n t e l e g e n ts y s t e m , w h i c hh i g h l yo p e n e dt ot h ee n v i r o n m e n t i t n e e d st or e a c ta n dm a k ed e c i s i o ni nr e a l t i m ea c c o r d i n gt oe v e r yc o m p l e xc o n d i t i o n so f t h er o a d i tr e a l i z e st h ef u n c t i o n so fr o a dt r a c k ，f o r k ，a v o l d - o b s t a c l e ，a n ds oo n s ot h e a r c h t e c h t r u eo ft h er o b o tm u s tb eo r g a n i z e d ，a n dt h er o b o t ss u b s y s t e mw o u l da p p e a r r u b yi n t e l e g e n tt os o l v et h el o c a lp r o b l e m sa u t o m a t i c l y , c o l l a b o r a t ew i t he a c ho t h e r , a n d f i n i s ht h eg l o b a lt a s kb yd i s p a t c h m e c h a n i s m t h ew h o l es y s t e mc o n s i s t so fs e v e r a lp r o c e s s e s i no r d e rt od ot h ew o r k s m o o t h l y w i t h o u td e a d l o c ka n dc o n g e s t i o nw i t ht h ec o m p l e xs y s t e m ，ap o w e r f u lt o o li sn e e d e dt o d e s c r i b ea n da n a l y s ei t ， t h i sp a p e rf i r s n ya n a l y s et h ea r c h t e c h t u r eo ft h eo n g r o u n dm i c r oi n t e l e g e n tr o b o t s y s t e m ，a n df o r m so u ti t sp e t r im o d e l ；a n dt h e ng e t t h es u i t a b l ed e a d l o c k - d e t e c t a l g o r i t h m st od e t e c tt h ed e a d l o c ki nt h ep e t r im o d e l ：f i r s t ，t oj e d g e i ft h e r ee x i t sad e a d l o c k m a r k i n g ，d e a dt r a n s i t i o n ；s e c o n d ，t op r o p o s ea n dr e a l i z eaa l g o r i t h mt od e t e c tw h e t h e ra l l t h er e a c h a b l em a r k i n gc a nr e t u r nc ot h ei n i t i a lm a r k i n g t h ee x p e r i m e n to ft h ed e t e c t i o ns h o w st h ep e t r id o n th a v ead e a d l o c km a r k i n ga n d d e a dt r a n s i t i o n ，a n da l lt h er e a c h a b l em a r k i n gc a nr e t u mt ot h ei n i t i a lm a r k i n g ，t h a ts h o w s t h ep e t r ii sa c d v e ，w h i c hc a nf u r t h e rb es u r et h a tt h e r ei sn od e a d l o c ki nt h ei n t e l e g e n t r o b o ts y s t e m k e y w o r d s ：i n t e l e g e n tr o b o t r e a c h a b i l i t yt r e e p e t r in e t s d e a d l o c kl i v e n e s s d e a d l o c km a r k i n gr e c u r s i v es y s t e m y 7 6 3 0 0 5 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名： ! 。蕴燕 年月日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的全部或部分内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的全部或部分内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名： 翌盔煎 年月 日 南京理工大学硕士学位论文 基于p e t r i 网的智能机器人系统死锁检捌 1 绪论 1 1 问置的提出 本课题来源于正在开展的国防科工委重点预研项目“微小型地面机器人技术”。 智能移动机器人研究，是机器人研究领域中重要的研究方向，具有重大的军事和 民用价值，可应用于各种对人类危险的环境中，如进入核化污染环境，及在敌对地区 执行侦察任务等。 由于智能移动机器人是一个对外界环境高度开放的智能系统，需要对各种复杂的 道路状况作出实时感知和决策，这就要求机器人的体系结构能够合理组织调度，整个 系统必然存在多种流程和不同的环节，如果设计不当，则这一错综复杂的系统就有可 能产生死锁、阻塞等情况。 “死锁”( d e a d l o c k ) 是人们不希望碰到但又不可回避的系统特性。在并发系统 的运行过程中，为保证系统的运行安全可靠，必须有效地解决死锁问题。解决死锁的 首要任务是发现死锁，然后才能设法排除它。因此，死锁分析与检测就显得很有意义 和十分必要， 当用p e t r i 网来模拟一个实际系统时，关心的问题之一就是要确定这个p e t r i 网模型是否具有一些所期望的特性，如活性、有界性等，这些特性均是系统的重要动 态行为，其中p e t r i 网的活性反映了被模拟系统的无死锁性。 基于以上分析，本文应用p e t r i 网理论对该地面微小型智能机器人进行建模，得 到其p e t r i 网结构图，并进行死锁检测。 本文待检测p e t r i 网为一循环系统，如果该p e t r i 网满足以下三个条件之一则说 明存在死锁：1 、存在可达的死锁标识；2 、存在死变迁：3 、存在不能到达初始标识 的可达标识。 1 2 本课是的研究意义 用p e t r i 网模拟系统的目的在于描述系统并以p e t r i 网导出该网的性质，并进丽 导出该网所模拟的系统在结构和动态行为方面的特征。 安全性与无死锁性是系统的基本要求，它们是系统建模首先应该考虑的问题。 对于一个系统，若能构造出它的p e t r i 网模型，并利用p e t r i 网严密的数学分析 方法加以分析，就能揭示出被描述的系统在结构和动态行为方面的许多重要信息。这 些信息可用于对系统的性能评估，或对系统提出改进设计的建议。 从p e t r i 网的角度来看，一个系统包括两部分：变迁( t r a n s i t i o n s ) 和条件 ( c o n d i t i o n s ) 。变迁代表系统中发生的事件或行为，条件是系统状态的逻辑描述。变 迁的发生是受条件控制的。变迁的前提条件( p r e c o n d i t i o n s ) 是使变迁激发必须满足 硕士论文 的条件，一旦某个变迁被激发后一些前提条件将不再成立，同时另外一些后验条件 ( p o s t c o n d i t i o n s ) 就被满足了。 网的初始标识( 即标记t o k e n 在库所的分布) 表达了系统的初始状态，变迁的激 发在网中移动标记，模拟了系统状态的变化。 在应用时，既可以把p e t r i 网作为辅助分析工具，也可以将p e t r i 网作为主要设计 工具，研究如何设计出符合要求的p e t r i 网并将p e t r i 网转换为系统。 实际应用中一般采用前者，首先是基于传统的表达方法建立设计，然后将这种设 计转换成p e t r i 网并分析该p e t r i 网。如果没有发现设计上的错误，那么该设计就以 传统的方式实现。如果有错误，就有必要确定在p e t r i 网表示中发现的错误如何在原 设计中得到解释，然后修正设计，并重复上述整个过程，直到得出满足要求的设计。 1 3 目前存在的几种并发系统模型的比较 p e t r i 网定义为一种实现并行异步活动的系统模型，从6 0 年代至今，已提出许许 多多的并发模型，其中影响较大，具有代表性的有f s m 、p e t r i 网、f t s 以及c s p 、c c s 、 s t a t e e h a r t 等模型 。 任何模型成功之处在于两个因素：它的模拟能力以及它的判定能力。模拟能力指 正确表现所模拟系统的能力，是模型忠实地代表所模拟的系统；判定能力指分析该系 统的特定形式以及确定所模拟系统的性质的能力。 ( 1 ) f s m 模型 f s m ( f i n i t es t a t ea u t o m a t am a c h i n e ) 有穷状态( 自动) 机是计算机科学中一个最 基本的模型，被广泛应用于计算机科学及人工智能的诸多领域，许多并发模型均是在 f s m 基础上建立的。f s m 作为并发系统的一种形式模型，在网络通信协议的形式化描 述、验证及测试等方面有广泛的应用1 3 】。方面它有很高的判定能力。另一方面，所 能模拟的系统类别受到苛刻的限制，这就意味着这样一种模型只有低的模拟能力。 ( 2 ) s r a t e c h a r t s 模型。 s t a t e c h a r t 是d h a r e l 于1 9 8 7 年提出的用于描述复杂的并发及反应式系统的 种图形记号【4 】，它通过状态、事件和条件对系统行为进行描述，而后两者的组合形成转 换，从而导致状态之间的转换，实质上是传统f s m 的一种扩充。 ( 3 ) f t s 模型 f t s ( f a i rt r a n s i t i o ns y s t e m ) 公平转换系统是z m a n n a 和a p n u e l i 在1 9 8 3 年 提出的用于反应式( r e a c t i v e ) 系统和并发系统的抽象计算模型【5 】，该模型包含了许多 具有不同语法表示及通信机制的并发系统，可以对应到许多具体的语言模型，如共享 变量( s h a r e d - v a r i a b l e s ) 模型、信息传递( m e s s a g e - p a s s i n g ) 模型及转换图 ( t r a n s i t i o nd i a g r a m s ) 模型等【3 j 。 南京理工大学硕士学位论文 基于p e t r i 网的智锈机器人系统死锬检测 目前该领域研究已取得很大进展口4 5 】，而最具代表性的是m a n - h a 和p n u e i i 的研 究成采【丑，同时由于并发程序形式描述十分复杂，该领域还存在许多闯题有待探讨解 决。 ( 4 ) p e t r i 网模型 1 2 1 p e t r i 网是c a p e t r i 子1 9 6 2 年在其博士论文中提出的一种为设计和分析并发 系统而开发的理论，被认为是第一个通用的并发( 理论) 模型。 在对这些模型中的许多模型豹性质进行比较之后得出：它们之中的大多数要么是 p e t r i 网的子类，要么与p e t r i 网等价，即它等价于或包含着其他大多数模型。 总的来说，p e t r i 网适于作为有事件驱动、状态演变的离散并发系统描述和分析 的模型，往往以位置表示条件，交迂表示事件，位置中有托学表示条件成立，启动规 则实质上是种推理机制。 其特点概括起来有： 】、p e t r j 网是以图形表示的模型，童观性强。 2 、p e t r i 网中的托肯流动表现了系统的动态演变过程。 3 、p e t r i 网能准确的刻画系统的些重要特性，如；并发、冲突、同步、异步、死 锁、饥饿、溢出等。 4 、有一套严格的数学理论和分析方法，支持对系统模型的各种性质和性能评价，借 助子数学开发的p e t r i 网分析方法和技术即可用于静态的结构分析，又可用子动态的 行为分析。 业已证明，它是现有模型中最适合于描述并行异步控制系统或过程的理想模型 1 6 j 。 1 4 本文的组织结构 本文的内容是这样安排的： 第一章：绪论 本章主要分析了对智能机器入系统进行死锁检测的必要往，并对目前存在的几种 并行系统模型进行了详细比较，指出p e t r i 网模型的优势所在。 第二章：对系统进行p e t r i 嘲建模 本章是整篇论文的重要章节。 首先对该地面微小型智能机器人系统进行结构分析，之后对各子系统分别进行 p e t r i 嘲建模，并将各子p e t r i 网结合成整个系统的p e t r i 网模型。 第三章：p e t r i 网死锁检测及讨论 在本章中首先对p e t r i 网的结构死锁和动态死锁从各方砸做了分析比较；由于本 文待检测p e t r i 网模型是一循环系统，根据这一特点分析总结出合适的死锁检测方 硕士论文 法。 第四章：死锁检测算法及其实现 本章是整篇论文的另重要章节，分为两部分： 第一部分针对本文所建p e t r i 网模型的特点得出合适的死锁检测步骤，并实现两 个关键算法。 第二部分首先根据需要给出合理的数据结构，接下来举出两个典型的简单循环 p e t r i 网实例，分别用三种方法对其进行死锁检测并对检测结果进行比较，以验证算 法有效性及程序正确性，为下一章中对智能机器人系统p e t r i 网模型( 图2 3 1 2 ) 进行死锁检测奠定基础。 第五章：死锁检测及结果分析 本章对智能机器人系统p e m i 网模型进行死锁检测：首先给出该p e m i 网的数学描述，再根据 初始标识和输入输出函数对其进行死锁检测，并对检测结果进行了分析。 4 南京理工太学硕士学位论文基于p e t r i 网的智能机器人系统死锁检测 2 对系统进行p e t r i 网建模 2 1 系统结构 该地面微小型智能机器人系统由传感器、信息融合、全局规划、局部规划、控制 等多个模块组成，其结构如图2 1 所示。 圈2 。l 智能机警人蓑统靖糟 2 1 1 模块功能及工作流程描述 ( 1 ) 传感器模块 传感器模块包括二维视觉处理模块( d 2 ) 、夜视处理模块、三维视觉处理模块( d 3 ) 和立体视觉处理模块( s t e r e o ) 。 二维视觉模块和夜视模块分别用于在不同条件下提取道路信息。 三维视觉系统主要用于获取周围环境三维信息，特别是车辆前方障碍的尺寸、距 离等信息。首先通过激光雷达采集到车辆前方路面的高度图象，接着对该图象进行处 理然后以规定的格式将数据发送给数据融合模块，最后接收黑板的状态消息和全球定 位系统( g p s ) 位置信息。 立体视觉模块主要负责检测前方路面的高度。该模块只在越野的状态下起作用， 用以检测越野时的路面状况。首先通过毫米波雷达采集到车辆前方路面的高度图象， 接着对该图象进行处理然后以规定的格式将数据发送给数据融合模块，最后接收黑板 的状态消息和g p s 位置信息。 ( 2 ) 融合模块( f u s i o n ) 数据融合( d a t af u s i o n ，或称传感器融合s e n s e rf u s i o n ) 是采用计算机技术对按 时序由若干传感器获得的观测信息，在一定准则下加以自动分析、综合以完成特定任 务而进行的信息处理过程。 多传感器数据融合的任务是：接收来自各传感器信息预处理模块输出的关于移动 载体前方各传感器有效观测区域内景物的特征描述，以及精确定位子系统给出的位 对系统进行p e t r i 网建模 硕士论文 置、姿态、运动参数等，结合数字地图，经过有效融合，向局部路径规划模块输出具 有明确语义表示的，适合于进行局部路径规划的，关于移动载体前方特定区域内景物 的可靠描述。 每一个循环开始后首先接收d 2 、d 3 、s t 、夜视以及黑板发送过来的消息，接着 如果当前状态是越野则融合d 3 、s t 的数据，否则融合d 3 、d 2 ( 或夜视) 的数据，最 后发送事件消息给黑板，发送融合好的数据给局部规划模块。 ( 3 ) 全局规划模块( g p l a n ) 全局规划模块主要是对一些全局点( 分叉点、越野点、终点) 进行监测，查看目 前车辆是否已经进入某个全局点的范围，以帮助黑板模块能够正确的获取和改变状态 ( 只涉及越野、分叉、终止状态) 。 该模块在每一个循环中首先接收黑板的状态信息和g p s 位置信息，接着根据获得 的位置信息和全局地图以及当前的状态判断是否应该向黑板发送以及发送何种事件 消息，最后是发送事件给黑板，发送全局点给局部规划模块。 ( 4 ) 局部规划模块( p l a n ) 每一个循环开始首先接收f u s i o n 的数据，黑板的状态信息，以及在分叉或者越 野情况下接收全局规划模块的全局规划点，接着根据当前的状态和f u s i o n 数据中的 路边、障碍、路面的情况规划出一条路径，最后发送事件给黑板，规划好的路径给车 辆控制模块。 ( 5 ) 车辆控制模块 车辆控制模块根据规划的路线控制车辆行驶，每一个循环开始接收局部规划模块 发送过来的路径规划数据和黑板模块发送过来的状态信息，控制车辆的行驶。 ( 6 ) 黑板模块 系统采用黑板结构来进行全局性动作协调，黑板调度器包括一个推理机和调度规 则库，调度规则库存放协调整个机器人系统的规则。关于自主机器人当前形势的全局 信号就由黑板调度器给出，并通过通讯接口发送到各个功能模块，协调整个机器人系 统中的各个功能模块工作。 2 1 2 系统结构分析 数据融合模块分析传感器数据得出对周围环境的描述，局部规划模块根据融合结 果和全局规划信息规划机器人当前行驶路径，交给控制模块执行。 各功能模块具有各自的输入、输出接口，其中输入可以来自其他功能模块，也可 以来自外部传感器，同样，输出可以输向其他功能模块，也可以输向外部驱动设备。 内部有专门的处理过程，处理某些特定的信息( 如摄像机获得的二维图象，激光雷达获 取的距离图象等) ，并将处理结果送到输出端口。整个自主移动机器人的行为是这些功 能模块协同工作的结果。 6 南京理工大学硕士学位论文基于p e t r i 网的智能机器人系统死锁检测 系统的各个模块运行在不同处理机上，是一个模块并行工作的分布式系统，而从 外界环境信息的获取到形成规划控制需要一系列的串行处理。 整个系统存在多种流程和不同的环节，有黑板系统与各个功能模块之间的控制协 调环节，也有功能模块之间的横向串行流程。为保障这一错综复杂的系统各个环节各 个模块能正常工作，不致产生死锁、阻塞等不协调的情况出现，需要一种强有力的描 述分析工具。 p e t r i 网有一套严格的数学理论和分析方法，是一种合适的模型。 2 2p e t r i 髓简介 ， p e t r i 网是1 9 6 2 年由德国b o n n 大学的p e t r i c a 在他的博士论文 “c o m m u n i c a t i o nw i t ha u t o m a t i o n ”中作为网状结构的信息流模型提出来的，是一 种系统描述和模拟的数学和图形分析工具。p e t r i 网主要用来描述异步并发系统，由 于其理论的不断完善和发展，其应用领域越来越广泛，网论中关于初始标识、可达标 识、发生权等概念的定义，使p e t r i 网不需任何附加的手段，就可以模拟表示整个系 统的动态行为。 p e t r i 网是一种系统描述和分析的工具，尤其便于描述和模拟并发系统。对于一 个系统，若能够造出它的p e t r i 网模型，并对之加以分析，就能揭示出被描述的系统 在结构和动态行为方面的许多重要信息。这些信息可用于对系统进行性能评估，或对 系统提出改进设计的建议。 2 2 1 基本概念 这里只给出与本文有关的p e t r i 网的些基本概念及相关分析旧7 。1 ”。 注：本文所用到的是一般的标识p e t r i 网一库所变迁系统( p t 系统) ，为了分析 方便和表示直观起见，借用了时间p e t r i 网中的时间变迁和瞬时变迁的概念。 定义2 1 p e t r i 网c 可表示为一个五元组，c = 。 其中： l 、p = p i f i = l ，2 n ：n o ) ，为位置( p l a c e ) 的非空有限集合。 2 、t ： t j i j = l ，2 ，m ：m _ - o ) ，为转移( t r a n s i t i o n ) 的非空有限集合。 3 、i ，0 ：t p 。，为输入输出函数，它们是从转移到位景的一个映射。 4 、m o ：初始标识，n 维向量m o = ( m 1 ，m 2 ，m 。) ，i ( 1 i n ) 表示位景p j 中的标记数是 从位置到非负整数集n 的一个映射函数m ：p n 并且满足：p n t = o ，p u t o 。 p e t r i 网的运行由网中标记( t o k e n ) 的数目和分布情况来控制。 转移启动( f i r i n g ) 时，从它的各个输入位置中移走标记，而将新产生的标记分配 7 对系统进行p e 哺网建模硕士论文 到它的各个输出位置中。 标识( m a r k i n g ) 描述了p e t r i 网的状态，p e t r i 网的状态空间是所有的可达标识的 集合。启动一个转移所引起的状态的变化，可用一个状态函数来表示。 定义2 2( 变迁发生条件) 对于p e t r i 网c = 和t e t ，当且仅当对任一p p 都有：m ( p ) i ( p ，t ) 时，其状态函数6 ：n n t n n 才有定义，且6 ( m ，t ) = m 其中：m7 ( p ) = m ( p ) 一i ( p ，t ) + 0 ( t ，p ) 注：i ( p ，t ) 表示变迁t 发生时所需要的库所p 中的t o k e n 数。 0 ( p ，t ) 表示变迁t 发生时移入库所p 中的t o k e n 数。 定义2 3 ( 可达标识集) 对于p e t r i 网c = ，其可达集r ( c ，蜘) 定义为满足下面两点 的最小标识集合： 1 、蜘r ( c ，i f 【o ) ： 2 、如果m7 r ( c ，m o ) ，并且存在某个转移t ，使得m = 6 ( m ，t ) ，则：m ”r ( c ，m ( ) ) 。 定义中限制每次只考虑个变迁的发生，但根据关于若干个变迁同时发生的并行 步的定义和定理【”，并行步可以到达的标识均可以每步由一个变迁发生到达，所以并 行可达的标识也包含在r ( c ，m o ) 中。 可达性集合r ( c ，) 为从 1 0 出发能够达到的所有标记的集合，它是直接可达的 自反传递闭包。 有标记的p e t r i 网的可达性集合是p e t r i 阏用任何可能执行所能进入的全部状态 的集合。因此，许多分析问题都涉及到p e t r i 网可达性集合的性质。 定义2 4 p e t r i 网c = ( 1 ) 盯= t l m l mt 2 t n m n 为c 的一个有限出现序列( o c c u r r e n c es e q u e n c e ) 的 充分必要条件是：对于所有i ，i = i ，2 ，n ，m i 1 t i = m i ，其中a l d 为c 的初始标 识，n 称为口的长度。 ( 2 ) 若o - = m o t j m l t 2 m 2 t 棚。为c 的出现序列，则f = t l t 2 t 。，称为c 的变迁 序列( t r a n s i t i o ns e q u e n c e ) ，f 的长度与盯长度同为n 。 一般来说，p e t r i 网的运行将产生两个序列：标识序列( m 0 ，m “，) 和变迁 序列( t l ，t 2 ，t ) 。 它们之间的关系为： 6 ( m bt k + 1 ) = m k + l ，其中k = o ，1 ，2 定义2 5 ( 相等) 当v p p ：m i ( p ) = m 2 ( p ) 。即，两标识的分量( 每个位置上的标记数) 一一对应相等。 r 南京理工大学硕士学位论文 基于p e t r i 网的智能机器人系统死锁检测 表示标识m l 和m 2 相等，记为m i = m 2 ， 定义2 6 ( 大于) 当v p e p ：m l ( p ) m 2 ( p ) 并且j p p ：m l ( p ) m 2 ( p ) 。即，标识m 1 的某些分量( 某些 位置上的标记数) 大于标识m 2 中相对应的分量，而其余分量一一对应相等。表示标识 m l 大于标识m 2 ，此时称m 2 被m l 覆盖，记为m i m o 。 定义2 7 ( 小于) ， 当v p p ：m l ( p ) m 2 ( p ) 并且j p p ：m i ( p ) m 2 ( p ) 。即，标识m 1 的某些分量( 某 些位置上的标记数) 小于标识m 2 中相对应的分量，而其余分量一一对应相等。表示标 识m l 小于标识，此时称m l 被m 2 覆盖，记为m i m 2 。 定义2 8 ( 循环系统) 若对p e t r i 网c 的任一有限出现序列d r ，都存在c 的出现序列盯l = m o t l m t t 2 m 2 t n m n ， 使得一方面盯是i 的前缀，另一方面t = t 1 ，t 2 ，t 。 ，且m o l 。，就说c 是循 环系统。 循环系统是活系统的一种特殊情况，它不仅要求系统不含死锁标识、死变迁，而 且要求从任何可达标识都能恢复到自覆盖初始标识的状态( m o s ) 。 定义2 9 ( 时闻变迁) 当某一变迁的发生条件满足时，若该变迁要延迟一段时间后才从相应的输入库所中移 走相应的托肯并得到发生后果，或该变迁发生后，立即从相应的输入库所中移走相应 的托肯，但要延迟一段时间后才得到发生后果，则称这样的变迁为时间变迁。 定义2 1 0 ( 瞬时变迁) 当某一变迁的发生条件满足时，若该变迁立即从相应的输入库所中移走相应的托肯， 且立即得到发生后果，则称这样的变迁为立即变迁。 一般用矩形框表示时间变迁，用黑线表示立即变迁。 2 2 。2p e t r i 网基本特性及其代表缒象境特性 p e t r i 网系统通过网结构来刻划系统的静态特性：通过初始标识( i n i t i a l m a r k i n g ) 和运行规则来刻划系统的动态特性。 针对p e t r i 网模型，利用可达树、可达图、状态方程和计算机仿真等方法，可分 析p e t r i 网的有界性、活性、周期性等特性。 下面列出p e t r i 网的各种特性所代表的系统特性1 2 舶】。 “ ( 1 ) 可达性( r e a c h a b i l i t y ) 可达性是指系统运行过程中能达到指定的状态。状态m l 从状态m 可达，是指存 在有关变迁发生序列s ，使得m s ) m l 。 ( 2 ) 有界性( b o u n d e d i l e s s ) 若构造的可达树中没有任何节点的元素包含。符号，则该p e t r i 网所描述的系统 9 对系统进行p e t n 网建摸硕士论文 是有界的。在实际系统设计中，必须是网中的每个位置在任何状态下的标志数小于位 置的容量，这样才能保证系统的正常运行，不至于产生溢出现象。 ( 3 ) 安全性( s a f e n e s s ) 如果构造的可达树中，每个节点的元素都小于等于l ，则该p e t r i 网所描述的系 统是安全的 ( 4 ) 活性( l i v e n e s s ) p e t r i 网的活性反映了实际系统的无死锁性( d e a d l o c k f r e e ) ，对p e t r i 网活性的研 究，具有非常重要的理论和应用价值，要保证系统避免死锁。 ( 4 ) 回复性 回复性表明系统运行的周期性和循环型。 ( 5 ) 公平性 公平性反映系统的无饥饿性( s t a r v a t i o n - f r e e ) ，即系统的各个子部分在竞争共享资源 时不出现饥饿现象。 ( 6 ) 可逆性 可逆性表明系统运行的可恢复性 ( 7 ) 保守性 保守性表明在实际系统中的资源是受限的，即保守的。 8 ) 一致性 致性对并行系统和并行算法比较重要，表明系统的两个行为之间不存在冲突。 2 2 3p e t r i 同分析技术 用p e t r i 网模拟系统的目的在于描述系统并出p e t r i 网分析技术导出该网的性 质，并进而导出该网所模拟的系统的性质。 并发系统可以按照一定的规则转换成p e t r i 网表示，经过化简，在此基础上通过 各种p e t r i 网分析技术对系统的各项性能指标进行分析。 f 面给出p e t r i 网目前的主要分析方法 l 2 d0 】： ( 1 ) 可达标识图和可达树 对于有界p e t r i 网，采用可达标识图或可达树可分析可达状态、可逆性、活性( 无 死锁性) 、公平性和位置有界性等。对于无界p e t r i 网，则可采用可覆盖树或可覆盖 图分析p e z r i 网的有界性、部分活性等。 ( 2 ) 状态方程和不变量 状态方程可用来分析p e t r i 网中不依赖于初始标识而仅和网结构有关的特性，如 结构有界性、结构公平性和可重复性等。状态方程法适合于事件图的性能分析。不变 量有位置不变量( p 一不变量) 和变迁不变量( t - - 不变量) 两种，前者反映部分位置 的托肯数的一种加权守恒性，可用于研究网的死锁性( 活性) 、互斥行为和错误恢复 1 0 南京理工大学硕士学位论文基于p e t r i - 网的智能机器人系统死锁检捌 等；后者表示使状态回归的可能变迁序列，可用于分析网的周期性和循环型等。 ( 3 ) 语言分析方法 一个变迁序列是一个字符串，字符串集合为一种语言，所有变迁序列之集合表征 了一个p e t r i 网，可用网中可能出现的变迁序列来分析p e t r i 网的性能。这种分析方 法的第一步为标识p e t r i 网：每个变迁对应于字母表中的一个符号，变迁序列就对应 了一个语言，可用于p e t r i 网的规范和自动综合。若一个系统的所要求的行为可用一 种语言来描述，则有可能自动综合出一个p e t r i 网，使其语言即为所要求的行为语言， 这种p e t r i 网就可作为一个控制器。 ( 4 ) 计算机仿真分析 计算机仿真分析作为一种有效工具，也可用于p e t r i 网的性能分析。通过计算机 仿真，可分析有界性、活性、回复性等性能。 ( 5 ) 结构分析 p e t r i 网的许多性能由网的结构所决定，所以，利用变迁之间的顺序关系、选择 关系、冲突关系和冲撞关系、同步异步关系以及守恒性等，可来研究网的性能。目前， 对p e t r i 网的结构分析，或者是针对某一癸特殊网，或者是针对一个具体的网的某个 性能。在结构分析中，可利用网的结构和连接关系进行化简或细化。例如，通过分析 系统能够是否存在死锁结构和陷阱结构来分析系统出现死锁的必要条件。对于大规模 p e t r i 网，通过分解和采用这种方法，可以避免生成和分析全部状态空间，从而避免 出现组合爆炸问题。 2 2 4p e t r i 陌的应用镁城 总的说，p e t r i 网主要用于计算机、通信和自动控制等学科，具体地说，已广泛 用于下面一些领域1 7 旧l ： ( 1 ) 网络通信协议的描述、验证与设计 通讯协议的验证是p e t r i 网应用最为成功的领域之一。最初应用在7 0 年代初期， 由于p e t r i 网以形式语言作为基础，可形式化的对通信协议进行正确性验证。 ( 2 ) 计算机通讯网络性能评价及多媒体应用 随着计算机网络技术和信息技术的发展，进入8 0 年代以后，p e t r i 刚在计算机 网络性能评价和多媒体技术领域内得到越来越多的应用。对网络进行性能分析的需 要，不仅出现于企业内部的生产控制的局域总线网，而且出现于光纤局域网或a t m 网中。 ( 3 ) 软件工程 由于产品开发中的竞争和革新需要，导致产品开发者面临巨大压力。在软件工程 中p e t r i 网主要用于软件系统的建模和分析，比较成熟的是加色p e t r i 网，可以用于 大型软件系统的设计、说明、仿真、确认和实现，在软件开发生命周期的各个阶段， 对系统进行p e t r i 网建模硕士论文 p e t r i 网都可以得到很好的应用。 ( 4 ) 知识处理 p e t r i 网可用于人工智能中的知识表达和推理的形式化模型的建立，可以表达各 个活动之间的各种关系，如顺序关系、与关系、或关系等，并可在模型基础上通过已 知的初始状态和初始条件进行逻辑推理。利用模糊p e t r i 网，表达在专家系统中的一 种不确定的逻辑推理连接，一旦给了初始条件，就可通过模糊推理计算出各个推理结 果的可信度，通过选取得到合理的推理结果。 ( 5 ) 柔性制造系统、计算机集成制造系统和智能制造系统的建模、分析、控制与优 化设计 柔性制造系统( f m s ) 对于现代制造业具有重要作用，p e t r i 网由于其自身优点， 在制造系统中应用广泛，如带缓冲区的简单生产线、机床加工中心、自动生产线、柔 性制造系统和及时加工系统。 ( 6 ) 系统可靠性分析 系统的可靠性不仅包括硬件的可靠性、也包括软件可靠性。利用随机p e t r i 网对 系统进行可靠性分析，对软件复用、软件可靠性分析。 ( 7 ) 多a g e n t 的冲突检测 利用p e t r i 网技术来解决多专家( a g e n t ) 的知识和决策间的冲突检测是一个有 效的方法。若使用p e t r i 网对多专家知识库进行建模与表达的话，通常任一个专家的 知识库可认为一个由产生式规则组成的知识簇，多个专家的推理行为之间存在很大程 度的冲突与矛盾，对这种设计模型的分析是必要的，尤其是应证明在运行时刻可能造 成的冲突的不一致性。因此，可以将p e t r i 网的模型用以分析和检测多专家知识的冲 突问题。 2 3 用p e t r i 两对系统进行建模 异步方式实际上是数据驱动的工作方式2 0 , 2 1 1 ，每个功能模块完成任务后就向黑板 调度器报告结果，同时自身转入空闲状态；调度器则根据各模块送来的结果进行推理 确定新的系统状态，并将状态信息发送给功能模块；处于空闲状态的工作模块若收到 调度器送来的状态信息并有新数据输入，就可转入工作状态。 本文采用自下而上的方法，把系统分解成若干个子系统，对每个子系统建立相应 的p e t r i 网子模型，并通过共享一些公共变迁、公共库所和公共路径来达到子系统间 的联络，从而构成整个系统的完整模型。 注；为后面p e t r i 网表示的方便起见，分析部分用t 表示变迁，用s 表示库所，以免 混淆。 南京理工大学硕士学位论文基于p e t r i 厨的智能规器人系统死锁检测 2 3 1 读写缓冲区 s l ：上一模块输出的数据 s 2 ：空闲缓冲区 s 3 ：信号量 s 4 ：数据在缓冲区中 t 1 ：将数据放入缓冲区 t 2 ：读取缓冲区中的数据 田2 3 1 带檀号量的存裒p s t r l 一 相对于调度器推理时间以及各模块的处理时间很短，数据的访问( 写入与读取) 时间短得多，可以抽象成一个瞬时变迁，因此信号量库所可以简化掉，而不会影响系 统性能的分析。 简化后如下： 圈2 3 2 t 倚化掉信号量库所的存取p b t r i 同 一般情况下，为了简化p e t r i 网会将s 2 、s 4 合并成一个库所s ，作为t 1 的输出 和t 2 的输入，库所中有t o k e n 表示缓冲区中有数据，反之表示缓冲区为空。 后经程序验证，就本文所建p e t r i 网丽言，如果将“空闲缓冲区”秘“数据在缓 冲区中”两个库所合并的话，在建可达树时会产生广义标识( 含符号u ) 。 广义标识的存在对p e t r i 网性能分析会造成一定的困难【7 ，8 1 ，可以归纳为如下两 点： l 、由于符号的引入。丢失了许多信息。例如，对分析p e t r i 网的两个十分重要的性 1 3 对系统进行p e m 网建模 硕士论文 质，如活性和可达性，在一般情况下不能提供有效的信息可供参考和利用。 2 、p e t r i 网的可达树不能唯一地确定网。换句话说，两个不同的p e t r i 网有可能产生 同一棵可达树。亩于这两方面的不足，使得基于可达树的活性、可达性分析比较困难。 实际上，这两点可归于一点，就是由于符号u 的引入，给死锁检测造成了一定的 困难，故本文所建p e t r i 网没有将这两个库所合并。 2 3 2 馋瘤器模块 传感器模块包括二维视觉处理模块、夜视处理模块、三维视觉处理模块和立体视 觉处理模块。 a 、传感器模块与黑板调度器之间的控制协调 由于传感器数据为融合模块的输入信息，必须各采集模块都完成数据采集处理后 融合模块才能工作，因此，二维视觉、三维视觉、立体视觉、夜视模块采取局部同步 的工作方式。用p e t r i 网表示如下： 说明， ( 1 ) 等待调度的二维信号：二维处理模块空闲，即已完成上一周期的处理，可以开 始下一周期的工作。 ( 2 ) 二维视觉模块的启动信号：黑板发给二维视觉模块的状态信息。 其它依次类推。 s 1 ：等待调度的二维信号t l ：黑板调度器准备推理( 二维等) 信号 s 2 ：等待调度的三维信号 t 2 ；黑板调度器进行推理( 二维等) 信号 s 3 ：等待调度的立体信号 s 4 ：等待调度的夜视信号 s 5 ：将要推理的黑板调度器 s 6 ：二维视觉模块的启动信号 s 7 ：三维视觉模块的启动信号 s 8 ：立体视觉模块的启动信号 s 9 ：夜视模块的启动信号 s 1 8 ：二维数据 s 1 9 ：三维数据 $ 2 0 ：立体数据 5 2 1 ：夜视数据 $ 2 2 ：空闲的黑板调度器 注：下图中的四个处理模块均应抽象为一个变迁，每个变迁对应一个子网，图中的表 示方法是为了增强可读性。 1 4 南京理工大学硕士学位论文基于p e t r i 鄹的智能机器人系统死锁检铡 s 1 8s 1 9 $ 2 0 $ 2 1 豳2 3 3 t 传暴楱块与l i 板谓度暴之间的协调p e t r l 月衰示 描述： s l 、s 2 、s 3 、s 4 、$ 2 2 中都有t o k e n 时，即二维视觉、三维视觉、立体视觉、夜 视信号都处于等待调度状态，且黑板调度器空闲，则变迁t i 发生，t o k e n 迁移到s 5 ， 表示黑板调度器准备工作，然后t 2 发生，经过一段时间，t o k e n 迁移到s 6 、s 7 、s 8 、 s 9 和$ 2 2 ，表示各传感器模块可以开始工作并重置黑板调度器空闲以等待下一轮的一1 ： 乍。传感器模块并行工作完毕，输出数据，同时将籀应的信号重量为等待调度状态。 以二维视觉为例：二维视觉处理模块工作完毕，t o k e n 迁移到s 1 、s 1 8 ，表示输出二维 数据，同时将二维信号重置为等待调度状态。 b 、二维视觉( 三维视觉、立体视觉、