⚡ electrical engineering

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

Cet article propose une reformulation des arbres de comportement temporels en utilisant une logique STL ternaire et des encodages linéaires en nombres entiers mixtes pour permettre la synthèse de stratégies de contrôle correctes par construction pour des systèmes dynamiques linéaires.

Auteurs originaux : Ryan Matheu, John S. Baras, Calin Belta

Publié 2026-04-15

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Ryan Matheu, John S. Baras, Calin Belta

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

🤖 Le Dilemme du Robot : "Je sais", "Je ne sais pas" et "Je ne peux pas"

Imaginez que vous donnez des instructions à un robot pour qu'il nettoie votre maison. Vous lui dites : "Va d'abord dans la cuisine, puis va dans le salon."

Dans le monde de la robotique classique, les robots sont un peu comme des élèves très stricts qui ne comprennent que deux réponses : OUI (c'est fait) ou NON (c'est raté).

Si le robot arrive dans la cuisine : OUI.
S'il tombe sur un obstacle : NON.

Mais la réalité est plus floue. Parfois, le robot est en train de marcher vers la cuisine, mais il n'y est pas encore. Il n'est pas "dans la cuisine" (NON), mais il n'est pas "hors de la cuisine" (OUI) non plus. Il est dans un état intermédiaire : "EN COURS".

C'est là que ce papier de recherche intervient. Les auteurs (Ryan, John et Calin) disent : "Arrêtons de forcer les robots à choisir entre OUI et NON. Donnons-leur une troisième option : JE NE SAIS PAS ENCORE."

🌳 L'Arbre de Décision (Behavior Trees)

Pour donner ces instructions, les chercheurs utilisent ce qu'on appelle des Arbres de Comportement (Behavior Trees). Imaginez un arbre généalogique, mais à l'envers :

Les racines sont le but final (Nettoyer la maison).
Les branches sont les étapes (Aller à la cuisine, aller au salon).
Les feuilles sont les actions concrètes (Avancer, tourner).

Ce qui est génial avec ces arbres, c'est qu'ils sont modulaires. Si vous voulez changer la cuisine, vous ne touchez pas au reste de l'arbre. C'est comme changer une pièce d'un Lego sans tout démolir.

⚡ Le Problème : La "Logique Ternaire"

Le problème, c'est que les ordinateurs sont très mauvais pour gérer l'incertitude quand ils doivent planifier un trajet. Ils veulent tout savoir à l'avance.

Les auteurs ont eu une idée brillante : utiliser une logique à trois valeurs (Ternaire) au lieu de la logique binaire habituelle (0 et 1).

VRAI (Vert) : La condition est remplie (ex: batterie pleine).
FAUX (Rouge) : La condition est échouée (ex: batterie vide).
INCONNU (Jaune) : La condition est en cours, ou on ne sait pas encore (ex: le robot est en train de charger, mais on ne sait pas si ça va durer assez longtemps).

En ajoutant cette couleur "Jaune", ils permettent au robot de dire : "Je ne suis pas encore arrivé, mais je suis en route, donc ne panique pas, continue à réfléchir."

🧩 La Magie Mathématique : Transformer le "Je ne sais pas" en Plan

Comment transformer ce "Je ne sais pas" en un plan d'action concret ?

Les auteurs ont créé une sorte de traducteur mathématique. Ils ont pris ces arbres de décision complexes et les ont transformés en une équation que l'ordinateur peut résoudre (ce qu'on appelle un "programme à nombres entiers mixtes").

Imaginez que vous devez organiser un voyage en train avec des correspondances :

Logique classique (Binaire) : Le train part-il ? Oui/Non. Si le train est en retard, le plan échoue.
Logique de ce papier (Ternaire) : Le train est-il en retard ? Oui/Non/En cours. Si le train est "En cours", le plan dit : "Attends 5 minutes, puis vérifie à nouveau."

Grâce à cette astuce, l'ordinateur peut calculer le trajet parfait (le plus rapide, le moins énergivore) tout en gérant les imprévus, comme une batterie faible ou un obstacle sur la route.

🚗 Les Exemples Concrets (Les Cas d'Usage)

Pour prouver que ça marche, ils ont testé leur méthode sur deux scénarios :

Le Robot Électrique :
Imaginez un robot qui doit aller au point A, puis au point B.
- Règle : "Si la batterie est > 80%, va directement à B. Sinon, va d'abord à la prise de charge (C), puis à B."
- Avec leur méthode, le robot calcule le trajet optimal. Si la batterie est juste à la limite, le robot sait qu'il doit faire un détour pour charger, et il le planifie parfaitement sans se bloquer.
L'Escouade de Robots :
Imaginez trois robots qui doivent traverser un couloir étroit rempli d'obstacles.
- Règle : "Ne vous percutez pas et ne heurtez pas les murs."
- Résultat : Les robots se mettent en file indienne, comme des voitures dans un embouteillage, attendant leur tour pour passer. C'est une solution intelligente qui émerge naturellement de leurs calculs.

💡 En Résumé

Ce papier est une avancée majeure car il permet de construire des robots plus intelligents et plus sûrs.

Au lieu de dire "Si ça ne marche pas, c'est fini", ils disent "Si on ne sait pas encore, continuons à calculer". C'est comme passer d'un GPS qui vous dit "Vous avez raté votre virage, c'est fini" à un GPS qui dit "Vous êtes en retard, voici une nouvelle route optimisée pour rattraper le temps perdu".

C'est une méthode qui permet de créer des systèmes autonomes (voitures, drones, robots de service) capables de gérer le chaos du monde réel avec une élégance mathématique.

1. Problématique

Les Arbres de Comportement (Behavior Trees - BTs) sont devenus un paradigme populaire pour la conception de stratégies de contrôle hiérarchiques et modulaires pour les systèmes autonomes. Ils offrent une interface graphique intuitive permettant de gérer l'exécution séquentielle, les mécanismes de repli (fallback) en cas d'échec, et le traitement parallèle de sous-tâches.

Cependant, l'intégration des BTs dans des processus de synthèse de contrôle formelle (garantie de correction) reste un défi. Les approches existantes basées sur la logique temporelle, comme la Logique Temporelle de Signaux (STL), sont puissantes mais souffrent de limitations majeures lorsqu'elles sont appliquées aux BTs :

Analyse a posteriori : La plupart des méthodes actuelles se limitent à la vérification post-exécution ou à la réparation de trajectoires, plutôt qu'à la génération de contrôle en temps réel.
Logique binaire insuffisante : Les BTs opèrent naturellement dans un domaine à trois états : Succès, Échec et En cours d'exécution (Running). La logique booléenne classique (Vrai/Faux) ne peut pas capturer l'état "En cours" ou l'incertitude liée à des trajectoires partielles, ce qui rend la modélisation formelle des BTs imparfaite pour la synthèse de contrôle.

L'objectif de cet article est de reformuler les Arbres de Comportement Temporels (TBTs) en utilisant une logique ternaire pour permettre la synthèse de contrôle par optimisation mathématique (contrôle correct par construction).

2. Méthodologie

Les auteurs proposent un cadre unifié combinant la logique ternaire, la logique temporelle et la programmation mixte-entière (MIP).

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

Le cœur de l'approche repose sur l'utilisation de la logique de Kleene ( $K_3$ ), qui introduit une troisième valeur de vérité : Inconnu (Unknown).

Mapping des états BT :
- Succès $\rightarrow$ Vrai ( $T$ )
- Échec $\rightarrow$ Faux ( $F$ )
- En cours / Indéterminé $\rightarrow$ Inconnu ( $U$ )
Cela permet de modéliser formellement les nœuds BT qui sont en cours d'exécution ou dont l'état final n'est pas encore déterminé par rapport à une trajectoire partielle.

B. Sémantique de la STL sur des Trajectoires Partielles

Les auteurs étendent la sémantique qualitative de la STL aux trajectoires finies (partielles) en utilisant la logique $K_3$ .

Prédicats ternaires : Un prédicat de signal $\mu$ peut évaluer à $T$ , $F$ ou $U$ selon qu'il est clairement satisfait, clairement violé, ou dans une zone d'incertitude (définie par un seuil $\delta$ ).
Opérateurs temporels : Les opérateurs "Toujours" ( $\Box$ ) et "Finalement" ( $\Diamond$ ) sont redéfinis pour gérer les fenêtres de recherche qui dépassent l'horizon de la trajectoire partielle. Si la fenêtre dépasse l'horizon sans qu'une condition de court-circuit (satisfaction ou violation certaine) ne soit atteinte, le résultat est $U$ (Inconnu).

C. Encodages Mixtes-Entiers (MILP/MIQP)

Pour rendre le problème soluble par des solveurs d'optimisation, les auteurs proposent des encodages linéaires mixtes-entiers :

Variables de décision : Les variables de satisfaction ne sont plus binaires $\{0, 1\}$ mais ternaires $\{-1, 0, +1\}$ (correspondant à $F, U, T$ ).
Opérateurs BT (Séquence et Sélecteur) :
- L'opérateur Séquence ( $\to$ ) est encodé comme une conjonction temporelle : il existe un instant $\tau$ tel que la première sous-formule est satisfaite jusqu'à $\tau$ et la seconde de $\tau+1$ à la fin.
- L'opérateur Sélecteur ( $?$ ) est encodé comme une disjonction temporelle : soit la première sous-formule est satisfaite, soit la seconde l'est à partir du prochain pas de temps.
Complexité : L'encodage des opérateurs BT introduit une complexité supplémentaire ( $O(T^{k+1})$ pour $k$ sous-formules) par rapport à la STL standard, en raison de la nécessité de gérer deux dimensions temporelles (pas de temps d'évaluation et horizon partiel).

D. Problème de Contrôle

Le problème est formulé comme un Programme Quadratique Mixte-Entier (MIQP) :

Minimiser une fonction de coût quadratique (effort de contrôle).
Soumis aux contraintes dynamiques linéaires du système.
Soumis aux contraintes de satisfaction du TBT encodées via des contraintes linéaires mixtes-entières.

3. Contributions Clés

Formalisation concrète des BTs en logique $K_3$ : Les auteurs établissent un lien formel rigoureux entre la structure des arbres de comportement et la logique ternaire, capturant l'état "En cours" et l'incertitude.
Encodages Mixtes-Entiers pour TBTs : Développement de schémas d'encodage pour les opérateurs STL et les opérateurs spécifiques aux TBTs (Séquence, Sélecteur) sur la logique ternaire, permettant l'utilisation d'outils d'optimisation standard.
Synthèse de contrôle correct par construction : Démonstration que ces encodages permettent de générer des trajectoires de contrôle pour des systèmes dynamiques linéaires qui satisfont strictement les spécifications TBT, y compris les mécanismes de repli complexes.
Généralisation des horizons : La logique ternaire permet de décider la satisfaction de formules même lorsque l'horizon de la trajectoire est inférieur à l'horizon théorique de la formule (résultat "Inconnu" au lieu d'échec), élargissant l'espace de recherche des solutions.

4. Résultats Expérimentaux

Les auteurs valident leur approche sur deux études de cas :

Cas 1 : Double Intégrateur Discrétisé (Robot Mobile)
- Scénario : Un robot doit naviguer vers un objectif A, puis, selon le niveau de batterie, soit aller directement à B, soit d'abord se recharger à C avant d'aller à B.
- Résultat : Le solveur (Gurobi) trouve une trajectoire optimale en moins de 100 secondes. Les trajectoires générées respectent dynamiquement la condition de batterie : si la batterie est faible, le robot effectue le repli vers C, démontrant la capacité du système à gérer les branches conditionnelles des BTs.
Cas 2 : Planification Multi-Agents
- Scénario : Trois agents doivent accomplir des tâches séquentielles tout en évitant des obstacles et en maintenant une distance de sécurité minimale entre eux.
- Résultat : Le système génère des trajectoires où les agents s'organisent naturellement en file d'attente (phénomène de "queuing") pour traverser un couloir étroit, respectant ainsi les contraintes de sécurité strictes. Le temps de résolution est d'environ 308 secondes pour un problème de grande taille.

5. Signification et Impact

Ce travail représente une avancée significative dans le domaine de la synthèse de contrôle formel pour les systèmes autonomes :

Bridging the Gap : Il comble le fossé entre la modélisation intuitive des tâches (via les BTs) et la rigueur mathématique nécessaire à la synthèse de contrôle (via la logique temporelle et l'optimisation).
Gestion de l'Incertitude : L'introduction de la valeur "Inconnu" permet de traiter des situations où l'information est incomplète (trajectoires partielles ou mesures bruitées), rendant le cadre plus robuste que les approches purement booléennes.
Applicabilité : Bien que la complexité computationnelle augmente avec la profondeur de l'arbre et le nombre d'agents, la méthode prouve qu'il est possible de résoudre des problèmes de contrôle optimal complexes avec des contraintes logiques hiérarchiques riches.
Perspectives : Les auteurs envisagent d'étendre cette approche aux systèmes non linéaires, ce qui élargirait considérablement le champ d'application aux robots complexes et aux environnements dynamiques réels.

En résumé, cet article propose un cadre théorique et pratique robuste pour transformer des spécifications de comportement complexes et hiérarchiques en problèmes d'optimisation solvables, garantissant ainsi que les systèmes autonomes exécutent leurs tâches de manière sûre et conforme aux intentions des concepteurs.