Research On Forbidden State Problems Of Discrete Event Systems With Unobservable Events

Man-made systems in real life,if analyzed in terms of logical behavior,are all discrete event systems,such as flexible manufacturing systems,communication systems,and rail transit systems.Forbidden state problems of discrete event systems have to be seriously considered in various fields since they are closely related to the productivity of systems in manufacturing,the security of information transmission in communication,the operation safety of rail transit systems,etc.Due to the limited existing observation technique,the high cost of observation on some events,the possible failure of devices and electrical wiring,etc,the presence of unobservable events in real systems is inevitable.Considering the operation safety and/or the economic gain of systems,it is necessary to do the research on forbidden state problems of discrete event systems with unobseverble events.Unfortunately,little progress has been made so far on forbidden state problems of discrete event systems with unobseverble events.Petri nets are adopted in this paper as a modelling tool to deal with such problems.Such problems can thus be called forbidden state problems of partially obersvable and controllable Petri nets.The main contributions of this work are as follows.1.For partially obersvable and controllable Petri nets,a systematic and complete theoretical framework is established to deal with forbidden state problems.It includes necessary concepts like"admissible observed transition sequences" and "the equivalence of state specifications",some important results,and basic ideas on the design of optimal control policies.2.For a class of partially obersvable and controllable Petri nets with a given specification being a linear constraint,a method with polynomial complexity is proposed to design an optimal control policy.This method relies on the following important results proposed in this work.a)For linear constraints whose forward influence subnets are forward-concurrent-free,an algorithm is proposed that can efficiently perform the optimal linear constraint transformation.b)For linear constraints whose backward observation subnets are backward-conflict-free,an efficient algorithm is presented to compute the minimal unobservable reduction.c)An optimal control policy is designed for a given specification being an uncontrollable admissible linear constraint.3.For partially obersvable and controllable Petri nets with given specifications being a class of disjunctions of linear constraints,a method is proposed to obtain an optimal control policy,which is also of polynomial complexity.In addition to the previous research results,the following results contribute to such a method.a)An efficient algorithm is proposed to perform the optimal transformation of a class of disjunctions of linear constraints.b)An optimal control policy is designed for a given specification being a disjunction of uncontrollable admissible linear constraints.Although the proposed methods with practical significance are only applicable to a class of Petri nets and/or a class of linear constraints,they not only guarantee the optimality of control policies but also enjoy a relatively wide range of application when compared with the state-of-the-art methods.Moreover,the future research on forbidden state problems of partially obersvable and controllable Petri nets all can be carried out based on the established theoretical framework.