×

zbMATH — the first resource for mathematics

Real time identification of discrete event systems using Petri nets. (English) Zbl 1283.93187
Summary: The paper defines the identification problem for Discrete Event Systems (DES) as the problem of inferring a Petri Net (\(PN\)) model using the observation of the events and the available output vectors, that correspond to the markings of the measurable places. Two cases are studied considering different levels of the system knowledge. In the first case the place and transition sets are assumed known. Hence, an integer linear programming problem is defined in order to determine a \(PN\) modelling the DES. In the second case the transition and place sets are assumed unknown and only an upper bound of the number of places is given. Hence, the identification problem is solved by an identification algorithm that observes in real time the occurred events and the corresponding output vectors. The integer linear programming problem is defined at each observation so that the \(PN\) can be recursively identified. Some results and examples characterize the identified \(PN\) systems and show the flexibility and simplicity of the proposed technique. Moreover, an application to the synthesis of supervisory control of \(PN\) systems via monitor places is proposed.

MSC:
93C65 Discrete event control/observation systems
93B30 System identification
90C10 Integer programming
Software:
UMDES; GLPK
PDF BibTeX Cite
Full Text: DOI
References:
[1] Angluin, D., Introductive inference of formal languages from positive data, Information and control, 45, 117-135, (1980) · Zbl 0459.68051
[2] Angluin, D., Learning regular sets from queries and counterexamples, Information and computation, 75, 87-106, (1987) · Zbl 0636.68112
[3] Badouel, E.; Berardinello, L.; Darondeau, P., The synthesis problem for elementary net systems is NP-complete, Theorical computer science, 186, 107-134, (1997) · Zbl 0893.68111
[4] Badouel, E.; Darondeau, P., Theory of regions, (), 529-586 · Zbl 0926.68088
[5] Basile, F.; Chiacchio, P.; Giua, A., Suboptimal supervisory control of Petri nets in presence of uncontrollable transitions via monitor places, Automatica, 42, 6, 995-1004, (2006) · Zbl 1110.93040
[6] Bourdeaud’Huy, T., & Yim, P. (2004). Synthése de réseaux de Petri á partir d’exigences. In Proc. 5th French conference on modeling and simulation
[7] Cabasino, M. P., Giua, A., & Seatzu, C. (2006). Identification of deterministic Petri nets. In Proc. 8th international workshop on discrete event systems (pp. 325-331) · Zbl 1125.93332
[8] Cassandras, C.G.; Lafortune, S., An introduction to discrete event systems, (1999), Kluwer Academic Publisher Boston, MA · Zbl 0934.93001
[9] Chung, S. L., Li, C. L., Wu, J. C., & Wang, S. T. (2003). Online modeling refinement for discrete event systems. In Proc. IEEE conf. on systems, man and cybernetics: Vol. 3 (pp. 2739-2744)
[10] Cortadella, J.; Kishinevsky, M.; Lavagno, L.; Yakovlev, A., Deriving Petri nets from finite transition systems, IEEE transactions on computers, 47, 8, 859-882, (1998) · Zbl 1392.68291
[11] Gaubert, S.; Giua, A., Petri net languages and infinite subsets of \(N^m\), Journal of computer and system sciences, 59, 373-391, (1999) · Zbl 0958.68120
[12] Giua, A.; Corona, D.; Seatzu, C., State estimation of \(\lambda\)-free labeled Petri nets with contact-free nondeterministic transitions, Journal of discrete event dynamic systems, 15, 1, 85-108, (2005) · Zbl 1071.93028
[13] Giua, A., & Seatzu, C. (2005). Identification of free-labeled Petri nets via integer programming. In Proc. 44th IEEE conf. on decision and control (pp. 7639-7644)
[14] http://www.gnu.org/software/glpk/glpk.html. Gnu Linear Programming Kit
[15] Gold, E.M., Language identification in the limit, Information and control, 10, 447-474, (1967) · Zbl 0259.68032
[16] Gold, E.M., Complexity of automaton identification from given data, Information and control, 37, 117-135, (1980)
[17] Hillier, F.S.; Lieberman, G.J., Introduction to operations research, (2005), Mc Graw Hill New York, NY, USA · Zbl 0155.28202
[18] Hiraishi, K., Construction of a class of safe Petri nets by presenting firing sequences, (), 244-262
[19] Hiraishi, K., Synthesis of supervisor for discrete event systems allowing concurrent behaviour, (), 13-20
[20] Meda-Campaña, M. E., & López-Mellado, E. (2005). Identification of concurrent discrete event systems using Petri nets. In Proc. of IMACS world congress (pp. 11-15)
[21] Nelles, O., Nonlinear system identification, (2001), Springer-Verlag Berlin, Heidelberg, Germany
[22] Peterson, J.L., Petri net theory and the modeling of systems, (1981), Prentice Hall Englewood Cliffs, NJ, USA
[23] Sreenivas, R.S., On minimal representations of Petri net languages, IEEE transactions on automatic control, 51, 5, 799-804, (2006) · Zbl 1368.68241
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.