DE69626964T2

DE69626964T2 - Verfahren zur Steuerung eines Prozessablaufs nach von einem Rechner spezifizierten Verhalten

Info

Publication number: DE69626964T2
Application number: DE69626964T
Authority: DE
Inventors: Dr. Brandin
Original assignee: Siemens AG
Current assignee: Siemens AG
Priority date: 1996-05-06
Filing date: 1996-05-06
Publication date: 2003-11-06
Anticipated expiration: 2016-05-07
Also published as: EP0806735B1; DE69626964D1; EP0806735A1; ATE235716T1

Description

Die Erfindung betrifft die automatisierte Prozeßsteuerung, darunter Prozesse mit spezifizierten Zeitzwangsbedingungen.
Fortschritte bei der automatisierten Herstellung und Trends in Richtung der Anwendung von mehr computerimplementierten Prozeßsteuerungen sowie die Zunahme der Größe solcher Implementierungen führen zu noch komplexeren und unhandlicheren Prozeßsteuerstrukturen. In Anwendungsgebieten wie zum Beispiel automatisierte Produktion, komplexe, geschichtete Kommunikationsprotokolle, wie etwa bei ISDN oder Abrufvideo, Computerkommunikation, interne Prozessorbusse, Transportsysteme oder Objektkommunikation in objektorientierten Programmen werden Zeitanforderungen immer wichtiger und erzwingen durch die Komplexität der Probleme die Notwendigkeit eines geeigneten Verfahrens der Beschreibung oder Modellierung solcher Prozeßflüsse. Das Ziel ist, solche Prozesse automatisch zu modellieren und zu analysieren, um eine Beschreibungsebene zu erzielen, bei der ein weiterer Schritt der Prozeßflußsteuerung automatisch erzeugt und der Prozeß selbst ohne Notwendigkeit intensiver Programmierungs- und Auswertungsbemühungen gesteuert werden kann.
Zu diesem Thema gab es mehrere Ansätze. Der jüngste bekannte eine Stand der Technik wird in B. A. Brandin, W. M. Wonham, "The supervisory control of timed discrete-event systems", IEEE Transactions on Automatic Control, Februar 1994, S. 329-342, beschrieben. Dort wird ein Modellierungsverfahren gezeigt, das auf Zeitzustand basierende Prozesse, Automaten, als Modellierungsteile zu modellierender Prozesse verwendet. Als "Ticks" bezeichnete Zeiteinheiten werden zum Zeigen der gegenseitigen Abhängigkeiten der Automaten verwendet. Aus dieser Schrift wird leicht ersichtlich, daß, obwohl Zeitzwangsbedingungen wie zum Beispiel obere und untere Zeitschranken unter gleichzeitiger Verwendung von Ticks und Automaten zur Modellierung geschaffen werden, auch kleine Automaten mit wenigen möglichen Aktivitäten und wenigen Zustandsübergängen zu relativ komplexen Aktivitätsübergangsgraphen führen. Um ein Modell eines komplexeren Prozeßflusses herzustellen, müssen diese Aktivitätsübergangsgraphen in einem globalen Prozeßmodell zusammengesetzt werden, was schließlich zu einer sehr großen unverständlichen Steuerstruktur führt, wie zum Beispiel in Fig. 20 gezeigt.
Die Synthese solcher Modelle, um einen Überwacher, einen sogenannten Automaten, abzuleiten, der alle möglichen und alle zulässigen Aktivitäten und Zustandsübergänge in der Prozeßsteuerstruktur enthält, ist sogar eine noch aufwendigere Aufgabe, da diese unhandlichen Strukturen korrekt gehandhabt werden müssen.
Eine Aufgabe der Erfindung ist somit die Bereitstellung eines Verfahrens zur Steuerung eines Prozeßflusses gemäß einem spezifizierten Verhalten mit einem Computer, so daß sich kleinere und benutzertransparentere Prozeßmodelle ergeben, und die Bereitstellung eines Verfahrens zur automatischen Erzeugung einer Überwachersteuerung.
Eine weitere Aufgabe der Erfindung ist der Einschluß der Behandlung spezifizierter Zeitzwangsbedingungen in die automatisierte Erzeugung von Überwachersteuerungen.
Eine weitere Aufgabe der Erfindung ist das Weglassen von "Ticks" als Zeiteinheiten.
Eine weitere Aufgabe der Erfindung ist die Erleichterung der Entwicklung und Analyse der Prozeßsteuerung komplexer technischer Prozesse.
Eine weitere Aufgabe der Erfindung ist die Bereitstellung eines Herstellungsprozesses für eine Prozeßsteuerung komplexer technischer Prozesse.
Diese Aufgaben werden gemäß der in Anspruch 1 beanspruchten Erfindung gelöst.
Bevorzugte Ausführungsformen der Erfindung werden in den abhängigen Ansprüchen beansprucht.
Die Erfindung hat den Vorteil, daß sie automatisch computererzeugte vollständige Modelle sehr komplexer Prozeßflüsse liefert, die im Hinblick auf die Eigenschaften des spezifizierten Prozesses kompakt und korrekt sind.
Die Erfindung hat den weiteren Vorteil, daß sie eine neue Behandlung von Zeitzwangsbedingungen bereitstellt, durch die das Modellierungsverfahren Aktivitäten behandeln kann, anstatt sich mit "Ticks" abzugeben, und liefert somit im Vergleich zum Stand der Technik eine enorme Menge an Kompaktifizierung.
Die Erfindung hat den weiteren Vorteil, daß sie leicht zur Modellierung von Prozeßflüssen in beliebigen der obenerwähnten technischen Gebiete und anderen ähnlichen Gebieten, die Fachleuten bekannt sind, verwendet werden kann, und daß aufgrund der Erfindung komplexe Prozesse analysiert und ihre Überwachungssteuerung automatisch erzeugt werden kann.
Die Erfindung hat den weiteren Vorteil, daß sie eine geeignete Methode bereitstellt, durch die das Modellierungs- und Steuerverfahren als ein sehr effizienter computerausführbarer Prozeß implementiert werden kann.
Die Erfindung hat den weiteren Vorteil, daß sie die computererzeugten Daten dergestalt abliefert, daß sie automatisch in Aktivitätsübergangsgraphen konvertiert werden können.
Die Erfindung hat den weiteren Vorteil, daß sie eine automatisierte Codierung von Prozeßsteuerungen ermöglicht.
Die Erfindung hat den weiteren Vorteil, daß sie die notwendige Arbeitsmenge zur Herstellung einer Prozeßsteuerung reduziert.
Die Erfindung hat den Vorteil, daß sie zum ersten Mal eine Modellierung und Analyse sehr komplexer Prozesse ermöglicht.
Die Erfindung hat den Vorteil, daß sie eine sehr kompakte Modellierung von auf Zeitgesteuerten Zuständen basierenden Prozessen und die effiziente Synthese und Verifizierung von Überwachungssteuerstrategien (Überwachern) für auf zeitgesteuerten Zuständen basierende Prozesse, die maximal permissive Prozeßverhaltensweisen innerhalb gegebener Spezifikationen garantieren, ermöglicht.
Die Erfindung hat den Vorteil eines Langzeitpotentials, da sie eine praktische und unvermeidliche Lösung für die Entwicklung von Echtzeit-Überwachungssteuersystemen für auf zeitgesteuerten Zuständen basierende Prozesse bereitstellt.
Vorteilhafterweise garantiert die Erfindung eine Kostenreduktion bei der Entwicklung von Steuersystemen durch (a) neue computerunterstützte Entwicklungswerkzeuge, wie zum Beispiel Benutzeroberflächen, Synthesewerkzeuge, Verifizierungswerkzeuge und automatisierte Codierungswerkzeuge und (b) ihre Anwendung sowohl auf nominale Verhaltensweisen, wie zum Beispiel das Routen als auch andere Verhaltensweisen, wie zum Beispiel Fehlerbehebung, Notabschaltungen, Testprozeduren und manuelle Operationen.
Die Erfindung hat die weiteren Vorteile, daß sie eine sehr kompakte Modellierung auf zeitgesteuerten Zuständen basierender Prozesse sowie eine effiziente Analyse und Verifizierung optimaler Überwachungssteuerstrategien für auf zeitgesteuerten Zuständen basierende Prozesse ermöglicht, und daß die erhaltenen Überwachungssteuerstrategien durch Konstruktion garantiert, daß Echtzeit-Verhalten der Prozesse auf innerhalb gegebener Verhaltensspezifikationen beschränkt, und daß die erhaltenen Überwachungssteuerstrategien durch Konstruktion garantiert maximal innerhalb der gegebenen Verhaltensspezifikationen permissiv sind. Außerdem ist das erhaltene eingeschränkte Echtzeit-Verhalten der Prozesse garantiert nicht blockierend, und die Erfindung ermöglicht eine automatisierte Codierung von Überwachungssteuerstrategien in industriellen Steuersystemen.
Im folgenden Teil der Beschreibung wird die Erfindung unter Verwendung von Gleichungen und Figuren weiter offengelegt.
Fig. 1 zeigt die Beziehung zwischen Σ, Σu, Σc und Σf;
Fig. 2 zeigt zwei Fahrzeuge V&sub1; und V&sub2;;
Fig. 3 zeigt das zeitgesteuerte Verhalten der beiden Fahrzeuge, die sich gleichzeitig bewegen;
Fig. 4 zeigt eine Spezifikation bezüglich des Verhaltens der beiden Fahrzeuge;
Fig. 5 zeigt das Überwacherverhalten oder eingeschränkte zeitgesteuerte Verhalten der beiden Fahrzeuge, die sich gleichzeitig bewegen;
Fig. 6 zeigt eine Herstellungszelle;
Fig. 7 zeigt das zeitgesteuerte Verhalten zweier gleichzeitig arbeitender Maschinen;
Fig. 8 zeigt eine Spezifikation bezüglich des Verhaltens der beiden Maschinen; und
Fig. 9 zeigt das Überwacher- oder eingeschränkte zeitgesteuerte Verhalten der beiden gleichzeitig arbeitenden Maschinen.

1. Notation

Es seien A und B beliebige Mengen. Es sei a ein Element von A. a A bedeutet, daß a ein Element von A ist. A · B bedeutet das kartesische Produkt von A und B. A bedeutet die Kardinalität von A, d. h. die Anzahl von Objekten in A. Es sei A eine beliebige Menge indizierter Objekte ai, i I, wobei I die entsprechende Indexmenge bezeichnet. Πi Iai bedeutet das kartesische Produkt der Objekte ai A über der Indexmenge I. Es seien A und B zwei beliebige Teilmengen einer Menge C von Objekten. A C bedeutet Mengeneinschluß und A C bedeutet strikten Mengeneinschluß. A B bedeutet die Vereinigungsmenge und A B die Vereinigung elementfremder Mengen. Es seien Ai, i I beliebige indizierte Teilmengen einer Menge C von Objekten, wobei I die entsprechende Indexmenge bedeutet. Ui IAi bedeutet die Vereinigungsmenge der Teilmengen Ai über die Indexmenge I. A B bedeutet die Schnittmenge.
Es bedeute ∞ unendlich. Es bedeute N die natürlichen Zahlen {0, 1, 2, ...}. Für a, b N {∞}, wobei a und b nicht gleichzeitig ∞ sind, definiere man a b = max(0, a-b).
Es sei der logische Disjunktionsoperator (or), der logische Disjunktionsoperator (and), der logische Negationsoperator (not), x die universelle Quantifizierung, x die existentielle Quantifizierung.
Ein Automat (engl. Finite state machine) G wird gegeben durch G = (Σ, Q, δ, q&sub0;, Qm), wobei Σ ein Alphabet, Q = {q&sub0;, q&sub1;, ...} die Zustandsmenge (von der angenommen wird, daß sie endlich und nicht leer ist), δ : Q · Σ → Q die Übergangsfunktion, q&sub0; Q der Anfangszustand und Qm Q die Menge markierter Zustände bedeuten. Die Übergangsfunktion δ : Q · Σ → Q sei bei jedem q Q nur für eine Teilmenge der Elemente σ Σ definiert; nämlich ist δ eine Partialfunktion. Die Notation δ(σ, q)! soll bedeuten, daß δ(σ, q) definiert ist. Die Ereignisse in einem auf Zuständen basierenden Prozeß, der durch den Automat G modelliert wird, bilden das Alphabet Σ und sind Zustandsübergänge von einem Zustand qi Q zu einem Zustand qj Q, wofür δ definiert ist.
Es sei G = (Σ, Q, δ, q&sub0;, Qm) ein Automat. Um G darzustellen, kann Q mit den Knoten eines gerichteten Graphen G identifiziert werden, dessen Kanten mit Symbolen σ Σ bezeichnet werden; nämlich ist (q, σ, q') eine gekennzeichnete Kante qo oq¹ von G genau dann, wenn δ(σ, q) = q' gilt. Ein solcher Graph ist ein Zustandsübergangsgraph für G. In G bindet man an q&sub0; einen Eintrittspfeil an, wie bei → oq&sub0;, und Markiererzustände q Qm werden wie in qo dargestellt.

2 Modellierung

Um das zeitgesteuerte Verhalten eines auf zeitgesteuerten Zuständen basierenden Prozesses zu modellieren, beginnt man mit folgendem:
(i) einem Automaten (finite state machine) A = (Σ, A, δA, ao, Am), der das nicht zeitgesteuerte Verhalten des auf Zuständen basierenden Prozesses darstellt. Σ ist ein endliches Alphabet von Ereigniskennzeichnungen (oder einfacher Ereignisse). A stellt eine Aktivitätsmenge dar, deren Elemente Aktivitäten A sind. Hierbei ist A immer endlich. Bei der hier betrachteten Interpretation von A Ereignisse momentan sind. Die Aktivitätsübergangsfunktion δA ist eine Partialfunktion δA : A · Σ → A. ao ist die Anfangsaktivität und Am A ist eine Teilmenge von Markiereraktivitäten. Diese sind Aktivitäten, die vom Steuerstandpunkt aus gesehen eine bestimmte Bedeutung haben, wie zum Beispiel das Ende eines Maschinenarbeitszyklus.
(ii) zusammen mit der unteren und der oberen Vorgabe- Zeitschranke für die Ereignisse σ Σ. Es sei N die Menge der natürlichen Zahlen {0, 1, 2, ...,}. Jede Ereigniskennzeichnung σ Σ ist mit einer unteren Vorgabe-Zeitschranke lσ N und einer oberen Vorgabe-Zeitschranke uσ N {∞} ausgestattet, mit lσ ≤ uσ.
Aus dem obigen Automaten A und der entsprechenden unteren und oberen Vorgabe-Zeitschranke modelliert man das zeitgesteuerte Verhalten des betrachteten auf zeitgesteuerten Zuständen basierenden Prozesses mit dem Automaten E = (Σ, E, δE, eo, Em). Σ ist das obige endliche Alphabet von Ereigniskennzeichnungen in A. E stellt die zeitgesteuerte Aktivitätsmenge dar, deren Elemente zeitgesteuerte Aktivitäten e sind. Wie bei dem obigen A soll E immer endlich sein. Die Aktivitätsübergangsfunktion δE ist eine Partialfunktion δE : E · Σ → E. eo ist die anfängliche zeitgesteuerte Aktivität und Em E ist die Teilmenge von zeitgesteuerten Markiereraktivitäten. Wie bei den obigen Am sind diese zeitgesteuerte Aktivitäten, die vom Steuerstandpunkt aus gesehen eine bestimmte Bedeutung haben.
Es wird nun der Automat E = (Σ, E, δE, eo, Em) definiert.
Für j, k N schreibe man [j, k] für die Menge ganzer Zahlen i mit j ≤ i ≤ k, und es sei für σ Σ
Rσ = [0, lσ].
Die zeitgesteuerte Aktivitätsmenge E wird gegeben durch E = A · ΠσΣ(Rσ · Tσ). Deshalb ist eine zeitgesteuerte Aktivität ein Element der Form
e = (a,{(rσ, tσ) für alle σ Σ})
mit a A, rσ Rσ und tσ Tσ; nämlich besteht e aus einer Aktivität zusammen mit n Paaren ganzer Zahlen, wobei n die Anzahl von Ereignissen σ in Σ ist. rσ wird als der Timer der unteren Schranke von σ in der zeitgesteuerten Aktivität e bezeichnet, und in ähnlicher Weise wird tσ als der Timer der oberen Schranke von σ der zeitgesteuerten Aktivität e bezeichnet. rσ stellt die Verzögerung zu der frühest möglichen Erscheinung von σ von der Aktivität a dar. tσ stellt die Verzögerung zu der spätest möglichen Erscheinung von σ von der Aktivität a dar (möglicherweise unendlich).
Die anfängliche zeitgesteuerte Aktivität wird gegeben durch
ea = (ao,{lσ, uσ) für alle σ Σ}).
Die zeitgesteuerte Markiereraktivitätsteilmenge wird in der folgenden Form genommen:
Em Am · (Rσ · Tσ).
Es wird nun die formale Definition von δE gegeben. Man schreibe δE(e, σ) = e', mit
e = (a,{(rτ, tτ) für alle τ Σ}),
e' = (a',{(r'τ, t'τ) für alle τ Σ}).
δE ist für σ Σ bei e genau dann definiert, wenn σ von a definiert ist und es kein anderes aus a definiertes Ereignis α Σ gibt, dessen obere Zeitschranke strikt kleiner als die untere Zeitschranke von σ ist:
δE(e, σ)! genau dann, wenn δA (a, σ)! und ( α ΣA) (α ≠ σ δA(a, α)! ta < τσ) gilt.
Die Aktivität e' = (a', {(r'τ, t'τ für alle τ Σ}) wird dann folgendermaßen definiert: a' = δA(a, σ) und
(i) für τ ≠ σ
(ii) für τ = σ
(r'τ, t'τ) = (lτ, uτ).
Die Ereignisse σ Σ werden in unsteuerbare, steuerbare und erzwingbare Ereignisse unterteilt. Die Teilmenge unsteuerbarer Ereignisse wird als Σu bezeichnet. Dabei handelt es sich um Ereignisse, die spontan in dem entsprechenden Zeitintervall auftreten und dessen Auftreten durch Steuerung nicht gesperrt werden kann. Die Teilmenge steuerbarer Ereignisse wird als Σc bezeichnet. Dabei handelt es sich um Ereignisse, deren Auftreten durch Steuerung unendlich zuvorkommend verhindert werden kann, d. h. ihr Auftreten kann durch Steuerung gesperrt werden. Ihre oberen Zeitschranken sind deshalb immer unendlich. Wenn sie nicht gesperrt sind, treten steuerbare Ereignisse innerhalb des entsprechenden Zeitintervalls auf. Die Teilmenge erzwingbarer Ereignisse wird als Σf bezeichnet. Erzwingbare Ereignisse können entweder unsteuerbar oder steuerbar sein. Dabei handelt es sich um Ereignisse, deren Auftreten durch Steuerung zu einem beliebigen Zeitpunkt während des entsprechenden Zeitintervalls erzwungen werden kann. Fig. 1 zeigt die Beziehung zwischen Σ, Σu, Σc und Σf.

3. Zusammensetzung

Um das zeitgesteuerte Verhalten einer Anzahl zeitgesteuert basierender Prozesse, die parallel arbeiten, zu modellieren, ist eine Zusammensetzung erforderlich, die nun dargestellt wird.
Bei einer gegebenen Anzahl von Automaten Ai = (Σi, Ai, δAi' ao,i, Am,i), i = 1, ..., n, die das nicht zeitgesteuerte Verhalten entsprechender auf zeitgesteuerten Zuständen basierender Prozesse darstellen, erhält man einen einzigen Automaten A = (ΣA, A, δA, ao, Am), der das synchronisierte nicht zeitgesteuerte Verhalten der Automaten Ai, i = 1, ..., n realisiert, folgendermaßen:
ΣA = Σi,
A = Ai,
ao = (ao,1, ..., ao,n),
Am = Am,i, und
wobei δA : A · ΣA → A nun definiert wird. Es sei σ ΣA. Man schreibe δA(a, σ) = a' mit
a = (a&sub1;, ..., an)
a' = (a'&sub1;, ..., a'n).
Dann ist δA(a, σ) genau dann definiert, wenn für i = 1, ..., n entweder δAi (ai, σ) definiert ist oder sich σ nicht in Σi befindet:
δA(a, σ)! genau dann, wenn (δAi(ai, σ)! σ Σi), i = 1, ..., n gilt.
Die Aktivität a' = (a'&sub1;, ..., a'n) wird dann gegeben durch:
für i = 1, ..., n
Zur weiteren Bezugnahme wird die synchrone Zusammenstellung von Ai, i = 1, ..., n zu A durch A = (ΣA, A, δA, ao, Am) = composition (A&sub1;, ..., An) bezeichnet.
Nach dem Zusammenstellen der verschiedenen Ai, i = 1, ..., n zu A, und wenn die untere und die obere Vorgabeschranke der Ereignisse σ ΣA gegeben ist, erhält man das zeitgesteuerte Verhalten E wie oben in Abschnitt 2 beschrieben.
Anmerkung: Es wird angenommen, daß jedes beliebige Ereignis σ ΣA eine eindeutige untere und obere Vorgabe-Zeitschranke (lσ, uσ) aufweist, auch wenn sich zwei oder mehr Alphabete Σi, i {1, ..., n} σ teilen.

4. Modellkonstruktionsalgorithmus

Während in den Abschnitten 2 und 3 das zeitgesteuerte Verhalten E gegebener auf zeitgesteuerten Zuständen basierender Prozesse, die durch eine Anzahl von Automaten Ai, i = 1, ..., n, modelliert werden, und die entsprechende untere und obere Vorgabe-Zeitschranke von Ereignissen definiert wurden, liefert der vorliegende Abschnitt einen Algorithmus zur Konstruktion von E aus Ai, i = 1, ..., n, und der entsprechenden unteren und oberen Vorgabe-Zeitschranke von Ereignissen.

(1) Initialisierung.

Zur weiteren Bezugnahme sollen vier Mengen definiert werden: (i) die neue Menge, (ii) die letzte Menge, (iii) die Markierermenge und (iv) die Übergangsmenge, von denen jeweils angenommen wird, daß sie zu Anfang leer sind.
Man betrachtet nun die anfängliche zeitgesteuerte Aktivität
eo = (ao,{(lσ, uσ) für alle σ Σ}) mit ao = {ao,1, ..., a,n)
Es sei
e = (a,{(rσ, tσ) für alle σ Σ}) mit a = (a&sub1;, ..., an) = eo,
Man fügt e zu der neuen Menge hinzu. Wenn alle Aktivitäten ai, i = 1, ..., n, aus denen a zusammengesetzt ist, Markiereraktivitäten sind, d. h. ai Am,i, i = 1, ..., n fügt man weiterhin e zu der Markierermenge hinzu.

(2) Konstruktion für zeitgesteuerte Aktivitäten.

Es sei e = (a{(rσ, tσ) für alle σ Σ} mit a = (a&sub1;, ... an).
e wird aus der neuen Menge entfernt und in der letzten Menge abgelegt.
Für alle Ereignisse σ Σ, so daß δE(e, σ) definiert ist, berechnet man die entsprechende zeitgesteuerte Aktivität δ(e, σ) = e', die durch σ von e aus erreicht wird.
Man erinnere sich, daß δE(e, σ) genau dann definiert ist, wenn (i) δA(a, σ) definiert ist und (ii) es kein anderes Ereignis σ Σ gibt, so daß δA(a, α) definiert ist, und dessen obere Zeitschranke tα streng kleiner als die untere Zeitschranke rσ, von σ ist.
Es sei e' = (a',{(r'τ, t'τ) für alle τ Σ}) mit a' = (a'&sub1;, a'n).
a' wird folgendermaßen berechnet: für i = 1, ..., n gilt
Die unteren und oberen Zeitschranken (r'τ, t'τ), τ Σ werden folgendermaßen berechnet:
für r ≠ σ
für r = σ
(r'τ, t'τ) = (lτ, uτ).
Wenn (i) e' nicht in der letzten Menge ist, fügt man e' zu der neuen Menge hinzu, und wenn alle Aktivitäten a'i, i = 1, ..., n, aus denen a' zusammengesetzt ist, Markiereraktivitäten sind, d. h. a'i Am,i, i = 1, ..., n, fügt man dann e' zu der Markierermenge hinzu; (ii) und der Übergang (e, σ, e') wird zu der Übergangsmenge hinzugefügt.

(3) Konstruktionsschleife für zeitgesteuerte Aktivitäten.

Es werden nun der Reihe nach alle zeitgesteuerten Aktivitäten in der neuen Menge betrachtet und die Schritte (2) bis (3) wiederholt, bis die neue Menge leer ist.
Für den Automaten E = (Σ, E, δE, eo, Em) hat man dann Σ wie oben gegeben und es gilt
E = letzte Menge
δE = Übergangsmenge
eo = (ao, {lσ, uσ) für alle σ Σ}) mit ao = (ao,1, ..., ao,n)
Em = Markierermenge.

Modellierungsbeispiel 1: Verkehrssystem

Das zeitliche Verhalten zweier über eine Kreuzung fahrender Fährzeuge wird nachfolgend modelliert. Die beiden Fahrzeuge V&sub1;, V&sub2; sind in Fig. 2 gezeigt. Für Vehicle1 sind gegeben:
A&sub1; = (Σ&sub1;, A&sub1;, δA1, ao,1, Am,1)
A&sub1; = {departing&sub1;, crossed&sub1;}
δA1 = {(departure&sub1;, pass&sub1;, crossed&sub1;)}
ao,1 = departing&sub1;
Am,1 = {crossed&sub1;}
zusammen mit der folgenden unteren und oberen Vorgabe- Zeitschranke (lpass1, upass1) = (8, 10).
Für Vehicle2 sind gegeben:
A&sub2; = (Σ&sub2;, A&sub2;, δA2, ao,2, Am,2)
A&sub2; = {departing&sub2;, crossed&sub2;}
δA2 = {(departure&sub2;, pass&sub2;, crossed&sub2;)}
ao,2 = departing&sub2;
Am,2 = {crossed&sub2;}
zusammen mit der folgenden unteren und oberen Vorgabe- Zeitschranke (lpass2, upass2) (5, ∞).
Das entsprechende zeitgesteuerte Verhalten E der beiden gleichzeitig fahrenden Fahrzeuge erhält man gemäß der in Abschnitt 4 dargestellten und in Fig. 3 gezeigten Verfahrensweise.
E = (Σ, E, δE, eo, Em)
Σ = {pass&sub1;, pass&sub2;}
E = {eo, e&sub1;, e&sub2;, e&sub3;} mit
eo = ((departing&sub1;, departing&sub2;), (8, 10)(5, ∞))
e&sub1; = ((departing&sub1;, crossed&sub2;),(0,5)(5, ∞))
e&sub2; = ((crossed&sub1;, departing&sub2;), (8, 10)(0, ∞))
e&sub3; = ((crossed&sub1;, crossed&sub2;),(8, 10)(5, ∞))
δE = {(eo, pass&sub1;, e&sub2;), (eo, pass&sub2;, e&sub1;), (e&sub1;, pass&sub1;, e&sub3;), (e&sub2;, pass&sub2;, e&sub3;)}
eo = ((departing&sub1;, departing&sub2;), (8, 10)(5, ∞))
Em = {((crossed&sub1;, crossed&sub2;), (8, 20)(5, ∞))}
Es ist wichtig, zu beachten, daß das vorliegende Modell 4 zeitgesteuerte Aktivitäten und 4 Übergänge aufweist, im Vergleich zu 19 Zuständen und 30 Übergängen bei Verwendung des Stands der Technik.

Modellierungsbeispiel 2: Eine Herstellungszelle mit zwei Maschinen

Das zeitgesteuerte Verhalten zweier Maschinen, die eine Herstellungszelle bilden, wird nachfolgend modelliert. Die Zelle ist in Fig. 6 gezeigt. Für Machinel ist folgendes gegeben:
A&sub1; = (Σ&sub1;, A&sub1;, δA1, ao,1, Am,1)
A&sub1; = {processing&sub1;}
δA1 = {(operational&sub1;, work&sub1;, operational&sub1;)}
ao,1 = operational&sub1;
Am,1 = {operational&sub1;}
zusammen mit der folgenden unteren und oberen Vorgabe- Zeitschranke (lwork1, uwork1) = (5, 5). Für Machine2 ist folgendes gegeben:
A&sub2; = (Σ&sub2;, A&sub2;, δA2, ao,2, Am,2)
A&sub2; = {processing&sub2;}
δA2 = {(operational&sub2;, work&sub2;, operational&sub2;)}
ao,2 = operational&sub2;
Am,2 = {operational&sub2;}
zusammen mit der folgenden unteren und oberen Vorgabe- Zeitschranke (lwork2, uwork2) = (2, ∞).
Das entsprechende zeitgesteuerte Verhalten E der beiden gleichzeitig arbeitenden Maschinen wird gemäß der in Abschnitt 4 dargestellten Verfahrensweise erreicht und ist in Fig. 7 gezeigt.
E = (Σ, E, δE, eo, Em) mit
Σ = {work&sub1;, work&sub2;}
E = {eo, e&sub1;, e&sub2;, e&sub3;, e&sub4;, e&sub5;, e&sub6;, e&sub7;, e&sub8;} mit
eo = ((operational&sub1;, operational&sub2;), (5, 5)(2, ∞))
e&sub1; = ((operational&sub1;, operational&sub2;), (5, 5)(0, ∞))
e&sub2; = ((operational&sub1;, operational&sub2;), (0, 3)(2, ∞))
e&sub3; = ((operational&sub1;, operational&sub2;), (0, 5)(2, ∞))
e&sub4; = ((operational&sub1;, operational&sub2;), (0, 1)(2, ∞))
e&sub5; = ((operational&sub1;, operational&sub2;), (5, 5)(1, ∞))
e&sub6; = ((operational&sub1;, operational&sub2;), (0, 4)(2, ∞))
e&sub7; = ((operational&sub1;, operational&sub2;), (0, 2)(2, ∞))
e&sub8; = ((operational&sub1;, operational&sub2;), (0, 1)(2, ∞))
δE = {(eo, work&sub1;, e&sub1;), (eo, work&sub2;, e&sub2;),
(e&sub1;, work&sub2;, e&sub3;), (e&sub1;, work&sub1;, e&sub1;),
(e&sub2;, work&sub1;, e&sub4;),
(e&sub3;, work&sub2;, e&sub2;), (e&sub3;, work&sub1;, e&sub1;),
(e&sub4; ,work&sub1;, e&sub5;),
(e&sub5;, work&sub2;, e&sub6;), (e&sub5;, work&sub1;, e&sub1;),
(e&sub6;, work&sub2;, e&sub7;), (e&sub6;, work&sub1;, e&sub1;),
(e&sub7;, work&sub2;, e&sub8;), (e&sub7;, work&sub1;, e&sub1;),
(e&sub8;, work&sub1;, eo)}
eo = (operational&sub1;, operational&sub2;),(5, 5)(2, ∞)),
Em = E.
Wieder ist es wichtig, zu beachten, daß das vorliegende Modell 9 zeitgesteuerte Aktivitäten und 15 Übergänge aufweist, im Vergleich zu 18 Zuständen und 24 Übergängen bei Verwendung des Stands der Technik.

5 Überwachersynthese

Wenn ein Automat E gegeben ist, der das zeitgesteuerte Verhalten gegebener auf Zeitgesteuerten Zuständen basierender Prozesse darstellt, kann man durch Steuerung dieses Verhalten auf innerhalb von gegebenen Verhaltensspezifikationen einschränken, die durch Automaten dargestellt werden.
Das resultierende eingeschränkte zeitgesteuerte Verhalten verletzt durch Konstruktion garantiert nicht die betrachteten Spezifikationen, und ist garantiert innerhalb dieser maximal permissiv und nichtblockierend zu sein. Ein solches eingeschränktes Verhalten wird ebenfalls in Form eines Automaten dargestellt. Nichtblockierend soll hier bedeuten, daß es von jedem beliebigen Punkt in dem betrachteten eingeschränkten zeitgesteuerten Verhalten aus möglich sein muß, einen Punkt in demselben Verhalten zu erreichen, mit besonderer Bedeutung vom Standpunkt der Steuerung aus gesehen, wie zum Beispiel das Ende eines Produktionszyklus.
Um zu garantieren, daß das zeitgesteuerte Verhalten der betrachteten auf zeitgesteuerten Zuständen basierenden Prozesse durch Steuerung innerhalb gegebener Verhaltensspezifikationen bleibt, muß folgendes gelten: an jedem beliebigen Punkt in dem Verhalten der betrachteten auf zeitgesteuerten Zuständen basierenden Prozesse gilt folgendes:
(i) jedes unsteuerbare Ereignis, das physisch möglich ist, muß durch die betrachteten Spezifikationen auch zugelassen sein; oder
(ii) es muß ein erzwingbares Ereignis geben, das sowohl physisch möglich als auch von den Spezifikationen erlaubt ist, das in der Lage ist, das Auftreten eines beliebigen physisch möglichen unsteuerbaren Ereignisses, das von den Spezifikationen nicht erlaubt wird, zuvorkommend zu verhindern; oder
(iii)es muß vor dem in dem Verhalten betrachteten Punkt möglich sein, durch Sperrung oder Erzwingung des Verhaltens ein Erreichen des betrachteten Punkts verhindern zu können.
Um zu garantieren, daß das zeitgesteuerte Verhalten der betrachteten auf zeitgesteuerten Zuständen basierenden Prozesse nichtblockierend ist, muß außerdem folgendes gelten:
(iv) von jedem Punkt in dem betrachteten Verhalten aus muß es möglich sein, einen Punkt in dem Verhalten mit besonderer Bedeutung vom Standpunkt der Steuerung aus gesehen zu erreichen.
Der in diesem Abschnitt dargestellte Synthesealgorithmus ermöglicht die Konstruktion des nichtblockierenden und maximal permissiven Verhaltens der Prozesse innerhalb durch Automaten dargestellter gegebener Spezifikationen. Auf der Grundlage von Sperrung, der obigen Bedingungen (ii) und (iii), wird das zeitgesteuerte Verhalten der betrachteten auf zeitgesteuerten Zuständen basierenden Prozesse eingeschränkt, um zu garantieren, daß die obigen Bedingungen (i) und (iv) an jedem Punkt des eingeschränkten Verhaltens gelten. Das eingeschränkte zeitgesteuerte Verhalten wird in Form eines Automaten C = (Σ, C, δC, co, Cm) zurückgegeben und wird als ein Überwacher bezeichnet. Man beachte, daß das eingeschränkte Verhalten leer sein kann, was bedeutet, daß es unmöglich ist, die betrachteten Spezifikationen zu erfüllen.
Man nehme an, daß folgendes gegeben ist:
(i) eine Anzahl von Automaten Ai = (Σi, Ai, δAi, ao,i Am,i), i = 1, ..., n, die das nicht zeitgesteuerte Verhalten entsprechender auf zeitgesteuerten Zuständen basierender Prozesse darstellt,
(ii) die entsprechende untere und obere Vorgabe-Zeitschranke des Ereignisses, und
(iii)eine Anzahl von Automaten Ai = (Σi, Ai, δAi, ao,i, Am,i), i = n + 1, ..., m, die das spezifizierte und gewünschte Verhalten der betrachteten auf zeitgesteuerten Zuständen basierender Prozesse darstellt, wobei die Vereinigungsmenge der gewünschten Verhaltensalphabete Σi, i = n + 1, ..., m in der Vereinigungsmenge der Alphabete der Prozesse Σi, i = 1, ..., n enthalten ist, d. h.
Ui=n+1,...,m Σi Ui=1,...,n Σi.
Es sei E = (Σ, E, δE, eo, Em) wie in Abschnitt 2 definiert aus A = (ΣA, A, δA, ao, Am) = composition (A&sub1;, ..., An) und den entsprechenden Zeitschranken. Es sei B = (ΣB, B, δB, Bo, Bm) = composition (An+1, ..., Am).
Das durch C realisierte Verhalten ist eine Teilmenge des durch die synchrone Zusammenstellung von E und B realisierten Verhaltens. Deshalb gilt für C = (Σ, C, δC, co, Cm)
Σ = Σi
C E · B
δC : C · Σ → C
co = (eo, bo)
Cm Em · Bm.
Es wird nun der Überwachersynthesealgorithmus dargestellt.

(1) Initialisierung.

Zur weiteren Bezugnahme werden sechs Mengen definiert: (i) die neue Menge, (ii) die letzte Menge, (iii) die schlechte Menge, (iv) die Markierermenge, (v) die nichtblockierende Menge und (vi) die Übergangsmenge, von denen jeweils angenommen wird, daß sie anfangs leer sind.
Man betrachtet nun die anfängliche zeitgesteuerte Aktivität
co = (eo, bo) = ((ao,1, ..., ao,n), {(lσ, uσ) für alle σ Σ}, (ao,n+1, ..., ao,m)).
Es sei
c = (e, b)
c = ((a&sub1;, ..., an), {(rσ, tσ) für alle σ Σ}, (an+1, ...., am)) = co.
Man plaziert c in der neuen Menge. Wenn alle Aktivitäten ai, i = 1, ..., n, aus denen a zusammengesetzt ist, Markiereraktivitäten sind, d. h. ai Am,i, i = 1, ..., n, dann fügt man weiterhin e zu der Markierermenge und der nichtblockierenden Menge hinzu.

(2) Konstruktion physisch möglicher und legaler Mengen.

Es sei c = (e, b) = ((a&sub1;, ..., am), {(rσ, tσ) für alle σ Σ}, (an+1, ..., am)).
Für e bestimmt man die Menge von Ereignissen σ Σ, so daß δA(a, σ) definiert ist. Der Einfachheit halber soll diese Menge von Ereignissen als die physisch mögliche Ereignismenge von c bezeichnet werden. Man erinnere sich, daß diese die Ereignisse sind, für die (i) δA(a, σ) definiert ist und für die (ii) es kein anderes Ereignis σ Σ gibt, so daß δA(a, α) definiert ist und dessen obere Zeitschranke tα streng kleiner als die untere Zeitschranke rσ von σ ist.
Für b bestimme man die Menge von Ereignissen σ Σ, so daß δB(b, σ) definiert ist. Der Einfachheit halber soll diese Menge von Ereignissen als die legale Ereignismenge von c bezeichnet werden.

(3) Identifikation schlechter zeitgesteuerter Aktivitäten.

Man entfernt die zeitgesteuerte Aktivität
c = (e, b) = ((a&sub1;, ..., am), {(rσ, tσ) für alle σ Σ}, (an+1, ..., am))
aus der neuen Menge.
Wenn (i) entweder alle unsteuerbaren Ereignisse σ in der physisch möglichen Ereignismenge von c in der legalen Ereignismenge von c enthalten sind oder (ii) wenn es für alle unsteuerbaren Ereignisse σ in der physisch möglichen Ereignismenge von c, die nicht in der legalen Ereignismenge von c enthalten sind, ein erzwingbares Ereignis β gibt, das sich sowohl in der physisch möglichen Ereignismenge von c als auch in der legalen Ereignismenge von c befindet, so daß seine untere Zeitschranke rβ streng kleiner als die untere Zeitschranke rσ von σ ist, wird c = (e, b) in der letzten Menge von σ plaziert, andernfalls wird c in der schlechten Menge plaziert.

(4) Identifikation schlechter zeitgesteuerter Aktivitäten.

Für alle zeitgesteuerten Aktivitäten c in der schlechten Menge findet man die entsprechenden zeitgesteuerten Aktivitäten C' in der letzten Menge, von denen aus C in einem Übergang σ erreicht werden kann.
Wenn der von c' zu c führende Übergang cv unsteuerbar ist und es weder in der physisch möglichen Ereignismenge von c noch in der legalen Ereignismenge von c kein erzwingbares Ereignis β gibt, so daß seine untere Zeitschranke rβ streng kleiner als die untere Zeitschranke rσ von σ ist, entfernt man die Aktivität c' aus der Markierermenge, der nichtblockierenden und der letzten Menge und fügt sie zu der schlechten Menge hinzu und entfernt den Übergang aus der Übergangsmenge.
Wenn der von c' zu c führende Übergang σ unsteuerbar ist und es sowohl in der physisch möglichen Ereignismenge von c als auch der legalen Ereignismenge von c ein erzwingbares Ereignis β gibt, so daß seine untere Zeitschranke rβ streng kleiner als die untere Zeitschranke rσ von σ ist, wird uβ so gesetzt, daß uβ streng kleiner als rσ ist.
Wenn der von c' zu c führende Übergang σ steuerbar ist, entfernt man den Übergang aus der Übergangsmenge und sperrt ihn dadurch.

(5) Identifikationsschleife für schlechte zeitgesteuerte Aktivitäten.

Schritt 4 wird wiederholt, bis die Anzahl zeitgesteuerter Aktivitäten in der schlechten Menge invariant bleibt.

(6) Konstruktion zeitgesteuerter Aktivitäten.

Für alle zeitgesteuerten Aktivitäten c in der letzten Menge und für alle Ereignisse σ, die sowohl in der physisch möglichen Ereignismenge von c als auch in der legalen Ereignismenge von c enthalten sind, berechnet man die entsprechende zeitgesteuerte Aktivität δ(c, σ) = c'.
Es sei
c' = (a',{(r'τ, t'τ) für alle τ Σ),b') mit a' = (a'&sub1;, ..., a'n) und b' = (a'n+1, ..., a'm).
a' wird folgendermaßen berechnet: für i = 1, ..., n
Die unteren und oberen Zeitschranken (r'τ, t'τ), τ Σ werden folgendermaßen berechnet:
Für τ ≠ σ
Für τ = σ folgendermaßen:
(r'τ, t'τ) = (lτ, uτ)
b' wird folgendermaßen berechnet: für i = n + 1, ..., m
(i) Wenn sich c' nicht bereits in der letzten Menge oder in der schlechten Menge befindet, fügt man c' zu der neuen Menge hinzu, und wenn alle Aktivitäten ai, i = 1, ..., m, aus denen a' und b' zusammengesetzt sind, Markiereraktivitäten sind, d. h. a'i Am,i, i = 1, ..., m, fügt man dann c' zu der Markierermenge und der nichtblockierenden Menge hinzu; (ii) und der Übergang (c, σ, c') wird zu der Übergangsmenge hinzugefügt.

(7) Konstruktionsschleife für zeitgesteuerte Aktivitäten.

Man betrachte der Reihe nach alle zeitgesteuerten Aktivitäten in der neuen Menge und wiederholt die Schritte (2) bis (7), bis die neue Menge leer ist.

(8) Identifikation nichtblockierender zeitgesteuerter Aktivitäten.

Für alle zeitgesteuerten Aktivitäten c in der nichtblockierenden Menge findet man die entsprechende zeitgesteuerte Aktivitäten c' in der letzten Menge, von denen aus c in einem Übergang σ erreicht werden kann. Man fügt c' zu der nichtblockierenden Menge hinzu.

(9) Identifikationsschleife für nichtblockierende zeitgesteuerte Aktivitäten.

Schritt 8 wird wiederholt, bis die Anzahl zeitgesteuerter Aktivitäten in der nichtblockierenden Menge invariant bleibt.

(10) Entfernung blockierender zeitgesteuerter Aktivitäten.

Alle zeitgesteuerten Aktivitäten c in der letzten Menge, die sich nicht in der nichtblockierenden Menge befinden, werden aus der Markierermenge und der letzten Menge entfernt und in der schlechten Menge plaziert.

(11) Entfernung blockierender zeitgesteuerter Aktivitäten.

Für alle Aktivitäten in der schlechten Menge findet man die entsprechenden zeitgesteuerten Aktivitäten c' in der letzten Menge, von denen aus c in einem Übergang σ erreicht werden kann.
Wenn der von c' zu c führende Übergang σ unsteuerbar ist und es weder in der physisch möglichen Ereignismenge von c noch in der legalen Ereignismenge von c ein erzwingbares Ereignis β gibt, so daß seine untere Zeitschranke rβ streng kleiner als die untere Zeitschranke rσ von σ ist, entfernt man die Aktivität c' aus der Markierer-, der nichtblockierenden und der letzten Menge und fügt sie zu der schlechten Menge hinzu und entfernt den Übergang (c', σ, c) aus der Übergangsmenge.
Wenn der von c' zu c führende Übergang σ unsteuerbar ist und es sowohl in der physisch möglichen Ereignismenge von c als auch in der legalen Ereignismenge von c ein erzwingbares Ereignis β gibt, so daß seine untere Zeitschranke rβ streng kleiner als die untere Zeitschranke rσ von σ ist, wird uβ so gesetzt, daß uβ streng kleiner als rσ ist.
Wenn der von c' zu c führende Übergang σ steuerbar ist, entfernt man den Übergang (c', σ, c) aus der Übergangsmenge.

(12) Identifikationsschleife für blockierende Aktivitäten.

Schritt 11 wird wiederholt, bis die Anzahl zeitgesteuerter Aktivitäten in der schlechten Menge invariant bleibt.
Dann ist für den Automaten
C = (Σ, C, δC, co, Cm) Σ wie oben gegeben und es gilt
C = letzte Menge
δC = Übergangsmenge
eo = (ao,{(lσ, uσ) für alle σ Σ}, bo) mit ao = (ao,1, ..., ao,n), bo = (ao,n+1, ..., ao,m)
Cm = Markierermenge.

Synthesebeispiel 1: Verkehrssystem

Man erinnere sich an das Verkehrssystembeispiel von Abschnitt 4:

Vehicle1:

A&sub1; = (Σ&sub1;, A&sub1;, δA1, ao,1, Am,1)
A&sub1; = {departing&sub1;, crossed&sub1;}
δA1 = {(departure&sub1;, pass&sub1;, crossed&sub1;)}
ao,1 = departing&sub1;
Am,1 = {crossed&sub1;}
zusammen mit der folgenden unteren und oberen Vorgabe- Zeitschranke (lpass1, upass1) = (8, 10). Weiterhin wird angenommen, daß pass1 unsteuerbar und nicht erzwingbar ist.

Vehicle2:

A&sub2; = (Σ&sub2;, A&sub2;, δA2, ao,2, Am,2)
A&sub2; = {departing&sub2;, crossed&sub2;}
δA2 = {(departure&sub2;, pass&sub2;, crossed&sub2;)}
ao,2 = departing&sub2;
Am,2 = {crossed&sub2;}
zusammen mit der folgenden unteren und oberen Vorgabe- Zeitschranke (lpass2, upass2) = (5, ∞). Weiterhin wird angenommen, daß pass2 steuerbar und erzwingbar ist.
Dem Verhalten der beiden Fahrzeuge wird eine Spezifikation auferlegt: vehicle&sub2; muß vor der Ankunft von vehicle&sub1; über die Kreuzung fahren. Diese Spezifikation wird durch den Automaten B = A&sub3; realisiert und ist in Fig. 4 gezeigt.
A&sub3; = (Σ&sub3;, A&sub3;, δA3, ao,3, Am,3)
A&sub3; = {0, 1}
δA3 = {(0, pass&sub2;, 1), (1, pass&sub1;, 0)}
ao,3 = 0
Am,3 = {0}
Der entsprechende Überwacher bzw. das eingeschränkte zeitgesteuerte Verhalten C der beiden gleichzeitig fahrenden Fahrzeuge innerhalb der Spezifikationen B = A&sub3; wird gemäß der im Abschnitt 5 dargestellten Überwachersyntheseprozedur erhalten und ist in Fig. 5 gezeigt.
C = (Σ, C, δC, co, Cm)
Σ = {pass&sub1;, pass&sub2;}
C = {co, c&sub1;, c&sub2;} mit
eo = ((departing&sub1;, departing&sub2;), (8, 10)(5, ∞), 0)
e&sub1; = ((crossed&sub1;, departing&sub2;), (0, 5)(5, ∞), 1)
e&sub2; = ((crossed&sub1;, crossed&sub2;), (8, 10)(5, ∞), 0)
dC = {(eo, pass&sub1;, e&sub1;),(e&sub1;, pass&sub2;, e&sub0;)}
eo = ((departing&sub1;, departing&sub2;), (8, 10)(5, ∞), 0),
Em = {((crossed&sub1;, crossed&sub2;), (8, 10)(5, ∞), 0)}
Anmerkung: pass&sub1; wird bei co gezwungen, um zuvorkommend das Auftreten von pass&sub1; zu verhindern, indem die obere Zeitschranke auf tpass2 < rpass1 = 8 gesetzt wird.
Es soll bitte beachtet werden, daß das vorliegende Modell 4 zeitgesteuerte Aktivitäten und 4 Übergänge aufweist, im Vergleich zu 15 Zuständen und 18 Übergängen bei Verwendung des Stands der Technik.

Synthesebeispiel 2: Eine Herstellungszelle mit zwei Maschinen

Man erinnere sich an das Herstellungszellenbeispiel von Abschnitt 4:

Machine1:

A&sub1; = (Σ&sub1;, A&sub1;, δA1, ao,1, Am,1)
A&sub1; = {processing&sub1;}
δA1 = {(operational&sub1;, work&sub1;, operational&sub1;)}
ao,1 = operational&sub1;
Am,1 = {operational&sub1;}
zusammen mit der folgenden unteren und oberen Vorgabe- Zeitschranke (lwork1, uwork1) = (5, 5). Weiterhin wird angenommen, daß work&sub1; unsteuerbar und nicht erzwingbar ist.

Machine2:

A&sub2; = (Σ&sub2;, A&sub2;, δA2, ao,2, Am,2)
A&sub2; = {procesing&sub2;}
δA2 = {(operational&sub2;, work&sub2;, operational&sub2;)}
ao,2 = operational&sub2;
Am,2 = {operational&sub2;}
zusammen mit der folgenden unteren und oberen Vorgabe- Zeitschranke (lwork2, uwork2) = (2, ∞). Weiterhin wird angenommen, daß work&sub2; steuerbar und erzwingbar ist.
Dem Verhalten der beiden Maschinen wird eine Spezifikation auferlegt: der Puffer der Größe eins darf nicht unter- oder überlaufen. Daraus folgt, daß, sobald die Zelle in Betrieb ist, dem Ereignis work&sub1; immer das Auftreten des Ereignisses work&sub2; folgen muß, und daß dem Ereignis work&sub2; immer das Auftreten des Ereignisses work&sub1; folgen muß. Die vorliegende Spezifikation wird durch einen Automaten B = A&sub3; realisiert und ist in Fig. 8 gezeigt.
A&sub3; = (Σ&sub3;, A&sub3;, δA3, ao,3, Am,3)
A&sub3; = {emptybuffer, fullbuffer}
δA3 = {(emptybuffer, work&sub1;, fullbuffer), (fullbuffer, work&sub2;, emptybuffer)}
ao,3 = emptybuffer
Am,3 = {emptybuffer}
Der entsprechende Überwacher bzw. das eingeschränkte zeitgesteuerte Verhalten C der beiden Maschinen, die gleichzeitig innerhalb der Spezifikationen B = A&sub3; arbeiten, wird gemäß der in Abschnitt 5 dargestellten Überwachersyntheseverfahrensweise erhalten und ist in Fig. 9 gezeigt.
C = {Σ, C, δC, co, Cm)
Σ = {work&sub1;, work&sub2;}
C = {co, c&sub1;, c&sub2;} mit
co = ((operational&sub1;, operational&sub2;), (5, 5)(2, ∞), emptybuffer)
c&sub1; = ((operational&sub1;, operational&sub2;), (5, 5)(0, ∞)), fullbuffer)
c&sub2; = ((operationol&sub1;, operational&sub2;), (0, 5)(2, ∞), emptybuffer)
δE = {(co, work&sub1;, c&sub1;), (c&sub1;, work&sub2;, c&sub2;), (c&sub2;, work&sub1;, c&sub1;)}
co = ((operational&sub1;, operational&sub2;, (5, 5) (2, ∞), emptybuffer)
Cm = {co, c&sub2;}
Anmerkung: work2 wird bei co und c&sub2; gesperrt, und es wird erzwungen, daß es bei c&sub1; auftritt, indem die obere Zeitschranke twork2 < rwork1 = 5 gesetzt wird.
Wiederum ist es wichtig, zu beachten, daß das vorliegende Modell 3 zeitgesteuerte Aktivitäten und 3 Übergänge aufweist, im Vergleich zu 24 Zuständen und 29 Übergängen bei Verwendung des Stands der Technik.

6 Besprechung

Der vorgeschlagene Ansatz für das Modellieren auf zeitgesteuerten Zuständen basierender Prozesse und der vorgeschlagene Ansatz für die Synthese von Überwachen für auf zeitgesteuerten Zuständen basierende Prozesse bieten wichtige Vorteile gegenüber anderen Ansätzen. Diese werden nachfolgend zusammengefaßt:
(i) sehr kompakte Modellierung, bei der die Zeitsteuerungsinformationen bezüglich des Auftretens von Ereignissen in die Aktivitäten der betrachteten Prozesse integriert werden und nicht explizit in Form von tick-Übergängen vorliegen; dadurch wird das Phänomen der Aktivitäts-(Zustands-)Explosion gezügelt, wenn im Stand der Technik, der ticks verwendet, große Zeitschranken betrachtet werden;
(ii) ein sehr effizienter Modellkonstruktionsalgorithmus, der weder (a) die Konstruktion aller Submodelle, die die betrachteten auf zeitgesteuerten Zuständen basierenden Prozesse zusammenstellen, noch (b) ihre nachfolgende Zusammenstellung zu einem letzten Modell erfordert: der Konstruktionsansatz zügelt somit das Phänomen der Aktivitäts- (Zustands-)Explosion durch direktes Konstruieren der Übergangsstrukturen, die das synchrone Verhalten aller Bestandteilsprozesse realisieren;
(iii)ein sehr effizienter Überwachersynthesealgorithmus, der (a) Überwacher ergibt, die durch Konstruktion garantiert nichtblockierend und maximal permissiv innerhalb gegebener Verhaltensspezifikationen sind; (b) nicht die Konstruktion aller Submodelle erfordert, die die betrachteten auf zeitgesteuerten Zuständen basierenden Prozesse und Verhaltensspezifikationen zusammenstellen, und auch nicht ihre nachfolgende Zusammenstellung zu letzten Prozessen und Spezifikationsmodellen erfordert: der Syntheseansatz zügelt das Phänomen der Aktivitäts-(Zustands-)Explosion durch direktes Konstruieren der Übergangsstrukturen, die das synchrone Verhalten aller Bestandteilsprozesse und Spezifikationen innerhalb der betrachteten Spezifikationen eingeschränkt realisieren.

Claims

1. Verfahren zur Modellierung eines Prozeßflusses gemäß einem spezifizierten Verhalten mit einem Computer mit den folgenden Merkmalen:

a) mindestens ein erster und ein zweiter teilweiser Prozeß des Prozeßflusses werden in Art eines ersten und eines zweiten Automaten beschrieben;

b) das spezifizierte Verhalten wird als specificationautomat in Art eines Automaten beschrieben;

c) abgeleitet aus dem Prozeßfluß und dem specificationautomat wird ein Automat als processautomat dergestalt konstruiert, daß beginnend mit einem Anfangszustand des Prozeßflusses und dann schrittweise weiter für jeden jeweiligen weiteren Zustand mindestens des ersten und des zweiten Automaten analysiert wird, welche Zustandsübergänge gemäß der Beschreibung des jeweiligen Automaten möglich sind, und außerdem geprüft wird, welche Zustandsübergänge gemäß dem specificationautomat zulässig sind, während nur solche Zustandsübergänge in den processautomat integriert werden, die möglich und zulässig sind;

d) der Prozeßfluß wird durch den Computer unter Verwendung des processautomat gesteuert.

2. Verfahren nach Anspruch 1 mit den folgenden Merkmalen:

a) Zustandsübergänge werden mindestens in steuerbare und unsteuerbare Zustandsübergänge unterschieden;

b) falls ein faulttransition während der Konstruktion des processautomat ein faultstate erreicht, wobei mindestens ein unsteuerbarer Zustandsübergang möglich ist, der von dem specificationautomat nicht zugelassen wird, dann wird der Konstruktionsprozeß des processautomat vor dem Übergang, der zu dem faultstate führte, dem beforefaultstate, in einer Neuanalyse im Modellzustand wiederaufgenommen, und von dort aus ein anderer Zustandsübergang analysiert.

3. Verfahren nach einem der vorhergehenden Ansprüche mit den folgenden Merkmalen:

a) mindestens die Zustandsübergänge des ersten und des zweiten teilweisen Prozesses des Prozeßflusses sowie die des specificationautomat werden jeweils mit einer oberen und einer unteren Zeitschranke versehen, die in Zeiteinheiten gemessenen werden, wohingegen die untere Zeitschranke den frühestmöglichen Zeitpunkt und die obere Zeitschranke den spätesten Zeitpunkt definiert, an dem der Zustandsübergang stattfinden kann, und die Zeiteinheiten gezählt werden, sobald ein Anfangszustand eines Automaten erreicht ist;

b) im Anfangszustand wird es mit mindestens einem Zustandsübergang als initialtransition gestartet, der die niedrigste untere Zeitschranke aufweist;

c) ein weiterer Zustand des processautomat wird erzeugt durch Bereitstellung aller möglichen Zustandsübergänge, die von diesem Modellzustand aus starten können, den furtherstatetransitions, mit Ausnahme des initialtransition, mit neuen Zeitschranken, durch Subtraktion der oberen Zeitschranke des initialtransition von der ehemaligen unteren Zeitschranke des jeweiligen Zustandsübergangs, um dessen neue untere Zeitschranke aufzubauen, und durch Subtraktion der unteren Zeitschranke des initialtransition von der ehemaligen oberen Zeitschranke des jeweiligen Zustandsübergangs, um dessen neue obere Zeitschranke aufzubauen;

d) negative Zeitwerte werden auf Null gesetzt;

e) im Fall der Neuanalyse des faultstate am beforefaultstate wird geprüft, ob es einen steuerbaren Zustandsübergang gibt, wodurch verhindert werden kann, daß das faultstate auftritt, durch Variation seiner Zeitgrenzen, und wenn dies möglich ist, wird mindestens eine Zeitgrenze dieses Zustandsübergangs entsprechend geändert.

4. Verfahren nach Anspruch 3, wobei im beforefaultstate ein Steuerbarszustandsübergang gestartet wird, indem mindestens eine Zeitgrenze variiert wird, und/oder es wird verhindert, daß das faultstate auftritt, durch Variation mindestens einer Zeitgrenze.

5. Verfahren nach einem der vorhergehenden Ansprüche, wobei das processautomat mindestens gemäß den folgenden Merkmalen konstruiert wird:

a) in einem ersten Initialisierungsschritt werden sechs Mengen, die neue Menge, die letzte Menge, die schlechte Menge, die Markierermenge, die nichtblockierende Menge und die Übergangsmenge, die alle, anfangs leer, mit der folgenden anfänglichen zeitgesteuerten Aktivität definiert:

c&sub0; = (e&sub0;, b&sub0;) = (a0,1, ..., a0,n), {(lσ, uσ) für alle σ Σ}, (a0,n+1, ..., a0,m))

und mit

c = (e, b)

c = c&sub0; = (a&sub1;, ..., an), {(rσ, tσ) für alle σ Σ}, (an+1, ..., am))

und wobei c zu der neuen Menge hinzugefügt wird, und wenn alle Aktivitäten ai, i = 1, ..., n, aus denen a besteht, Markiereraktivitäten sind, d. h. ai Am,i, i = 1, ..., n, gilt, e zu der Markierer- und der nichtblockierenden Menge hinzugefügt wird;

b) wobei

c = (e, b) = ((a&sub1;, ..., an), {(rσ, tσ) für alle σ Σ}, (an+1, ..., am))

mit e gleich der Menge von Ereignissen σ Σ, für die δ(a, σ) definiert ist, als die physisch mögliche Ereignismenge von c bezeichnet, bestimmt wird und mit b gleich der Menge von Ereignissen σ Σ, für die δB(b, σ) definiert ist, als die legale Ereignismenge von c bezeichnet, bestimmt wird;

c) die zeitgesteuerte Aktivität

wird aus der neuen Menge entfernt, wenn entweder alle unsteuerbaren Ereignisse σ in der physisch möglichen Ereignismenge von c in der legalen Ereignismenge von c enthalten sind oder wenn für alle unsteuerbaren Ereignisse σ in der physisch möglichen Ereignismenge von c, die nicht in der legalen Ereignismenge von c enthalten sind, ein erzwingbares Ereignis β existiert, das sich sowohl in der physisch möglichen Ereignismenge von c als auch in der legalen Ereignismenge von c befindet, dergestalt, daß seine untere Zeitschranke rβ streng kleiner als die untere Zeitschranke rσ von σ ist, wird c = (e, b) in der letzten Menge von σ plaziert, andernfalls wird c in der schlechten Menge plaziert;

d) für alle zeitgesteuerten Aktivitäten c in der schlechten Menge werden die entsprechenden zeitgesteuerten Aktivitäten c' in der letzten Menge aus c, die bei einem Übergang σ erreicht werden können, bestimmt und

- wenn der von c zu c führende Übergang σ unsteuerbar ist und es weder in der physisch möglichen Ereignismenge von c noch in der legalen Ereignismenge von c ein erzwingbares Ereignis β gibt, dergestalt, daß seine untere Zeitschranke rβ streng kleiner als die untere Zeitschranke rσ von σ ist, wird die Aktivität c' aus der Markierer-, der nichtblockierenden und der letzten Menge entfernt und zu der schlechten Menge hinzugefügt, und der Übergang (c', σ, c) wird aus der Übergangsmenge entfernt,

- wenn der von c zu c' führende Übergang σ unsteuerbar ist und es sowohl in der physisch möglichen Ereignismenge von c als auch in der legalen Ereignismenge von c ein erzwingbares Ereignis β gibt, dergestalt, daß seine untere Zeitschranke rβ streng kleiner als die untere Zeitschranke rσ von σ ist, wird uβ streng kleiner als rσ gesetzt,

- wenn der von c zu c' führende Übergang σ steuerbar ist, wird der Übergang (c', σ, c) aus der Übergangsmenge entfernt und dadurch gesperrt;

e) Merkmal d wird wiederholt, bis die Anzahl von zeitgesteuerten Aktivitäten in der schlechten Menge invariant bleibt.

6. Verfahren nach Anspruch 5 mit den folgenden Merkmalen:

a) für alle zeitgesteuerten Aktivitäten c in der letzten Menge und für alle Ereignisse σ, die sowohl in der physisch möglichen Ereignismenge von c als auch in der legalen Ereignismenge von c enthalten sind, wird die entsprechende zeitgesteuerte Aktivität δ(c, σ) = c' berechnet mit

c' = (a',{(r'τ, t'τ) für alle τ Σ},b'), und mit a' = (a'&sub1;, ..., a'n)

und

b' = (an+1', ..., a'm)

a' wird für i = 1, ..., n folgendermaßen berechnet:

und für τ ≠ σ werden die untere und die obere Zeitschranke (r'τ, t'τ), r Σ, folgendermaßen berechnet:

und für τ = σ folgendermaßen:

(r'τ, t'τ) = (lr, ur),

während b' für i = n + 1, ..., m folgendermaßen berechnet wird:

b) und wenn sich c' nicht bereits entweder in der letzten Menge oder in der schlechten Menge befindet, wird c' zu der neuen Menge hinzugefügt, und wenn alle Aktivitäten ai, i = 1, ..., m, aus denen a' und b' bestehen, Markiereraktivitäten sind, d. h. a'i Am,i, i = 1, ..., m, wird c' zu der Markierer- und der nichtblockierenden Menge hinzugefügt; und der Übergang (c', σ, c) wird zu der Übergangsmenge hinzugefügt.

7. Verfahren nach einem der Ansprüche 5 und 6, wobei aufeinanderfolgend von Anspruch 5 die Merkmale b bis e und von Anspruch 6 die Merkmale a und b wiederholt werden, bis die neue Menge leer ist.

8. Verfahren nach einem der Ansprüche 5 bis 7 mit den folgenden Merkmalen:

a) für alle zeitgesteuerten Aktivitäten c in der nichtblockierenden Menge werden die entsprechenden zeitgesteuerten Aktivitäten c' in der letzten Menge, von denen aus c in einem Übergang σ erreicht werden kann, bestimmt, und c' wird zu der nichtblockierenden Menge hinzugefügt, wohingegen Merkmal a) wiederholt wird, bis die Anzahl von zeitgesteuerten Aktivitäten in der nichtblockierenden Menge invariant bleibt;

b) alle zeitgesteuerten Aktivitäten c in der letzten Menge und nicht in der nichtblockierenden Menge werden aus der Markierer- und der letzten Menge entfernt und in der schlechten Menge plaziert;

c) für alle Aktivitäten in der schlechten Menge werden die entsprechenden zeitgesteuerten Aktivitäten c' in der letzten Menge, von denen aus c in einem Übergang σ erreicht werden kann, bestimmt und:

- wenn der von c zu c' führende Übergang σ unsteuerbar ist und es Weder in der physisch möglichen Ereignismenge von c noch in der legalen Ereignismenge von c ein erzwingbares Ereignis β gibt, dergestalt, daß seine untere Zeitschranke rβ streng kleiner als die untere Zeitschranke rσ von σ ist, wird die Aktivität c' aus der Markierer-, der nichtblockierenden und der letzten Menge entfernt und zu der schlechten Menge hinzugefügt, und der Übergang (c', σ, c) wird aus der Übergangsmenge entfernt,

- wenn der von c zu c' führende Übergang σ unsteuerbar ist und es sowohl in der physisch möglichen Ereignismenge von c als auch in der legalen Ereignismenge von c ein erzwingbares Ereignis β gibt, dergestalt, daß seine untere Zeitschranke rβ streng kleiner als die untere Zeitschranke rσ von σ ist, wird uβ so gesetzt, daß uβ streng kleiner als rσ ist;

d) Merkmal c) wird wiederholt, bis die Anzahl von zeitgesteuerten Aktivitäten in der schlechten Menge invariant bleibt.

9. Verfahren nach einem der Ansprüche 5 bis 8, wobei eine graphische Ausgabe erzeugt wird, durch Anzeigen aller Elemente in der Übergangsmenge zusammen mit ihren zugeordneten Zuständen.

10. Herstellungsprozeß für eine Prozeßsteuerung, wobei ein Computer aufgebaut wird, der eines der Verfahren nach Anspruch 1 bis 9 ausführt und als Prozeßsteuercomputer angewandt wird.