Hierarchical control of decentralized discrete event systems [Elektronische Ressource] : theory and application / vorgelegt von Klaus Schmidt

Informations

• Publié par: friedrich-alexander-universitat_erlangen-nurnberg
• Publié le: 01 janvier 2005
• Nombre de lectures: 3
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Hierarchical Control of Decentralized Discrete Event Systems
Theory and Application
Der Technischen Fakultät der
Universität Erlangen-Nürnberg
zur Erlangung des Grades
DOKTOR-INGENIEUR
vorgelegt von
Klaus Schmidt
Erlangen 2005Als Dissertation genehmigt von
der Technischen Fakultät der
Universität Erlangen-Nürnberg
Tag der Einreichung: 23. 05. 2005
Tag der Promotion: 11. 07. 2005
Dekan: Prof. Dr. rer. nat. A. Winnacker
Berichterstatter: Prof. Dr.-Ing. T. Moor
Prof. Bruce KroghAcknowledgement
At first I would like to thank my thesis advisor Prof. Dr.-Ing. Thomas Moor for his interest in
my work and for his helpful and constructive comments and ideas. Further on I want to highlight
the hospitality of Prof. Bruce Krogh who gave me the opportunity to participate in his research
activites on various topics at the Carnegie Mellon University in Pittsburgh.
I am grateful to Prof. Dr.-Ing. Günter Roppenecker, the chairman of my Ph.D. committee, for
supporting my work at the Lehrstuhl für Regelungstechnik and for encouraging my studies and
research abroad. Also I want to thank Prof. Dr.-Ing. Christoph Plaum for his participation in the
Ph.D. committee as the external faculty member.
It was very important for my scientific career to work with my colleague Dr. Ing. Johann Reger who
introduced me to the area of discrete event systems. Along the same lines I would like to thank my
former student and colleague Dipl.-Ing. Sebastian Perk for his collaboration, and my colleagues
Dipl.-Ing. Felix Antritter, Dr.-Ing. Joachim Deutscher and Dipl.-Ing. Gerald Drenckhahn for their
friendship.
In particular I would like to express my gratitude to my family for their constant love, availability
and support, and I would like to thank my parents-in-law for their encouragment and trust. Finally
my love and gratefulness goes to my wife for sharing my academic interests as well as my life and
for her love and care during the final time of my thesis work.
Erlangen, July 2005 Klaus SchmidtIVTable of Contents
1 Introduction 1
2 Basics of RW Supervisory Control Theory 9
2.1 Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.1 General Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.2 Regular Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2 Automata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3 Supervisory Control in a Language based Framework . . . . . . . . . . . . . . . . 20
2.3.1 Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3.2 Controllability and Nonblocking Control . . . . . . . . . . . . . . . . . . 23
2.4 Automata Representation in Supervisory Control . . . . . . . . . . . . . . . . . . 27
3 Nonblocking Hierarchical Control 31
3.1 Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2 Hierarchical Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.3 Nonblocking Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.3.1 Condition on the High-level Closed Loop . . . . . . . . . . . . . . . . . . 43
3.3.2 Structural Condition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.4 Hierarchical Control For Finite Automata . . . . . . . . . . . . . . . . . . . . . . 48
3.4.1 Natural Projection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.4.2 Algorithmic Verification of Marked String Acceptance . . . . . . . . . . . 53
3.4.3 Algorithmic Verification of the Locally Nonblocking Condition . . . . . . 56VI TABLE OF CONTENTS
3.4.4 Algorithmic Verification of Liveness . . . . . . . . . . . . . . . . . . . . . 59
3.4.5 Algorithmic Verification of Marked String Controllability . . . . . . . . . 59
3.4.6 Evaluation of the Hierarchical Approach . . . . . . . . . . . . . . . . . . . 63
4 Hierarchical and Decentralized Control 65
4.1 Hierarchical and Decentralized Control Architecture . . . . . . . . . . . . . . . . 66
4.2 Hierarchical Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.3 Nonblocking Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.3.1 Condition on the High-Level Closed Loop Subsystems . . . . . . . . . . . 75
4.3.2 Structural Condition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.4 Automata Implementation for the Decentralized Case . . . . . . . . . . . . . . . . 79
4.4.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.4.2 Feasible Projected Decentralized Control Systems . . . . . . . . . . . . . 79
4.4.3 Marked String Acceptance and Locally Nonblocking Condition . . . . . . 82
4.4.4 Liveness and Marked String Controllability . . . . . . . . . . . . . . . . . 82
4.4.5 Supervisor Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5 Manufacturing System Case Study 85
5.1 Manufacturing System Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.3 Supervisor Synthesis for the Distribution System . . . . . . . . . . . . . . . . . . 88
5.3.1 Stack Feeder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
5.3.2 Conveyor Belt cb1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.3.3 Conveyor Belts cb2 and cb3 . . . . . . . . . . . . . . . . . . . . . . . . . 97
5.3.4 Overall Distribution System . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.3.5 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
5.4 Controller Design for the Manufacturing System . . . . . . . . . . . . . . . . . . 102
5.4.1 Production Cell pc1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.4.2 exit1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107VII
5.4.3 exit2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
5.4.4 Production Cell pc2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
5.4.5 Interchange System ics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
5.4.6 Overall Manufacturing System . . . . . . . . . . . . . . . . . . . . . . . . 118
5.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
6 Conclusions 121
Appendix 123
A Proofs 123
A.1 Projection of a Regular Language . . . . . . . . . . . . . . . . . . . . . . . . . . 123
A.2 Computation of the Projection . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
A.2.1 Space Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
A.2.2 Time Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
A.3 Computation of the High-Level Plant . . . . . . . . . . . . . . . . . . . . . . . . . 126
A.4 Feasible Projected Decentralized Control Systems . . . . . . . . . . . . . . . . . . 127
A.5 Mutual Controllability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
B Table of Events 130VIII TABLE OF CONTENTSZusammenfassung
Gegenstand dieser Arbeit ist der hierarchische und dezentrale Steuerungsentwurf für ereignisdis-
krete Systeme (DES). Ereignisdiskrete Systeme besitzen einen diskreten Zustandsraum und auch
die Zeitwerte sind als diskrete Zeitpunkte aufzufassen. Das dynamische Verhalten von DES ist
dabei ereignisgetrieben, das heißt diskrete Zustandsänderungen werden durch das Auftreten asyn-
chroner Ereignisse verursacht.
Mitte der 80er Jahre wurde von P.J. Ramadge und W.M. Wonham eine Steuerungstheorie (RW-
Steuerungstheorie) für ereignisdiskrete Systeme entwickelt. Ereignisdiskrete Systeme werden durch
formale Sprachen über dem Alphabet der Systemereignisse charakterisiert, wobei die Sprache
selbst die Systemtrajektorien beschreibt. Durch Verhindern sogenannter “steuerbarer“ Ereignisse
kann das Systemverhalten eingeschränkt werden, um einem spezifizierten Verhalten zu genügen.
Da ereignisdiskrete Systeme sehr viele Zustände haben können, ist die RW-Steuerungstheorie für
große zusammengesetzte Systeme nicht direkt anwendbar. Aufgrund dessen werden in der Lite-
ratur verschiedene Ansätze — modulare, dezentrale und hierarchische Ansätze — untersucht, um
durch die Ausnutzung der Systemstruktur die theoretischen Ergebnisse der RW-Steuerungstheorie
umzusetzen.
Unser Ansatz verbindet dabei dezentrale und hierarchische Verfahren, um die RW-Steuerungs-
theorie für große ereignisdiskrete Systeme zu erweitern. Es wird ausgenutzt, dass große DES aus
vielen Systemkomponenten zusammengesetzt sind, welche interagieren. Die einzelnen Kompo-
nenten werden lokal gesteuert und dann auf das für die Interaktion relevante Verhalten abstrahiert.
Die abstrahierten dezentralen Systemmodelle werden in einem höheren Level der Hierarchie zu-
sammengesetzt und dort gesteuert. Diese mit geringerem Rechenaufwand ermittelte Steuerung
wird dann in dezentrale Steuerungen im unteren Level der Hierarchie übersetzt. Unser Verfahren
stellt dabei strukturelle Bedingungen an die Komponentenmodelle sowie ihre Abstraktionen. Sind
diese Bedingungen erfüllt, so garantiert unsere Methode hierarchisch konsistentes sowie blockie-
rungsfreies Verhalt