Issues in modelling and identification of Discrete Event Systems

Abstract

Discrete Event System (DES) are systems whose behavior is governed by discrete events occurring asynchronously over time and solely responsible for generating state transitions. DESs are particularly used in the field of the manufactured systems, handling systems and transportation systems: even if such system are being studying for long time, because of their complexity, they still present many issues that attract research interest. In particular this dissertation focuses about handling system modeling and DES identification. Obtaining a good model of a system (both time-driven and event-driven) allows to more easily execute operations as performance analysis, control, monitoring of system evolution. However, in some cases modeling of a system is not simple because of several complications due to the behavior of the system or of the context it belongs to. As example, sometimes, especially in the context of material handling and transportation, systems present both an event-driven and a time-driven behavior. In all that cases a very high accuracy is not requested it is usual neglect the latter and “looking” at the system as a DES (as example modeling a handling system it is possible to be interested in knowing if a vehicle is or not in a zone of the path while it is not important to know its exactly position). When the time-driven behavior plays a fundamental role in the obtaining the overall system performance, such dynamics cannot be neglected and they have to be explicitly modeled. This is the case, as example, of the automated warehouse systems, where the handling subsystem, as will be shown in the rest of this dissertation, presents time-driven dynamics that greatly influence the warehouse’s performance. Consequently a new way to model the system behavior has to be used. However, there are situation in which the difficult issue is not choosing the right formalism to model the system but it is the modeling itself. This is typical in many practical contexts, where it can occur that one has to work with unknown ready-made systems and no documentation about their behavior is available, or the model of a very complex system is needed. In these and other cases modeling becomes hard and another way to obtain the model of the system is needed: automated identification can be the solution. In the modeling environment, contribution of this thesis consists in presenting a new methodology to obtain a model oriented to the control and performance analysis of complex material handling systems that is highly modular, compact and made of parameterized modules. First a discrete event model is presented and then a new formalism that merges the concepts of Hybrid Petri Nets and Colored Petri Nets is introduced: the Colored Modified Hybrid Petri Nets (CMHPNs). Hence a new CMHPN model is proposed: it allows to model both the event nature and the continuous nature of the system. As more, to allow the monitoring of system evolutions, a freeware simulation tool for the CMHPNs is presented. Finally it is shown how the CMHPN model can be used to execute analysis and performance evaluation. Liveness analysis is performed by means of a hybrid automaton obtained from the net model. A deadlock prevention policy is synthesized working on an aggregated model. To prove the effectiveness of this new formalism an existing large automated warehouse system is presented as case study: its CMHPNs model is used to simulate the system behavior and to analyze the warehouse’s performance. In the identification environments, the guidelines of a new “active” approach to identify the model of a preexisting system is described. The proposed preliminary algorithm identifies a free labeled PN model on the basis of the observed output sequences and of the modifiable input consisting of the enabled controllable transitions set. The main idea is to use the knowledge of the set of enabled controllable transitions together with additional information on the conflicting transitions to accelerate the net identification with respect to the passive identification approaches. In particular, the system assumes that the maximum time that must elapse from the enabling of a transition until it fires is known and that it is possible to detect if the system is entered in a cyclic behavior. Using this additional information, it is possible to determine set of constraints to represent sequences that are not accepted by the system. Such constraints can be used to improve the net identification. [edited by author]