SpringerLink
Log in

Approximated timed reachability graphs for the robust control of discrete event systems

  • Published:
Discrete Event Dynamic Systems Aims and scope Submit manuscript

Abstract

This paper is about control sequences design for Discrete Event Systems (DES) modeled with Time Petri nets (TPN) including a set of temporal specifications. Petri nets are known as efficient mathematical and graphical models that are widely used to describe distributed DES including choices, synchronizations and parallelisms. The domains of application include but are not restricted to manufacturing systems, computer science and transportation networks. Incorporating the time in the model is important to consider many control problems such as scheduling and planning. This paper solves some control issues in timed context and uncertain environments that include unexpected events modeled with uncontrollable transitions. To deal with such uncertainties, we propose first to build an Approximated Timed Reachability Graph that includes the time specifications and model all feasible timed trajectories at a given accuracy under earliest firing policy. Then, this graph is used to search optimal paths by using an approach based on Markov Decision Processes that encode the environment uncertainties. Such optimal paths lead to near-optimal solutions for the TPN. Several simulations illustrate the benefit of the proposed method from the performance and computational points of view.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (France)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13

Similar content being viewed by others

References

  • Alur R, Henzinger T (1999) Reactive modules. Formal Methods in System Design 15(1):7–48

    Article  Google Scholar 

  • Baker KR, Trietsch D (2009) Principles of Sequencing and Scheduling. Wiley

  • Basile F, Cabasino MP, Seatzu C (2015) State estimation and fault diagnosis of labeled time petri net systems with unobservable transitions. IEEE Trans Autom Control 60(4):997–1009

    Article  MathSciNet  MATH  Google Scholar 

  • Beccuti M, Franceschinis G, Haddad S (2007a) Markov decision petri net and Markov decision well-formed net formalisms. LNCS 4546:43–62

    MathSciNet  MATH  Google Scholar 

  • Beccuti M., Codetta-Raiteri D, Franceschinis G, Haddad S (2007b) A framework to design and solve Markov Decision Well-formed Net models. In Proc. of the 4th IEEE Int. Conf. on Quantitative Evaluation of Systems (QEST’07); 165–166, Edinburgh, Scotland, UK

  • Beccuti M, Franceschinis G, Haddad S (2011) A framework to design and solve Markov decision petri nets. IJPE 7(5):417–442

    Google Scholar 

  • Bellman RE (1957) Dynamic programming. Princeton University Press, Princeton

    MATH  Google Scholar 

  • Berthomieu B, Diaz M (1991) Modeling and verification of time dependent systems using time petri nets. IEEE T Software Eng 17(3):259–273

    Article  MathSciNet  Google Scholar 

  • Berthomieu B, Menasche M (1983) An enumerative approach for analyzing time petri nets. In IFIP Congress, pages 41–46

  • Berthomieu B, Vernadat F (2003) State class constructions for branching analysis of time petri nets. In TACAS 2003, volume 2619 of LNCS, pages 442–457. Springer

  • Cassandras C (1993) Discrete event systems: modeling and performances analysis. Aksen Ass. Inc. Pub.

  • Chen Y, Li Z, Khalgui M, Mosbahi O (2011) Design of a Maximally Permissive Liveness-Enforcing Petri net Supervisor for flexible manufacturing systems. IEEE Trans Autom Sci Eng 8(2):374–393

    Article  Google Scholar 

  • Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms. MIT Press and McGraw-Hill

  • Daoui C, Abbad M, Tkiouat M (2010) Exact decomposition approaches for Markov decision processes: a survey. Advances in Operations Research 2010:1–19

    Article  MATH  Google Scholar 

  • David R, Alla H (1992) Petri nets and grafcet – tools for modelling discrete events systems. Prentice Hall, London

    MATH  Google Scholar 

  • Dijkstra EW (1971) A short introduction to the art of programming

  • Eboli MG, Cozman FG (2010) Markov decision processes from colored petri nets, SBIA 2010. Lecture Notes in Computer Science, vol 6404. Springer

  • Gardey G, Roux OH, Roux OF (2003) Using zone graph method for computing the state space of a time petri net. In FORMATS 2003, volume 2791 of LNCS, pages 246–259. Springer

  • Haddad S, Moreaux P (2009) Stochastic Petri Nets (Chapter 7), In Petri Nets: Fundamental Models and Applications. Wiley

  • Heidari P, Boucheneb H (2012) Maximally permissive controller synthesis for time petri nets. Int J Control

  • Heidari P, Boucheneb H (2013) Controller synthesis of time petri nets using stopwatch, Journal of Engineering, Hindawi Publishing Corporation, Article ID 970487

  • Jeng MD, Chen SC (1998) Heuristic search approach using approximate solutions to petri net state equations for scheduling flexible manufacturing systems. Int J FMS 10(2):139–162

    Google Scholar 

  • Klai K, Aber N, Petrucci L (2013) A new approach to abstract reachability state space of time petri nets. 20th International Symposium on Temporal Representation and Reasoning

  • Lee DY, DiCesare F (1994) Scheduling flexible manufacturing systems using petri nets and heuristic search. IEEE Trans Robot Autom 10(2):123–133

    Article  Google Scholar 

  • Lefebvre D (2016a) Approaching minimal time control sequences for timed petri nets. IEEE Trans Autom Sci Eng 13(2):1215–1221

    Article  Google Scholar 

  • Lefebvre D (2016b) Deadlock-free scheduling for Timed Petri Net models combined with MPC and backtracking. Proc. IEEE WODES 2016, Invited session “Control, Observation, Estimation and Diagnosis with Timed PN”, pp. 466-471, **’an, China

  • Lefebvre D, Leclercq E (2015) Control design for trajectory tracking with untimed petri nets. IEEE Trans Autom Control 60(7):1921–1926

    Article  MathSciNet  MATH  Google Scholar 

  • Lei H, **ng K, Han L, **ong F, Ge Z (2014) Deadlock-free scheduling for flexible manufacturing systems using petri nets and heuristic search. Comput Ind Eng 72:297–305

    Article  Google Scholar 

  • Leung Y-T (2004) Handbook of Scheduling: Algorithms, Models, and Performance Analysis. Chapman & Hall/CRC Computer & Information Science Series

  • Lime D, Roux OH (2006) Model checking of time petri nets using the state class timed automaton. DEDS 16(2):179–205

    MathSciNet  MATH  Google Scholar 

  • Lopez P, Roubellat F (2008) Production scheduling. ISTE/Wiley, London

    Book  Google Scholar 

  • Mejia G, Nino K (2017) A new hybrid filtered beam search algorithm for deadlock-free scheduling of flexible manufacturing systems using petri nets. Comput Ind Eng 108:165–176

    Article  Google Scholar 

  • Merlin P, Faber DJ (1976) Recoverability of communication protocols. IEEE Trans Commun 24(9):1036–1043

    Article  MATH  Google Scholar 

  • Pan L, Ding Z, Zhou MC (2014) A configurable state class method for temporal analysis of time petri nets. IEEE Trans Syst Man Cybern Syst 44(4):482–493

    Article  Google Scholar 

  • Puterman M (1994) Markov decision processes: discrete stochastic dynamic programming. Wiley, New York

    Book  MATH  Google Scholar 

  • Ramchandani C (1973) Analysis of asynchronous concurrent systems by timed petri nets. Ph. D, MIT, USA

  • Reyes-Moro A, Hu H, Kelleher G (2002) Hybrid heuristic search for the scheduling of flexible manufacturing systems using petri nets. IEEE Trans Robot Autom 18(2):240–245

    Article  Google Scholar 

  • Tarek A, Lopez-Benitez N (2004) Optimal legal firing sequence of petri nets using linear programming. Optim Eng 5:25–43

    Article  MathSciNet  MATH  Google Scholar 

  • Tuncel G, Bayhan GM (2007) Applications of petri nets in production scheduling: a review. Int J Adv Manuf Technol 34:762–773

    Article  Google Scholar 

Download references

Acknowledgements

The Project MRT MADNESS 2016-2019 has been funded with the support from the European Union with the European Regional Development Fund (ERDF) and from the Regional Council of Normandie.

Author information

Authors and Affiliations

  1. UNIHAVRE, GREAH, Normandie University, 76600, Le Havre, France

    Dimitri Lefebvre

Authors
  1. Dimitri Lefebvre
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Dimitri Lefebvre.

Additional information

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Lefebvre, D. Approximated timed reachability graphs for the robust control of discrete event systems. Discrete Event Dyn Syst 29, 31–56 (2019). https://doi.org/10.1007/s10626-019-00275-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10626-019-00275-z

Keywords

Search

Navigation