direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Discrete Event Systems

From Fachgebiet Regelungssysteme TU Berlin

Jump to: navigation, search

Contents

Description

Supervisory Control

The prime paradigm for control of purely logical discrete event systems is commonly referred to as supervisory control theory. It was first introduced by Ramadge and Wonham in the 1980s. Its purpose is to synthesize a least restrictive (or maximally permissive) feedback controller, if both plant and specification can be modelled by formal languages on a finite alphabet. Symbols in the alphabet correspond to the occurrence of discrete events, and typically only a subset of these events can be prevented by a controller. If plant and specification language are regular and can therefore be realized by deterministic finite automata (DFA), the optimal, i.e., least restrictive, solution can, at least in principle, be readily determined by a fixed point algorithm. Supervisory control theory is often used in the context of abstraction based controller synthesis, where plant abstractions are typically in the form of DFA. However, requiring that the specification can also be realized as a DFA is rather restrictive. We have therefore been working on extending supervisory control theory to a larger class of specifications, namely specifications that can be written as deterministic context free languages (DCFL). The class of DCFL contains the class of regular languages, and DCFL can be realized by deterministic pushdown automata (DPDA). First, in [1], we extended supervisory control theory on the language level to capture all relevant operational criteria and verified an approach to connect this implementation independent formalization of the control problem with specific algorithms operating on automata realizations. Based on this, we have provided an implementable algorithm solving the problem for the case where the specification is described by a DPDA [2], [3]. In the latter, we show that an earlier attempt to provide an optimal solution for a slightly more restrictive class of problems does not guarantee minimal restrictiveness.

Discrete Event Systems in a Dioid Framework

Timed event graphs (TEGs) are a special class of Petri nets that represent timed discrete event systems ruled by standard synchronization phenomena ("the i th occurrence of event a is, at the earliest, t time units after the j th occurrence of event b"). TEGs are often used for the event-based modeling of manufacturing systems and transportation networks. They admit a linear model in specific algebraic structures called dioids. Hence, by analogy with standard control theory, many modeling and control methods have been extended to this class of dynamic systems. In this context, in collaboration with Prof. Hardouin's team at the Université d'Angers (France), we have investigated various aspects. Motivated by problems in high-throughput screening systems, we investigated TEGs with negative t and i-j by introducing a dual product in the respective dioid and adapting available control results for this case [4] We improved the control strategy available for uncontrollable inputs by taking into account an input prediction [5]. Applied to manufacturing systems, this new controller leads to smaller intermediate buffers. Another interesting result allows, under some assumptions, to reduce energy consumption of manufacturing systems without degrading input-output performance [6]. Finally, a major contribution consists in extending the dioid-related modeling and control approaches to a more general class of timed discrete event systems which allows to represent asymmetric interactions between subsystems, with primary subsystems providing time window constraints for secondary ones without being affected by the latter ones [7]. This is a common phenomenon in transportation systems, where, e.g., the departures of buses would be synchronized by the arrival of trains, but not the other way round. Other promising applications for this extension are model predictive control for supply chains [8], [9] and road networks subject to traffic lights [10]. [11] investigates timed discrete event systems involving shared resources that are operated under a fixed prioritization policy. By introducing a signal denoting the number of resources available for competing subsystems at each instant of time, a modeling procedure is obtained. Using residuation theory, an optimal control policy is developed, where optimality is in the sense of a lexicographical order reflecting the chosen prioritization of subsystems.

Tutorials

In the context of the summer school of the European DISC project, three tutorial papers on modelling of logical discrete event phenomena by finite automata and on modelling, analysis and control of timed discrete event systems in dioid frameworks were published [12], [13], [14].

People involved

  • Anne-Kathrin Schmuck (now with Max-Planck-Institut für Softwaresysteme, Kaiserslautern
  • Sven Schneider (now with Hasso Plattner Institute Potsdam)
  • Thomas Brunsch (now with IAV, Berlin)
  • Xavier David-Henriet (now with Evonik, Hanau)
  • Soraia Moradi
  • Johannes Trunk
  • Jörg Raisch

Cooperation

  • Laurent Hardouin (Laboratoire d'Ingénierie des Systèmes Automatisés, Université d'Angers, France)
  • Bertrand Cottenceau (Laboratoire d'Ingénierie des Systèmes Automatisés, Université d'Angers, France)
  • Carlos Maia (Universidade Federal de Minas Gerais)
  • Uwe Nestmann (TU Berlin)

Publications

  1. S. Schneider, A.-K. Schmuck, U. Nestmann, J. Raisch. Reducing an Operational Supervisory Control Problem by Decomposition for Deterministic Pushdown Automata. In Proceedings of the 12th IFAC- IEEE International Workshop on Discrete Event Systems, page 214–221, 2014.
  2. A.-K. Schmuck, S. Schneider, J. Raisch, U. Nestmann. Extending Supervisory Controller Synthesis to Deterministic Pushdown Automata —Enforcing Controllability Least Restrictively. In Proceedings of the 12th IFAC- IEEE International Workshop on Discrete Event Systems, page 286–293, 2014.
  3. Schmuck, Anne-Kathrin, Schneider, Sven, Raisch, Jörg, Nestmann, Uwe. Supervisory control synthesis for deterministic context free specification languages. Discrete Event Dynamic Systems, pages 5–32, 2016.
  4. T. Brunsch, L. Hardouin, C. A. Maia, J. Raisch. Duality and interval analysis over idempotent semirings. Linear Algebra and its Applications, 437 (10):2436–2454, November 2012.
  5. X. David-Henriet, T. Brunsch, J. Raisch, L. Hardouin. Stock Reduction for Timed Event Graphs Based on Output Feedback. In 11th International Workshop on Discrete Event Systems (WODES 2012), Guadalajara, Mexico, October 2012.
  6. X. David-Henriet, L. Hardouin, J. Raisch, B. Cottenceau. Holding Time Maximization Preserving Output Performance for Timed Event Graphs. IEEE Transactions on Automatic Control, 59 (7):1968-1973, 2014.
  7. X. David-Henriet, L. Hardouin, J. Raisch, B. Cottenceau. Optimal Control for Timed Event Graphs under Partial Synchronization. In Proc. 52nd IEEE Conference on Decision and Control (CDC 2013), pages 7609-7614, Firenze, Italy, December 2013.
  8. X. David-Henriet, J. Raisch, L. Hardouin, B. Cottenceau. Modeling and Control for Max-Plus Systems with Partial Synchronization. In Proceedings of the 12th IFAC-IEEE International Workshop on Discrete Event Systems (WODES), Paris, France, pages 105-110, 2014.
  9. Xavier David-Henriet, Laurent Hardouin, Jörg Raisch, Bertrand Cottenceau. Model predictive control for discrete event systems with partial synchronization. Automatica, 70 pages 9 - 13, 2016.
  10. David-Henriet, X., Raisch, J., Hardouin, L., Cottenceau, B.. Modeling and control for (max, +)-linear systems with set-based constraints. In Automation Science and Engineering (CASE), 2015 IEEE International Conference on, pages 1369-1374, Aug 2015.
  11. S. Moradi, L. Hardouin, J. Raisch. Modeling and control of resource sharing problems in dioids. In 2016 13th International Workshop on Discrete Event Systems (WODES), pages 410-417, May 2016.
  12. J. Raisch. Modelling of Engineering Phenomena by Finite Automata. In Seatzu, Carla and Silva, Manuel and van Schuppen, Jan H., editor, Control of Discrete-Event Systems, volume 433 of Lecture Notes in Control and Information Sciences, 1, pages 3-22. Springer Berlin / Heidelberg, 2013.
  13. T. Brunsch, J. Raisch, L. Hardouin, O. Boutin. Discrete-Event Systems in a Dioid Framework: Modeling and Analysis. In Seatzu, Carla and Silva, Manuel and van Schuppen, Jan H., editor, Control of Discrete-Event Systems, volume 433 of Lecture Notes in Control and Information Sciences, 21, pages 431-450. Springer Berlin / Heidelberg, 2013.
  14. L. Hardouin, O. Boutin, B. Cottenceau, T. Brunsch, J. Raisch. Discrete-Event Systems in a Dioid Framework: Control Theory. In Seatzu, Carla and Silva, Manuel and van Schuppen, Jan H., editor, Control of Discrete-Event Systems, volume 433 of Lecture Notes in Control and Information Sciences, 22, pages 451-469. Springer Berlin / Heidelberg, 2013.

Recommend this page