Supervisory Control Of Discrete Event Systems Based On Time Petri Nets And Generalized Mutual Exclusion Constraints

With the rapid development of computing,communications and sensor technologies,a large number of complex dynamic systems,such as automated manufacturing systems,air traffic control systems,intelligent transportation systems,and logistics systems,have emerged,which are quite characterized by a mix command,control,communication,and information issues.Due to the concurrency and conflict of various signals and the operational rules designed by humans,the system states can only be changed by discrete events that occur asynchronously over time.Such artificial systems can be studied as discrete event systems(DESs).In particular,the supervisory control theory proposed by Ramadge and Wonham provides powerful results for the control of DESs,where the occurrence of some events,called controllable events,can be prohibited by establishing state feedback control mechanism,such that the behavior of the system is limited to the given control specifications.Modeling and performance evaluation play a vital role in the design and control of DESs and thus the selection of appropriate mathematical modeling tools is extremely important.The popularity that Petri nets(PNs)have been gaining in modeling of DESs is due to their powerful representational ability of concurrency and asynchronization.In the framework of PNs,supervisory control aims to enforce various types of specifications on a DES.Such specifications can be the overflow or underflow of a resource,deadlock prevention,liveness enforcement,etc.Usually,specifications collectively define a set of legal reachable markings.Moreover,a supervisor can be designed by solving a state-based control problem,such that enforcing these specifications on a PN system by restricting the reachable states of the closed-loop system.Generally,a set of legal markings is expressed in terms of linear inequalities,called Generalized Mutual Exclusion Constraints(GMECs),that can be effectively implemented by a monitor-based supervisor.In the last three decades,much work has been done on the supervisory control of DESs modeled by logical(untimed)PNs.Considering timing information,however,is crucial for the specification and the verification of systems such as transportation systems,communication protocols and real-time systems,as well as the study of extremely important problems such as state estimation,state feedback control and fault diagnosis.The reason is that timing structure may provide additional knowledge of the sequences that can be effectively generated by a system at a certain time.Therefore,time Petri nets(TPNs),associating time constraints with the firing times of enabled transitions,are widely used for modeling and verification of real-time systems.Thanks to the high complexity of the state explosion problem when time is included in the plant,however,there are few reports on the supervisory control of TPN systems.Thus this thesis aims to enforce GMECs and deadlock-freeness on a TPN system by exploiting timing information and supervisory control method such that obtaining a control system with more permissive behavior.Firstly,without considering the deadlock problem of the controlled TPN system,i.e.,assuming that the closed-loop system is deadlock-free,the work has been focused on the design of an optimal supervisor to implement GMECs on a TPN system.Secondly,considering the deadlocks caused by the enforcement of GMECs,an optimal deadlock-free supervisor is designed for a closed-loop system to ensure its safe operation.The main contributions are summarized as follows.1.Given a control specification that requires the reachability set of a net system to be restricted to a set of legal states,the controllability of the system can be generally enforced from two perspectives of structure and behavior.Indeed,structural controllability can be considered separately during the design phase of the supervisor.The method is to limit the monitor-based supervisor to have no arcs directing to uncontrollable transitions.Moreover,behavioral controllability affects both the reachability preprocessing phase and supervisor design,which usually requires that the system will not enter an illegal state by firing uncontrollable transitions only.Therefore,the concept of behavioral controllability of a PN system is extended to a controlled TPN system.2.To reduce the computational effort of the control synthesis for a TPN system,this thesis first ignores the timing information associated with the transitions and exploits the existing solution to compute a logical supervisory control law implementing GMECs on the underlying untimed PN system.Therefore,the evolution of the TPN system can be confined in a proper region,avoiding to consider a search on the entire state space for the control synthesis.Then,based on the Modified State Class Graph(MSCG)(i.e.,a typical tool for the state space abstraction of TPN systems),a Partial Modified State Class Graph(PMSCG)is proposed to represent the states generated by firing uncontrollable transitions only,and therefore it has a smaller size.3.In this thesis,all transitions are assumed to be observable but some transitions,called controllable,can be disabled in order to forbid reaching states violating given GMECs.To effectively implement GMECs,an online control algorithm that runs with a logical supervisory control law is presented.When the firing of a controllable transition violates the logical supervisory control law,the algorithm evaluates,by online computing a set of PMSCGs and solving linear programming problems,if the aforementioned controllable transition should be effectively disabled,taking into consideration the timing structure.Meanwhile,it is proved that the approach can enforce behavioral controllability in a maximally permissive way.4.When GMECs are enforced on a live(deadlock-free)PN system by monitors,the deadlock-freeness of a closed-loop system may be lost.A logical supervisory control law is first assumed to be available for implementing GMECs without deadlocks.Then,a Reduced Modified State Class Graph(RMSCG)derived from the MSCG is developed,representing a reduced portion of the state space of a TPN system generated by firing a specific set of transitions.This specific set of transitions depends on the transformed GMECs to be enforced on the TPN system and includes controllable as well as uncontrollable transitions.Note that the transformed GMECs are associated with the logical supervisory control law and may therefore differ from the originally given GMECs.Especially,the computation of an RMSCG is performed only when the firing of an enabled controllable transition violates the logical supervisory control law at a current state.5.Based on the RMSCG,a control synthesis approach is presented to compute a control function for each controllable transition enabled at a current state.In particular,the synthesis approach evaluates whether the controllable transitions can fire by solving some linear programming problems formulated on the basis of a set of RMSCGs.Finally,the proposed approach is proved to enforce GMECs and deadlock-freeness in a maximally permissive way.That is,a legal marking set with respect to a TPN system is deadlock-free controllable under the control function.Indeed,for all the markings belonging to this legal marking set,no forbidden markings are reachable such that the closed-loop system is deadlock-free.Finally,conclusions and future work on supervisory control of TPN systems are prospected.