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

Each language version is independently generated for its own context, not a direct translation.

Stel je voor dat je een robot moet leren navigeren door een onbekende stad. Je hebt geen plattegrond (het model is onbekend), maar je hebt wel een dagboek vol met verhalen van eerdere reizen (de data). Soms weet je ook zeker dat bepaalde straten er niet zijn of gevaarlijk zijn (voorafgaande kennis).

Het doel is om een "verkeersregelaar" (een supervisor) te bouwen die de robot veilig naar zijn bestemming leidt, zonder dat hij vastloopt of in gevaarlijke zones belandt.

Dit artikel, geschreven door Liu, Fuchiwaki en Cai, gaat over hoe je zo'n verkeersregelaar kunt bouwen alleen op basis van die verhalen (data), zonder dat je de stad zelf kent.

Hier is een uitleg in simpele taal, met een paar creatieve vergelijkingen:

1. Het Probleem: De "Blinde" Robot

Normaal gesproken bouwen ingenieurs een computermodel van een systeem (zoals een fabriek of een robot) en bouwen ze daarop een controller. Maar wat als je het systeem niet kent?

De situatie: Je hebt een robot die door een onbekend terrein loopt. Je ziet wat hij doet (bijvoorbeeld: "hij ging linksaf, toen rechtdoor, en bereikte het doel"). Je ziet ook wat hij niet doet (bijvoorbeeld: "hij probeerde nooit door een muur te lopen").
De vraag: Kunnen we op basis van deze losse verhalen een regelmaat maken die altijd werkt, ook voor de echte robot die we nog niet volledig begrijpen?

2. Het Concept: "Informatieve Data" (Het Volledige Pakket)

De auteurs introduceren een nieuw woord: Marking Data-Informativity.
Laten we dit vergelijken met het oplossen van een raadsel.

De Observaties ( $D$ ): Je hebt een lijstje met routes die de robot heeft afgelegd.
De Doelen ( $D_m$ ): Je hebt een lijstje met routes die succesvol eindigden bij het doel (de "markering").
De Onmogelijkheden ( $D^-$ ): Je hebt een lijstje met routes die nooit kunnen bestaan (bijvoorbeeld: "de robot kan niet vliegen").

Wanneer is je data "informatief"?
Stel je voor dat je een verkeersregelaar maakt. Als de robot op een kruispunt staat en er is een oncontroleerbaar licht (een gebeurtenis die je niet kunt stoppen, zoals een plotselinge windvlaag), dan moet je zeker weten dat de robot niet in een doodlopende straat belandt.

Als je data laat zien dat de robot altijd veilig blijft, of als je zeker weet dat de gevaarlijke route onmogelijk is (staat op je lijstje $D^-$ ), dan is je data informatief. Je hebt genoeg informatie om een veilige regelaar te bouwen.
Als je data een gat laat (je weet niet of de robot veilig is, en je weet ook niet of de gevaarlijke route onmogelijk is), dan is je data niet informatief. Je kunt geen veilige regelaar bouwen zonder risico.

3. De Oplossing: De "Slimme Verkeersregelaar"

Als de data informatief is, kunnen de auteurs een algoritme (een recept) geven om de perfecte verkeersregelaar te bouwen. Deze regelaar zorgt ervoor dat:

De robot zijn doel bereikt (hij loopt niet vast).
Hij nooit in gevaarlijke zones komt.
Hij zoveel mogelijk vrijheid heeft om te bewegen, zolang het maar veilig is.

4. Wat als de Data Niet Volledig is? (Beperkte Informativiteit)

Soms is je data niet perfect. Misschien heb je te weinig verhalen of te weinig kennis over wat onmogelijk is. Dan is de data "niet informatief" voor het hele doel.

De oplossing: In plaats van het hele doel op te geven, kijken de auteurs of ze een kleinere, veilige versie van het doel kunnen vinden.
Vergelijking: Stel je wilt de robot laten lopen van punt A naar punt B, maar je weet niet of de route via de brug veilig is. In plaats van te zeggen "het kan niet", zeggen we: "Oké, laten we de route via de tunnel gebruiken. Die is veilig en leidt ook naar het doel."
Dit noemen ze Marking Informatizability: Kunnen we een klein stukje van het doel vinden waarvoor de data wél werkt?

5. Het "Grootste Veilige Stukje" (Minimaal Beperkt)

Als je een veilige route kunt vinden, willen we natuurlijk de langste en meest vrijheidsgevende route hebben.

De auteurs bouwen een algoritme dat alle mogelijke "gevaarlijke" routes uit de data haalt en kijkt wat er overblijft.
Het resultaat is de grootst mogelijke veilige route die je kunt garanderen met de informatie die je hebt. Het is alsof je een pad door een bos kapt: je haalt alle struiken weg die je niet kent (die misschien giftig zijn), en laat alleen het pad over dat je zeker weet dat veilig is.

Samenvatting in één zin

Dit artikel leert ons hoe we een robot (of ander systeem) veilig kunnen sturen naar een doel, zelfs als we het systeem niet kennen, zolang we maar genoeg verhalen hebben over wat hij wel doet, wat hij niet doet, en welke routes hij nooit kan nemen. Als de verhalen niet genoeg zijn, vinden ze het grootste veilige stukje route dat wel werkt.

De kernboodschap: Je hoeft niet alles te weten om iets veilig te besturen; je hebt alleen de juiste combinatie van "wat we hebben gezien" en "wat we weten dat onmogelijk is" nodig.

Each language version is independently generated for its own context, not a direct translation.

Hier is een gedetailleerde technische samenvatting van het paper "Marking Data-Informativity and Data-Driven Supervisory Control of Discrete-Event Systems" in het Nederlands.

Titel: Marking Data-Informativity en Data-Gedreven Supervisieve Controle van Discrete-Event Systemen

Auteurs: Yingying Liu, Kuma Fuchiwaki, en Kai Cai (Osaka Metropolitan University)

1. Probleemstelling

Traditionele supervisieve controle voor Discrete-Event Systemen (DES) is modelgebaseerd: men bouwt eerst een exact model (een eindige automaat) van het systeem en ontwerpt vervolgens een controller (supervisor) op basis van dit model. In veel praktische scenario's, zoals autonome voertuigen of magazijnautomatisering, is het echter moeilijk of onmogelijk om een exact model van de omgeving te construeren.

Dit paper richt zich op een data-gedreven aanpak waarbij het model van het plant (het te controleren systeem) onbekend is. In plaats daarvan zijn drie soorten data beschikbaar:

Observatie-data ( $D$ ): Een verzameling waargenomen gedragsreeksen (strings van gebeurtenissen) van het systeem.
Gemarkeerde observatie-data ( $D_m$ ): Een subset van $D$ die reeksen bevat die een "doel" of markerende toestand bereiken.
A priori kennis ( $D^-$ ): Data over onmogelijke gedragsreeksen (wat het systeem niet kan doen).

De centrale vraag: Onder welke voorwaarden van deze beschikbare data-set kan een geldige, niet-blokkerende supervisor worden ontworpen voor een onbekend DES om een gegeven specificatie te voldoen?

Het paper introduceert het concept van marking (gemarkeerd gedrag), wat essentieel is om te garanderen dat het systeem niet vastloopt (deadlock) en dat de specifieke doelstellingen (gemarkeerde toestanden) bereikt kunnen worden.

2. Methodologie

De auteurs ontwikkelen een theoretisch raamwerk en algoritmen om de bruikbaarheid van data voor supervisieve controle te verifiëren en synthetiseren.

A. Concept: Marking Data-Informativity

De kern van de methodologie is het definiëren van marking data-informativity. Een data-set $(D, D_m, D^-)$ is "marking informatief" voor een specificatie $E$ als er een supervisor bestaat die voor alle mogelijke plant-modellen die consistent zijn met de data, een niet-blokkerende gesloten-lus creëert die voldoet aan de specificatie.

Criterium (Stelling 1): Een data-set is marking informatief dan en slechts dan als voor elke string $s$ $s$ in de gespecificeerde taal $K_{D_m}$ $K_{D_{m}}$ en voor elke oncontroleerbare gebeurtenis $\sigma \in \Sigma_u$ $σ \in Σ_{u}$ , geldt dat $s\sigma$ $s σ$ óf in $K_{D_m}$ $K_{D_{m}}$ zit, óf in de set van onmogelijke gedragingen $D^-$ $D^{-}$ zit.
- Dit betekent dat als een oncontroleerbare gebeurtenis optreedt, het resultaat ofwel binnen de specificatie moet blijven, óf we moeten met zekerheid weten dat het onmogelijk is (via $D^-$ ). Als het noch in de specificatie zit, noch als onmogelijk bekend is, is de data onvoldoende informatief.

B. Data-Gedreven Automaten

Om dit te verifiëren, introduceren de auteurs een data-gedreven automaat ( $\hat{G}$ ). Dit is een prefix-boomstructuur die is gebaseerd op de waargenomen data ( $D \cup D^-$ ).

Toestanden corresponderen met waargenomen strings.
De automaat helpt bij het visualiseren van overgangen en het identificeren van "niet-informatieve toestanden" (waar de data onzekerheid creëert over oncontroleerbare overgangen).

C. Beperkte Marking Data-Informativity en Informatiseerbaarheid

Als de data-set niet informatief is voor de volledige specificatie, stellen de auteurs twee nieuwe concepten voor:

Restricted Marking Data-Informativity: Is er een subset van de specificatie waarvoor de data wel informatief is?
Marking Informatizability: Bestaat er überhaupt een niet-lege subset van de specificatie waarvoor de data informatief is?

D. Algoritmen

Het paper presenteert drie kernalgoritmen:

Algoritme 1: Controleert of een data-set marking informatief is voor een gegeven specificatie door te inspecteren of er oncontroleerbare overgangen zijn die leiden naar toestanden die noch in de specificatie, noch in de onmogelijke set zitten.
Algoritme 2: Identificeert de set van "niet-informatieve toestanden" ( $N(Q_K)$ ) in de data-gedreven automaat.
Algoritme 3: Berekent de grootste subset ( $K_{sup}$ ) van de specificatie waarvoor de data-set "least restricted marking informatief" is. Dit wordt gedaan door de niet-informatieve toestanden te verwijderen en een supremale controleerbare subtaal te berekenen (via een supcon functie) op een gemodificeerde automaat.

3. Belangrijkste Bijdragen

Formalisatie van Marking Data-Informativity: De eerste definitie en necessary/sufficient voorwaarden voor data-gedreven supervisieve controle die specifiek rekening houdt met gemarkeerd gedrag (doelbereiking en non-blocking).
Nieuwe Concepten: Introductie van restricted marking data-informativity en marking informatizability om om te gaan met onvolledige data.
Synthese van de Grootste Toelaatbare Specificatie: Een algoritme (Algoritme 3) dat de maximale subset van een specificatie vindt die veilig kan worden afgedwongen op basis van de beschikbare data, zelfs als de oorspronkelijke specificatie niet haalbaar is.
Vergelijking met Model-Gebaseerde Aanpak: Het paper toont aan dat het negeren van gemarkeerd gedrag (zoals in eerdere data-gedreven studies) kan leiden tot supervisors die weliswaar de specificatie respecteren, maar wel blokkerend zijn (het systeem kan vastlopen zonder het doel te bereiken). De voorgestelde methode garandeert non-blocking gedrag.

4. Resultaten en Validatie

De auteurs valideren hun theorie met diverse voorbeelden, waaronder een robotnavigatiescenario:

Voorbeeld 1 & 2: Demonstreert hoe een onbekende plant (robot) kan worden gecontroleerd op basis van waarnemingen. Het toont aan dat met voldoende data en kennis van onmogelijke bewegingen ( $D^-$ ), een geldige supervisor kan worden ontworpen zonder het exacte model te kennen.
Voorbeeld 3 & 4: Vergelijkt de aanpak met en zonder rekening te houden met gemarkeerd gedrag. Het resultaat toont aan dat de methode zonder "marking" een pad kan toestaan dat leidt tot een dead-end (blokkering), terwijl de voorgestelde methode deze paden elimineert en alleen paden naar het doel toestaat.
Voorbeeld 9: Toont de toepassing van Algoritme 3. Wanneer de volledige specificatie niet haalbaar is, berekent het algoritme automatisch de grootste mogelijke subset (bijv. alleen het pad aed in plaats van alle gewenste paden) die wel veilig en haalbaar is.

Conclusie van de experimenten: De kwaliteit van de data-set (in termen van de match tussen observaties en kennis van onmogelijkheden) is belangrijker dan de pure hoeveelheid data. Hoe complexer het systeem of hoe meer oncontroleerbare gebeurtenissen er zijn, hoe meer specifieke kennis over onmogelijk gedrag ( $D^-$ ) nodig is om marking informativity te bereiken.

5. Betekenis en Toekomstperspectief

Dit paper is significant omdat het de kloof overbrugt tussen modelgebaseerde supervisieve controle en de realiteit van data-gedreven systemen, met een sterke focus op veiligheid en doelbereiking (non-blocking).

Praktische Toepassing: Het biedt een methode voor systemen in onbekende omgevingen waar modellering te duur of onmogelijk is, maar waar wel data beschikbaar is.
Veiligheid: Door expliciet "marking" te integreren, wordt gegarandeerd dat het systeem niet vastloopt, wat cruciaal is voor kritieke toepassingen zoals autonome voertuigen.
Toekomstig Werk: De auteurs suggereren het uitbreiden van de methodologie naar andere eigenschappen zoals observabiliteit, diagnoseerbaarheid en opaciteit, en het onderzoeken van hoe supervisors kunnen worden geüpdatet met nieuwe data zonder volledig opnieuw te beginnen.

Samenvattend biedt dit onderzoek een robuust theoretisch fundament en praktische algoritmen om controleproblemen op te lossen wanneer het systeemmodel onbekend is, maar gedragdata wel beschikbaar is, met een nadruk op het garanderen van succesvolle en veilige systeemoperaties.