Idempotent versions of Haar’s Lemma: links between comparison of discrete event systems with different state spaces and control

Mourad Ahmane; Laurent Truffet

Kybernetika (2007)

  • Volume: 43, Issue: 3, page 369-391
  • ISSN: 0023-5954

Abstract

top
Haar's Lemma (1918) deals with the algebraic characterization of the inclusion of polyhedral sets. This Lemma has been involved many times in automatic control of linear dynamical systems via positive invariance of polyhedrons. More recently, it has been used to characterize stochastic comparison w.r.t. linear/integral ordering of Markov (reward) chains. In this paper we develop a state space oriented approach to the control of Discrete Event Systems (DES) based on the remark that most of control constraints of practical interest are naturally expressed as the inclusion of two systems of linear (w.r.t. idempotent semiring or semifield operations) inequalities. Thus, we establish tropical version of Haar's Lemma to obtain the algebraic characterization of such inclusion. As in the linear case this Lemma exhibits the links between two apparently different problems: comparison of DES and control via positive invariance. Our approach to the control differs from the ones based on formal series and is a kind of dual approach of the geometric one recently developed. Control oriented applications of the main results of the paper are given. One of these applications concerns the study of transportation networks which evolve according to a time table. Although complexity of calculus is discussed the algorithmic implementation needs further work and is beyond the scope of this paper.

How to cite

top

Ahmane, Mourad, and Truffet, Laurent. "Idempotent versions of Haar’s Lemma: links between comparison of discrete event systems with different state spaces and control." Kybernetika 43.3 (2007): 369-391. <http://eudml.org/doc/33864>.

@article{Ahmane2007,
abstract = {Haar's Lemma (1918) deals with the algebraic characterization of the inclusion of polyhedral sets. This Lemma has been involved many times in automatic control of linear dynamical systems via positive invariance of polyhedrons. More recently, it has been used to characterize stochastic comparison w.r.t. linear/integral ordering of Markov (reward) chains. In this paper we develop a state space oriented approach to the control of Discrete Event Systems (DES) based on the remark that most of control constraints of practical interest are naturally expressed as the inclusion of two systems of linear (w.r.t. idempotent semiring or semifield operations) inequalities. Thus, we establish tropical version of Haar's Lemma to obtain the algebraic characterization of such inclusion. As in the linear case this Lemma exhibits the links between two apparently different problems: comparison of DES and control via positive invariance. Our approach to the control differs from the ones based on formal series and is a kind of dual approach of the geometric one recently developed. Control oriented applications of the main results of the paper are given. One of these applications concerns the study of transportation networks which evolve according to a time table. Although complexity of calculus is discussed the algorithmic implementation needs further work and is beyond the scope of this paper.},
author = {Ahmane, Mourad, Truffet, Laurent},
journal = {Kybernetika},
keywords = {max-plus algebra; control; monotonicity; positive invariance; residuation; duality; max-plus algebra; control; nonotonicity; positive invariance; residuation; duality},
language = {eng},
number = {3},
pages = {369-391},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Idempotent versions of Haar’s Lemma: links between comparison of discrete event systems with different state spaces and control},
url = {http://eudml.org/doc/33864},
volume = {43},
year = {2007},
}

TY - JOUR
AU - Ahmane, Mourad
AU - Truffet, Laurent
TI - Idempotent versions of Haar’s Lemma: links between comparison of discrete event systems with different state spaces and control
JO - Kybernetika
PY - 2007
PB - Institute of Information Theory and Automation AS CR
VL - 43
IS - 3
SP - 369
EP - 391
AB - Haar's Lemma (1918) deals with the algebraic characterization of the inclusion of polyhedral sets. This Lemma has been involved many times in automatic control of linear dynamical systems via positive invariance of polyhedrons. More recently, it has been used to characterize stochastic comparison w.r.t. linear/integral ordering of Markov (reward) chains. In this paper we develop a state space oriented approach to the control of Discrete Event Systems (DES) based on the remark that most of control constraints of practical interest are naturally expressed as the inclusion of two systems of linear (w.r.t. idempotent semiring or semifield operations) inequalities. Thus, we establish tropical version of Haar's Lemma to obtain the algebraic characterization of such inclusion. As in the linear case this Lemma exhibits the links between two apparently different problems: comparison of DES and control via positive invariance. Our approach to the control differs from the ones based on formal series and is a kind of dual approach of the geometric one recently developed. Control oriented applications of the main results of the paper are given. One of these applications concerns the study of transportation networks which evolve according to a time table. Although complexity of calculus is discussed the algorithmic implementation needs further work and is beyond the scope of this paper.
LA - eng
KW - max-plus algebra; control; monotonicity; positive invariance; residuation; duality; max-plus algebra; control; nonotonicity; positive invariance; residuation; duality
UR - http://eudml.org/doc/33864
ER -

References

top
  1. Ahmane M., Ledoux, J., Truffet L., Criteria for the comparison of discrete-time Markov chains, In: 13th Internat. Workshop on Matrices and Statistics in Celebration of I. Olkin’s 80th Birthday, Poland, August 18-21, 2004 
  2. Ahmane M., Ledoux, J., Truffet L., Positive invariance of polyhedrons and comparison of Markov reward models with different state spaces, In: Proc. Positive Systems: Theory and Applications (POSTA’06), Grenoble 2006 (Lecture Notes in Control and Information Sciences 341), Springer–Verlag, Berlin, pp. 153–160 Zbl1132.93333MR2250251
  3. Ahmane M., Truffet L., State feedback control via positive invariance for max-plus linear systems using -algorithm, In: 11th IEEE Internat. Conference on Emerging Technologies and Factory Automation, ETFA’06, Prague 2006 
  4. Ahmane M., Truffet L., Sufficient condition of max-plus ellipsoidal invariant set and computation of feedback control of discrete events systems, In: 3rd Internat. Conference on Informatics in Control, Automation and Robotics, ICINCO’06, Setubal 2006 
  5. Aubin J.-P., Viability Theory, Birkhäuser, Basel 1991 MR1134779
  6. Baccelli F., Cohen G., Olsder G. J., Quadrat J.-P., Synchronization and Linearity, Wiley, New York 1992 Zbl0824.93003MR1204266
  7. Bertsekas D. P., Rhodes I. B., On the minimax reachability of target sets and target tubes, Automatica 7 (1971), 233–247 (1971) Zbl0215.21801MR0322648
  8. Blyth T. S., Janowitz M. F., Residuation Theory, Pergamon Press, 1972 Zbl0301.06001MR0396359
  9. Braker J. G., Max-algebra modelling and analysis of time-table dependent networks, In: Proc. 1st European Control Conference, Grenoble 1991, pp. 1831–1836 (1991) 
  10. Butkovic P., Zimmermann K., A strongly polynomial algorithm for solving two-wided linear systems in max-algebra, Discrete Appl. Math. 154 (2006), 437–446 MR2203194
  11. Cochet-Terrasson J., Gaubert, S., Gunawardena J., A constructive fixed point theorem for min-max functions, Dynamics Stability Systems 14 (1999), 4, 407–433 (1999) Zbl0958.47028MR1746112
  12. Cohen G., Gaubert, S., Quadrat J.-P., Duality and separation theorems in idempotent semimodules, Linear Algebra Appl. 379 (2004), 395–422 Zbl1042.46004MR2039751
  13. Costan A., Gaubert S., Goubault, E., Putot S., A policy iteration algorithm for computing fixed points in static analysis of programs, In: CAV’05, Edinburgh 2005 (Lecture Notes in Computer Science 3576), Springer–Verlag, Berlin, pp. 462–475 Zbl1081.68616
  14. Cuninghame-Green R. A., Butkovic P., The equation over , Theoret. Comp. Sci. 293 (2003), 3–12 Zbl1021.65022MR1957609
  15. Vries R. de, Schutter, B. De, Moor B. De, On max-algebraic models for transportation networks, In: Proc. Internat. Workshop on Discrete Event Systems (WODES’98), Cagliari 1998, pp. 457–462 (1998) 
  16. Farkas J., Über der einfachen Ungleichungen, J. Reine Angew. Math. 124 (1902), 1–27 (1902) 
  17. Gaubert S., Gunawardena J., The duality theorem for min-max functions, Comptes Rendus Acad. Sci. 326 (1999), Série I, 43–48 (1999) MR1649473
  18. Gaubert S., Katz R., Rational semimodules over the max-plus semiring and geometric approach of discrete event systems, Kybernetika 40 (2004), 2, 153–180 MR2069176
  19. Golan J. S., The theory of semirings with applications in mathematics and theoretical computer science, Longman Sci. & Tech. 54 (1992) (1992) Zbl0780.16036MR1163371
  20. Haar A., Über Lineare Ungleichungen, 1918. Reprinted in: A. Haar, Gesammelte Arbeiten, Akademi Kiadó, Budapest 1959 
  21. Hennet J. C., Une Extension du Lemme de Farkas et Son Application au Problème de Régulation Linéaire sous Contraintes, Comptes Rendus Acad. Sci. 308 (1989), Série I, pp. 415–419 (1989) MR0992520
  22. Hiriart-Urruty J.-B., Lemarechal C., Fundamentals of Convex Analysis, Springer–Verlag, Berlin 2001 Zbl0998.49001MR1865628
  23. Katz R. D., Max-plus (A,B)-invariant and control of discrete event systems, To appear in IEEE TAC, 2005, arXiv:math.OC/0503448 
  24. Klimann I., A solution to the problem of (A,B)-invariance for series, Theoret. Comput. Sci. 293 (2003), 1, 115–139 Zbl1025.68050MR1957615
  25. Ledoux J., Truffet L., Comparison and aggregation of max-plus linear systems, Linear Algebra. Appl. 378 (2004), 1, 245–272 Zbl1052.15014MR2031795
  26. Lhommeau M., Etude de Systèmes à Evénements Discrets: 1, Synthèse de Correcteurs Robustes dans un Dioide d’Intervalles. 2. Synthèse de Correcteurs en Présence de Perturbations. PhD Thesis, Université d’Angers ISTIA 2003 
  27. Lhommeau M., Hardouin, L., Cottenceau B., Optimal control for (Max,+)-linear systems in the presence of disturbances, In: Proc. Positive Systems: Theory and Applications (POSTA’03), Roma 2003 (Lecture Notes in Control and Information Sciences 294), Springer–Verlag, Berlin, pp. 47–54 Zbl1059.93090MR2019300
  28. Muller A., Stoyan D., Comparison Methods for Stochastic Models and Risks, Wiley, New York 2002 MR1889865
  29. Dam A. A. ten, Nieuwenhuis J. W., A linear programming algorithm for invariant polyhedral sets of discrete-time linear systems, Systems Control Lett. 25 (1995), 337–341 (1995) MR1343218
  30. Truffet L., Monotone linear dynamical systems over dioids, In: Proc. Positive Systems: Theory and Applications (POSTA’03), Roma 2003 (Lecture Notes in Control and Information Sciences 294), Springer–Verlag, Berlin pp. 39–46 Zbl1059.93093MR2019299
  31. Truffet L., Some ideas to compare Bellman chains, Kybernetika 39 (2003), 2, 155–163. (Special Issue on max-plus Algebra) MR1996554
  32. Truffet L., Exploring positively invariant sets by linear systems over idempotent semirings, IMA J. Math. Control Inform. 21 (2004), 307–322 Zbl1098.93025MR2076223
  33. Truffet L., New bounds for timed event graphs inspired by stochastic majorization results, Discrete Event Dyn. Systems 14 (2004), 355–380 Zbl1073.93039MR2092597
  34. Wagneur E., Duality in the max-algebra, In: IFAC, Commande et Structures des Systèmes, Nantes 1998, pp. 707–711 (1998) 

NotesEmbed ?

top

You must be logged in to post comments.