Marking Data-Informativity and Data-Driven Supervisory Control of Discrete-Event Systems

Dieses Papier entwickelt einen datengesteuerten Ansatz für die nicht-blockierende Markierungsüberwachung diskreter Ereignissysteme, indem es das neuartige Konzept der Markierungsdaten-Informativität einführt, dessen Verifizierungsalgorithmus bereitstellt und bei unzureichenden Daten Strategien zur Einschränkung der Spezifikation oder zur Daten-Informativierung vorschlägt.

Das Wesentliche

Hier ist eine einfache Erklärung der wissenschaftlichen Arbeit, die sich an ein allgemeines Publikum richtet, ohne den technischen Jargon zu verwenden.

🤖 Der Roboter im Nebel: Wie man Maschinen steuert, ohne sie zu verstehen

Stellen Sie sich vor, Sie müssen einen Roboter durch ein unbekanntes Labyrinth führen. Ihr Ziel ist es, den Roboter sicher zum Ausgang (dem „Markierungs"-Punkt) zu bringen und dabei gefährliche Zonen zu vermeiden.

Das Problem: Sie kennen die Karte des Labyrinths nicht. Sie haben keine Baupläne für die Wände oder die Türen. Sie wissen nur, dass der Roboter existiert und dass er bestimmte Bewegungen machen kann.

Was Sie aber haben, ist ein Schnipsel-Notizbuch mit drei Arten von Informationen:

1. Beobachtungen (D): Sie haben gesehen, dass der Roboter in der Vergangenheit bestimmte Wege erfolgreich zurückgelegt hat (z. B. „Links, Rechts, Geradeaus").
2. Erfolge (Dm): Von diesen Wegen wissen Sie genau, welche tatsächlich zum Ziel geführt haben.
3. Unmögliches (D-): Sie wissen aus Erfahrung, dass der Roboter niemals bestimmte Dinge tun kann (z. B. „Er kann nicht durch eine Wand laufen" oder „Er kann nicht sofort nach dem Start nach links abbiegen").

Die Frage der Forscher ist: Reichen diese Notizen aus, um eine perfekte Steuerungsanleitung (einen „Aufseher") zu schreiben, die den Roboter immer sicher ans Ziel bringt, ohne dass wir die komplette Karte kennen?

---

🕵️‍♂️ Das Konzept der „Daten-Informativität"

Die Autoren nennen das, was sie suchen, Marking Data-Informativity (auf Deutsch etwa: „Daten-Aussagekraft für das Erreichen des Ziels").

Stellen Sie sich vor, Sie spielen ein Spiel, bei dem Sie raten müssen, welche Wege sicher sind.

• Wenn Ihre Notizen (die Daten) so detailliert sind, dass Sie jeden möglichen Weg des Roboters vorhersagen können, der zu einem Ziel führt, und Sie wissen, welche Wege zu einem Absturz führen, dann sind Ihre Daten „informativ".
• In diesem Fall können Sie eine Regel aufstellen: „Wenn der Roboter hier ist, darf er nur diesen Knopf drücken." Diese Regel funktioniert für jeden Roboter, der so aussieht wie der, den Sie beobachtet haben.

Die magische Regel (Das Theorem):
Die Forscher haben herausgefunden, dass man die Daten nicht komplett durchgehen muss, um zu wissen, ob sie reichen. Man muss nur prüfen:

• Wenn der Roboter an einem Punkt steht, an dem er das Ziel erreichen könnte, und es gibt einen Weg, den er nicht kontrollieren kann (z. B. ein Windstoß, der ihn wegpustet), dann muss dieser Weg entweder:
  1. Immer noch sicher zum Ziel führen (in Ihren Notizen enthalten), ODER
  2. Etwas sein, das Sie wissen, dass es unmöglich ist (in Ihrer Liste der „Unmöglichen" enthalten).

Wenn beides nicht zutrifft – also der Roboter durch einen unkontrollierbaren Windstoß in eine unbekannte, potenziell gefährliche Zone geraten könnte, von der Sie nichts wissen – dann sind Ihre Daten nicht informativ genug. Sie können keine sichere Regel aufstellen.

---

🛠️ Was tun, wenn die Daten nicht reichen? (Die „Restriktive" Lösung)

Stellen Sie sich vor, Ihre Notizen sind lückenhaft. Der Roboter könnte durch einen unkontrollierbaren Windstoß in eine graue Zone geraten, von der Sie nichts wissen. Dann ist Ihre Datenlage „nicht informativ". Sie können keine Regel für das gesamte Zielgebiet aufstellen.

Aber! Vielleicht können Sie das Ziel verkleinern.

Die Autoren schlagen vor: Schneiden wir das Zielgebiet so lange zu, bis es passt.
Das nennen sie Restricted Marking Data-Informativity.

• Analogie: Sie wollen einen Roboter durch ein riesiges Waldgebiet steuern. Aber Sie wissen nicht, ob im Norden ein Abgrund ist. Also sagen Sie: „Okay, wir lassen den Norden weg. Wir steuern den Roboter nur durch den Süden, wo wir sicher sind."
• Die Forscher haben einen Algorithmus entwickelt, der automatisch das größte mögliche Gebiet findet, das noch sicher ist. Es ist wie ein Schere, die das unsichere Gebiet wegschneidet, bis nur noch der sicherste, größte Rest übrig bleibt.

Wenn dieser Rest noch größer als Null ist, haben Sie eine Lösung! Wenn er komplett weggeschnitten wird, dann sind Ihre Daten so schlecht, dass Sie den Roboter gar nicht sicher steuern können, ohne mehr Informationen zu sammeln.

---

🧩 Warum ist das „Markieren" (Marking) wichtig?

In der alten Welt der Robotik (modellbasiert) schaut man oft nur darauf, ob der Roboter irgendwie nicht stecken bleibt. In dieser neuen, datengetriebenen Welt ist es entscheidend, dass er das Ziel erreicht.

• Ohne Markierung: Ein Supervisor könnte sagen: „Der Roboter darf nicht stecken bleiben." Das Ergebnis könnte sein, dass der Roboter ewig im Kreis läuft, aber nie stirbt. Das ist technisch „sicher", aber nutzlos.
• Mit Markierung: Der Supervisor sagt: „Der Roboter darf nicht stecken bleiben UND er muss das Ziel erreichen."
• Der Unterschied: Die Autoren zeigen, dass wenn man nur auf „Nicht-Steckenbleiben" achtet, man manchmal Wege zulässt, die zwar sicher sind, aber in eine Sackgasse führen, aus der es kein Ziel mehr gibt. Durch das Hinzufügen des „Ziel-Kriteriums" (Markierung) werden diese nutzlosen Pfade automatisch abgeschnitten.

---

🚀 Zusammenfassung: Der Fahrplan für die Zukunft

Die Autoren haben einen neuen Weg gefunden, um Roboter in unbekannten Umgebungen zu steuern, ohne dass man sie vorher genau modellieren muss. Ihr Rezept lautet:

1. Sammeln: Beobachten Sie das System und notieren Sie, was passiert, was erfolgreich war und was unmöglich ist.
2. Prüfen (Algorithmus 1): Sind diese Notizen detailliert genug, um eine perfekte Steuerungsregel zu schreiben?
   • Ja? Super! Schreiben Sie die Regel.
   • Nein? Kein Problem.
3. Anpassen (Algorithmus 3): Schneiden Sie das Zielgebiet so lange zu, bis es mit Ihren Notizen übereinstimmt. Finden Sie den größten noch sicheren Bereich.
   • Ist noch etwas übrig? Schreiben Sie die Regel für diesen Bereich.
   • Ist alles weg? Dann brauchen Sie mehr Daten (mehr Beobachtungen oder mehr Wissen über das Unmögliche).

Fazit:
Diese Arbeit ist wie ein Kompass für Ingenieure in einer Welt voller Unsicherheit. Sie zeigt, wie man mit unvollständigen Informationen (Daten) trotzdem sichere und zielgerichtete Entscheidungen treffen kann, anstatt zu warten, bis man die perfekte Landkarte hat. Das ist besonders wichtig für autonome Fahrzeuge, Lagerroboter oder Systeme in unbekannten Umgebungen, wo das Erstellen perfekter Modelle unmöglich ist.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des vorliegenden Papers auf Deutsch:

Titel

Marking Data-Informativity and Data-Driven Supervisory Control of Discrete-Event Systems
(Markierungs-Dateninformativität und datengesteuerte überwachende Steuerung diskreter Ereignissysteme)

1. Problemstellung

Das Paper adressiert das Problem der überwachenden Steuerung (Supervisory Control) von Diskreten Ereignissystemen (DES), bei denen das zugrundeliegende Modell des Systems (die "Pflanze") unbekannt ist.

• Kontext: In der traditionellen modellbasierten Steuerung wird ein DES als endlicher Automat modelliert, und ein Supervisor wird basierend auf diesem Modell entworfen. In vielen realen Szenarien (z. B. autonome Fahrzeuge in unbekanntem Gelände) ist eine vollständige Modellierung jedoch schwierig oder unmöglich.
• Datenlage: Anstelle eines Modells stehen nur Daten zur Verfügung:
  1. Beobachtungsdaten ($D$): Eine Menge beobachteter Verhaltensweisen (Ereignisfolgen).
  2. Markierte Beobachtungsdaten ($D_m$): Eine Teilmenge von $D$, die Zustände erreicht, die als "Zielzustände" (Marker States) definiert sind.
  3. Vorwissen ($D^-$): Eine Menge von Ereignisfolgen, die bekanntermaßen nicht vom System generiert werden können (unmögliche Verhaltensweisen).
• Ziel: Es soll ein markierender, nicht-blockierender Supervisor entworfen werden, der eine gegebene Spezifikation erfüllt, ohne dass das exakte Modell der Pflanze bekannt ist. Der Supervisor muss für alle möglichen Modelle gültig sein, die konsistent mit den vorliegenden Daten sind.
• Herausforderung: Ein Supervisor ist nur dann gültig, wenn er das System nicht in einen Zustand führt, von dem aus kein Zielzustand mehr erreichbar ist (Nicht-Blockierbarkeit). Die Frage ist: Unter welchen Bedingungen an die Datenmenge ist ein solcher Supervisor überhaupt konstruierbar?

2. Methodik und Theoretischer Rahmen

Die Autoren entwickeln einen datengesteuerten Ansatz, der direkt auf den Daten operiert, anstatt zuerst ein Modell zu identifizieren.

A. Konzept der "Marking Data-Informativity" (Markierungs-Dateninformativität)

Dies ist das zentrale neue Konzept des Papers. Eine Datenmenge $(D, D_m, D^-)$ ist markierungsinformativ für eine Spezifikation $E$, wenn ein markierender, nicht-blockierender Supervisor existiert, der für alle mit den Daten konsistenten Pflanzen die Spezifikation $K_{D_m} = D_m \cap E$ erzwingt.

• Kriterium (Theorem 1): Die Daten sind genau dann informativ, wenn für jede Zeichenkette $s \in K_{D_m}$ und jedes unkontrollierbare Ereignis $\sigma \in \Sigma_u$ gilt:
  $$s\sigma \in K_{D_m} \cup D^-$$
  Das bedeutet: Wenn ein unkontrollierbares Ereignis nach $s$ auftritt, muss es entweder im erlaubten Bereich ($K_{D_m}$) bleiben oder als unmöglich bekannt sein ($D^-$). Tritt es in einem Bereich auf, der weder erlaubt noch als unmöglich bekannt ist, ist die Datenmenge nicht informativ.

B. Verifikationsalgorithmus (Algorithmus 1)

Um die Informativität zu prüfen, wird ein datengesteuerter Automat ($\hat{G}$) konstruiert. Dieser ist ein Präfixbaum, der alle Zeichenketten aus $D \cup D^-$ abbildet.

• Der Algorithmus prüft für jeden Zustand, der durch eine Zeichenkette aus $K_{D_m}$ erreicht wird, ob alle möglichen unkontrollierbaren Übergänge entweder in $K_{D_m}$ oder in $D^-$ führen.
• Führt ein Übergang in einen "weißen" Bereich (nicht beobachtet, nicht als unmöglich bekannt), scheitert die Informativität.

C. Eingeschränkte Markierungsinformativität und Markierungsinformatisierbarkeit

Falls die Datenmenge nicht informativ ist, schlagen die Autoren zwei neue Konzepte vor:

1. Eingeschränkte Markierungsinformativität ($K$-Informativität): Gibt es eine Teilmenge $K \subseteq K_{D_m}$, für die die Daten informativ sind?
2. Markierungsinformatisierbarkeit: Existiert überhaupt eine nicht-leere Teilmenge $K$, für die die Daten informativ sind?

Das Paper zeigt, dass die Bedingung für Informativierbarkeit strenger ist als bei nicht-markierten Ansätzen, da die Nicht-Blockierbarkeit des Supervisors garantiert werden muss.

D. Berechnung der am wenigsten eingeschränkten Lösung (Algorithmus 3)

Um die größtmögliche zulässige Spezifikation zu finden, wird ein Algorithmus entwickelt, der:

1. Die Menge der nicht-informativen Zustände ($N(Q_K)$) im datengesteuerten Automaten identifiziert.
2. Einen Teilautomaten konstruiert, der diese Zustände vermeidet.
3. Den supremalen kontrollierbaren Teilautomaten ($supcon$) berechnet, um die größtmögliche Teilmenge $K_{sup} \subseteq K_{D_m}$ zu finden, für die ein nicht-blockierender Supervisor existiert.
4. Prüft, ob $K_{sup}$ nicht-leer ist. Ist dies der Fall, ist die Datenmenge "markierungsinformatisierbar".

3. Wichtige Beiträge

1. Formalisierung von Marking Data-Informativity: Einführung und mathematische Charakterisierung eines neuen Konzepts, das die Notwendigkeit von Zielzuständen (Markern) und Nicht-Blockierbarkeit in datengesteuerten Steuerungsproblemen berücksichtigt.
2. Verifikationsalgorithmen: Entwicklung effizienter Algorithmen (basierend auf datengesteuerten Automaten), um zu prüfen, ob Daten ausreichen, um einen Supervisor zu entwerfen.
3. Lösung bei unzureichenden Daten: Einführung der Konzepte "Restricted Marking Data-Informativity" und "Marking Informatizability". Das Paper bietet einen Weg, auch bei unvollständigen Daten die größtmögliche Teilmenge der Spezifikation zu finden, die sicher gesteuert werden kann.
4. Unterscheidung zu nicht-markierten Ansätzen: Demonstration, dass Ansätze ohne Berücksichtigung von Markern (Zielzuständen) zu blockierenden Supervisoren führen können, was in sicherheitskritischen Anwendungen (wie Roboternavigation) inakzeptabel ist.

4. Ergebnisse und Validierung

• Beispiel Roboternavigation: Das Paper verwendet ein Szenario mit einem Roboter, der eine Gefahrenzone vermeiden muss.
  • Es wird gezeigt, dass ein datengesteuerter Supervisor, der Markierungen ignoriert, Pfade zulassen kann, die zwar die Spezifikation erfüllen, aber den Roboter in einer Sackgasse stecken lassen (Blockierung).
  • Der vorgeschlagene Ansatz mit Markierungen eliminiert diese blockierenden Pfade und garantiert, dass das Ziel erreicht werden kann.
• Algorithmische Wirksamkeit: Die Algorithmen (1 und 3) werden an mehreren Beispielen demonstriert, um zu zeigen, wie sie entscheiden, ob Daten informativ sind, und wie sie im negativen Fall die bestmögliche Teilmenge berechnen.
• Einfluss von Vorwissen ($D^-$): Die Ergebnisse zeigen, dass die Qualität der Daten (insbesondere das Vorwissen über unmögliche Verhaltensweisen $D^-$) entscheidend ist. Mehr Vorwissen kann die Anforderungen an die Beobachtungsdaten ($D, D_m$) senken.

5. Bedeutung und Ausblick

• Praktische Relevanz: Der Ansatz ermöglicht die Steuerung komplexer Systeme in unbekannten Umgebungen, wo eine vollständige Modellierung zu aufwendig oder unmöglich ist. Dies ist besonders relevant für IoT, autonome Systeme und Produktionsumgebungen.
• Garantie von Sicherheit und Zielerreichung: Durch die explizite Berücksichtigung von Markern und Nicht-Blockierbarkeit wird sichergestellt, dass das gesteuerte System nicht nur Regeln einhält, sondern auch funktionsfähig bleibt (kein Deadlock).
• Zukünftige Forschung: Die Autoren schlagen vor, die Methoden auf andere Eigenschaften wie Beobachtbarkeit (Observability), Diagnosefähigkeit (Diagnosability) und Opazität (Opacity) zu erweitern und zu untersuchen, wie neue Daten in bereits konstruierte Supervisoren integriert werden können.

Fazit: Das Paper stellt einen wichtigen Schritt in der Entwicklung datengesteuerter Kontrolltheorie dar, indem es die Lücke zwischen reinen Datenanalysen und den strengen Anforderungen der nicht-blockierenden Steuerung von diskreten Ereignissystemen schließt.