State estimation plays an important role in the field of system supervisory control. With the increase in the scale and complexity of practical systems, problems of state/event estimation for discrete event systems in Petri nets have attracted significant attention. One of the well-studied problems is how to estimate the minimum initial markings (MIMs) in a known labeled Petri net based on the observation of its event sequence. The existing approaches have disadvantages such as (1) much higher computational complexity in order to increase the MIM quantity; and (2) much fewer MIMs in order to decrease the computational complexity. In this paper, a variant of simulated annealing (SA) algorithm is developed to determine the set of MIMs. We take advantage of SA for global search in the problem’s search space to find initial markings that are minimal in their token counts, and then use the selection strategy of SA to determine MIMs from them. Finally, the effectiveness of the proposed method is illustrated through two simulation experiments of industrial applications. Comparisons with existing work are conducted to demonstrate the merits of our method.
WonhamWMCaiKRudieK.Supervisory control of discrete-event systems: a brief history. Annu Rev Control2018; 45: 250–256.
2.
SilvaM.On the history of discrete event systems. Annu Rev Control2018; 45: 213–222.
3.
LefebvreD.Algorithms of reduced complexity to design control sequences for untimed Petri nets in varying and uncertain environments. Proc IMechE, Part I: J Systems and Control Engineering2018; 232(6): 638–651.
4.
YouDWangSZhouM, et al. Supervisory control of Petri nets in the presence of replacement attacks. IEEE Trans Automat Contr2022; 67(3): 1466–1473.
5.
BasileFDe TommasiGSterleC.Noninterference enforcement via supervisory control in bounded Petri nets. IEEE Trans Automat Contr2021; 66(8): 3653–3666.
6.
GaiedMMhallaALefebvreD, et al. Robust control for railway transport networks based on stochastic P-timed Petri net models. Proc IMechE, Part I: J Systems and Control Engineering2019; 233(7): 830–846.
7.
CongXFantiMPManginiAM, et al. Decentralized diagnosis by Petri nets and integer linear programming. IEEE Trans Syst Man Cybern Syst2018; 48(10): 1689–1700.
8.
RanNHaoJSeatzuC.Prognosability analysis and enforcement of bounded labeled Petri nets. IEEE Trans Automat Contr2022; 67(10): 5541–5547.
9.
WuJYanSGuY.Fault severity analysis of the time-dependent mechanical systems by the revised time Petri net. Proc IMechE, Part I: J Systems and Control Engineering2014; 228(4): 207–220.
10.
LiJYuXZhouM.Analysis of unbounded Petri net with lean reachability trees. IEEE Trans Syst Man Cybern Syst2020; 50(6): 2007–2016.
11.
WuNQiaoYLiZ, et al. A novel control theory-based approach to scheduling of high-throughput screening system for enzymatic assay. IEEE Trans Syst Man Cybern Syst2022; 52(12): 7667–7678.
12.
DotoliMEpicocoNFalagarioM, et al. A decision support system for optimizing operations at intermodal railroad terminals. IEEE Trans Syst Man Cybern Syst2017; 47(3): 487–501.
13.
KiaeiILotfifardS.Fault section identification in smart distribution systems using multisource data based on fuzzy Petri nets. IEEE Trans Smart Grid2020; 11(1): 74–83.
14.
KuTTLiCSLinCH, et al. Faulty line-section identification method fordistribution systems based on fault indicators. IEEE Trans Ind Appl2021; 57(2): 1335–1343.
15.
LafortuneSLinFHadjicostisCN.On the history of diagnosability and opacity in discrete event systems. Annu Rev Control2018; 45: 257–266.
16.
TongYLiZSeatzuC, et al. Current-state opacity enforcement in discrete event systems under incomparable observations. Discrete Event Dyn Syst2018; 28: 161–182.
17.
DeclerckPBonhommeP.State estimation of timed labeled Petri nets with unobservable transitions. IEEE Trans Autom Sci Eng2014; 11(1): 103–110.
18.
YueHChenJWangC, et al. Minimum initial marking estimation in labeled Petri nets for required resource minimization of automated manufacturing systems. IEEJ Trans Electr Electron Eng2025. DOI: 10.1002/tee.70044.
19.
LiLHadjicostisCN.Minimum initial marking estimation in labeled Petri nets. IEEE Trans Automat Contr2013; 58(1): 198–203.
20.
YueHWangCZhaoZ, et al. Engineering efficiency unleashed: minimum initial marking estimation in labeled Petri nets through a cutting-edge hybrid evolutionary heuristic. Eng Comput2025; 42(3): 1267–1284.
21.
YeJLiZChenX.An algorithm for the minimum initial marking problem of a structurally live Petri net with inhibitor arcs. IEEJ Trans Electr Electron Eng2016; 11(5): 586–592.
22.
WangSWangCYuY, et al. An algorithm to find the minimal initial markings of resource places ensuring liveness of finite-capacity SPR. Int J Prod Res2012; 50(6): 1528–1538.
23.
OchiiwaSTaokaSYamauchiM, et al. Two enhanced heuristic algorithms for the minimum initial marking problem of Petri nets. IEICE Trans Fundam Electron Commun Comput Sci2009; E92.A(11): 2732–2744.
24.
ZhuGFengLLiZ, et al. An efficient fault diagnosis approach based on integer linear programming for labeled Petri nets. IEEE Trans Automat Contr2021; 66(5): 2393–2398.
25.
AbdellatifAJabeur TelmoudiABonhommeP, et al. Minimum initial marking estimation of labeled Petri nets based on GRASP inspired method (GMIM). Cybern Syst2020; 51(4): 467–484.
26.
KmimechHTelmoudiAJSlimanL, et al. Genetic-based approach for minimum initial marking estimation in labeled Petri nets. IEEE Access2020; 8: 22854–22861.
27.
MaZLiZGiuaA.Marking estimation in a class of time labeled Petri nets. IEEE Trans Automat Contr2020; 65(2): 493–506.
28.
MaZZhuGLiZ.Marking estimation in Petri nets using hierarchical basis reachability graphs. IEEE Trans Automat Contr2021; 66(2): 810–817.
29.
MaZYinXLiZ.Marking predictability and prediction in labeled Petri nets. IEEE Trans Automat Contr2021; 66(8): 3608–3623.
30.
CabasinoMPHadjicostisCNSeatzuC.Probabilistic marking estimation in labeled Petri nets. IEEE Trans Automat Contr2015; 60(2): 528–533.
31.
CabasinoMPHadjicostisCNSeatzuC.Marking observer in labeled Petri nets with application to supervisory control. IEEE Trans Automat Contr2017; 62(4): 1813–1824.
32.
FengYRenSXingK, et al. Configuration of liveness-enforcing initial marking with the minimum resources for resource allocation systems. Inf Sci2025; 691: 121623.
33.
YueHXuYHuH, et al. Minimum initial marking estimation in labeled Petri nets using minimum token number prediction. IEEE Trans Automat Contr2025; 70: 3296–3302.
34.
YueHXuYXingK, et al. Minimum initial marking estimation in labeled Petri nets with unobservable transitions based on minimal explanations. IEEE Trans Syst Man Cybern Syst2025; 54: 3427–3438.
35.
GamMAbdellatifATelmoudiAJ, et al. Minimum initial marking estimation in labeled Petri nets through genetic algorithm and tabu search. In: International conference on advanced systems and emergent technologies IEEE, 2020. DOI: 10.1109/ICASET49463.2020.9318298.
36.
LiJLefebvreDHadjicostisCN, et al. Verification of state-based timed opacity for constant-time labeled automata. IEEE Trans Automat Contr2025; 70(1): 503–509.
37.
LefebvreDHadjicostisCN.Exposure and revelation times as a measure of opacity in timed stochastic discrete event systems. IEEE Trans Automat Contr2021; 66(12): 5802–5815.
38.
AnLYangGH.Enhancement of opacity for distributed state estimation in cyber-physical systems. Automatica2022; 136: 110087.
39.
RanNLiTHeZ, et al. Codiagnosability enforcement in labeled Petri nets. IEEE Trans Automat Contr2023; 68(4): 2436–2443.
40.
LiBKhlif-BouassidaMToguyeniA.Reduction rules for diagnosability analysis of complex systems modeled by labeled Petri nets. IEEE Trans Autom Sci Eng2020; 17(2): 1061–1069.
41.
DengWQiuD. State-based fault diagnosis of discrete-event systems. In: 2016 Chinese control and decision conference (CCDC), 2016, pp.5470–5475. DOI: 10.1109/CCDC.2016.7531974.
42.
YinX.Initial-state detectability of stochastic discrete-event systems with probabilistic sensor failures. Automatica2017; 80: 127–134.
43.
LaiALahayeSGiuaA.State estimation of max-plus automata with unobservable events. Automatica2019; 105: 36–42.
44.
LiLDengMLiuB, et al. State estimation in labeled time Petri net systems using observed modified state class graph. Inf Sci2024; 656: 119922.
45.
BasileFCabasinoMPSeatzuC.State estimation and fault diagnosis of labeled time Petri net systems with unobservable transitions. IEEE Trans Automat Contr2015; 60(4): 997–1009.
46.
BonhommeP.Decentralized state estimation and diagnosis of P-time labeled Petri nets systems. Discrete Event Dyn Syst2021; 31: 137–162.
47.
LefebvreDSeatzuCHadjicostisCN, et al. Probabilistic state estimation for labeled continuous time markov models with applications to attack detection. Discrete Event Dyn Syst2022; 32: 65–544.
48.
AnDZhangFCuiF, et al. Toward data integrity attacks against distributed dynamic state estimation in smart grid. IEEE Trans Autom Sci Eng2023; 21(1): 881–894.
49.
MolaeiANikoofardASedighAK, et al. Parameter and state estimation of managed pressure drilling system using the optimization based supervisory framework. IEEE Trans Control Syst Technol2023; 31(6): 2937–2944.
50.
GiuaASeatzuCCoronaD.Marking estimation of Petri nets with silent transitions. IEEE Trans Automat Contr2007; 52(9): 1695–1699.
51.
BonhommeP.Marking estimation of P-time Petri nets with unobservable transitions. IEEE Trans Syst Man Cybern Syst2015; 45(3): 508–518.
52.
KirkpatrickSGelattCDVecchiMP.Optimization by simmulated annealing. Science1983; 42(3): 671–680.
53.
PengSRippelDBeckerM, et al. Scheduling of offshore wind farm installation using simulated annealing. IFAC-PapersOnLine2021; 54(1): 325–330.
54.
ZamanTUMacLachlanSPOlsonLN, et al. Coarse-grid selection using simulated annealing. J Comput Appl Math2023; 431: 115263.
55.
NguyenLTKimJShimB.Gradual federated learning with simulated annealing. IEEE Trans Signal Process2021; 69: 6299–6313.
56.
KmimechHTelmoudiAJSlimanL, et al. Minimum initial marking estimation in labeled Petri nets using simulated annealing. In: International conference on new trends in intelligent software methodologies, tools and techniques, 2019.
57.
GiuaA.Petri net state estimators based on event observation. In: Proc. 36th IEEE int. conf. decision control, December 1997, vol. 4, pp.4086–4091.
