Reachability Analysis Of Petri Net
Author: Wu Wen-Yuan Advisor: Yang Lu (Research Scientist)
ABSTRACT
This work makes a general introduction for the reachability analysis of Petri net and presents the energy optimization model. Furthermore, the structures and behaviors of the Petri net are described by using linear space and polynomial ring. Highly concurrent system suffers from the state explosion problem produced by an exponential increase of the number of reachable states. The state explosion can be handled by using a hybrid method, which is based on Grobner Basis and the energy optimization model.
In the preface of this paper gives a concise statement of the reachability analysis of Petri net and introduces the most general methods, which are using in the field at present.
In the first chapter, the background of Petri net, such as the research history, development, research approach and its application fields, is elucidated. Afterward, this paper illustrates Petri net model, related knowledge, the importance of reachability analysis and the bottleneck of the problem.
Computer algebra method is the main content in the second chapter. Firstly, the paper depicts the fundamental ideal, how the Petri net model is mapped to algebra system, then gives out the relevant algebra expressions for behaviors of the Petri net. Sequentially, essential knowledge about computer algebra, Grobner basis, the key tool of reachability, and Maple, the most famous mathematics software, are introduced. Moreover, the paper emphasizes on the limits of computer algebra method.
From the third chapter, a new way to resolve reachability is coming out from matrix-equation method and the idea of penalty function, and naturally the concept of weak reachable condition is derived from this model. Using integer programming to solve weak reachable condition and building energy optimization model are the main content of this chapter.
In the fourth chapter, we propose to use neural network to calculate the result of the model. Consequently, many concepts and properties about neural network are discussed, especially the Hopfield network. This paper gives out the total energy
IV
function and parameters of the model. Afterwards, implementation of neural network by software and hardware tools is mentioned.
In the fifth and sixth chapters, we present a hybrid method by combining computer algebra method and energy optimization method, which are introduced in previous chapters. A representative example is presented in order to show how the energy optimization model is generated, described and calculated by using relevant software, and how the hybrid method is applied to reachability test.
Finally, the promises and problems of the approach are illustrated. By using the energy optimization framework, properties requiring an exhaustive analysis need an advanced research.
Key Words: Petri net, Reachability, Grobner basis, Energy optimization model,
Hopfield network, Weak reachable condition, Hybrid method
V
前 言
自从1962年Carl Adam Petri 在他的博士论文[1]中提出Petri网模型以来，该
模型就成为理论计算机科学包括自动机模型和形式语言理论的一个分支。在分析并行系统的状态行为的技术中，Petri网模型具有自然，直观，简单易懂等特点。它是一种形式化模型描述方法，在并行模型分析，协议的验证，自动控制等方面有广泛的应用。可达性分析是系统的状态，行为分析的基础。可达性就是研究系统可能达到的状态和状态间的关系，而连接状态和状态的纽带就是变迁。可达性也是研究系统最基本的行为，其他行为特征比如：可逆性、有界性、活性、可覆盖性、公平性等，都可归结为可达性的研究。但是，随着系统规模的扩大，状态空间的组合爆炸使可达性分析非常困难。利用Petri网模型进行系统分析的复杂度呈指数倍提高，明显阻碍了该方法在实时系统中的应用。各种相关的处理方法被提出，但各有优缺点。
可达性的研究最基本方法就是穷举法，构造可达树，遍历所有的过程和状态，是最彻底也是最低效的方法,该方法对于规模较小的问题是有效的，但对于复杂的系统该方法就无能为力了。因为可达性的研究面临的主要困难就是组合爆炸，当问题规模变大，可能的状态数呈几何级数增加，解决问题所需的时间空间也呈几何级数增加。这就阻碍了实时并行系统的分析。
目前提出的解决方法主要还有以下几种：转化为代数问题再利用Grobner基作判断的方法[2](在第二章我们将着重介绍计算代数的方法)；转化为矩阵计算问题利用不变量求解线性方程的方法(与第三章介绍的能量优化方法的出发点一致)；通过进程代数将问题分而治之的方法[3]；还有基于布尔函数计算和二叉决策图压缩状态空间的方法[4]。下面先介绍一下后两种方法。
基于进程代数的分而治之的分析方法：
组合爆炸可以通过利用分而治之的方法来加以控制，一般称为组合分析方法(compositional analysis technique)。主要思想是分析一个大系统的各个部分，再将各个部分按层次合成起来。传统的可达性分析方法不能将系统分解，而进程代数和进程计算方法可将一个大系统分解为等价的子系统。
进程代数是关于通信并发系统的代数理论的统称。20世纪70年代后期，英国学者R.Milner和C.A.R.Hoare分别提出了通信系统演算CCS[5]和通信顺序进程TCSP[6]，开创了用代数方法研究通信并发系统的先河。之后Bergestra和Klop提出的 ACP[7]，ED Brinksma 提出的LOTOS[8]等等，这些代数理论都使用通信，而不是共享存储，作为进程间相互作用的基本手段，表现出面向分布式系统的特征。在语法上，进程代数用一组算子作为进程的构件。算子的语义通常用结
VI
构化操作语义方法定义，这样进程就可以看成是带标号的变迁系统。进程代数的一个显著特征是把并发性归结为非确定性，将并发执行的进程行为看成是各单个进程行为的所有可能的交错合成。进程代数研究的核心问题是进程的等价性，即在什么意义下两个进程的行为相同。但问题在于，在分解时可能将一个大系统分为子系统的同时，产生过多的进程图和进程图节点[3]。
基于布尔函数计算和二叉决策图压缩状态空间的方法：
主要思想是用布尔函数来表示Petri网的结构和行为，将Petri网的变迁转化为布尔函数的计算。Petri网转化为布尔代数是很自然的，PN=(T,S;F,K,W,M0)，假定K=1, 令MT=2T，就可以表示Petri网系统所有的状态空间，而可达标识集必是MT的一个子集。Bn=(2M,∪,∩,?，MT)，映射函数 ?：MT?Bn
T?1，如果pi?M ?M?MT ?i，pi??0，如果p?Mi?可达状态空间由该集合的特征函数来表示，只要是属于可达状态空间的点，通过特征函数计算，输出为1，反之亦然。所以无论状态空间的大小，一个特征函数与可达标识集是一一对应的。特征函数：??：Bn?B?1，如果p??的一个子集。?p?B p??
0，如果p???n??2MT,既是MT
比如：???(p2,p3)(p2,p7)(p4,p7)?，
??＝p1p2p4p5p6(p3?p7)?p1p3p5p6p7p4
所以，求可达状态集就可以通过循环计算特征函数来得到。 算法：
Reached=From=M0 do To=0
for each t?T do To= To+ Img(t,from) New=To - Reached From=New
Reached=Reached + New while (New ?0) return Reached
其中: Reached, From, New 都是状态点集对应的特征函数，Img(t, From)的含义是将变迁t作用于布尔函数From，既是计算From对应的可达状态集中能实施
V II
变迁t所得到的所有新可达状态集所对应的特征函数。
算法中所有的运算都是布尔运算，而布尔运算的实现可通过二叉决策图(Binary Decision Diagrams)的相应运算实现，并且可以证明每种运算都是多项式时间完成，在此不再做介绍，相关文献请见[9][10]。
该方法的优点在于求出特征函数后可快速判断某个状态是否可达。但该方法的问题在于：1. 在运算过程中使用的二叉决策图峰值远远大于最后结果的个数
2. 求出的特征函数只是一个无结构的集合，不能给出标识间的结
构关系，不能构造变迁过程，也无法讨论系统的可逆性。
这些方法都有自己的适用范围和优缺点。我们提出的方法是基于计算代数和神经计算的方法：综合了计算代数方法和矩阵计算方法，建立了能量优化模型，并用神经网络来实现算法，其特点就在于提出了一种可利用基于硬件的大规模并行的神经计算代替了基于软件的串行的数字计算。
在第一章简要介绍了Petri网的背景知识，第二章介绍了计算代数的方法和相关知识。后四章给出了作者的主要工作。附录中给出上述算法的Matlab程序。
VIII