（计算机应用技术专业论文）基于有色网的行动推理的描述与分析.pdf

江苏大学硕士学位论文 摘要 行动推理是人工智能的一个重要的研究领域。a g e n t 一般处于动态不完全可 知的环境中，为了完成给定的任务，通过自主推理、规划、寻找出从初始状态到 达目标状态的动作序列，从而实现目标。 p e t r i 网是公认的特别适合描述并发和同步的形式化工具，它具有图形化的直 观表示方式和丰富的分析方法，非常适合表示和模拟具有异步、并发、动态等特 征的系统。本文基于p e t r i 网的高级网形式有色网来描述行动推理。本文的主 要工作如下： ( 1 ) 提出了一种基于有色网的形式化表示单a g e n t 行动推理的方法 p n s r a a 网( c o l o r e dp e t r in e tf o rs i m p l ea g e n to fr e a s o n i n ga b o u ta c t i o n ) ， 采用c p n s r a a 网对状态、动作以及动作之间的各种复合关系( 顺序关系、循环 关系、条件关系、异步并发关系、冲突关系、真并发关系、中断关系) 进行了形 式化地表示。 ( 2 ) 提出了一种根据系统的初始条件、目标以及动作的前提条件和后继状态， 来构造表示行动推理的c p n s r 从网系统的有效方法，使用该方法构造的 c p n s r a a 网系统能描述和实现a g e n t 在动态环境下进行自主行动推理和面向目 标规划，同时提出了一个在c p n s 凡诅网系统中进行搜索，寻找出实现目标的动 作序列生成方法。 ( 3 ) 提出了一个针对多a g e n t 系统的c p n m r a a 网j ( c o l o r e dp e t r in e tf o rm u l t i a g e n to f r e a s o n i n ga b o u t a c t i o n ) 模型。该模型把多a g e n t 行动推理系统分为a g e n t 模块和环境模块两个大模块，对a g e n t 模块中的动作模块和通信模块，以及环境 模块中的同步模块和对a g e n t 的通信和动作进行处理的模块都分别进行了形式化 地表示与分析，并采用它为办公室环境多a g e n t 行动推理实例进行了建模和分析。 ( 4 ) 对研究的内容进行了建模和仿真。对办公室环境单a g e n t 行动推理实例进 行建模和仿真，得出了实现目标的动作序列，并对a g e n t 的赋时行动推理进行了 仿真，结果验证了c p n s r a a 网表示行动推理的有效性和可行性，最后通过仿真 报告进一步分析了c p n s r a a 网系统的有界性和活性。 本论文利用p e t r i 网能较好地表示系统的异步、并发等特征的优点，在采用 江苏大学硕士学位论文 p e t r i 网表示a g e n t 行动推理方面做了一些尝试，为a g e n t 行动推理技术的研究和实 现打下了一定的基础。 关键词：p e t r i 网， c p n ，行动推理， a g e n t ，并发，冲突，异步 n 江苏大学硕士学位论文 a bs t r a c t r e a s o n i n g a b o u ta c t i o no fi n t e l l i g e n ta g e n ti ss u r e l yo n eo ft h em o s te x c i t i n ga n d c h a l l e n g i n ga r e a si na r t i f i c i a li n t e l l i g e n c e i n t e l l i g e n ta g e n t sa r ee m b e d d e di na l l i n c o m p l e t e ，d y n a m i ce n v i r o n m e n t ，a n dt h i sr e q u i r e st h ea g e n t sh a v eh i g h e rc o g n i t i v e c a p a b i l i t i e ss u c ha sr e a s o n i n ga b o u ta c t i o n ，d e v i s i n gap l a n ，a n dd r a w i n gl o g i c a l c o n c l u s i o n sf r o ms e n s o ri n f o r m a t i o na c q u i r e d ，t of i n dap l a nf r o mt h ei n i t i a ls t a t et o t h ef i n a ls t a t e p e t r i n e t s ，a s af o r m a lt o o l s p e c i a l s u i t a b l e t o s p e c i f yc u r r e n c ya n d s y n c h r o n i z a t i o na n dh a v i n gg r a p h i c a lr e p r e s e n t a t i o n sa n dr i c ha n a l y s i sa p p r o a c h e s ， a l e v e r y s u i t a b l et o r e p r e s e n t a n ds i m u l a t et h e s y s t e m s c h a r a c t e r i z e da s s y n c h r o n i z a t i o n ，c o n c u r r e n c y , a n dd y n a m i c s t h i sp a p e rd e s c r i b e sr e a s o n i n ga b o u t a c t i o nb a s e do nt h ea d v a n c e dn e to fp e t r in e t “o l o r e dp e t r in e t sa n dt h em a i n w o r k sa l ea sf o l l o w s ： ( 1 ) b a s e do nc o l o r e dp e t r in e t san e wf o r m a l i z e dr e p r e s e n t a t i o nm e t h o d - - c p n s r a an e ti si n t r o d u c e d t h es t a t e s ，a c t i o n sa n dt h ec o m p o u n dr e l a t i o n sa m o n g a c t i o n s ( s u c ha ss e q u e n c e ，i t e r a t i o n , c o n d i t i o n , s y n c h r o n i z a t i o nc o n c u r r e n c y , c o n f l i c t , t r u ec o n c u r r e n c ya n di n t e r r u p t i o n ) a l ec o n s t r u c t e db yu s i n gc p n s r a an e t ( 2 ) am e t h o dh a sp r o v i d e df o rc o n s t r u c t i n gc p n s r a a n e ts y s t e ma c c o r d i n gt h e i n i t i a lc o n d i t i o n s ，g o a lo ft h es y s t e ma n dt h ep r e - c o n d i t i o n sa n dp o s t c o n d i t i o n so f a c t i o n , w h i c hc a nm a k et h e a g e n t r e a s o na b o u ta c t i o n s a u t o m a t i c a l l ya n d g o a l o r i e n t e di nt h ed y n a m i ce n v i r o n m e n t a na l g o r i t h mu s e dt op r o d u c ea c t i o n s e q u e n c ei nc p n s r a a n e ts y s t e mt or e a c hg o a lh a sa l s op r o v i d e d ( 3 ) ac p n m r a an e tm o d e lh a si n t r o d u c e dt om o d e lt h em u l t i - a g e n ts y s t e m s ， w h i c hc a nb ed i v i d e da s a g e n tm o d u l ea n de n v i r o n m e n tm o d u l e t h ea g e n tm o d u l e c o n t a i n sa c t i o nm o d u l ea n dc o m m u n i c a t i o nm o d u l e ，w h i l et h ee n v i r o n m e n tm o d u l e c o n t a i n ss y n c h r o n i z a t i o nm o d u l e ，c o m m u n i c a t i o np r o c e s s i n gm o d u l ea n da c t i o n p r o c e s s i n gm o d u l e t h ec a s eo fm u l t i a g e n tr e a s o n i n ga b o u ta c t i o ni nr o b o to f f i c e i i i 江苏大学硕士学位论文 e n v i r o n m e n ta r em o d e l e da n da n a l y z e db yu s i n gc p n m r a am o d e l ( 4 ) t h er e s e a r c h i n gc o n t e n t sa r es i m u l a t e d t h ec a s eo fs i m p l ea g e n tr e a s o n i n g a b o u ta c t i o ni nr o b o to f f i c ee n v i r o n m e n ta n dt h ec a s ew i t ht i m eh a v es i m u l a t e d ，w h i c h p r o v e sc p n s r a a n e ta saf e a s i b l ea n de f f e c t i v er e p r e s e n t a t i o nf o rr e a s o n i n ga b o u t a c t i o nc a nr e a s o nt h ea c t i o n s e q u e n c et oa c h i e v et h eg o a lp e r f e c t l y , a n dt h e b o u n d e d n e s sa n dl i v e n e s so ft h ec p n r a an e tw em o d e l e da l s oa r ev e r i f i e db yt h e s i m u l a t i n gr e p o r t s o u rp a p e rt a k e st h ea d v a n t a g eo ft h ea s y n c h r o n i s ma n dc o n c u r r e n c yo ft h e f o r m a lm e t h o do fp e t r in e t ，a n dd o e ss o m et r i e so nu s i n gp e t r in e t t or e p r e s e n t r e a s o n i n ga b o u ta c t i o no fa g e n t s ，w h i c hl a y st h ef o u n d a t i o nf o rt h ef u t u r er e s e a r c ha n d t h es p r e a df o rt h et e c h n o l o g yo fr e a s o n i n ga b o u ta c t i o no fa g e n t s k e yw o r d s ：p e t r in e t s ，c p n ，r e a s o n i n ga b o u ta c t i o n , a g e n t , c o n c u r r e n c y , c o n f l i c t , a s y n c h r o n i z a t i o n i v 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部 内容或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于， 不保密幽。 导师签名： 甸一葶乏 签字日期：1 一矿年肛月珍日 时 矽 牛m 名 年 签 扩 者 驴 雕 埘 文 期 沦 日 位 字 学 签 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容以外，本论文 不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的 研究做出重要贡献的个人和集体，均己在文中以明确方式标明。本人 完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 矽掣 魄巾3 年f 工月矽日 江苏大学硕士学位论文 第一章绪论 本章首先介绍了智能a g e n t 的定义、特征及应用领域；然后介绍了a g e n t 行 动推理理论的定义及其在国内外的研究现状和发展趋势；接着又介绍了p e t r i 网理 论以及其表示行动推理的研究背景；最后概述了本论文的主要工作及论文结构安 排。 1 1 智能a g e n t a g e n t 的原意是“代理”指具有智能的任何实体，包括人类、智能硬件和智 能软件。到目前为止，a g e n t 在研究领域中尚没有一个统一的定义，但人们普遍认 为，a g e n t 是驻留在某一环境下能够自主( a u t o n o m o u s ) 、灵活( f l e x i b l e ) 地执行动作 以满足设计目标的行为实体。 a g e n t 通常具备下列特性【l 】： ( 1 ) 自主性 a g e n t 是一个行为主体，它具有一组动作并能执行这组动作，是动作执行的 决策者和实施者，同时它具有属于其自身的计算资源( 数据、信息等) 和局部于自 身的控制机制，能根据内部状态和从环境中获得的感知输入，自主地决定应该执 行什么样的动作以实现其设计目标。 ( 2 ) 反应性 反应性是指a g e n t 能够感知所处的环境( 可能是物理世界、或操纵图形界面的 用户或与它进行相互通信的其它a g e n t 等) ，并能对环境中发生的相关事件( 如a g e n t 之间交互和通信、系统中时钟事件的发生和用户的界面操作等) 作出适时地反应， 以满足系统设计目标。 ( 3 ) 自发性 a g e n t 并不是仅仅简单地对环境中发生的事件做出适时的反应，而且它还能 够表现出某种目标制导机制。 ( 4 ) 社会性 a g e n t 行为的社会性是指它所驻留的环境可能存在其他主体，它拥有这些主 体的有关信息和知识( 如这些主体的名字、物理位置、所拥有的资源和能力和对外 江苏大学硕士学位论文 提供的服务) ，并能与它们进行交互和通信，实现灵活多样的复杂的合作、协商和 竞争，以满足系统的设计的目标。 1 2 行动推理 行动推理 2 1 由j o h nm c c a r t h y 首次提出，并认为行动推理在常识推理研究中占 有基础性的地位，其核心思想为任何引起系统状态变化的因素都可以看作是动作。 至此以后，行动推理成为人工智能的一项重要研究内容。利用形式化的方法对世 界和行动进行描述和推理构成行动推理的主要内容。行动推理有时也被称为行动 逻辑。在这里把关于行动和变化的推理总称为行动推理。目前的行动推理任务可 以是下面两个方面： ( 1 ) t e m p o r a lp r o j e c t 问题：其主要任务是在给出系统的初始状态和变化规则以 后，预测某个行动或者行动序列的效果。 ( 2 ) p o s t d i c t i o n t e m p o r a le x p l a n a t i o n 问题：即给出系统的初始状态和目标状态， 解释系统经历了哪些行动，使得系统从初始状态到达了目标状态。 行动推理自从2 0 世纪6 0 年代后期提出以来。取得的较为突出的成果有7 0 年代末8 0 年代初的非单调推理技术。8 0 年代中期关于y s p 问题的讨论和结果问 题的发现以及“极小化+ 限定域”模式的提出。9 0 年代中后期对因果关系的形式 化等等。近年来，行动推理研究受到广泛的重视，一些行动推理的专门国际会议 相继召开，国际联合人工智能大会( i j c a j ) 于1 9 9 9 年将行动推理列为一项专题。 行动推理的研究已经有了4 0 多年的历史，虽然取得了很多成果，推动了一批 相关领域的研究，出现了许多表达能力强、形式优美的行动推理系统，但大多数 都基于较为抽象的数理逻辑系统，一般的用户不容易理解，同时这些系统的计算 复杂性较高。实用系统仍然以简单的类s t r i p s l 3 1 系统为主。 要使得“智能a g e n t 在环境中像人一样思考并且对环境作出反应，那么它必 须具有在动态的、不完全可知的环境中进行感知、推理和行动的能力。为了更好 地研究和发展智能a g e n t 的行动推理，需要找到一种工具来描述智能a g e n t 的行动 推理以寻找出到达目标的规划过程。目前影响较大行动推理的形式化系统主要有 s t r i p s 系统、情景演算、事件演算和流演算等。 2 江苏大学硕士学位论文 1 2 1s t r j p s 系统 s t r i p s t 3 1 系统简单而实用，它采用逻辑公式集合描述系统的状态，一个动作 是由前提条件、增加列表和删除列表三部分构成的。当前提条件满足时动作就可 以执行，动作执行后在系统的状态描述中添加增加列表中的公式，而去掉删除列 表中的公式。 1 2 2 情景演算 情景演算p 】【5 1 的基本特点是引入一类情景变元s ，情景表示某一时刻系统的状 态。系统状态变量的取值与情景有关，被称为流。情景的变化由动作引起，所以 情景可以看作是一个从初始状态开始实现目标的动作序列。它采用后继状态公理 解决了框架问题的表示。 1 2 3 事件演算 事件演算【6 】【刀是一种基于时间的方法，状态变量的值与时间段有关。状态变 量一般称为性质( p r o p e r t y ) 。i n i t i a t e ( e ，f ) 表示事件e 导致状态变量厂为真。 t e r m i n a t e ( e ，f ) 表示事件e 导致状态变量为假。h o l d s ( f ，t ) 表示性质厂在时y l i t 成立。其基本推理机制在于根据事件的叙述和行动的效应来推理出什么时间什么 为真。 1 2 4 流演算 流演算【8 j 9 j 1 0 1 1 基于经典的谓词逻辑，是一种多型的二阶逻辑描述语言，用 来公理化动态环境以及行动推理。它是在情景演算的基础上发展起来的，沿用了 情景演算的一些概念，如：流表示了世界的原子属性，情景是动作执行的历史， 同时又增加了状态的概念，状态是某时刻世界的快照，是流的集合，流演算可以 表示不完全的世界模型。同时，它通过状态更新公理解决了框架问题的表示和推 理。 流演算的实现语言f l u x ，是一种基于p r o l o g 的带有约束的逻辑程序设计语 江苏大学硕士学位论文 言，利用约束求解库进行行动推理，产生动作序列。它包含了编码不完全世界状 态的方法以及更新世界状态的技术，能够很方便地表示a g e n t 在不完全状态下的 行动推理，同时它采用前推( r e g r e s s i o n ) 的推理机制，根据动作的执行不断地更新 世界的状态，验证动作成立时不需要回归整个动作历史，对于动作较多，规模较 大的系统来说，具有良好的计算性能，适合于设计a g e n t 的规划活动。 上述几种形式化系统主要基于经典逻辑，其缺点是难以描述系统的并发性。 1 2 5p e t r i 网表示行动推理 p e t r i 网【1 2 】是德国的c a p e t f i 博士在其博士论文“c o m m u n i c a t i o n 谢吐l a u t o m a t a 中首先提出来的，最初是用来研究信息系统及其相互关系的数学模型。 p e t r i 具有以下优点【1 3 】【1 4 】【1 5 】【1 6 】： ( 1 ) p e t r i 网有严格的形式化定义，又有直观的图形表示，具有直观、易懂和易 用的优点，对描述和分析并发现象有独到的优越之处。 ( 2 ) p e t r i 网有严格定义的数学对象，借助数学开发的p e t r i 网分析方法和技术 既可以用于静态的结构分析，又可用于动态的行为分析。 ( 3 ) 可以进行层次化。p e t r i 网可以使用层次建模的方法，实现模块化和逐步求 精，具有很好的重用性，对软件设计和开发人员的工作具有重要的指导意义。 由上述性质可知，p e t r i 网非常适合于异步并发系统的描述和创建1 7 】【1 8 】【1 9 】【2 0 】， 而行动推理系统具有异步、并发、动态等特征，行动推理系统中的不同动作的运 行能实现状态的转变，而p e t r i 网中的变迁和库所分别与行动推理中的动作和状态 的语义很接近，并且变迁元素的激活伴随着其前置条件和后置条件的变化，这是 是可以利用p e t r i 网对a g e n t 的行动推理进行表示和分析的主要原因。 9 0 年代开始，d u 2 1 1 2 2 】和1 a d a o 【2 3 1 别提出基于谓词变迁网( p r e d i c a t e 仃a i l s i t i o n n e t ) 对行动推理进行表示，采用了积木世界的例子，把所有目标表示成合取式的 形式，采用类s t r i p s 的方法，把s t r i p s 系统中一系列动作对应的前提条件， 删除条件和增加条件转化为谓词变迁网的相应的谓词。d u 提出使用关联矩阵求 解出实现目标的动作集合，然后再对这些动作进行排序的方法，从而得出最终的 动作序y o ；而t a d a o 采用可达树算法求解出从初始状态到目标状态的偏序动作序 列。但他们的这种表示方法，所有同一个状态的两个相反的方面需要用两个谓词 4 江苏大学硕士学位论文 来表示，如h o l d i n g 和h a n d e m p t y 。如果问题规模变大，可能会引发状态爆炸问 题。在此基础上，t a d a o 2 4 1 又对多个a g e n t 的积木世界的例子进行建模，实现了使 用谓词变迁网来表示多a g e n t 行动推理的首例。但是，其中涉及到多a g e n t 系统 中a g e n t 之间协调的部分，直接采用规则来进行限制，对具体问题的依赖性很大， 缺乏通用性，同时建模出的表示行动推理谓词变迁网系统没有限制目标实现的结 束条件，因此可能会导致死循环。 m o l d t 2 5 1 等采用面向对象的有色网来表示多a g e n t 系统的行动推理，实现了 a g e n t 之间和a g e n t 内部动作的并发，用一个类来表示a g e n t ，而类中的方法表示了 a g e n t 的能力，因此类中方法的并发可以实现a g e n t 内部动作的并发。 s i l v a t 2 6 1 等将规划图转化为一个无回路的p e t r i 网来进行行动推理，但是它仍 然保持了规划图的冗余性，仅仅只是把其中的p r o p o s i t i o n 结点和a c t i o n 结点分别 转化为p e t r i 网中的库所和变迁元素，没有很好地利用p e t r i 的动态性。 c a s t i l h o 2 7 】在s i l v a 基础上的进一步提出了直接从问题出发，对问题的动作之 间的关系直接讨论，直接得到了对应的、无回路的p e t r i 网系统，并利用了p e t r i 网的动态性进行行动推理，但缺乏对动作的形式化描述。 b u i 2 8 】提出了通过构造规划图来生成多a g e n t 系统动作序列的过程，规划图的 生成是从初始事实前向链接的过程，规划的生成则是依据规划图中不同级别的结 点进行回溯求解，在规划空间中进行搜索求解。 v i 铷r i o 【2 9 】【3 0 】利用p e t r i 网对动作之间的关系进行了图形化地表示，但缺乏对 动作和环境的形式化描述，且其生成的网模型不能自动生成动作序列。 x u 3 1 1 1 3 2 1 基于谓词变迁网对多主体行为进行了描述，而c o s t 3 3 1 对多主体之间 的会话进行了描述，但是他们方法主要集中在少数主体间的交互，没有形成一种 通用的描述多主体行为的结构，同时不能很好地对系统中的冲突进行有效分析。 d a n n y 3 4 】【3 5 】提出了一种基于有色网的多a g e n t 的协作模型，考虑了社会性对 a g e n t 行为的影响，但是他所提出的模型不能生成实现目标的动作序列，因而不便 于描述规划。 文献 3 6 3 7 3 8 1 n 样采用p e t r i 网行动推理建模，但同样不能自动生成实现目 标动作序列。 上述所有方法均采用p e t r i 网描述行动推理，但是都没有采用一种通用的能表 江苏大学硕士学位论文 示出动作之间的各种复合关系的形式化表示方式，从而不便于描述主体规划，且 上述各种方法得出的网模型，不能自动生成动作序列。本文提出一种基于有色网 表示行动推理的形式化模型，提出了构造表示行动推理的p e t r i 网系统的方法，考 虑了瞬时和持续动作的情况并对各种动作以及动作之间复合关系进行了形式化地 表示，同时在构造算法中为网系统加入动作序列库所，保存a g e n t 做过的所有动 作，并使用目标库所对系统的结束情况进行控制，并有效地解决的了多a g e n t 社 会性对a g e n t 行动推理的影响。 1 3 论文主要研究内容 由前面的介绍可知，智能a g e n t 在诸多领域都有非常高的应用价值，对其研 究具有重要的现实意义。本文主要关注于用p e t r i 网表示智能a g e n t 的行动推理： 第一章绪论部分。本章概述了智能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 网和网系统的概念， 介绍了p e t r i 网的基本分析技术以及基本性质。 第三章c p n s r a a 网。本章在有色网基础上，提出了一种基于有色网的形 式化地表示单a g e n t 行动推理的方法一p n s 凡诅网( c o l o r e d p e t r in e tf o r s i m p l ea g e n to f r e a s o n i n ga b o u ta c t i o n ) ，采用c p n s r a a 网对动作以及动作之间 的各种复合关系进行了形式化地表示，并提出了c p n s r a a 网系统的构造方法和 动作序列生成方法。 第四章c p n m r a a 网。本章提出了表示多a g e n t 行动推理的形式化表示方 法c p n m r a a 网( c o l o r e dp e t r in e t f o rm u l t ia g e n to fr e a s o n i n ga b o u ta c t i o n ) ， 把多a g e n t 系统分为a g e n t 模块和环境模块，并对其进一步的划分，a g e n t 模块中 a g e n t 既可以执行普通动作又可以和其它a g e n t 通信，而环境模块中则包含了对同 步模块以及对a g e n t 的所有动作进行处理的模块。 第五章办公室环境a g e n t 行动推理建模。本章在前面提出的c p n s r a a 网 和c p n m r a a 网的基础上，为办公室环境单a g e n t 和多a g e n t 行动推理实例分别 进行了建模和分析。 6 江苏大学硕士学位论文 第六章办公室环境单a g e n t 行动推理实例仿真。本章采用c p n t o o l s 5 0 1 工具， 对办公室环境单a g e n t 行动推理实例的c p n s r a a 网系统进行了仿真，自动生成 了a g e n t 实现目标的动作序列，并对办公室环境单a g e n t 赋时行动推理的 c p n s r a a 网系统进行了仿真，最后对仿真报告进行了分析。 第七章总结与展望。是对论文工作的总结和进一步工作的展望。 1 4 本章小结 本文对智能a g e n t 的研究主要是考虑动态、不确定系统的描述与分析，而p e t r i 网具有严格的数学基础，能够表示具有不确定性、动态性和真并发等特征的系统。 为此本文采用p e t r i 网表示行动推理，并将其应用于办公室环境a g e n t 行动推理实 例中，下面的章节将分别对其进行详细介绍。 7 江苏大学硕士学位论文 2 1p e t r i 网概述 第二章p e t r i 网介绍 一般的系统模型均由两类元素构成：表示状态的元素和表示变化的元素。比 如在程序语言中用变量表示状态；用语句，特别是赋值语句表示变化。同样p e t r i 网也由这两类基本元素构成，它的状态元素称为s 元，表示库所或条件；其变迁 元素称为r 元，表示事件或变迁。在p e t r i 网中，变迁能否发生及发生的影响完全 取决于自然规律，不带主观性。 下面是p e t r i 网的一些基本概念： 一、三元组n = ( s ，丁；f ) 称为有向网( d i r e c t e dn e t ) ，简称网( n e t ) 的充分必要条 件是： 1 ) s r 、t = 妒； 2 ) s u t 痧； 3 ) f s t u t x s ； 4 ) d o m ( f ) t ) c o d ( f ) = s u t ； 其中：d o m ( f ) = x3 x ：( x ，y ) f ) ，c o d ( f ) = 秒i3 x ：( x ，y ) f ) 分别称为f 的 定义域和值域。s 和丁分别称为的库所( p l a c e ) 集和变迁( t r a n s i t i o n ) 集，f 为流关 系( f l o wr e l a t i o n ) ，s 表示库所结点集合，丁表示变迁结点集合，f 为库所结点与 变迁结点之间的有向弧集合。 注意： 库所集和变迁集是有向网的基本成分，流关系是从它们构造出来的，所以 在丁和f 之间用分号“；”隔开； 库所和变迁是两类不同的元素，所以它们的交集为空；而它们的并集不能 为空，表示网中至少要有一个元素； 不参加任何变迁的资源表现为孤立的库所，不引起资源流动的变迁表现为 江苏大学硕士学位论文 孤立的变迁，d o m ( f ) u c o d ( f ) = s u t 规定网中不能有孤立元素； 每个库所代表一种资源，资源的流动是由流关系规定的，所以变迁只能与 库所有直接的流关系：f s x t u t x s 。 二、令n = ( s ，t ，f ) 是一个p e t r i 网，设x s u 丁为中的任一元素，则x 的 前置集定为x = y s u tl ( y ，x ) f ) ，其后置集定义为弦= y su tl ( x ，y ) f ) 。 节点的集合h s u t 的前置集( 后置集) 可以定义为h = u ，胡x ( h = u 。日x ) 。 1 ) 若有x ，y s w t ，但x = y x = y j x = y ，那么无论从结构还是从行为 上来说，x 和y 都无法区别，把不含这种元素的网称为简单网( s i m p l en e t ) 。 2 ) 若v x ，y s u t ，x n 弦= 则称为单纯网。 3 ) v x ，y s u t ，x = y x y - j x = y 则为简单网。 三、如果n = ( s ，t ，f ) 是普通网： 1 ) 若对于v t t ，爿t i - 1 ，则称是状态机( s t a t em a c h i n e ) 。 2 ) 若对于v s s ，卜i = j8 - i _ 1 ，则称是标识图( m a r k e t g r a p h ) 。 3 ) 若既是一个状态机又是强连通的，则称为强连通的状态机。 2 2p e t r i 网系统 网是系统静态结构的基础，但还不是系统静态结构的全貌。网系统的静态部 分还应包括库所的容量以及变迁与其激活所需要资源的数量关系。 有向网是系统的结构框架，就象演戏的舞台。活动在框架上的是系统中流动 的资源( 演员) 。从网到网系统的过程必须指明资源的初始分布，规定框架上的活 动规则，即库所的容量和变迁与资源之间的数量关系。对有向网n = ( s ，t ，f ) 而言， 记= 0 ，1 ，2 ，叩= 1 ，2 ，3 ，) ，并以表示无穷：c o = c o + l = c o - l = + 。 下面是p e t r i 网系统的一些基本概念： 一、六元组= ( s t ；f ，k ，w ，) 构成网系统的条件是： 9 江苏大学硕士学位论文 1 ) n = ( s ，t ；f ) 构成有向网，称为的基网； 2 ) k ：s n w r o 称为的容量函数( c a p a c i t y f u n c t i o n ) ； 3 ) z ：f 专7 7 称为n 上的权函数，对于( x ，y ) f ，w ( x ，y ) = 形( 阮少) ) 称为( x ，y ) 上的权。 4 ) 对给定的m ：s 专叩0 称为的一个标识( m a r k i n g ) 的条件是： v s s ：m ( j ) k ( s ) ； 网论尊重资源有限的事实，所以代表资源分布的标识m 只能为每个库所指定 有限多个资源，库所的容量也是有限的。按定义允许有些库所的容量为，这只 是表明这些库所的容量不会对系统的行为构成限制。以上定义了网系统从结构到 资源的静态特征。下面介绍网系统的动态规律，即变迁规贝l j ( t r a n s i t i o nr u l e ) 。 二、设m 为网系统= ( s ，t ；f ，k ，w ，心) 的基网( s ，丁；f ) 上的任一标识，t t 为任一变迁： 1 ) 变迁发生条件： 设r 一t l ) t 称为，的外延( e x t e m i o n ) ，f 在m 有发生权( f i r a b l e ) 的条件是： v s 彳：m ( s ) r v ( s ，t ) v s f ：m ( s ) + 形( s ，) k ( s ) ，f 在m 有发生权记做： m t ，也说m 授权( e n a b l e s ) t 发生。 2 ) 变迁发生结果： 若m t ，则f 在m 可以发生，将标识m 改变为m 的后继( s u c c e s s o r ) ，m 的 定义是：对于v s s ， im 0 ) s 盛t m ( s ) ：jm o ) 一形 舱川 一 im ( s ) - w ( s ，f ) + 缈( f ，s ) s t n t 【m ( s ) + 形o ，s ) s t t 2 3 网系统分类 网系统的容量函数k 和权函数形可以分为三种情况： 1 0 江苏大学硕士学位论文 ( 1 ) k 三l ，w 暑l 这时每个s 元只有“有托肯 和“无托肯”两种状态，因而可以理解为“真 与“不真 两种状态的布尔变量。网论中把这种s 元称为条件( c o n d i t i o n ) ，只与 条件关联的变迁称为事件( e v e n t ) 。习惯上，分别用召和e 表示条件集合和事件集 合。由条件和事件构成的系统称为基本网系统( e l e m e n t a r yn e ts y s t e m ) 或e n _ 系统。 ( 2 ) k 兰c o ，w 兰1 这是传统上称为p e t r i 网的网系统，又称p t 网( p l a c e t r a n s i t i o n n e t ) 。 ( 3 ) k 和缈为任意函数 这种系统通常称为库所变迁系统( p l a c e t r a n s i t i o ns y s t e m ) 或p t 系统。p 卫 网和p t 系统中流动的均是物质资源，与e n 系统有质的区别，自然是不同类的。 而p t 网和p 厂r 系统的区别在于k 和形的不同，借助s 补技术消除冲撞可以消 除k 兰和k 为任意函数区别，通过把库所分为很多小库所，从每个库所中取出 一个托肯可以消除w 三1 和矽为任意函数的区别，所以可以把p t 网和p t 系统 看作是同类的：库所中的托肯代表同一种类的物质资源。 如果把作用相似但是不同种类的资源用一个库所表示，那么库所中的托肯就 应该有“个性”，以体现它所属的种类。这样得到的网系统称为个性托肯系统( n e t s y s t e m 丽mi n d i v i d u a lt o k e n s ) 。以个性托肯为特征的网系统称为高级网系统，如谓 词变迁系统【3 9 】【4 0 1 和有色网系统【4 1 1 1 4 2 ，其中s 元和r 元都是由p 厂r 系统中的若干s 元和丁元合并而来的，因而较p t 系统的s 元和丁元更加抽象。 表2 1 网系统的分类特征 s 元 类别实例 名称特征 e n 系统 条件 代表同一个体状态e n 系统 代表无个性的同类 p t 系统库所p t 系统 资源 代表作用及状态类有色网系统 高级网系统谓词 似的不同类资源 p r t 系统 2 4p e t r i 网基本分析技术 基于p e t r i 网的分析方法可以分为可达标识集、覆盖树和覆盖图、出现序列和 变迁序列、进程和不变量等。 江苏大学硕士学位论文 2 4 1 覆盖树和覆盖图 从初始标识眠开始，能够到达p e t r i 网所有可能的标识，这些标识通过变迁 而关联。将所有标识以及产生这些标识的变迁用一个图形表示，图中的节点为标 识，节点之间用标识用代表变迁的带箭头的线或弧连接，带箭头的线起端的标识 通过由该线代表的变迁激发，产生该线末端所连接的标识，这样的图称为可达图 ( 或覆盖树) 。 设m 和m 为p t 系统基网( s ，t ；f ) 上的两个标识。若v s s ： m ( s ) m ( s ) ，就说m 被m 覆盖，记做m m 。 覆盖树的算法流程如下所示： 步骤一：首先，把初始标识坛成为树根，并加上“+ ”标记表示该节点尚未扩 展； 步骤二：如果存在着含有标记“+ ，的节点，则转步骤三，否则终止； 步骤三：选择任一含有标记“+ ”的标识m ； ( 1 ) 若m 与当前覆盖树中的已有的其它标识相同，则将起标记为“一”，然后转 向其它含有“+ ”的节点标识； ( 2 ) 若在m 下无变迁具有发生权，则将m 标记为“d e a d ； ( 3 ) 触发r ，产生标识m ； ( 4 ) 若在树根至m 的路径上存在一个标识m ”，使得m m ”，即m 覆盖 m ”，对于那些使m l ( s ) m ”( s ) 成立的s ：用代替m ( s ) ； ( 5 ) 把m 的标记从“+ ”改为“一”； 覆盖树有如下明显的不足之处：首先如果在节点x 的标识以下，变t 1 年 f l t 2 都有发生权，那么根据算法x 会有两个子节点分别与和乞对应，而不区分t lt 2 是冲突还是并发。其次，死标识和活标识不能很明显地区分开来，有限序列和无 限序列也不能从覆盖树的结构上看出来，为了解决第二个问题，可以把覆盖树转 化为覆盖图。 如果存在着覆盖树r ( z ) 到g 的映射h ：丁( ) j g ，使得： 1 2 江苏大学硕士学位论文 ( 1 ) x 为丁( ) 的节点，则h ( x ) 为g 的节点，且j 1 2 ( x ) 以x 在丁( ) 中的标记坂为 标记。 ( 2 ) ( x ，y ) 为丁( z ) 上以变迁，为标记的有向弧，则( i ，7 i ) 为g 上以，为标记的 有向弧。 ( 3 ) x y 为丁( ) 的不