（计算机软件与理论专业论文）一类时间不确定性问题的处理.pdf

内容摘要 郑州大学硕士学位论文 内容摘要 时间知识具有一定的不确定性，其表示和处理具有一定的难度。在复杂应用系 统建模过程中，由于冲突关系的普遍存在，产生了一系列与冲突事件相关的时间不 确定性问题。现有时间知识处理方法在处理与冲突事件相关的时间不确定性问题时 缺乏有效的定量分析，不能应对众多复杂应用系统建模的特定需求。 本文在现有时间不确定性问题研究的基础上，针对复杂系统形式化建模过程中 存在的、与冲突事件相关的时间不确定性问题，结合可能性理论，在扩展模糊时间 p e t r i 网中引入模糊时间区间及可能性值的运算，并构建了相应不确定时间知识的表 示方法及分析方法，在对系统进行建模的基础上进行时间知识的定量分析该方法 用模糊时间区间来表示不确定时间知识，通过模糊时间函数的计算来实施不确定时 间知识的推理，基于可能性理论定量分析冲突事件中时间的不确定性。在此基础上 针对一个铁路智能交通系统的列车群运行实例进行建模分析，验证了方法的有效性， 并与已有的基于p e 仃i 网的不确定时间知识推理算法进行对比分析。对比结果表明该 方法能够处理冲突事件中的时间不确定性问题，克服了现有方法存在的缺陷，其相 对于已有的方法具有冲突分析定量、计算容易、推理过程简单的特点。 本文描述的扩展模糊时间l e t r i 网及相应的时间知识推理方法能够定量分析处 理复杂系统中与冲突事件相关的时间不确定性问题。不仅能够对列车群运行和调整 进行研究，还适用于其它交通种类、通信、网络、工矿机器控制等领域。 关键字：不确定性，时间知识，冲突，p e t r i 网，可能性，铁路智能交通系统 内容摘要 郑州大学硕士学位论文 a b s t r a c t t h et e m p o r a lk n o w l e d g ei so fc e r t a i nu n c e r t a i n t y , m a k i n gi t s e x p r e s s i o na n d p r o c e s s i n gh a sc e r t a i nd i f f i c u l t y b e c a u s eo ft h eu n i v e r s a le x i s t e n c eo fc o n f l i c tr e l a t i o n s ， as e r i e so ft e m p o r a lu n c e r t a i n t yp r o b l e m sa s s o c i a t e dw i t hc o n f l i c te v e n t sa r i s ei nt h e c o m p l i c a t e da p p l i c a t i o ns y s t e mm o d e l i n gp r o c e s s h o w e v e gt h ee x i s t i n gm e t h o d so f t e m p o r a lk n o w l e d g ep r o c e s s i n ga r en o tc a p a b l eo fh a n d l i n gq u a n t i t a t i v et e m p o r a l u n c e r t a i n t i e si nc o n f l i c ta n d , t h e r e f o r e c 柚n o td e a lw i t ht h es p e c i f i cn e e d si nv a r i o u s c o m p l i c a t e da p p l i c a t i o ns y s t e mm o d e l i n g o nt h eb a s i so fe x i s t i n gs m d i e so nt e m p o r a lu n c e r t a i n t y , t h i sp a p e r g i v e sp r o m i n e n c e t ot e m p o r a lu n c e r t a i n t ya s s o c i a t e dw i t hc o n f l i c te v e n t se x i s t si nc o m p l i c a t e ds y s t e m m o d e l i n g c o m b i n i n gw i t hp o s s i b i l i t yt h e o r y , w ep r o p o s e a nu n c e r t a i nt e m p o r a l k n o w l e d g ee x p r e s s i o na n da n a l y s i sm e t h o db yi n t r o d u c i n gf u z z yt i m ei n t e r v a la n d c o m p u t a t i o no fp o s s i b i l i t yt od oq u a n t i t a t i v ea n a l y s i sf o rt e m p o r a lu n c e r t a i n t yb a s e do n s y s t e mm o d e l i n g t h em e t h o dr e p r e s e n t st h eu n c e r t a i nt e m p o r a lk n o w l e d g ew i t hf u z z y t i m ei n t e r v a l ，i m p l e m e n t st h er e a s o n i n gt h r o u g hc o m p u t a t i o no ff u z z yt i m ef u n c t i o n s ，a n d a n a l y z e sq u a n t i t a t i v e l yt e m p o r a lu n c e r t a i n l yi nc o n f l i c te v e n t sb a s e do np o s s i b i l i t yt h e o r y at r a i ng r o u po p e r a t i o ni n s t a n c ei nr 1 t ss h o w st h a tt h em e t h o dc a l le f f e c t i v e l ya n a l y z e t h et e m p o r a lu n c e r t a i n t yi nt r a i ng r o u po p e r a t i o na n da d j u s t m e n ta n dc a p a b l eo fd e a l i n g 稍t ht e m p o r a lu n c e r t a i n t ya s s o c i a t e dw i t hc o n f l i c te v e n t s ，a n dt h e r e f o r e ，o v e r c o m et h e s h o r t c o m i n g so fe x i s t i n gm e t h o d s c o m p a r e dw i t he x i s t i n gm e t h o d s ，t h i sm e t h o dh a s 8 0 m eo u t s t a n d i n gc h a r a c t e r i s t i c ss u c ha s q u a n t i t a t i v ea n a l y s i s f o rc o n f l i c t , e a s yt o c a l c u l a t ea n d s i m p l er e a s o n i n gp r o c e s s t h ee x t e n d e df u z z y - t i m i n gp e t r in e td e s c r i b e di nt h i sp a p e ra n dt h ec o r r e s p o n d i n g r e a s o n i n gm e t h o dc a l ld e a lw i t hq u a n t i t a t i v e l yt h et e m p o r a lu n c e r t a i n t ya s s o c i a t e dw i t h c o n f l i c te v e n t si nc o m p l i c a t e ds y s t e m i tc a nb eu s e dt os t u d yn o to n l yt r a i ng r o u p o p e r a t i o na n da d j u s t m e n tb u ta l s oo t h e rt r a n s p o r ts y s t e m , c o m m u n i c a t i o n ，n e t w o r k , i n d u s t r ya n dm i n i n gm a c h i n ec o n t r o la n ds oo n k e y w o r d s ：u n c e r t a i n t y , t e m p o r a lk n o w l e d g e c o n f l i c t , p c 仃in e t , p o s s i b i l i t y , r i t s 第一章绪论 郑州大学硕士学位论文 第一章绪论 客观世界中的绝大部分现象都是不确定的，随着不确定性研究的深入，世界的 不确定性特征越来越得到学术界的普遍认可。时间知识具有一定的不确定性。不确 定时间知识的合理表示和处理是众多应用系统的关键问题。由于冲突现象的普遍存 在，有效定量分析冲突事件中的各种时间不确定性问题，对于各研究领域中多路径 选择等与冲突相关的时间不确定性问题的分析处理具有重要意义。本文在现有时间 不确定性问题研究的基础上，结合可能性理论，在扩展模糊时间p e t r i 网中引入模糊 时间区间及可能性值的运算，来表示和处理复杂系统形式化建模过程存在的、与冲 突事件相关的时间不确定性问题。 本章主要介绍基于p e t r i 网进行时间知识推理的研究背景与现状、本文的研究内 容及组织结构。 1 1 研究背景与现状 时间知识具有定的不确定性，在许多应用系统中起着重要作用，如智能交通， 电子商务，网络协议等模型的分析。如何恰当合理的表示这种不确定的时间知识是 众多应用系统的关键问脚m 7 】。 p e t f i 网自1 9 6 2 年由德国的c ap c t r i 提出以来，经历四十多年的发展，已经形 成了较为坚实的理论基础，并形成多种类型的应用体系。p e t r i 网2 1 l 易于描述系统 的并发、竞争、同步等特征，基于p e 耐网模型进行分析可以得到许多有关结构和动 态行为的重要信息，由此进行系统评价和改进。 p e t r i 网能够清楚地描述时间之间的因果相关性和不相关性，相互独立的事件不 会被放在一个线性的时间段里。因此，基于p e t r i 网模型分析系统时间问题是解决时 间不确定性问题的条有效途径。目前已有的基于p e t r l 网的推理方法有：在p e t r i 网中引入线性逻辑的推理，基于可达树的推理，等价矩阵方法，演绎或分解技术等。 现有的时间知识表示方法大多采用单时间点或时间区间，与p e t r i 网理论相结合已 经构建了多种时间p e t r i 网模型 2 2 - 3 1 1 。基于p c t r i 网进行不确定时间知识的处理是p e t r i 网建模研究领域的热点问题之一【1 9 1 。 第一章绪论 郑州大学硕士学位论文 文献【1 5 】提出了一种统一的时间p e t f i 网模型，能够将时间信息的定性和定量处 理结合起来。文献【1 6 】指出该模型在检测时间知识的一致性时存在缺陷。文献【1 4 】 提出了一种用时间p e t r i 网描述状态和时间之间联系的方法来进行时间知识表示和 推理，并给出了一个算法以检测时间知识的一致性。该方法可以避免文献 1 5 1 中存 在的问题，但是对时间知识采用时间区间的表示方法使得对时间的定量分析仍然不 够充分，不能表达区间内时间属性的变化趋势，不适于表示不确定时间知识，无法 进行定量的推理和验证，算法适用面较窄。 为了解决实时系统中的时间不确定性问题，m u r a t a l l 坞l 入模糊集合论表示不确 定的或主观的时间信息，在高级p e t r i 网中引入模糊时间，提出了带有四个模糊时间 函数的模糊时间高级p c 仃i 网( f r h n ，s ) 。模糊时间函数的计算涉及两个重要的运算： e a r l i e s t 和l a t e s t ，文献【2 】给出了执行这两个运算的具体算法。文献f 1 3 】在f 1 4 】的基础 上引入模糊时间区间的操作，并将算法应用于铁路智能运输系统中列车运行时间知 识的分析推理和验证。文献 1 0 ，1 1 】引入【1 】提出的模糊时间函数定义了模糊时间p a d 网( f 1 1 p n ) ，将时间区问扩展为用四元组形式表示的模糊时间区间，随着初始标识 库所中托肯的移动来计算模糊时间函数进行时间知识推理。该方法改进了时间知识 推理过程中对不确定时间的表示，简化了时间知识推理过程，但在事件发生冲突时 对路径的选择缺乏定量分析。 文献【6 ，7 】结合模糊时间p e w i 网( f r n ) 和m e r l i n 的时间p e t r i 网1 3 0 1 扩展了f i n ， 提出了扩展模糊时间p e t r i 网( e f i ：n ) 及可能性值的运算。一个扩展模糊时间p e t r i 网是一个模糊延迟默认为【o ，o ，o o 】的f r n ，其中的每一个变迁与一个带有可能性值 的触发时间区间关联触发时间区间的引入赋予冲突变迁不同的触发可能性和优先 级，有利于在实时系统建模中更加充分地描述不确定时间因素和属性。文献【1 2 1 在 e f t n 中引入模糊时间区间来表示与变迁关联的触发时间区间，提出一种基于 e f t p n 的不确定时间知识推理和验证方法，适用于解决复杂系统不确定时间知识的 推理和验证问题。但是文献 1 2 1 仍然采用 1 4 1 提出的时间知识推理算法，需要通过 搜索系统状态构建复杂的系统状态生成图来进行不确定时间知识的推理分析。 在我们的社会生活中。冲突作为一种普遍现象而广泛存在。冲突是一种对立状 态，产生予系统中各方所追求目标的对立性。多个实体在有限资源下进行合作时， 2 第一章绪论郑州大学硕士学位论文 均会产生冲突。作为不确定性的一种，冲突意味着选择的不确定性。在公共交通中 乘客的出行路径选择、驾驶员路径选择、交通分配、通信网络中的路径选择、口网 络中的o o s 路径选择以及列车运行计划调整过程中，都普遍存在着多条可选路径构 成的冲突。针对冲突事件进行各种时间不确定性分析，对于各研究领域中与冲突相 关的时间不确定性问题，如多路径选择的分析处理具有重要意义。而现有时间知识 处理方法在处理与冲突事件相关的时间不确定性问题时缺乏有效的定量分析，不能 应对众多复杂应用系统建模的特定需求 综上所述。目前基于p e t r i 网的时间知识推理方法研究主要集中在以下几个方 面： ( 1 ) 不确定时间知识的表示。用单一时间点、时间区间、模糊时间函数或模糊 时间区间表示不确定时间知识不同的表示方式对时间知识的描述精度不同。采用 单一的时间点表示既不实际也不完整，而常用的时间区间的表示也缺少定量的分析。 ( 2 ) 时间知识的推理过程。时间知识的线性推理不易编程实现。已有的基于时 间p c 仃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 c 圩i 网、模糊时间高级p e t r i 网、模糊时间p e t r i 网等。 1 2 本文工作概述 本文旨在针对冲突事件中不确定时间知识的推理分析定义一种新的扩展模糊时 间p e 圩i 网并提出相应的不确定时间知识表示和推理方法。 在复杂应用系统建模过程中，资源共享导致各种冲突事件、冲突关系不可避免。 有些冲突可以通过各种方式消除，而有些冲突无法消除或被特意保留以方便对系统 旋加外部决策力量。科学有效地描述、分析冲突关系中涉及的不确定时闯知识，将 有助于冲突的合理解决或有效利用。 现有的时间知识推理方法不能定量处理冲突关系中的时间不确定性。本文以现 3 第一章绪论帮卅大学硕士学位论文 有时间不确定性问题研究成果为基础【“x 6 1 ，结合可能性理论p 纠1 1 提出一种新的扩展 模糊时间p e t r i 网定义及相应的不确定时间知识表示和推理方法，来定量分析复杂系 统形式化建模过程存在的、与冲突事件相关的时间不确定性问题。该方法能定量描 述使能变迁触发的不确定性，适用于复杂系统中冲突事件的建模分析；结合可能性 值的计算实现了不确定时间知识的定量分析：能定量分析冲突变迁且效率更高，克 服了现有方法存在的缺陷。 随着列车群运行速度的提高，以及一系列客观不确定性因素的影响，列车运行 中与时间参数相关的不确定性问题的处理就显得日益突出7 1 ，其中列车运行的时 间不确定问题的分析，对列车运行过程中的动态控制、对站内的列车调度、对乘客 的换乘、列车的货物中转、铁路系统的资源分配等问题的处理都有很现实的意义。 本文通过一个r i t s 的列车群运行实例验证了方法的有效性，表明该方法能够针对 冲突事件定量分析列车运行和调整过程中的时间不确定性问题，从而为合理制定行 车计划提供科学依据。其相对于已有的方法具有冲突分析定量、计算容易、推理过 程简单的特点，可以应用于智能交通、计算机的通讯控制、区域性供电网的调度和 监控等。 本文具体工作概述如下： ( 1 )引入模糊时间区间及模糊时间函数，提出改进后的扩展模糊时间p e t r i 网的形式化定义，适用于冲突事件建模分析。 ( 2 )给变迁关联模糊触发区间来定量描述变迁的时间知识。模糊触发区间能 定量描述使能变迁触发的不确定，赋予冲突变迁不同的触发可能性即使用 资源的优先级 ( 3 )根据新的扩展模糊时间p e t r i 网系统重新定义相关模糊时间函数的计算 公式，通过模糊时间函数的计算模拟网状态的更迭，实现不确定时间知识 的推理。 ( 4 )针对不确定时间知识，基于可能性理论，定量分析冲突关系中的各种可 能性问题。 ( 5 )通过定量分析列车群运行实例中的时间不确定性问题验证本文方法的 有效性，并与现有时问知识推理算法进行对比分析。 4 第一章绪论 郑州大学硕士学位论文 本文的扩展模糊时间p e t r i 网能够有效描述和推理一类复杂系统在形式化建模 过程中存在的、尤其是与冲突事件相关的不确定时间知识，能够进行各种可能性问 题的定量分析针对冲突关系研究不确定时间知识的推理，对时间不确定性问题进 行定量分析，不仅为列车群运行调整新方法的研究提出了一个方向，适应铁路智能 运输系统发展的要求，同时丰富了知识工程中其它领域专家系统的研究。 1 3 本文内容与结构 本文以现有时间不确定性问题研究成果为基础，结合可能性理论提出一种新的 基于e f t n 的不确定时间知识表示和推理方法，来定量分析复杂系统形式化建模过 程存在的、与冲突事件相关的时间不确定性问题。应用实例表明该方法能定量描述 使能变迁触发的不确定性，适用于复杂系统中冲突事件的建模分析。 本文内容组织结构如下： 第一章：绪论。 介绍本文的研究背景与现状、研究内容以及本文的组织结构。 第二章：相关知识介绍。 这一章主要介绍本文涉及到的相关理论。包括不确定信息的处理方法、p e t r l 网 基本理论。其中2 1 节介绍了不确定性的基本含义、处理不确定知识的常用理论与 方法，重点介绍了可能性理论方法；2 2 节介绍了时间知识的表示方法，包括时间区 间和模糊时间区间；2 3 节介绍了几个基于模糊时间区间计算可能性值的公式；2 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 网处理不确定时间知识的基本思想，并针对冲突关系进 行不确定时间知识的推理分析。 5 第一章绪论 郑州大学硕士学位论文 第五章，基于r r r s 列车群运行实例的多种方法对比分析。 本章首先给出一个基于r r r s 的列车群运行实例，然后用本文方法及现有的基 于p e t r i 网的不确定时间知识推理方法针对该实例进行不确定时间知识的推理分析， 并将不同方法的分析结果进行对比分析。 第六章，总结与展望 本章对本文工作进行总结，并展望未来工作。 6 第二章相关知识介绍 郑州大学硕士学位论文 第二章相关知识介绍 不确定性问题的研究工作受到越来越多的关注。可能性理论是处理不确定信息 的一种方法，模糊集合论的发展使得该理论具有较完善的理论基础，已经在实际专 家系统和推理系统中得到应用不确定时间知识的表示有多种方法。将不确定时间 知识用模糊时间区间表示，可以定量分析两个不确定时间之间各种关系存在的可能 性。由于p e t r i 网能够清楚地描述时间之间的因果相关性和不相关性，基于p e t r i 网 模型分析系统时间问题是解决时间不确定性问题的一条有效途径。 本章主要介绍本文工作涉及到的一些相关理论。包括不确定信息的处理方法、 时间知识的表示，基于模糊时间区间的可能性计算方法以及p e t r i 网基本理论。其中 2 1 节介绍了不确定性的基本含义、处理不确定知识的常用理论与方法，重点介绍了 可能性理论方法；2 2 节介绍了时间知识的表示方法，包括时间区间和模糊时间区间； 2 3 节介绍了几个基于模糊时间区问计算可能性值的公式；2 4 节介绍了基本p e t r i 网理论。 2 1 不确定信息及其处理 客观世界中的绝大部分现象都是不确定的。客观世界的不确定性，决定了人类 主观认知过程的不确定性以及人类记忆、思维、自然语言的不确定性。随机性和模 糊性是不确定性的最基本内涵。不确定性人工智能是人工智能中的研究热点，也是 人工智能中的重大前沿课题 4 s , 4 9 1 。 人们目前所说的不确定性信息可分为四类，分别是由于发生条件提供的不充分 或偶然因素的干扰所产生的随机不确定性；因信息的外延模糊导致的模糊不确定性； 信息部分已知部分未知所导致的灰色不确定性和由于决策者在主观上的、认识上的 不足所产生的未确知不确定性。针对不同类型的不确定性信息，人们提出了主观 b a y e s 方法、确定性理论、可能性理论和证据理论等传统方法，以及灰色系统理论、 粗集理论、概念图、基于信比概念的知识处理和集对分析等新方法。 知识的模糊性是由模糊性信息引起的，其外延不清晰，描述的是亦此亦彼的现 象。1 9 6 5 年z a d e h 提出了处理模糊信息的模糊集合论。1 9 7 8 年z a d e h 将模糊集合论 7 第二章相关知识介绍 郑州大学硕士学位论文 应用于专家系统中处理不确定性知识，提出了可能性理论方法1 3 2 】。 在可能性理论中主要利用模糊变换进行知识的处理，常用的方法有模糊综合评 判和模糊推理。可能性理论具有较完善的理论基础，经由d u b o i sd 、p r a d eh 等人 的发展f 枷】，已经在专家系统和推理系统中得到应用。 可能性理论的基本思想是要确定可能性、可能性分布、可能性分布函数、条件 可能性分布函数、边缘可能性分布函数等几个度量和它们之间的关系，以及各种模 糊命题的转换规则和不精确命题的推理规则等等。 设a 是论域ok 的模糊集合，它对应的隶属函数为砌r 耐。如果a 表示变量y 取 值的范围，4 就是变量y 的一个模糊限制，隶属函数砌f 叫表示把赋给变量l ，时 满足限制a 的程度。 z a d e h 把可能性分布定义为在变量的给定值上有弹性的模糊限制。设变量y 在 论域口中取值，a 是- o k 的模糊集合，它的隶属函数为砌。若a 是y 取值的模糊限 制r ，即r - - - - a ，则命题“l r 是a ”规定了变量y 的个可能性分布肠一尉矽。 y 的可能性分布函数朋可相应地定义为p y = 砌。 上述定义将可能性理论与模糊集合论联系起来。即元素对a 的隶属度纵f 叫 代表命题“1 ，是彳”成立的可能性程度。 本文所引入的模糊时间函数是根据可能性理论来表示和计算时间的不确定性 的。这里给出一种模糊时间函数涉及的可能性分布定义：令y 是一个在x 中取值的 变量，那么与y 有关的可能性分布用尼，黔【o ，1 】来表示。 具体的模糊时间函数的定义及计算在3 2 小节中给出。 2 2 时间知识的表示 人工智能的研究领域中，常识知识的表示具有一定的重要性，但常识知识的形 式化描述也有一定的困难。例如，自然语言理解，空间的表示和推理，物理过程和 事件的形式化描述，以及时间知识的表示等等 时闯的描述本身具有不确定性，其表示具有一定的难度，如何恰当合理表示这 种不确定的时间知识是众多应用系统的关键问题p 埘，也是知识表示领域研究的热 点【3 l - 3 3 1 。一般来说，事件、过程或者计算都发生在时间里，系统中首先需要一个全 8 幕二章相关知识介绍 郑州大学硕士学位论文 局时间作为系统参数，时间知识表示方法或者将时间作为事件或过程的“容器”，即 作为一个区间，或者将时间作为事件或过程的一种属性，即标记为一种属性的度量 值。 时间不确定性在本质上可区分为不精确性( i m p r e c i s i o n ) 和模糊性 ( u n c e r t a i n t y ) 3 2 1 。现有的时间知识表示采用的方法有时间点和时间区间，= 者都存在 一定的局限性。采用单一的时间点来表示应用系统的时间知识，不能表达出时间知 识的不确定性，既不实际也不完整；采用时间区间表示方法，对时间的不确定性缺 乏定量的分析。 在时间p e t r i 网【1 3 1 4 1 中，每个变迁都关联一个时间区间弘6 】，且4 6 ，其中： ( 1 ) a ( 0 口) 是最早触发时间，是变迁从使能到触发所必须经历的最短时间； ( 2 ) b ( 0 厶哆是最晚触发时间，是变迁从使能到触发可能经历的最长时间。 当一个变迁触发所需的所有托肯在时问孔都到达，即变迁处于使能状态时，变 迁并不立即触发，而是经过时间a 在时间区间 t o + a ，+ 6 】内触发。 文献f 3 2 】基于可能性理论，将不精确性和模糊性进行统一，采用时间轴上的梯 形模糊时间区间来表示不确定时间( 包括时间点和时间段) 。一个模糊时间区间是一 个四元组形式的梯形可能性分布，如图2 所示。 l 图2 。1 模糊时间区闻 对于图2 1 中的模糊时间区间b6 jg 明，可以简单认为【6 ，c 1 表示系统的正常运 行时间区间，区间b6 】和瞳川表示系统有可能正常运行的时间段，在模糊区间以外 时间系统一定不能运行。时间区间【4 ，田是模糊时间区间的特例，可以认为a = b ，c - - - d ， 从而等同于模糊时间区间【4 ，4 ，4 引。模糊时间区间进一步细分时问区间的不同时 段，增强了不确定时间知识的描述和处理能力。 9 第二章相关知识介绍郑州大学硕 + 学位论文 本文在扩展模糊时间p e t r i 网的定义中用模糊时间区间来表示变迁的模糊触发 区间。 2 3 可能性计算方法 文献 2 提出了模糊时态逻辑( f u z z ym e t r i ct e m p o r a ll o g i c ，f m t l ) 及一个 计算方法，该方法可以计算一个f m t l 公式满足一个给定的f t n 变迁触发序列的可能 性。 给定两个可能性分布e 、厶z 。、刀，分别为其隶属度函数，图4 2 中梯形区域 a b c d 为万。，梯形区域g h l m 为万，。关系p ，表示p 在，之前发生，e ，则表示p 在，之后发生，e = f 表示e 、，同时发生。对于这些关系成立的可能性有下面的运 算公式： 胁批y 峪舻等糕 亿。 其中， 后闩= e + 一) n ( 一o 。，用，在图2 2 ( a ) 中为a b l m 部分， 历月nj r ， 是a b c d 部分。 胁蜘呛伊等鬈 ， 其中， 只明= 只+ 一) n ( 一。o ，胡，在图2 2 ( b ) 中为g h c d 部分， 只朗nj r ， 也是g h c d 部分。 i b i l i ty p o s s i b i l i t 忙俨乞篆孚， ( p = 厂) = _ 二旦 ( 2 3 当f 是精确值时，卢 ，7 ，f 7 ，7 ，7 ； possibility(p厂)：area(the p a r tofz,wherer f ) a r e a 【石。) p o s s i b i l i t y ( e = ，) fh 。，当p 是一个精确值时，石，= h e ( e 矗岛口) 10 ，其它。( 当p 是一个模糊值时) 。 ( 2 4 ) ( 2 5 ) ( 2 6 ) l o 第二章相关知识介绍 郑州大学硕l 学位论文 如图2 2 ( c ) 所示：j r 。中f ，的部分为a b g h ，r ，的部分为h g c d 。 2 4p e t r i 网理论 0 o 0 ( a ) ( b ) ( c ) 幽2 2 可能性值的计算 p e t r i 网是一种以图形形式研究系统组织结构和动态特性的理论，具有严密的数 学基础和多种分析手段1 2 0 1 。p e t r i 网理论既有直观的图形表示方式又有严格的数学理 论基础和分析方法，支持系统模型各种性质的分析和性能的评价，能够肘具有并行 第二章相关知识介绍郑州大学硕士学位论文 ( p a r a l l e l i s m ) 、并发( c o n c u r r e n c y ) 、同步( s y n c h r o n i z a t i o n ) 、资源共享( r e s o u r c es h a i i n g ) 等特性的系统建立模型。p e t r i 网广泛应用于软件体系结构、软件工程、知识表达与 推理、并行计算、网络通信协议、柔性制造系统的建模、分析、控制领域。基于p c m 网模型进行分析可以得到许多有关结构和动态行为的重要信息，由此进行评价和改 进系统。 p e t r i 网的基本性质主要体现在可达性、有界性、安全性和活性等方面，这些性 质充分体现了系统性能、结构和行为之间的对应关系i 冽。 p c t r i 网的分析技术包括可达性分析、不变量分析、保持特性的变换( 包括化简) 、 构造理论、形式语言理论、同步距离以及网的分解和等价。使用这些分析方法可以 刻画系统的结构，展现系统的运行机制，表示和分析系统的动态行为，降低系统分 析的复杂度。 p e t r i 网的主要结构特性例包括有界性、守恒性、可重复性、协调性、p 不变量、 t 不变量、可重复向量、死锁与陷阱等。可用关联矩阵表示p e t r i 网的结构特性，通 过关联矩阵的判定准则，得到结构性质比较完整的分析结果，而这些结果又是用代 数方法分析p e 硒网的基础【2 1 1 。 p e t r i 网理论在包括硬件、软件和社会领域等许多领域中都得到了广泛的应用 隆埘，已经大量地应用于各种系统的建模，如计算机的通讯控制、铁路系统的实时 指挥和监控、城市交通系统的实时指挥和监控、区域性供电网的调度和监控等。 p e t d 网的局限性在于其托肯缺乏表示信息内容的能力，缺乏描述选择使能变迁 的策略等。为弥补这些局限以适应特定系统建模需求，人们对基本p e t r i 网进行了不 同形式的扩展。包括对托肯赋予一定的信息，制定使能变迁的触发策略，将时间概 念引入p e t r i 网等。 下面给出p e t r i 网的基本定义以及引入了时间因素的时间p e t r i 网的定义【1 4 1 。 定义2 1p e 仃i 网( p n ) p n 是一个三元组，即p n = ( p 正爿) ，其中相应符号的含义为： ( 1 ) p = p 1 ，p 2 , ，办 为有限的库所集： ( 2 ) t - f l ，2 ，) 为有限的变迁集； ( 3 ) p n t = ( 集合p 和集合r 不相交) ，p u t ( 集合p 和集合r 不同 第二章相关知识介绍 郑州大学硕士学位论文 时为空) ； ( 4 ) a ( 尸r ) u ( t p ) 是有限的弧的集合( 流关系仅存在元素p 和r 之 间) ； 定义2 2 普通p e t r i 网系统 一个带标记的普通p e t r i 网系统是六元组三= 僻写4 彤k 肘曲，其中： ( 1 ) ( p ，r a ) 是一个网； ( 2 ) 茁：p 一 1 ，2 3 是库所容量函数； ( 3 ) 阢，呻 l ，2 ，3 ) 是弧权函数； ( 4 ) 朋i ：p 一 0 ，1 ，2 3 ) 是初始标识，满足：吻p ：m o ( p ) k ( p ) 。 定义2 3 时间p e t r i 网系统( t p n s ) t p n s = s 层曰霉p r e , p o s t , 口，夕，t d , m o ) 其中。 ( 1 ) s = j l ，s 2 ，& ) ，有限的状态集； c 2 ) e = e 1 ，e 2 , ，) ，有限的事件集； ( 3 ) p = p 1 p 2 , ，胁 ，有限的库所集； ( 4 ) t - - t l ，t 2 , ，) ，有限的变迁集，并满足于p u 降正无p n 强现 ( 5 ) 前相关函数 r e ：，丁。，n 是非负整数集合； ( 6 ) 后相关函数p o s t ：p x t n ； ( 7 ) a ：尸岛库所到状态的对一的映射函数，假设网中最多只有一个托肯， 则每个库所关联一个状态； ( 8 ) 鼻：e l 事件到变迁的一对一的映射函数，表示每个事件关联一个变迁； ( 9 ) t d 是一个静态时间区间映射函数，表示一个变迁关联一个时间区间； ( 1 0 ) 初始标识函数m o ：p - - n 。 第三章一种扩展模糊时同 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 网中托肯移 动及网状态更新的过程。 3 1 带有模糊触发区间的e f t n 的定义 扩展模糊时间p e t r i 网( e x t e n d e df u z z y - t r m i n gp e t r in e t ，e f t n ) 由模糊时间 p e t r i 网( f t n ) t 1 】扩展而来。一个扩展模糊时间p e t r i 网模型是一个默认延迟为【o ，0 , 0 ，0 】 的模糊时间p e 仃i 网，其每个变迁都关联一个带有可能性值p 的、形如p 【4 ，6 】的时间 区间i 鲫 为了更加精确地表示和分析与变迁相关的时间不确定性，我们将该时间区间扩 展为形如p 陋，五，c ，司的模糊时间区间【3 2 】，称为变迁的模糊触发区间 定义3 1 模糊触发区间( f u z z yf i r i n gi n t e r v a l ) 变迁的模糊触发区间h i a ，玩c ，明是一个模糊时间区间，用于表示变迁使能后触 发的时间限制。当变迁使能后，在时间区间p ，c 】内变迁触发的可能性为h ，在时间 区间k ，6 】和【c ，明内变迁触发的可能性小于h ，但在时间区间陋，明之外变迁不可能触 发。 如果变迁不与其它任何变迁发生冲突，那么h = l ，否则， 可以是( 0 ，1 ) 之间的 任意实数。如果有多个变迁构成结构冲突，可以根据需要令它们的模糊触发区间带 有不同的的小于1 的h 值，从而赋予各个变迁不同的触发机会。 给变迁关联带有可能性值的模糊触发区间使得冲突中的变迁具有不同的触发可 能性和优先级，有利于实时系统建模。同时，模糊触发区间相对二元组形式的时间 区间具有更强的描述能力，配合模糊时间函数的计算能够更加精确地对不确定时间 知识进行定量表示和处理。 1 4 第三章一种扩展模糊时阃p e t r i 同郑卅i 大学硕士学位论文 定义3 2 扩展模糊时间p e t r i 网系统( e n n ，s ) 一个扩展模糊时间p e 打i 网系统( e f t n s ) 是一个普通网，可用7 元组表示： e f t n s = 仞写4 口c 写明m o ，其中： 尸；是有限库所集，p = p 1 ，p 2 ，p 。) ； 乃是有限变迁集，拈 f 1 ，f 2 ，f ，满足：p u z 妒，p n 强妒； a ：是弧的集合，x c ( e x l ) u ( r x d ； d ：是模糊延迟的集合，与变迁输出弧关联； c t ：是从变迁集t 到模糊触发区间的映射函数，c t ：t 一| l p ，b ，c ，司，满足： 0 h 1 ，o 4 厶c d ； 豫是模糊时间片集合。一个模糊时间片与库所中的托肯相关。模糊时间片【o ，0 ， o 0 】表示与之关联的托肯不受时间约束： a o 是初始标识函数， 知：p - - f t 。 说明l ： 对于同一变迁，其不同输出弧的模糊延迟可能不同，在实时系统建模中可用于 表示同一事件发生后对不同后续对象产生的不同影响。 说明2 ： 系统的标识埘：p 一刀用于表示系统的状态，是对系统动态行为的描述。系统 的每一个状态对应于库所的一个标识向量。本文用托肯的集合表示系统标识，z z p ， 玎( r ) ) p p 万( r ) 册。当前没有携带托肯的库所不出现在集合中在初始标识 中携带托肯的库所称为初始标识库所。 3 2 模糊时间函数及其计算 针对不确定时间知识的处理，m u r a t a 提出了四个模糊时间函数( f h z z yt i m e f u n c t i o n ) ：模糊时间片、模糊使能时间、模糊发生时间和模糊延迟【。 一个模糊时间函数即一个可能性分布是一个从时间刻度r ( 非负实数集) 到实 数区间【o ，1 】的函数。函数值表示事件在时间点t 上呈现可能性的度量。模糊时间函 数用四元组形式给出，如p q ) = h f 4 ，b ，c ，明，矗表示可能性度量，当 = 鼍时可省略。 第三章一种扩展模糊时间p t a r i 网郑州大学硕士学位论文 模糊时间函数的图形表示是梯形或三角形，和p e t r i 网模型中托肯到达库所的最早时 问、最可能时间和最晚时间相对应。当b = c 时该模糊时问函数即为三角形分布【4 ，b ， b ，田 模糊时间函数的基本思想在许多文章或应用中均有体现 s o l ，其完整定义由 m u r a t a 等人完成1 1 , 2 1 。 由于我们为变迁关联了模糊触发区问，模糊时间函数的计算及网状态的更新过 程也需进行相应调整下面介绍模糊时间函数的定义，以及引入模糊触发区间后模 糊时间函数的计算方法。 定义3 3 模糊时间片p o ) 咖z 巧t i m e s t a m p ) 模糊时间片p o ) 与库所中的托肯相关，表示托肯在时间t 到达某一库所的可能 性分布。例如p ( t ) = 【4 ，b ，c ，田，其梯形图如图2 1 所示，表示在时间段p ，c 】内托肯 到达库所的可能性是1 ，而在【1 ，2 】和【3 ，4 】内托肯到达库所的可能性小于1 ，在其它时 段托肯不可能到达库所。 定义3 4 模糊使能时间p 俐( f u z z ye n a b l i n gt i m e ) 一个变迁的模糊使能时间是一个可能性分布，表示该变迁所需的所有托肯到达 其输入库所的最迟时间。如果变迁的触发只需要一个资源( 即托肯) ，则该变迁的模 糊使能时间就是该托肯的模糊时间片；当变迁的触发需要多个资源时，对这些托肯 的模糊时间片实施l a t e s t 运算得到它们的最迟时间可能性分布，就是该变迁的模糊 使能时间。假设变迁t 被n 个托肯使能，且这些托肯的模糊时间片为z r ) ，i = i ，2 ，”j 雄，变迁t 的模糊使能时间由下式计算： e ) i l ll a t e s t 筇f p ) ，f 一1 2 ，甩) ( 3 1 ) 其中l a t e s t 运算基于