（计算机软件与理论专业论文）基于混合petri网的列车运行系统中时间推理问题的研究.pdf

摘要 i i ii ii lr l li iii iii iiii y 18 3 3 8 5 3 摘要 列车运行系统( t o g ) 是铁路智能系统( r i t 8 ) 中的核心系统，也是典型的混 杂系统。如何对t o s 进行建模分析是r i t s 研究中的关键问题。由于t o s 是一 类强实时性的反应系统，其动态行为与离散事件的发生密切相关，因此，对于 系统中关键事件的时间推理也是t o s 研究的重要内容。 针对列车运行系统中关键事件发生的时间推理问题，本文基于混合p e t r i 网， 用代数系统的方法进行时间的定量分析，动态确定关键事件发生的时间区间。 该方法相对于已有的基于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 t r a i no p e r a t i n gs y s t e mi sa t y p i c a lk i n do fh y b r i ds y s t e m s ，w h i c hi st h ec o r ep a r t o fr a i l w a yi n t e l l i g e n tt r a n s p o r t a t i o ns y s t e m ( r i t s ) h o wt ob u i l dt h em o d e li st h e k e yp r o b l e mi nt h er e s e a r c ho fr i t s i ti sa l s oas t r o n g l yr e a l t i m er e a c t i v es y s t e m t h ed y n a m i cb e h a v i o ro ft h es y s t e mi s c l o s e l yr e l a t e dt od i s c r e t ee v e n t s ，a n dt h e t e m p o r a lr e a s o n i n go f k e ye x , e n t si sa ni m p o r t a n tp a r to ft h es y s t e m + t o q u a n t i t a t i v e l ya n a l y s i st h et e m p o r a lr e a s o n i n go fk e ye v e n t si nt r a i no p e r a t i o n s y s t e m ，t h ep a p e ri n t r o d u c e st h em e t h o do fa l g e b r as y s t e mi n t oh y b r i dp e t r in e t m o d e l t h i sm e t h o dc a nd y n a m i c a l l yi d e n t i f yt h et i m ei n t e r v a li nw h i c ht i m eak e y e v e n tm i g h th a p p e n c o m p a r e dw i t he x i s t i n gm e t h o d so f t e m p o r a lr e a s o n i n gi np e t r i n e t s ，t h i sm e t h o dh a ss o 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 sa c c u r a t ea n a l y s i sa b o u t t i m ei n t e r v a l ，h a n d l et h ed y n a m i cc h a n g e so f s y s t e ms t a t e ，a d a p tt or e a l t i m es y s t e m s ， a n ds u p p o r tc o n t i n u o u sc e n t r e ls y s t e m k e ye v e n t sl i k e l ya r o u s et h ep r o c e s so ft r a i n s p e e da d j u s t m e n t w ed e s i g nt w oe x p e r i m e n t sf o rv e r i f y i n gt h ea d v a n t a g eo ft h e m e t h o dw h i l et r a i n sa r et r a c k i n go t h e r s a se x p e r i m e n t a lr e s u l ts h o wt h a tt h ed y n a m i c t i m ei n t e r v a lr e f l e c tt h ei n t e r a c t i o nb e t w e e nt r a i n sr u n n i n gs t a t u sa n do t h e rc o m p l e x f a c t o r s ，w h i c hh a sag r e a ts i g n i f i c a n c ei nd e t e c t i n ga n dm o n i t o r i n gt h ee m e r g e n c i e so f t r a i n sr u n n i n gp r o c e s s t h i sp a p e rp r o p o s e sam e t h o do ft e m p o r a lr e a s o n i n gb a s e do n h y b r i dp e t r in e t s f o ra n a l y z i n gt h ep r o c e s so fk e ye v e n t sa n dm o n i t o r i n gt h er e a l t i m ec h a n g e t h e m e t h o dc a nb ee f f e c t i v e l yu s e do nr e s e a r c h i n ga s p e c t ss u c ha st r a i ns p e e d a d j u s t m e n t ， t r a i nt r a c k i n g , e m e r g e n c i e sa n ds o o n k e yw o r d s ：h y b r i dp e t r in e t ，t r a i no p e r a t i o ns y s t e m ，t e m p o r a lr e a s o n i n g ，t r a i n c o n t r o l ，。 h 目录 目录 摘要i - a b s t r a c t i i 目录i i i 1绪论1 1 1 研究背景与现状：1 1 2 本文工作概述2 1 3 本文内容与组织结构3 2 相关知识介绍5 2 1 p e t r i 网! ； 2 1 1 基本p e t d 网一5 2 1 2 混合p e t r i 网6 2 1 3 时间p e t r i 网7 2 2 时间推理9 2 2 1 基本时问推理理论二9 2 2 2 基于p e t r i 网的时间推理方法l o 2 3 本章小结12 3时间关联的列车运行系统混合p e t d 网模型l3 3 1混合p e t r i 网中时间因素的引入1 3 3 2 列车运行系统的建模15 3 3 系统运行机制的分析17 3 3 1 系统模型中的速度调整：1 8 3 3 2 系统模型中的时间推理。1 9 3 4 本章小结：= 2 0 4 系统模型的仿真实验：一2 l 4 1 列车追踪问题的仿真设计2 1 4 2 单线轨道上列车追踪运行时间推理分析2 2 i i i 目录 4 3 双线轨道上列车追踪运行时间推理分析。2 5 4 4 与其他基于p e t r i 网的时间推理方法的对比分析2 8 4 5本章小结3 0 5 总结与展望31 参考文献3 3 致谢j 3 6 个人简历、在学期间发表的学术论文与研究成果3 7 i v 1 绪论 1绪论 铁路运输是一种与国民经济密切相关的陆上交通方式。随着经济的发展， 国民经济对铁路的依赖程度越来越高。如何有效地利用有限的铁路资源，是世 乔各国都在考虑的问题，铁路智能运输系统( r a i l w a yi n t e l l i g e n tt r a n s p o r t s y s t e m r i t s ) 因而应运而生。r i t s 主要包括运输管理系统、运输自动控制、 列车控制系统、安全保障系统等部分，它解决目前铁路运输面临的来自效率方 面、安全方面和服务方面的关键难题，以获得铁路运输的持续发展【l 硼。 1 1 研究背景与现状 列车运行系统是铁路智能运输系统的核心系统，其为典型的混杂系统，由 连续变量动态系统( c v d s ) 和离散事件动态系统( d e d s ) 组成。此系统的混杂性表 现为：一方面，列车运行是一个连续的过程，其能耗、位置的变化都具有连续 性；另一方面，对列车的操作和控制、铁路信号控制、关键事件的发生等是离 散的。混杂系统是p e t r i 网建模研究领域的热点之一【“l l 】。其中，混合p e t r i 网是 对传统p e t r i 网的扩展，将库所和变迁区分为连续( c o n t i n u o u s ) 和离散( d i s c r e t e ) 两种类型，非常适用于建模和分析具有混杂特性的系统【l 1 0 7 1 。 列车运行系统同时也是交互性强的反应系统( r e a c t i v es y s t e m ) ，系统状态与 外界环境相互影响，而且系统的持续行为与瞬间行为相互作用。反应系统的实 时性要求比较高，对反应系统进行分析时需要考虑系统与环境实时交互信息而 不是只得到一个最终结果。列车运行系统、飞机控制系统以及核反应系统等都 属于典型的反应系统。时间推理的方法被广泛用来描述反应系统的行为，传统 的研究中使用离散事件方法来对反应系统建模进而进行时间推理，反应系统的 行为被描述成离散事件的发生序列【1 8 2 。但在现实世界中，只用离散事件的方 法来对各种系统建模是不完备的，譬如控制一辆快速行驶的列车就必须考虑列 车连续变化的状态与环境之间的相互作用。文献 2 2 扩展了处理离散事件的时序 逻辑框架，使得其还能处理反应系统中的连续过程，而文献 2 3 2 6 分别从计划、 时间安排、不确定性表示等方面进行了时间推理研究。 p e t r i 网能够清楚地描述时间之间的因果相关性和不相关性，基于p e t t i 网模 1 绪论 型分析系统时问问题是解决时间推理问题的一条有效途径。自1 9 7 6 年m e r l i n 提出时间p e t r i 网【2 7 】后，p e t r i 网的时间相关性问题成为研究的热点，通过单一 时间点或时间区间与p e t r i 网的变迁或库所相关联的方式，针对不同的应用领域 建立了许多不同的时间相关的p e t r i 网系统模型【捌。为了解决系统中事件发生 的随机性和时间的不确定性问题，随机p e t r i 刚2 9 1 、模糊时间p e t r i 网【3 0 】相继被 提出。 列车运行系统的混杂性和交互性使得其系统行为的描述和分析非常困难。 文献 3 1 ，3 2 将面向对象p e t r i 网方法应用于列车运行系统中，其针对列车群行为 所建的模型是典型的离散事件动态系统，其不能表示系统中的连续变量的动态 变化。文献 3 3 】将一种基于时间p e t r i 网的时间知识推理算法应用于铁路智能运 输系统，但其没有考虑系统的混杂性。文献 1 7 】建立了列车运行系统的混合p e l r i 模型，解决了连续变量和离散事件的混合描述问题，不足的是其关于离散事件 发生时间区间的分析是静态不可变的，不能处理意外事件发生、列车追踪运行 等复杂情况。文献 3 4 】定义了一种模糊时间p e t r i 网( f t p n ) 来解决列车运行 过程中的时间不确定性问题，基于模糊时间p e t f i 网构建的模型定量处理冲突关 系中的时间不确定性，从而使模型凸显了关键事件，简化了系统的建模和分析。 虽然f t p n 模型在描述离散事件上能力强，但是其在描述和分析连续变量方面较 弱。 一， 1 2 本文工作概述 针对列车运行系统中关键事件发生的时间推理问题，基于混合p e t r i 网，本 文使用代数系统的方法进行时间的定量分析，动态确定关键事件发生的时间区 间。在本文列车运行系统的混合p e t r i 网模型( t t h p n ) 中，连续托肯标识具有 连续特征属性的列车以及连续库所有与之对应的关联方程，同时引入时间函数 使得离散事件发生的时间区间动态可计算。该方法将离散变迁对应的时间区间 设定为变量，通过动态预测列车运行系统中关键事件的发生时间区间，可以在 不同速度调整方式下监控列车运行。针对不同速度调整策略下列车追踪运行过 程的仿真实验表明：该方法能将系统中多种复杂因素的分析归结为关键事件发 生时间区间的分析；能体现系统状态的量变到质变的过程；能检测系统中的突 发事件。该方法相对于已有的基于p e t r i 网的时间推理方法，具有支持系统连续 2 1 绪论 状态处理、实时性好等优点。 本文具体工作概述如下： ( 1 ) 在已有的混合p e t r i 网形式化定义中加入时间函数，将关键事件的发生 与时间区间相关联。而事件的发生将引起相关离散变迁的触发，这样时间区间 也是与变迁触发相关联的。 ( 2 ) 基于混合p e t r i 网，建立时间关联的列车运行系统混合p e t r i 网模型， 模型中的主体部分为列车速度调整过程。模型中设定连续库所的关联方程并设 定变迁触发的条件方程，用于描述列车运行过程中连续变量变化规律以及系统 中关键事件发生与连续变量的相互影响。 ( 3 ) 在模型中使用时间推理中代数系统的方法，将关键事件的发生区间上 下界设定为变量。此变量计算过程中不仅分析列车本身的运行状态，还考虑了 其运行环境( 如车站、前行列车等) 对列车运行的影响。 ( 4 ) 与现有其他的基于p e t r i 网的时间推理方法在时间区间的可计算性、实 时性、意外事件是否可处理方面进行相关的对比分析，并得出结论。 混合p e t r i 网能体现离散事件和连续变量的相互影响，为列车运行系统提供 了定量描述连续状态变化以及离散事件发生的建模工具。本文在有关列车运行 系统时间推理的研究中，使用时间推理中代数系统的方法，将连续状态和离散 事件的相互影响归结于对关键事件发生时间区间的动态分析。通过不同速度调 整策略下列车追踪运行的仿真实验表明，该方法能有效的分析外部环境对列车 运行的影响，并且能实时的监控列车运行状态的变化。本文旨在解决列车运行 系统中关键事件发生的时间推理问题，其为列车安全运行提供支持。此时间推 理方法可扩展应用到面向列车群的一类智能混杂系统中。 1 3 本文内容与组织结构 本文在已有的混合p e t r i 网形式化定义中引入时间区间与离散事件相关联， 然后建立时间关联的列车运行系统混合p e t r i 网模型t t h p n 。在t t h p n 的基础 上对列车运行系统中关键事件的发生过程进行时间推理分析：时间区间的上下 界表示为时间函数，通过相关计算将系统连续参数、离散事件、人参等因素的 相互作用归结于对关键事件发生时间区间的分析。仿真表明本文的时间推理方 法能定量分析关键事件的发生过程，能实时处理系统状态的动态变化。 3 1 绪论 本文内容组织结构如下： 第一章：绪论。 本章介绍本文的研究背景与现状、工作概述以及本文的内容和组织结构。 第二章：相关知识介绍。 本章介绍本文涉及到的相关理论知识，包括p c t r i 网理论、时间推理的相关 概念等内容。其中，2 1 节介绍了基本p c t r i 网、混合p c t r i 网、时间p c t r i 网以及 对象p c t r i 网等与本文相关的的p c t r i 网概念；2 2 节介绍了时间推理的相关知识； 2 3 节介绍了基于p c t r i 网的时间推理方法。 第三章：时间关联的列车运行系统混合p c t r i 网模型。 本章在3 1 节在已有的混合p c t r i 网形式化定义中引入时间因素，使得其与 时间关联；3 2 节建立列车运行系统模型( t t h p n ) ，在该模型的基础上能够进行 关键事件的时间推理分析；3 3 节描述了列车速度调整过程中模型变迁的可能触 发序列，并分析了t r h p n 模型中时间推理过程。 第四章：系统模型的仿真实验。 本章给出了不同速度调整策略下列车追踪运行的实例，概述时间区间的计 算过程。4 1 节为列车追踪问题的仿真设计，介绍了移动闭塞系统并设定列车相 关参数；4 2 节、4 3 节分别就单线轨道、双线轨道上列车追踪运行过程做时间 推理分析；4 4 节与其它的基于p c t r i 网的时间推理方法进行相关的对比分析，最 后得出结论。 第五章：总结与展望。 本章对本文的工作进行总结，并展望下一步的工作。 4 2 相关知识介绍 2 相关知识介绍 列车运行系统是一个复杂的系统，从计算机仿真的角度，其分为数据模块 和列车运行控制模块两部分： ( 1 ) 数据模块包含列车数据、线路数据和车站数据，其中列车数据是动态 连续的，线路数据和车站数据基本是固定的。 ( 2 ) 列车运行控制模块在列车运行系统仿真中占有非常重要的地位，通过 对列车的运行间隔的设定对前后列车进出站和区间的运行进行控制。移动闭塞 系统中，列车控制模块包括列车自动运行操作系统和列车自动运行控制系统， 为列车自动运行提供保障。 上述列车运行系统的两个模块体现了其混杂性，本文基于混合p e t r i 网建立 模型对列车运行系统中的连续变量和离散事件的混合属性进行描述。同时，在 所建立的混合p e t r i 网模型中引入时间函数对列车运行系统中关键事件进行时间 推理分析。本章主要介绍本文工作所涉及的一些相关理论知识，包括时间推理、 p e t r i 网理论以及现有的基于p e t r i 网的时间推理的研究。 2 1p e t r i 网 一 2 1 1 基本p e 仃i 网 p e t r i 网是1 9 6 0 年代由卡尔a 佩特里发明的，适合于描述异步、并发、分布 式和随机性的计算机系统模型【3 5 1 。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 网是简单的过程模型，由库所和变迁，有向弧，以及托肯等元 5 2 相关知识介绍 素组成的，下面给出基本p e t r i 网的形式化定义。 定义2 1p e t r i 网( p n ) p n 是一个三元组，即p n = ( p ，乃彳1 ，此处： ( 1 ) p = p l 枕，扔，为库所的有限集合，n 0 为库所的个数： ( 2 ) r = t l ，免，t m ) 为变迁的有限集合，m 0 为变迁的个数； ( 3 ) p n r = 彩( 二元性) ，p u t = o ( 网非空) ； ( 4 ) a ( p x d u 仃一是有限的弧的集合( 流关系仅存在元素尸和r 之 间) 。 定义2 2 普通p e t r i 网系统 一个普通p e t r i 网系统是一个六元组，即= ( p ，兀a ，职k ，m o ) ，其中： ( 1 ) ( p ，la ) 是一个网； ( 2 ) k ：尸o l ，2 ，3 ，) 是库所容量函数； ( 3 ) 胍n 1 ，2 ，3 ，) 是弧权函数； ( 4 ) m o n o ，l ，2 ，3 ，) 是系统的初始标识，满足：v p 尸：m o ( 功s ) 。 由于p e t r i 网主要是用于离散事件系统的建模和分析，在现实应用中具有其 局限性：没有测试库所中0 托肯的能力、模型容易变得庞大、不能反应时间方 面的内容与不支持构建大规模模型。为了解决上述问题，在基本p e t r i 网基础上 进行了各种形式的延伸和扩展，如时间p c t r i 网( t i m e dp e t r in e t s ) 2 7 , 2 引、着色 p e t r i 网【3 6 1 、模糊时间p e t r i 网f 3 0 , 3 4 1 ) 、连续p e t r i 网【3 7 1 、混合p e t r i 网等。 2 1 2 混合p e t r i 网 混合p c t r i 网是由b a i l 在9 0 年代初首次提出的，其模型中定义了连续库所 和连续变迁，用于描述离散事件系统和连续事件系统交互作用的混杂系统。它 继承了普通p e t r i 网能够描述并发、同步、冲突的建模能力，并能够以直观的方 式描述连续变量变化的线性过程及系统内部的演变过程。混合p e t r i 网在同一模 型框架下将系统划分为两个部分来建模：1 ) 连续部分包括连续库所和连续变迁， 用于描述系统中连续变量动态过程；2 ) 离散部分包括离散库所和离散变迁，用于 描述系统中离散事件动态过程。随着对混合p e t r i 理论研究的深入，混合p e t r i 网的描述和分析能力日益完善，其广泛应用于各类混杂系统的建模与分析。混 合p e t f i 网的定义如定义2 3 所示。 6 2 相关知识介绍 定义2 3 基本混合p e t r i 网 一个基本混合p e t r i 网系统( h p n s ) 是一个七元组h p n s - ( p ，la ，m o ， p r e ，p o s t ，d r ) ，其中： ( 1 ) 只t 分别为库所和变迁的有限非空集合，满足p u t = a ，p a t = a 。 库所集p 包含连续库所子集只和离散变迁子集n ，且n 乞= f 2 j ；库所集p 包 含连续库所子集疋和离散变迁子集乃，且zf i t , = f 2 j 。 ( 2 ) a ( p x 乃u ( t xp ) 是库所与变迁之间的有向弧集合。 ( 3 ) m o 为初始标识。 ( 4 ) p r e ：p x t 专r 一，表示p 到t 的有向弧权；p o s t ：p x t r + ，表示 t 到p 的有向弧权重。若p i 是离散库所，p r e ( p t ，e ) 和p o s t ( p ，只) 为正整数；若 p i 是连续库所，p r e ( p t ，) 和p o s t ( p , ，e ) 为正实数。 ( 5 ) 对于离散变迁殇，d ：t 专n + ( 正整数和零) 是变迁触发时延， d r - - - d l ，d 2 9o - 9 d m ) ；对于连续变迁，研对应于最大激发速度v ( 正实数) ，v _ 1 d 。 由混合p e t r i 网的形式化定义可知，一个混合p e t r i 网模型既包含连续库所和 连续变迁，也包含离散库所和离散变迁，为了区别这两种类型的节点，一般采 用如图2 1 所示的符号表示。有关混合p e t r i 网中的变迁的使能、触发以及其性 质分析参见文献 3 8 】。 2 1 3 时间p e t r i 网 在使用普通p e t r i 网建模时，其不能反映时间方面的内容，为了在p e t r i 网中 解决时间约束问题，o c l 暗- p e t r i 网( t i m ep e t r in e t s ，t p n ) 和赋时p e t r in ( t i m e d 7 2 相关知识介绍 p e t r in e t s ) 的概念被提出来【2 1 7 1 。时间p e t r i 网中变迁在时间区间内使能并触发，而 赋时p e t r i 网变迁触发是瞬时的。基本的时间p e t r i 网系统( t e n s ) 可以定义为六 元组，其形式化定义为： 定义2 4 基本时间p e t r i 网 t e n s i 伊，t ，p r e ，p o s t ，l ，m o ，其中： ( 1 ) p ，t 为所有库所和变迁的有限集合，p u t = g ，p n t = a 。； ( 2 ) m 为后向关联函数，肌：尸_ 死 ， ( 3 ) p o s t 为前向关联函数，p o s t ：n p ； ( 4 ) ，n z + 口u 和) ，其中矿表示正整数。这里体现时间p e t r i 网与普通 p e t r i 网的不同之处，每个变迁都与一个时间区间i f , u 相关，和u 都为非负整数， 此时间区间为变迁使能的时间区间，可以为相对时间，也可以为全局时间。 ( 5 ) 初始标识函数m o ：阳。 图2 2 为一个时间p e t r i 网的例子，其为“学生a 用5 分钟时间吃早餐，然后 花了4 0 - - ，5 0 分钟早读”的时间p e t r i 网模型。库所p l 和变迁t l 表示“a 吃早餐花 了5 分钟”；库所p 2 和变迁t 2 表示a 早读时间为4 0 5 0 分钟”。有关t p n7 s 变 迁的使能、触发规则问题参见文献 2 8 】。 为了处理现实中不确定的或主观的时间信息，m u r a t a 【3 0 1 在p e t r i 网中引入模 糊时间片、模糊使能时间、模糊发生时问和模糊延迟四个模糊时间函数来表示 不确定时间信息以及进行模糊时间推理，从而模糊时间p e t r i 网j ( f t p n ) 被提出来。 8 2 相关知识介绍 f t p n 的形式化定义与t p n 相似，只是f t p n 中与变迁相关联的是作为托肯到 达库所的可能性度量的模糊时间区间。 定义2 5 模糊时间p e t r i 网 用五元组表示一个模糊时问p e t r i 网系统( e f t n7 s ) ，e f t n s = 职z a ，c t , m o ， 其中： ( 1 ) p z 为所有库所和变迁的有限集合，p u t = o ，p f 3 r = 彩。； ( 2 ) a 为弧的集合，彳( p x t ) k ：( t x 尸) ； ( 3 ) 是从变迁集t 到模糊触发区间的映射函数，c t ：n j i l 以6 ，c ，刃，满足： o 劲s 1 ，o 如奶9 翻； ( 4 ) m o 是初始标识函数。 2 2 时间推理 2 2 1 基本时间推理理论 时间是人类用以描述物质运动过程或事件发生过程的一个参数，在反应系 统中系统的行为都是时间相关的。理解反应系统的行为方式的最好途径是在时 间系统框架下分析有关现象，而后结合系统中的其他因素进行分析。在反应系 统中进行时间推理分析，可以间接地认知过去或将来关键事件的发生。 反应系统中主要考虑系统状态的动态变化，而系统的动态行为是影响系统 状态变化的一个主要原因，把动态的行为进一步细分为瞬间行为和持续行为。 例如，在列车运行时，列车位置的变化和能耗是持续行为；对列车的操作控制 是瞬间行为。对于具有反应系统特性的列车运行系统，本文在时间推理上的研 究关注的是：若以自然时间的流逝作为参照系，在一条时间轴上表示所有的系 统行为的发生或展开过程，那么随着时间的延伸，不同的情形在同一时刻或相 同情形在不同的时刻所呈现的系统行为方式可能不同。 对反应系统中的行为进行时间推理时需要考虑系统中的内部联系。在列车 运行系统中考虑两辆列车追踪运行的问题，如：前行列车进站，后续列车减速。 这是一个简单命题，如果放进时间逻辑中，便有若干的可能，下面给出三种典 型的可能情况： ( 1 ) 前行列车到达某一站点，追踪运行的后续列车也减速进站，两车停在 不同的站道； 9 2 相关知识介绍 ( 2 ) 前行列车进站避让后续列车，后续列车减速后以一定速度越行前行列 车； ( 3 ) 前行列车进站占据站道，后续列车减速站外停车。 时间推理问题是人工智能研究中需要解决的一个重要问题，同时，在系统 形式化基础上进行时间推理的技术也已经成为一种基于知识的软件智能化技 术。时间推理问题包括预测、计划、学习新规则、自然语言理解、时间相关的 数据分析等等方面，目前在时间推理方面的研究方法基本上可分为三类：时序 逻辑、行为逻辑和代数系统【3 9 1 。 ( 1 ) 时序逻辑也叫时态逻辑，时序逻辑被用来描述为表现和推理关于时间 限定命题的规则和符号化的任何系统，主要用于形式验证。 ( 2 ) 行为逻辑，在这里即为逻辑的行为。在进行时间推理时，几乎都会遇 到行为和变化的表示或推理，譬如情景演变和动态逻辑等。 ( 3 ) 代数系统方法关注的是与时间点或是时间区间的关系，该方法可以把 时间点或时间区间表示为变量，并给出定性或定量方程去确定或限制时间变量 的取值。本文有关时间推理的研究使用代数系统的方法。 关于时间推理中的时间度量方法，本文使用国际公制下定义的时间最基本 单位( 秒) 。 2 2 2 基于p e t r i 网的时间推理方法 p e t r i 网应用领域非常广泛，而时间p e t r i 网的提出使得p e t r i 网还能处理时间 约束等问题。研究者们使用时间p e t d 网和模糊时间p e t r i 网等时间相关的p e t r i 网进行时间知识表示、时间推理算法、不确定知识的表示等方面的研究【训5 1 。 时间知识表示是时间推理研究的基础，时间呈直线性，如果以直线表示时 间，那么直线上的每一个点都可表示为一个瞬间，时间长度为具有方向区别的 时段距离。在物理学上时间是连续的，而在实际日常生活中，时间不一定连续。 本文中的实验将时间看做离散的点组成，列车运行系统中时间的单位为秒( s ) ， 系统状态和行为的分析都基于此时间单位。对于事件的发生过程的时间表示， 需要考虑的是，假定瞬时完成动作的时间点定义为零时间段，那么事件的产生、 变化和结束都必然限定于某时段上，通过时间区间的形式可以表示时间段。而 对于不确定的时间知识，时间区间的上下界是不能确定的，可以使用模糊时间 区间去表示。在众多的时间推理方法中，如果按对时间的表示进行分析，可分 l o 2 相关知识介绍 为基于时间点的时间推理方法、基于事件的时间推理方法和基于时间片段的时 间推理方法三大类。 在时间p e t r i 网中，网中的变迁都关联着一个时间区间 1 0 w e r ，u p p 卅，l o w e r 表示变迁从使能到触发必然经历的时间，而u p p e r 表示如果变迁使能后二直没有 触发的时间超过u p p e r 则变迁将不再使能。从全局时钟来看，当一个变迁使能的 时间为k ，那么变迁触发的时间区间为 k + l o w e r , k + u p p e r 。基于时间p c t r i 网可 以利用可达图分析进行时间推理的运算】，建立一个从初始标识到所有可达标 识的全部路径，这种时间推理分析方法不能很好解决的问题是对并发和冲突描 述问题。针对传统分析方法的不足，文献 4 5 】提出一种基于线性逻辑的时间p e t r i 网推理方法。此方法在线性逻辑的基础上，通过定义了4 种规n ( s e q 规则、p a r 规则，a l t 规则和s h a 规则) ，可以清楚的分析时间p e t r i 网的运行行为并进行 时间推理。由于线性逻辑的方法推理过程复杂，一种扩展的引入模糊时间区间 的时间知识推理算法被提出，其针对列车运行的时间知识系统进行算法的应用 研究【3 3 1 ，旨在解决时间知识的一致性、时间知识的不确定性处理与不同事件同 时发生等问题。而对于时间不确定知识的处理，例如不确定的事件发生时间和 不确定的过程进行时间，m u r a t a 在时间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 7 】中基于混合p c t r i 网建 立列车运行系统的模型t o h p n 。在对列车运行速度调整做分析时，不同列车的 初始速度决定了其制动过程的的最晚发生时间，通过对连续参数的定量分析可 以分析离散事件发生的时间区间。本文在t o h p n 模型的基础上建立时间关联的 列车运行系统混合p e t r i 网模型t t h p n ，引入时间推理中代数系统的方法，通过 动态分析时间区间来进行关键事件发生的时间推理分析。 2 相关知识介绍 2 3 本章小结 本章首先介绍了p e t r i 网相关理论知识，给出了基本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 “网适用于对混杂系统 的建模与分析；而在时间p e t r i 网的基础上能进行时间知识的表示及推理的研究。 随后介绍了时间推理的一般概念，讨论了时间推理方面主要的三类研究方法， 。给出本文的时间度量单位。最后，本章就已有的基于p e t r i 网的时间推理方法做 了概括。 。 1 2 3 时间关联的列车运行系统混合p e t r i 网模型 3 时间关联的列车运行系统混合p e t r i 网模型 在面向铁路智能运输系统的列车运行行为的建模过程中，如何描述智能主 体( 列车) 的行为是建模的关键问题。列车运行系统中列车运行状态参数是连 续变化的，如列车距离下一站点的路程、列车的运行速度等。而影响这些状态 参数连续变化的原因是关键事件的发生所引起的列车加速度的变化，加速度的 变化是离散的，但也有一定规律可循。 列车的运行状态可划分为：停止状态、启动状态、加速状态、匀速状态和 减速状态。任一时刻的列车处于且只处于其中某一状态，列车不可能同时处于 两个或两个以上运行状态，列车在运行过程中，由于关键事件的影响促使其列 车运行状态变化。例如，列车进站时通过减速进站，列车从匀速状态进入减速 状态，然后列车停止运行进入停止状态。同理，列车出站时加速达到指定速度， 即列车从停止状态进入启动状态，而后进入加速状态，达到指定速度后进入匀 速状态。总体来说，当列车运行状态发生变化时，都需要一个速度调整过程。 本章以列车速度调整过程作为列车运行系统的核心，建立基于时间关联混合 p e t r i 网的模型。 3 1混合p e t f i 网中时间因素的引入 定义3 1 时间关联的混合p e t r i 网 混合p e t r i 网适用于混杂系统建模，本文在文献 1 7 1 所定义的一类混合p e t f i 网系统上引入时间函数，时间关联的混合p e t r i 网的形式化定义可以用一个九元 组来表示，即h p n s = ( 尸，乃a ，r ，c ，e ，f ，口，m o ) ，其中： ( 1 ) p ：有限库所集合，尸= p l , p 2 ，a ) ，包括连续库所p c 和离散库所， 其中p u 只且只n 只= o ； ( 2 ) 乃有限变迁集合，t = t o ，乃，t m ，包括连续变迁乃和离散变迁殇，其 中z = zu 乃且zf l 乃= 彩； ( 3 ) a ：库所和变迁之间的有向弧集合，彳( p x t ) u ( t x p ) ； ( 4 ) r ：与连续库所对应的关联方程集合，、连续库所p 对应的关联方程记作 尺p ) 。当p s p c - 1 1 被标识时，v t e m ( p ) ，连续托肯) ，的属性依照尺p ) 变化； 3 时间关联的列车运行系统混合p e t r i 网模型 ( 5 ) c ：与连续变迁对应的条件方程，连续变迁t 对应的条件方程记作c ( 0 ； ( 6 归：有限的事件集合，e = e j ，e 2 ，) ； ( 7 妒：n 才( z + u 细) ，其中才表示正整数。f 为h p n 中的时间函数， v f t o ，有只矽= 【，纠，“纠】，朋砂血纠，以砂和“俐分别称作事件e 的最早发生时间 和最晚发生时间。 ( 8 ) ：点。殇：事件到离散变迁的一对一的映射函数，表示每个事件关联一 个离散变迁； ( 9 龇：系统的初始标识，表示0 时刻系统的状态。 设定删、o ( 0 分别为变迁的入库所和出库所，朋p ) 是库所p 的标识函数， 则变迁使能和触发的规则如下： 定义3 2 混合p e t r i 网中离散变迁的使能规则 离散变迁f 殇使能的充要条件为： 定义3 3 混合p e t r i 网中离散变迁的触发规则 离散变迁f t o 触发规则为： 定义3 4 混合p e t r i 网中连续变迁的使能规则 连续变迁f 死使能的充要条件为： r 一 7 j _ l坳i ( t ) n 足，j 7 e m ( p ) c ( 力( 力，| | 坳e i ( t ) n p o ，3 8 m ( p ) ( 33 ) | 。：。，。+ ，。 7 ； ) ，标识为变迁t 的输入库所p 中的托肯，c ( 力( ) ，) 为库所t 的条件方程，当t 的 输入库所p 中的托肯属性使得c ( 力( 力为真时，连续变迁t 将使能。 定义3 5 混合p e t r i 网中连续变迁的触发规则 1 4 3 时间关联的列车运行系统混合p e t r i 网模型 |坳，o ) r 、芝，3 r e m ( p ) c ( f ) ( 力，坳o ( t ) n p c ，| lm ( 力m ( 力协，觚p ) m ( p ) u 力；| 卜坳， r 、弓，3 8 e m ( p ) ，v p - o ( t ) n p o ，3 4 卜| ；m ( 力_ m ( 力鼢，m ( p ) ：= 必q ) u 哪| 3 2 列车运行系统建模 列车速度调整过程是列车运行系统中最核心的一部分，贯穿于整个列车运 行系统生命期，列车进站、列车出站和列车追踪运行都可以看作是列车速度调 整过程。列车运行的过程是复杂的，列车操作员的调度指令、列车时刻表、追 踪运行的其他列车以及外界随机因素等等都可能是列车运行调整的原因。本文 基于列车运行系统的混杂特性，在文献 1 7 】的基础上，建立时间关联的列车运行 系统混合p e t r i 网模型( t t h p n ) 。 图3 1 所描述的是可