Control design for untimed Petri nets using Markov Decision Processes

• Authors: DAOUI Cherki , LEFEBVRE Dimitri
• Languages of publication: EN

Abstracts

EN

Design of control sequences for discrete event systems (DESs) has been presented modelled by untimed Petri nets (PNs). PNs are well-known mathematical and graphical models that are widely used to describe distributed DESs, including choices, synchronizations and parallelisms. The domains of application include, but are not restricted to, manufacturing systems, computer science and transportation networks. We are motivated by the observation that such systems need to plan their production or services. The paper is more particularly concerned with control issues in uncertain environments when unexpected events occur or when control errors disturb the behaviour of the system. To deal with such uncertainties, a new approach based on discrete time Markov decision processes (MDPs) has been proposed that associates the modelling power of PNs with the planning power of MDPs. Finally, the simulation results illustrate the benefit of our method from the computational point of view.

Keywords

EN

discrete event systems; Petri nets; control design; Markov Decision Process; value iteration algorithm

• Publisher: Politechnika Wrocławska. Oficyna Wydawnicza Politechniki Wrocławskiej
• Journal: Operations Research and Decisions
• Year: 2017
• Volume: 27
• Issue: 4
• Pages: 27-43

Contributors

author

DAOUI Cherki

• Sultan Moulay Slimane University, TIAD, Avenue Mohamed V, Quartier Taqaddoum 591-23000 Béni Mellal, Morocco

author

LEFEBVRE Dimitri

• Normandie Université, UNIHAVRE, GREAH, 76600 Le Havre, 25 rue Philippe Lebon, France

References

• ABBAD M., DAOUI C., Hierarchical algorithms for discounted and weighted markov decision processes, Math. Meth. Oper. Res., 2003, 58 (2), 237–245.
• ALUR R., HENZINGER T., Reactive modules, Formal Meth. Syst. Des., 1999, 15 (1), 7–48. 42 C. DAOUI, D. LEFEBVRE
• BAKER K.R., TRIETSCH D., Principles of Sequencing and Scheduling, Wiley, 2009.
• BECCUTI M., FRANCESCHINIS G., HADDAD S., A framework to design and solve Markov decision Petri nets, Int. J. Perform. Eng., 2011, 7 (5), 417–442.
• BECCUTI M., FRANCESCHINIS G., HADDAD S., Markov decision Petri net and Markov decision wellformed net formalisms, Lecture Notes in Comp. Sci., 2007, 4546, 43–62.
• BECCUTI M., CODETTA-RAITERI D., FRANCESCHINIS G., HADDAD S., A framework to design and solve Markov decision well-formed net models, Proc. 4th IEEE Int. Conf. Quantitative Evaluation of Systems (QEST 2007), Scotland, UK, 2007, 165–166.
• BELLMAN R.E., Dynamic Programming, Princeton University Press, Princeton, NJ, 1957.
• CASSANDRAS C., Discrete event systems. Modeling and performance analysis, Aksen Ass. Inc. Pub., Homewood 1993.
• CHEN Y., LI Z., KHALGUI M., MOSBAHI O., Design of a maximally permissive liveness-enforcing Petri net supervisor for flexible manufacturing systems, IEEE Trans. Automation Science and Engineering, 2011, 8 (2), 374–393.
• DAOUI C., ABBAD M., TKIOUAT M., Exact decomposition approaches for Markov decision processes. A survey, Adv. Oper. Res., 2010, 1–19.
• DAVID R., ALLA H., Petri Nets and Grafcet. Tools for Modelling Discrete Events Systems, Prentice Hall, London 1992.
• EBOLI M.G., COZMAN F.G., Markov decision processes from colored Petri nets, SBIA 2010, Lecture Notes in Comp. Sci., Springer, 2010, 6404.
• FENG Y., XING K., GAO Z., WU Y., Transition cover-based robust Petri net controllers for automated manufacturing systems with a type of unreliable resources, IEEE Trans. Syst., Man Cyber. Syst., 2016, 1–11.
• GIVAN R., LEACH S., DEAN T., Bounded-parameter Markov decision processes, J. Art. Int., 2000, 122 (1–2), 71–109.
• JENG M.D., CHEN S.C., Heuristic search approach using approximate solutions to Petri Net state equations for scheduling flexible manufacturing systems, Int. J. Flex. Manuf. Syst., 1998, 10 (2), 139–162.
• LARACH A., DAOUI C., CHAfiK S., Accelerated decomposition techniques for large discounted Markov decision processes, J. Ind. Eng., Springer, 2017.
• LEFEBVRE D., On-line fault diagnosis with partially observed Petri nets, IEEE Trans. Aut. Control, 2014, 59 (7), 1919–1924.
• LEFEBVRE D., LECLERCQ E., Control design for trajectory tracking with untimed Petri nets, IEEE Trans. Aut. Control, 2015, 60 (7), 1921–1926.
• LEFEBVRE D., Approaching minimal time control sequences for timed Petri nets, IEEE Trans. Aut. Sci. Eng., 2016, 13 (2), 1215–1221.
• LEFEBVRE D., Deadlock-free scheduling for timed Petri net models combined with MPC and backtracking, Proc. IEEE WODES 2016, Control, Observation, Estimation and Diagnosis with Timed PNs, Xian, China, 2016, 466–471.
• LEFEBVRE D., Deadlock-free scheduling for flexible manufacturing systems using untimed Petri nets and model predictive control, Proc. IFAC – MIM, DES for Manufacturing Systems, Troyes, France, 2016.
• LEI H., XING K., HAN L., XIONG F., GE Z., Deadlock-free scheduling for flexible manufacturing systems using Petri nets and heuristic search, Comp. Ind. Eng., 2014, 72, 297–305.
• LEUNG Y.-T., Handbook of Scheduling. Algorithms, Models, and Performance Analysis, CRC Computer and Information Science Series, Chapman Hall, 2004.
• LOPEZ P., ROUBELLAT F., Production Scheduling, ISTE Wiley, London 2008.
• PUTERMAN M., Markov Decision Processes. Discrete Stochastic Dynamic Programming, Wiley, New York 1994.
• TUNCEL G., BAYHAN G.M., Applications of Petri nets in production scheduling. A review, Int. J. Adv. Manuf. Techn., 2007, 34, 762–773.
• WANG Q., WANG Z., Hybrid heuristic search based on Petri net for FMS scheduling, En. Proc., 2012, 17, 506–512.
• WIESEMANN W., KUHN D., RUSTEM B., Robust Markov decision processes, Math. Oper. Res., 2013, 138 (1), 153–183.
• YUE H., XING K., HU H., WU W., SU H., Petri-net-based robust supervisory control of automated manufacturing systems, Control Eng. Pract., 2016, 54, 176–189.

Identifiers

DOI

10.5277/ord170402