⚡ electrical engineering

Ternary Logic Encodings of Temporal Behavior Trees with Application to Control Synthesis

Dit artikel introduceert een ternaire logica-encoding voor Temporele Gedragsbomen die correct-by-construction besturingsstrategieën mogelijk maakt voor lineaire dynamische systemen via gemengd-integer lineaire optimalisatie.

Oorspronkelijke auteurs: Ryan Matheu, John S. Baras, Calin Belta

Gepubliceerd 2026-04-15

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Ryan Matheu, John S. Baras, Calin Belta

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een robot bestuurt die een heleboel taken moet uitvoeren, zoals een bezorgdroid die pakketten moet afleveren of een zelfrijdende auto die door de stad moet navigeren. Om deze robot slim te maken, geven we hem een "plan". Maar hoe zorg je ervoor dat dit plan niet alleen slim is, maar ook veilig en foutloos werkt, zelfs als er onverwachte dingen gebeuren?

Dit artikel van Ryan Matheu en zijn collega's gaat over een nieuwe manier om zulke plannen te maken en te controleren. Ze gebruiken een combinatie van drie concepten: Bomen, Twee of Drie Opties, en Wiskundige Puzzels.

Hier is de uitleg in gewoon Nederlands, met een paar creatieve vergelijkingen:

1. Het Plan: Gedragsbomen (De "Kies-je-avontuur" Boek)

Stel je een "Gedragsboom" (Behavior Tree) voor als een kies-je-avontuur boek voor robots.

In zo'n boek lees je: "Als je een draak ziet, ga dan links. Als je een magische sleutel vindt, ga dan rechts."
Robots gebruiken deze bomen om beslissingen te nemen. Ze hebben knoppen zoals "Volg deze route" (Sequentie) of "Probeer dit, en als het mislukt, probeer dan dat" (Selectie).
Het probleem: Tot nu toe konden we deze bomen alleen na het feit controleren ("Oh, de robot is tegen de muur gereden, dat was een slecht plan"). Of we moesten de robot handmatig repareren. We konden ze nog niet voordat de robot start, wiskundig garanderen dat het plan perfect zou werken.

2. De Nieuwe Truc: De "Onbekende" Kleur (Ternaire Logica)

Normaal gesproken denken computers in Ja/Nee (Waar/Niet Waar).

Is de batterij vol? Ja of Nee.
Is de weg vrij? Ja of Nee.

Maar in de echte wereld is het vaak niet zo simpel. Soms weten we het nog niet. Misschien is de batterij net op 79%, en de sensor is een beetje wazig. Is het dan vol? Nee. Is het leeg? Ook niet echt. Het is Onbekend.

De auteurs introduceren een derde optie: Onbekend.

Groen: Alles goed (Waar).
Rood: Alles mis (Niet Waar).
Geel: We weten het nog niet (Onbekend).

Dit is als een stoplicht dat niet alleen rood en groen heeft, maar ook een flitsend oranje dat zegt: "Ik weet niet zeker of ik kan oversteken, wacht even."
Door deze "Onbekende" status toe te staan, kunnen ze plannen maken die omgaan met onzekerheid. Als de robot niet zeker weet of hij een doel haalt, wordt het plan niet direct afgekeurd als "fout", maar gemarkeerd als "nog niet beslist". Dit maakt het plan veel robuuster.

3. De Oplossing: De Wiskundige Puzzel (Mixed-Integer Programming)

Nu hebben ze een plan (de boom) en een slimme manier om onzekerheid te meten (de drie kleuren). Hoe vertalen ze dit naar instructies voor de robot?

Ze veranderen het hele probleem in een gigantische wiskundepuzzel (een Mixed-Integer Linear Programming probleem).

Stel je voor dat je een legpuzzel hebt, maar in plaats van stukjes die passen of niet passen, heb je stukjes die moeten passen, mogen passen, of nog niet weten of ze passen.
De computer (de "puzzel-oplosser") zoekt naar de perfecte rij bewegingen voor de robot zodat:
1. De robot veilig blijft (geen botsingen).
2. De robot zijn taken in de juiste volgorde doet (eerst naar punt A, dan naar B).
3. De robot de "Onbekende" situaties oplost door slimme keuzes te maken.

De computer doet dit door een wiskundige formule op te stellen die alle regels van de boom en de onzekerheid bevat, en dan de "beste" route te berekenen die aan alles voldoet.

4. Wat hebben ze bewezen? (De Voorbeelden)

Ze hebben hun methode getest met twee leuke voorbeelden:

De Robot met de Batterij:
Stel je een robot voor die eerst naar punt A moet, en dan naar punt B. Maar er is een valkuil: als de batterij laag is, moet hij eerst naar het laadstation (punt C) voordat hij naar B gaat.
- Met hun nieuwe methode kan de computer precies berekenen: "Als de batterij 80% is, ga direct naar B. Als hij 70% is, ga eerst naar C." En dit wordt allemaal automatisch berekend voordat de robot begint, zodat hij nooit vastloopt.
Het Zee-gevecht van Robots (Multi-Agent):
Ze lieten drie robots door een smalle gang met obstakels lopen. Ze moesten elkaar niet raken en op tijd bij hun bestemming zijn.
- Het resultaat? De robots begonnen vanzelf in een rij te staan (queuing). Omdat ze wiskundig moesten garanderen dat ze niet tegen elkaar botsten, besloot de computer dat robot 1 eerst moest gaan, dan robot 2, en dan robot 3. Het was alsof ze een onzichtbare lijn trokken en respectvol op elkaar wachtten.

Samenvatting

In het kort:
De auteurs hebben een manier bedacht om robot-plannen te maken die slimmer omgaan met twijfel. In plaats van te denken in "Ja of Nee", denken ze in "Ja, Nee, of Misschien". Ze vertalen deze "Misschien"-situaties naar een wiskundige puzzel die een computer kan oplossen om de perfecte, veilige route te vinden.

Het is alsof je een robot niet alleen een strikt strak plan geeft, maar hem ook een verstandige navigator geeft die weet wat hij moet doen als het weer onzeker is, en die van tevoren weet hoe hij dat moet doen zonder vast te lopen.

Titel: Ternaire Logische Encoderingen van Temporele Gedragsbomen met Toepassing in Controlesynthese

Auteurs: Ryan Matheu, John S. Baras en Calin Belta (Universiteit van Maryland)

1. Probleemstelling

Autonome systemen vereisen robuuste methoden voor het modelleren van taken en het garanderen van veiligheid. Gedragsbomen (Behavior Trees - BTs) bieden een intuïtieve grafische interface voor het ontwerpen van complexe, lange-termijn plannen met fallback-mechanismen. Echter, het formele verifiëren en synthetiseren van besturingssignalen op basis van BTs is uitdagend.

Bestaande benaderingen, zoals het gebruik van Signal Temporal Logic (STL) via "Temporal Behavior Trees" (TBTs), zijn beperkt tot:

Offline analyse: Analyse vindt plaats na het uitvoeren van een traject (post hoc).
Tracereparatie: Het corrigeren van een foutief traject door minimale verstoringen.
Binaire logica: Traditionele logica kent alleen "Waar" (True) en "Onwaar" (False). Dit is onvoldoende voor BTs, die ook een "Lopend" (Running) status hebben. Als een traject nog niet volledig is voltooid of als er onzekerheid bestaat over een predicate, kan een binaire logica geen onderscheid maken tussen "nog niet voltooid" en "falen".

Het paper adresseert de noodzaak om TBTs te formuleren in een logica die geschikt is voor controlesynthese (het automatisch genereren van besturingssignalen) en die rekening houdt met onzekerheid en de "Running"-status van BT-nodes.

2. Methodologie

De auteurs stellen een nieuw raamwerk voor dat BTs formaliseert binnen een ternaire logica (drie-waardige logica) en deze koppelt aan Mixed-Integer Linear Programming (MILP) voor controlesynthese.

A. Ternaire Logica (Kleene's Strong Logic - $K_3$ )

In plaats van de traditionele binaire logica, gebruiken de auteurs de logica $K_3$ met drie waarheidswaarden:

True (T): Succes / Voldaan.
False (F): Falen / Niet voldaan.
Unknown (U): Onbekend / Lopend / Onbepaald.

Deze "Unknown"-waarde is cruciaal omdat:

Het de "Running"-status van een BT-node formeel vastlegt.
Het onzekerheid in systeemmetingen kan modelleren (bijv. als een sensorwaarde dicht bij de drempel ligt).
Het toestaat dat formules over gedeeltelijke trajecten (partial trajectories) worden geëvalueerd zonder dat ze direct als "Onwaar" worden afgedaan als het tijdsvenster nog niet is verstreken.

B. Semantiek van Signal Temporal Logic (STL) over $K_3$

De kwalitatieve semantiek van STL wordt uitgebreid naar $K_3$ . Voor een gedeeltelijk traject met horizon $t_2$ en evaluatietijdstip $t_1$ :

Als het zoekvenster van een tijdsoperator (bijv. "altijd" of "uiteindelijk") volledig binnen het gedeeltelijke traject valt, wordt de standaard binaire logica toegepast.
Als het zoekvenster het einde van het traject overschrijdt ( $t_1 + b > t_2$ ), wordt de uitkomst Unknown, tenzij er sprake is van een "short-circuit" (bijv. een "Altijd"-operator faalt direct als één punt faalt, of een "Uiteindelijk"-operator slaagt direct als één punt slaagt).

C. Mixed-Integer Lineaire Encoderingen

Om deze logica te gebruiken in optimalisatieproblemen, worden de ternaire waarden geëncodet als gehele getallen:

$True \rightarrow +1$
$Unknown \rightarrow 0$
$False \rightarrow -1$

De auteurs ontwikkelen specifieke encoderingschema's voor:

STL-operatoren: Predicaten, logische connectieven (AND, OR, NOT) en tijdsoperatoren (Always $\square$ , Eventually $\diamond$ ) worden vertaald naar lineaire constraints met binaire beslissingsvariabelen die de ternaire waarden representeren.
TBT-operatoren:
- Sequence (Seq): Vereist dat subtaken opeenvolgend worden voltooid. De auteurs bewijzen de associativiteit en gebruiken recursieve definities om de encodering te structureren.
- Selector (Sel): Vereist dat ten minste één subtaak wordt voltooid (fallback-mechanisme). Dit is de logische dualiteit van Sequence.

D. Controlesynthese Probleem

Het doel is het vinden van een besturingsreeks $u$ voor een lineair discreet tijdssysteem ( $x_{t+1} = A_t x_t + B_t u_t$ ) die een TBT-formule $\varphi$ voldoet, terwijl een kwadratische kostenfunctie (bijv. besturingsinspanning) wordt geminimaliseerd.
Dit wordt geformuleerd als een Mixed-Integer Quadratic Program (MIQP). De constraints van de TBT-formule worden vertaald naar lineaire constraints met ternaire beslissingsvariabelen.

3. Belangrijkste Bijdragen

Formalisatie van BTs in $K_3$ : Het paper concretiseert de formele definitie van Gedragsbomen binnen een ternaire logische context, wat essentieel is voor het modelleren van de "Running"-toestand.
Ternaire STL en TBT Encoderingen: Introductie van mixed-integer lineaire encoderingen voor zowel STL als TBT-operatoren (Sequence en Selector) over ternaire logica. Dit maakt het mogelijk om formele specificaties direct om te zetten in optimalisatieproblemen.
Controlesynthese via MIQP: Demonstratie dat deze encoderingen kunnen worden gebruikt om "correct-by-construction" besturingsstrategieën te genereren voor lineaire dynamische systemen.
Omgaan met Onzekerheid: Door de "Unknown"-waarde te introduceren, kan het systeem omgaan met gedeeltelijke informatie en onzekerheid in metingen, wat leidt tot een robuustere zoekruimte voor oplossingen.

4. Resultaten en Case Studies

De auteurs testen hun framework op twee optimalisatieproblemen:

Case Study 1: Discrete-Time Double Integrator (Mobiele Robot)
- Scenario: Een robot moet doelen A, B en C bezoeken volgens een BT-strategie. De strategie hangt af van het batterijniveau: als het batterijniveau $\ge 80\%$ is, gaat de robot direct naar B; anders moet hij eerst naar C (opladen) en dan naar B.
- Resultaat: Het MIQP-model (opgelost met Gurobi) genereerde binnen ~97 seconden een globaal optimale traject. De robot slaagde erin om de juiste tak van de beslissingsboom te kiezen op basis van de initiële batterijconditie en vermijdt obstakels.
Case Study 2: Multi-Agent Planning
- Scenario: Drie agenten moeten doelen bereiken terwijl ze obstakels vermijden en een minimale onderlinge afstand bewaren.
- Resultaat: Het systeem synthetiseerde trajecten waarbij de agenten een "wachtrij" (queuing) vormden om door smalle obstakelcorridors te navigeren. Dit illustreert hoe de strikte veiligheidsconstraints (minimale afstand) automatisch leiden tot gecoördineerd gedrag zonder expliciete communicatieprotocollen.

Complexiteit: De auteurs erkennen dat de complexiteit van de TBT-encodering exponentieel toeneemt met het aantal subformules ( $O(T^{k+1})$ ) in vergelijking met traditionele STL-encoderingen ( $O(T)$ ), vanwege de extra tijdsdimensie die nodig is voor gedeeltelijke trajecten. Echter, voor de geteste gevallen was het oplossen binnen redelijke tijdsbestekken mogelijk.

5. Significantie

Dit werk is significant omdat het de kloof overbrugt tussen de intuïtieve modellering van complexe taken via Gedragsbomen en de rigoureuze wiskundige garanties van formele controlesynthese.

Van Analyse naar Synthese: Het verplaatst TBTs van een louter analytisch hulpmiddel (na het feit) naar een constructief hulpmiddel (voor het feit).
Logische Expressiviteit: Door ternaire logica te gebruiken, kunnen BTs nu exact worden gemodelleerd zonder de "Running"-status te hoeven simplificeren tot waar of onwaar.
Toekomstperspectief: De methode biedt een basis voor het uitbreiden van controlesynthese naar niet-lineaire systemen en complexere multi-agent scenario's, waarbij onzekerheid en gedeeltelijke uitvoering een centrale rol spelen.

Kortom, het paper biedt een wiskundig onderbouwd raamwerk om autonome systemen te laten "redeneren" over hun eigen voortgang en onzekerheid, en hierop gebaseerd veilige en optimale besturingscommando's te genereren.