Offline analysis of the relaxed upper boundedness for online estimation ofoptimal event sequences in Partially Observable Petri Nets
Author: 
P. DeclerckAuthors Info & Claims
Pages 351 - 374
Abstract
The aim of this paper is the analysis of the property of the relaxed structurally boundedness of the unobservable subnet of the Petri net which brings a condition guaranteeing the finitude of all possible sequence lengths in the context of an on-line estimation in Partially Observable Petri Nets relevant to a sliding horizon or a receding horizon starting from the initial marking. Based on specific invariants defined over the real numbers, the approach focuses on an offline structural analysis, that is, the determination of the parts of the unobservable subnet where an online estimation for any criterion can be made. The decomposition-composition technique is based on a block triangular form obtained with any technique. The composition of the substructures leads to a propagation of the relaxed structurally boundedness property through the structure. The study of a large-scale manufacturing system shows that the direct treatment of the large system system can be avoided and that the triangular form brings a sequential treatment allowing a computation based on smaller systems independently of the resolution of the complete system.
References
[1]
L. Aguirre-Salas, O. Begovich, and A. Ramirez-Trevino, Observability in interpreted Petri nets using sequence invariants. In Proc. of the 41st IEEE Conf. on Decision and Control, volume 4, pp. 3602–3607, 2002
[2]
Aybar A and Iftar A Decentralized Structural Controller Design for Large-scale Discrete-Event Systems Modelled by Petri Nets Kybernetika 2009 45 1 3-14
[3]
F. Arichi, M. Petreczky, M. Djemai, and B. Cherki, Observability and Observer Design of Partially Observed Petri Nets, IFAC-PapersOnLine 48 (27), pp. 27-32, 4, 2015
[4]
F. Baccelli, and B. Gaujal, Liveness in Free-Choice Petri Nets- An Algebraic Approach, research report, Inria, 1996
[5]
Basile F, Chiacchio P, and De Tommasi G On K-diagnosability of Petri nets via integer linear programming Automatica 2012 48 9 2047-2058
[6]
T. Becha, R. Kara, S. Collart-Dutilleul, and J. J. Loiseau, Modelling, Analysis and Control of Electroplating Line Modelled by P-Time Event Graphs, in Proc. 6th International Conference on Management and Control of Production and Logistics, Fortaleza, Brazil, pp. 311-316, Sep. 11-13, 2013
[7]
Bonhomme P Decentralized state estimation and diagnosis of P-time labeled Petri nets systems Journal of Discrete Event Dynamic Systems 2021 31 1 137-162
[8]
A. Boussif, B. Liu, and M. Ghazel, Diagnosability Analysis of Intermittent Faults in Discrete Event Systems, International Journal of Control, Automation and Systems 17(X), pp. 1-14, 2019
[9]
P. Bunus, and P. Fritzson, Methods for structural analysis and debugging of modelica models, in Proc. International Modelical Conference, pp.157-165, 2002
[10]
Cane J-M, Kubicki A, Michelucci D, Barki H, and Foufou S Re-paramétrisation et réduction des systèmes irré ductibles Revue électronique Francophone d’Informatique Graphique 2014 8 2 7991
[11]
A. Chouchane, P. Declerck, A. Khedher, and A. Kamoun, Diagnostic based on estimation using linear programming for partially observable Petri nets with indistinguishable events, International Journal of Systems Science: Operations & Logistics, pp. 1-14, Taylor & Francis, 2018
[12]
Chouchane A and Declerck P Diagnosis on a sliding horizon for partially observable Petri nets, Kybernetika, International journal of Institute of Information Theory and Automation of The Czech Academy of Science 2022 58 4 479-497
[13]
F. Baccelli, G. Cohen, G.J. Olsder, and J.P. Quadrat Synchronization and Linearity. An Algebra for Discrete Event Systems, Available from http://maxplus.org, New York, 1992, Wiley
[14]
P. Declerck and P. Bonhomme, State Estimation of Timed Labeled Petri Nets with Unobservable Transitions, IEEE Transactions on Automation Science and Engineering, Special Issue on Discrete Event Systems for Automation, Vol. 11, No. 1, ITASC9, pp. 103-110, January 2014
[15]
P. Declerck, Counter approach for the estimation of optimal sequences in Partially Observable Untimed Petri Nets, Journal of Discrete Event Dynamic Systems, 2021
[16]
Declerck P and Bonhomme P Two-staged Approach for Estimation of sequences in Partially Observable P-time Petri Nets on a sliding horizon with schedulability analysis International Journal of Control 2023
[17]
P. Declerck, and M. Staroswiecki, Identification of structurally solvable sub-systems for the design of Fault Detection and Isolation Schemes, using the Embedding Procedure, 9th IFAC/IFORS Symposium on Identification and System Parameter Estimation, pp. 230-235, Vol.1, Budapest, Hungary, July 8-12, 1991
[18]
P. Declerck, and M. Staroswiecki, Characterization of the Canonical Components of a Structural Graph for Fault Detection in Large Scale Industrial Plants, First European Control Conference, ECC’91, pp. 298-303, Vol.1, Grenoble, France, July 2-5, 1991
[19]
F. Defossez, S. Collart-Dutilleul, and P. Bon, Temporal requirements checking in a safety analysis of railway systems, FORMS/FORMAT 2008, Symposium on Formal Methods for Automation and Safety in Railway and Automotive Systems, TU Braunschweig and Budapest University of Technology and Economics, October, 2008
[20]
Dotoli M, Fanti MP, and Mangini AM Fault detection of discrete event systems by Petri nets and integer linear programming Automatica 2009 45 11 2665-2672
[21]
Dulmage AL and Mendelsohn NS Covering of bipartite graphs Canadian J. Math 1958 10 517-534
[22]
A. L. Dulmage, and N. S. Mendelsohn, A structure theory of bipartite graphs of finite exterior dimension, Trans. of Royal Soc. Canada, Section III, 53, pp. 1-13, 1959
[23]
F. Ahmad, H. Huang, and X. Wang, A Technique for Reachability Graph Generation for the Petri Net Models of Parallel Processes, International Journal of Computer and Information Engineering, Vol: 3, No: 3, 2009
[24]
Frisk E, Bregon A, Aslund J, Krysander M, Pulido B, and Biswas G Diagnosability Analysis Considering Causal Interpretations for Differential Constraints, IEEE transactions on systems, man and cybernetics Part A. Systems and humans 2012 42 5 1216-1229
[25]
Gougam HE, Pencolé Y, and Subias A Diagnosability analysis of patterns on bounded labeled prioritized Petri nets Discrete Event Dynamic Systems 2017 27 143-180
[26]
J. Komenda, S. Lahaye, J-L. Boimond, and T. van den Boom, Max-plus algebra in the history of discrete event systems, Annual Reviews in Control. 45. 10.1016/j.arcontrol.2018.04.004, 2018
[27]
Lefebvre D On-Line Fault Diagnosis With Partially Observed Petri Nets IEEE Transactions on Automatic Control 2014 59 7 1919-1924
[28]
L.Li, Y. Li, B. Liu, and W. Wu. Least-Cost Transition Sequence Estimation in Labeled Time Petri Net Systems with Unobservable Transitions, International Journal of Control, pp 1-14, 10.1080/00207179.2022.2121764, 2022
[29]
Libeaut L Sur l’utilisation des dioides pour la commande des systèmes à événements discrets 1996 Nantes Ph.D
[30]
Mahulea C, Seatzu C, Cabasino M, and Silva M Fault Diagnosis of Discrete-Event Systems Using Continuous Petri Nets IEEE Transactions on Systems, Man, and Cybernetics 2012 42 970-984
[31]
Murata T (Apr. 1989) Petri Nets: Properties. Analysis and Applications, in PROCEEDINGS OF THE IEEE 77(4):541–580
[32]
K. Murota, Systems Analysis by Graphs and Matroids. Structural solvability and controllability, Algorithms and Combinatorics 3, Springer-Verlag, 1987
[33]
Pothen A, Fan C-J (December 1990) Computing the Block Triangular Form of a Sparse Matrix. ACM Transactions on Mathematical Software 16(4):303–324
[34]
Ru Y and Hadjicostis CN Sensor selection for structural observability indiscrete event systems modeled by Petri nets IEEE Trans. Autom. Control 2010 55 8 1751-1764
[35]
K. Schmidt, Using Petri Net Invariants in State Space Construction, Proc. of Tools and Algorithms for the Construction and Analysis of Systems TACAS, LNCS, vol. 2619, Springer, pp. 473-488, 2003
[36]
V. M. Savi, and X. Xie, Liveness and Boundedness Analysis for Petri Nets with Event Graph Modules, Lecture Notes in Computer Science book series (LNCS,volume 616), International Conference on Application and Theory of Petri Nets, pp 328–347, 1992
[37]
H. Yue, S. Xu, G. Zhou, H. Hu, Y. Guo, and J. Zhang, Estimation of least-cost transition firing sequences in labeled Petri nets by using basis reachability graph, IEEE Access, pp. 1-1. 10.1109/ACCESS.2019.295205, 2019
Recommendations
Counter approach for the estimation of optimal sequences in Partially Observable Untimed Petri Nets
AbstractIn this paper, we consider the on-line estimation of optimal current subsequences in Partially Observable Untimed Petri Nets. Applying the counter approach classically used in max-plus algebra for Timed Petri nets, the idea is to exploit the ...
Discrete Time Stochastic Petri Nets
Basic graph models of processes, such as Petri nets, have usually omitted the concept of time as a parameter. Time has been added to the Petri net model in two ways. The timed Petri net (TPN) uses a fixed number of discrete time intervals. The ...
Relaxed Unfolding for Time Petri Nets
CSA '13: Proceedings of the 2013 International Conference on Computer Sciences and ApplicationsState Class Graph is a very useful tool to analyse Time Petri nets properties. It generates however a states explosion problem in large Petri nets. This can be overcome by using unfolding technique, which still imposes restrictions on time analysis. ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2024. Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
Publisher
Kluwer Academic Publishers
United States
Publication History
Published: 10 April 2024
Accepted: 26 February 2024
Received: 07 June 2023
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 28 Sep 2024
Other Metrics
Citations
View Options
View options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in