加标Petri网的死锁分析与控制

Labeled Petri nets are an essential mathematical formalism to address the analysis and control of discrete event systems with partial observations. This project focuses on the deadlock characterization, analysis, and control of discrete event systems modeled with labeled Petri nets consisting of undistinguishable and unobservable transitions. Considering the state explosion problem, we first present a representation of system behavior using basis reachability graphs and study the conditions of a labeled Petri net, under which a basis reachability graph can fully characterize and analyze its deadlock problem. Second, for the Petri nets that cannot be addressed using a basis reachability graph, we develop the concept of observation graph such that it can fully cope with the deadlock analysis and characterization of general bounded labeled Petri nets. Then, we consider the modular synthesis of labeled Petri nets and investigate the liveness consistency conditions and generation algorithms of basis reachability graphs and observation graphs of the synthesized net model. Third, by taking into account the malicious attacks from an intruder to a system, we deal with the liveness robustness and the deadlock characterization problem, where the malicious attacks include modification, insertion, and removal of event labels in a system observation (output). Finally, we investigate the deadlock control strategies, Petri net supervisor implementation and the existence problem of a Petri net supervisor.

加标Petri网是研究部分可观离散事件系统分析与控制的重要数学工具。本项目拟研究具有不可区分以及不可观变迁加标Petri网的死锁描述分析和控制问题。考虑Petri网的状态爆炸，首先研究加标Petri网的基础可达图表示方法及其可用于描述与分析加标Petri网死锁的约束条件。对于基础可达图不能描述的加标Petri网，研究一种称之为观测图的Petri网行为紧凑表示，使得能够准确描述和分析任何有界加标Petri网的死锁问题。然后考虑加标Petri网的模块化综合技术，研究合成Petri网的活性一致性条件及其基础可达图和观测图的生成算法。再次，考虑系统有入侵者恶意攻击下，加标Petri网的死锁分析和控制。本项目主要考虑对系统输出事件标号进行篡改、插入和移除三种情况下，系统活性的鲁棒性问题和鲁棒增强策略。最后研究一般加标Petri网系统的死锁控制策略、活性控制器的Petri网实现以及存在性问题。

本项目旨在解决基于基础可达图和观测图的加标Petri网的死锁描述分析和控制理论、模块化Petri网综合的活性一致性（稳定性）问题，以及系统遭受入侵者恶意攻击下的活性鲁棒性问题。研究工作取得了较好的成果，发表SCI国际期刊论文32篇，国际会议论文3篇。主要成果包括：1.离散事件系统故障诊断方法研究：1a基于加标Petri网离散事件系统故障诊断方法，通过向诊断函数引入一个新的包含所有故障变迁的故障类，使得诊断结果包含更多信息且更加精确。1b部分可观输出下的基于状态观测的离散事件系统故障诊断方法，给出了具有多项式计算复杂性的系统可诊断性验证算法。1c基于整数线性规划问题，提出了一个称为QBRG的结构来描述系统的行为，避免了计算系统的所有可达标识。2.考虑资源不可靠因素的Petri网死锁控制研究：2a提出了鲁棒合法标识的定义并研究基于基本信标的两阶段鲁棒死锁控制策略。2b针对含有多种类型的不可靠资源的自动制造系统提出了一种自适应死锁控制策略。2c针对具有多个不可靠资源的简单顺序进程系统设计鲁棒活性监督控制器。2d验证了自适应控制器无论受控系统是否出现资源故障都能保证其活性。3.离散事件系统不透明性保障问题研究：3a将离散事件系统建模为有限状态自动机的不透明度保障问题，提出了一种扩展插入机制，以保障系统不透明性。3b提出在离散架构中验证K-步不透明性的方法。3c展示了时间观测器改进状态估计的过程，讨论了定时系统的保密准则，设计的时间观测器具有规模有限的优点。4.基于时间Petri网的离散事件系统研究：4a提出了一种以最大行为许可的方式计算在时间Petri网系统上实施广义互斥约束的监督控制方法。4b提出了一种符号方法，抽象了发射顺序约束并绕过了参数域的使用及其相关的高代价操作。4c改进了TERG现有的近似构造算法，定义了新的对象“顶点”来描述时间Petri网中的时间约束，设计了度量值。5.离散事件系统的建模与调度方法研究：5a针对批处理生产系统，并提出了一种基于Petri网模型的建模与调度方法，设计了一种新的过滤集束搜索方法。5b基于一种新的DES建模工具构建了一个具有普适性的实时系统模型。本项目的研究总体来说是成功的，成果是丰富的，在一定程度上解决了Petri网的死锁分析以控制、活性和鲁棒性问题。初步建立计算高效的自动制造系统全性能优化活性Petri网控制器设计理论和方法。