Analyse approfondie des Arbres de Comportement (Behavior Trees) et des Machines à États Finis (FSM)

Les mécanismes de décision qui constituent le fondement des agents autonomes, des personnages de jeux vidéo complexes et des systèmes robotiques industriels représentent l'un des domaines les plus critiques et les plus débattus de l'ingénierie logicielle moderne et de la recherche en intelligence artificielle. La manière dont un agent réagit à des stimuli environnementaux en constante évolution, la sélection de ses priorités parmi d'innombrables objectifs et l'ordre d'exécution de tâches spécifiques dépendent entièrement de la robustesse et de la flexibilidad de son architecture de prise de décision fondamentale. L'examen du développement historique montre que ce domaine a été dominé pendant de nombreuses années par les Machines à États Finis (Finite State Machines - FSM). Cependant, la complexité croissante des mondes numériques et des tâches robotiques physiques a poussé les développeurs et les chercheurs à rechercher des structures plus évolutives, réactives et modulaires, une quête qui a conduit à l'émergence de structures hiérarchiques révolutionnaires telles que les Arbres de Comportement (Behavior Trees - BT).

Ce rapport examine en profondeur ces deux architectures fondamentales, aujourd'hui acceptées comme normes industrielles pour la modélisation de la prise de décision et du comportement dans les systèmes autonomes, à travers leurs détails techniques, leurs fondements mathématiques, leur évolution historique, leurs cas d'usage industriels et leurs avantages et inconvénients structurels mutuels. En outre, les approches hybrides les plus récentes dans les moteurs de jeu modernes (par exemple Unreal Engine) et les solutions de nouvelle génération telles que les Arbres d'États (State Trees) sont également évaluées comme faisant partie intégrante de cette analyse.

Machines à états finis (FSM) : Infrastructure théorique et fondements mathématiques

Une machine à états finis (FSM) est un modèle de machine abstraite dans lequel un système ne peut se trouver qu'à un seul état prédéfini à la fois et effectue des transitions entre les états en réponse à des entrées environnementales ou à des événements internes spécifiques (entrées/événements). L'une des pierres angulaires de la théorie du calcul, ce modèle est largement utilisé en informatique, de la conception d'algorithmes à la construction de circuits électroniques numériques.

Les FSM peuvent être théoriquement conçues en étant divisées en deux catégories principales : déterministes ou non déterministes. Cependant, l'un des théorèmes fondamentaux de la théorie du calcul prouve que pour toute machine à états finis non déterministe, il est toujours possible de construire une machine à états finis déterministe équivalente qui reconnaît exactement le même langage et produit les mêmes sorties comportementales. Ce théorème permet aux ingénieurs logiciels de réduire des scénarios complexes à des structures déterministes plus prévisibles.

Représentation logique et dynamique des transitions d'états

Les machines à états finis sont intrinsèquement visualisées et exprimées sous forme de graphe orienté ou de diagramme d'états. Dans ce graphe orienté, les nœuds représentent les états internes de la machine abstraite, tandis que les flèches orientées reliant ces nœuds (arêtes) représentent les transitions d'états. L'état actuel du système à un moment « t » donné est toujours calculé comme une fonction déterministe de l'état précédent et des entrées actuelles entrant dans le système à ce moment-là.

Dans un contexte mathématique, cette fonction de transition d'états s'exprime comme suit :

Dans cette formulation, représente le prochain état du système, l'état précédent (actuel) de la machine, la valeur d'entrée actuelle et la fonction de transition d'états. Cette relation est également souvent représentée dans la littérature comme l'opération de mise en correspondance du produit cartésien de l'ensemble des états (S) et de l'ensemble des entrées (I) vers l'ensemble des états lui-même, c'est-à-dire . Les machines à états finis sont également divisées en deux sous-classes architecturales principales en fonction de la nature des sorties qu'elles produisent : dans le modèle de la machine de Moore, la fonction de sortie dépend uniquement de l'état actuel du système (), tandis que dans le modèle de la machine de Mealy, la fonction de sortie dépend simultanément de l'état actuel et de l'entrée instantanée ().

Dans la conception du système, les états et les entrées sont généralement représentés par un alphabet binaire ou des énumérations prédéfinies (enum), et les fonctions et sont généralement codées sous la forme d'une table de correspondance (look-up table) ou d'une table de transition d'états (state transition table). Dans l'architecture logicielle, la réalisation des transitions ne dépend pas seulement de la présence d'entrées, mais aussi de la satisfaction de conditions supplémentaires (gardes). Dans un diagramme d'états UML typique ou dans les implémentations de moteurs modernes, la notation d'une transition est généralement exprimée par la syntaxe déclencheur[garde]/effet (trigger[guard]/effect). Ici, le déclencheur (trigger) peut être un signal, un appel, une temporisation ou un événement de changement. La garde (guard) est un test logique supplémentaire qui doit être vérifié pour que la transition ait lieu. L'effet (effect) est l'action spécifique exécutée pendant la transition.

Cependant, la puissance de l'architecture FSM réside non seulement dans les transitions entre les états, mais aussi dans les actions qui peuvent être exécutées lors de l'entrée dans certains états, du maintien dans ces états et de la sortie de ces états. Des blocs de code spéciaux peuvent être exécutés lorsqu'on entre dans un état FSM (action d'entrée), périodiquement lorsqu'on est dans l'état (action pendant) et lorsqu'on quitte l'état (action de sortie). Par exemple, dans un système de radio, lorsque l'appareil est dans l'état « Radio », appuyer sur le bouton « Suivant » permet de passer à la station de radio suivante, tandis que lorsque l'appareil est dans l'état « CD », appuyer sur ce même bouton « Suivant » déclenche le passage à la piste musicale suivante ; ainsi, exactement le même stimulateur environnemental produit des actions complètement différentes en fonction de l'état contextuel dans lequel se trouve la machine.

La place des FSM dans les standards de l'industrie et leurs avantages pratiques

Les machines à états finis ont persisté en tant que standard de l'industrie dans un vaste contexte historique allant de la conception de circuits numériques à l'industrie du jeu vidéo. Leurs avantages les plus évidents sont leur compréhension extrêmement facile sur le plan conceptuel, leur simplicité architecturale et leur vitesse d'exécution phénoménale au niveau du matériel et du logiciel. Le fait qu'un concepteur puisse visualiser ce qu'un personnage ou un système peut faire et dans quels états il peut passer à l'aide d'un diagramme en boîte et flèche (« box and arrow » diagram) fait des FSM une structure extrêmement intuitive et facile à déboguer (debugging) pendant le processus de codage.

Les FSM sont incomparables, en particulier dans les domaines où il est essentiel de définir le mode instantané du système, la phase d'animation ou l'état physique du personnage avec des frontières précises et impénétrables. Les contextes spécifiques où les FSM fonctionnent parfaitement sont les suivants :

Premièrement, les jeux de combat (fighting games) sont l'un des domaines d'application les plus brillants de l'architecture FSM. Dans un jeu de combat, les états « Attaque », « Saut », « Étourdi » (Stunned), « Accroupi » ou « Défense » d'un personnage doivent être séparés les uns des autres par des lignes logiques strictes et nettes. Par exemple, lorsqu'un personnage subit un coup violent de son adversaire et entre dans l'état « Étourdi », il ne peut pas sauter, même si le joueur appuie sur le bouton de saut. Si l'architecture FSM n'est pas utilisée, il est nécessaire d'écrire des instructions conditionnelles imbriquées qui s'étendent indéfiniment à chaque tentative d'action du personnage sous la forme « si le personnage n'est pas étourdi et s'il n'est pas en l'air et s'il n'est pas bloqué dans une animation d'attaque... », ce qui rend la maintenance impossible. Les FSM évitent ce gigantesque fouillis de spaghetti dans les blocs de code en traitant parfaitement la logique « si le personnage est dans l'état A, il ne peut passer qu'à l'état B ou C ».

Deuxièmement, les contrôleurs d'animation de personnages sont largement basés sur les FSM. Dans les moteurs de jeu modernes tels que le leader de l'industrie Unreal Engine, les animations de personnages sont contrôlées par des interfaces appelées « Animation Blueprints » (Schémas d'animation) qui exécutent une machine à états en arrière-plan. Le moment et la manière dont un personnage passe de l'animation « Attente » (Idle) à l'animation « Marche » (Walk), puis à l'animation « Course » (Run), constituent la fonction de base des FSM gérées par cette interface de boîtes et de flèches.

Troisièmement, dans les systèmes d'arcade et les jeux nécessitant une logique de décision simple, les FSM sont idéales pour fonctionner selon le principe « KISS » (Keep It Simple, Stupid - Fait simple, imbécile). Dans de nombreux jeux de style arcade, les ennemis ont des états très limités et spécifiques tels que « Patrouiller », « Poursuivre », « Attaquer » ou « Fuir ». Une FSM implémentée dans un environnement natif C++ offre des performances uniques en fonctionnant au niveau des nanosecondes sur les processeurs modernes. Les développeurs de logiciels peuvent définir des états à l'aide d'énumérations sans nom (unnamed enums) et lier ces états à des identifiants d'événements (event IDs) avec une structure « un grand switch » (« one big switch ») ou des techniques de masquage de bits. L'architecture de code ordonnée apportée par cette structure permet à la FSM d'être compilée au moment de l'exécution (hot-recompiling), tout en assurant une exécution sûre et ininterrompue (execution safety) en renvoyant des identifiants d'état non nuls à partir des gestionnaires d'événements (event handlers) au lieu de sous-routines telles que SetState(). Ce flux d'exécution linéaire permet d'atteindre des fréquences d'images (framerate) élevées en évitant toute saccade (stutter) dans la boucle de jeu.

Point de crise architecturale : Le problème de l'explosion des états (State Explosion)

Bien que les FSM soient parfaites et performantes pour les modèles de comportement déterministes dotés d'un nombre limité d'états, elles ont tendance à s'effondrer structurellement à mesure que la complexité du système autonome, le nombre de variables environnementales et le répertoire comportemental attendu de l'intelligence artificielle augmentent. Cette vulnérabilité chronique est appelée « Explosion des états » (State Explosion) dans la littérature.

La contrainte fondamentale de l'architecture FSM est que la machine ne peut se trouver que dans un seul état à la fois. Si un personnage doit pouvoir courir et tirer en même temps, le personnage ne peut pas se trouver simultanément dans les états « Courir » et « Tirer » dans l'architecture FSM ; au lieu de cela, un tout nouvel état hybride appelé « Courir en tirant » doit être créé. Chaque nouvelle variable ajoutée au système nécessite la production de nouveaux états à hauteur de toutes les combinaisons possibles avec tous les états existants. Le nombre d'états que le modèle doit représenter atteint des dimensions gigantesques, équivalentes au produit cartésien des ensembles de variables.

Le problème encore plus critique est la complexité des transitions (transition) créée par l'augmentation du nombre d'états. Ajouter un état dans une FSM ne signifie pas seulement créer cet état ; cela nécessite de coder un par un, avec des règles spécifiques, la manière de passer de tous les autres états pertinents du système vers ce nouvel état ajouté, et de cet état vers quels autres états il est possible de revenir. Dans le jargon de l'informatique, le taux de croissance de la complexité des transitions avec l'augmentation du nombre d'états est exprimé comme étant proportionnel au carré. Ce taux de croissance géométrique crée une charge de complexité cumulative similaire à la loi de Metcalfe, qui soutient dans l'économie des réseaux que la valeur d'un réseau de télécommunications est proportionnelle au carré du nombre d'utilisateurs.

Lorsqu'une FSM atteint environ 10 états, sa gestion devient difficile ; lorsque le nombre d'états atteint 40 (par exemple, dans l'intelligence artificielle d'un combat de boss avancé de style Sekiro ou Dark Souls), le fichier de code se remplit de centaines de

lignes de logique de transition et se transforme littéralement en « code spaghetti » (Spaghettification). 13 À ce stade, la maintenance (maintenance) ou le débogage (debugging) du code se transforme en cauchemar. En effet, la cause profonde de tout bogue logique (bug) qui apparaît peut être un déclencheur défectueux dans l'une des dizaines de transitions d'états différentes, un ordre de priorité mal conçu ou une flèche de transition oubliée. 23

Des « Machines à états finis hiérarchiques » (Hierarchical Finite State Machines - HFSM) ont été développées afin d'atténuer cette explosion des états et d'empêcher dans une certaine mesure la formation de code spaghetti. Dans le modèle HFSM, les états sont conçus de manière à pouvoir s'imbriquer les uns dans les autres ; un « état parent » (parent state) héberge en son sein des sous-états (substates) fonctionnant de manière autonome. Par exemple, un état principal appelé « Combat » peut avoir une sous-machine qui exécute les sous-états « Se mettre à couvert », « Viser » et « Tirer » à l'intérieur de celui-ci. Si le système est dans l'état principal « Combat » et que le joueur s'éloigne, une seule « Transition de groupe » (Group Transition) de l'état principal vers l'état « Patrouiller », quel que soit le sous-état dans lequel on se trouve, élimine la nécessité d'écrire du code de fuite ou d'annulation un par un dans chacun des sous-états internes. 8 Grâce aux points de transition (transition points) et aux priorités de déclenchement des événements (event triggering precedence), les HFSM poussent la capacité des FSM un peu plus loin. 24 Cependant, lorsque la complexité du système dépasse un certain seuil (par exemple, dans un planificateur de tâches complexe contenant des dizaines d'états et des centaines de transitions), même les HFSM succombent à la complexité visuelle et deviennent structurellement fragiles. 8

Arbres de Comportement (Behavior Trees) : Évolution, Structure et Logique d'Exécution

La barrière de scalabilité géométrique imposée par les machines à états finis (FSM) et les machines à états finis hiérarchiques (HFSM) a rendu indispensable l'émergence d'un tout nouveau paradigme architectural dans les processus de prise de décision des personnages et agents autonomes. Les Arbres de Comportement (Behavior Trees - BT) sont des structures de décision modulaires et hiérarchiques développées précisément pour surmonter ce blocage et offrir à l'intelligence artificielle une feuille de route claire et visuelle, sans se perdre dans les labyrinthes de transitions rigides du type "si ceci se produit, alors fais cela". 2

Origines Historiques et Processus d'Adoption Industrielle

Bien que les récits académiques et industriels présentent de légères divergences quant au moment et au lieu exacts de l'apparition des arbres de comportement, il est largement admis que ces structures sont nées des tranchées des studios de développement de jeux vidéo plutôt que de laboratoires de recherche sophistiqués. 2 L'une des plus anciennes utilisations documentées remonte à SimCopter, un jeu développé par Maxis en 1996. Selon les explications de Don Hopkins, ancien employé de Maxis, un langage visuel appelé "SimAntics" était utilisé pour contrôler les PNJ dans le jeu, désigné sous le nom d'"arbres de réaction" (reaction trees) dans le fichier people.df du code du jeu. Les lignes de commentaires de ce fichier contiennent des définitions évoquant les mécanismes modernes des arbres de comportement, telles que "un arbre de réaction peut être appelé par un autre arbre de réaction mais ne peut pas être interrompu pendant ce temps". 25

Cependant, la formulation de l'architecture des Arbres de Comportement au sens moderne, sa transformation en standard industriel et l'acquisition d'une base académique solide se sont produites en grande partie grâce à la conférence emblématique de Damian Isla lors de la Game Developers Conference (GDC) de 2005, où il a présenté l'architecture d'IA révolutionnaire du jeu Halo 2 ("Handling Complexity in the Halo 2 AI"). 3 Durant le développement de Halo 2, l'équipe de Bungie a été confrontée à deux impasses majeures induites par les FSM : la perte de scalabilité du système face à la variété croissante des comportements et le problème d'instabilité, connu sous le nom de "dithering", causé par les hésitations rapides de l'IA entre différentes décisions. 3

Voulant résoudre cette surcharge mentale (mental bandwidth) provoquée par les FSM, l'équipe a organisé les comportements des personnages dans une hiérarchie appelée "DAG de comportement" (Directed Acyclic Graphs - Graphes Orientés Acycliques). 3 Ce système intégrait environ 50 comportements de base différents.

Dans la structure décrite par Isla, les nœuds situés dans les parties supérieures de l'arbre étaient responsables des algorithmes de décision, tandis que les nœuds feuilles situés aux extrémités étaient chargés de l'exécution des actions. Cette approche a permis à l'IA non seulement de savoir quoi faire, mais aussi d'agir avec bon sens (common sense). De plus, pour percevoir les cibles, les personnages disposaient de leurs propres "listes de cibles" (target lists) internes et d'une conscience spatiale (firing positions). 3 Cette structure modulaire était si flexible, tolérante aux pannes et lisible que le concept s'est rapidement propagé au domaine de la robotique et du monde académique. Aujourd'hui, des véhicules aériens sans pilote aux robots collaboratifs industriels (collaborative robots) et aux systèmes de conduite autonome, les Arbres de Comportement sont devenus un standard de fait (de facto standard) dans une large gamme d'applications. 1

Architecture Structurelle des BT et Hiérarchie des Nœuds (Node)

Les arbres de comportement sont une structure de données arborescente et hiérarchique qui relie les actions et les décisions entre elles comme des blocs de LEGO numériques. 2 Contrairement aux Arbres de Décision (Decision Trees) classiques, les BT ne se contentent pas de suivre un chemin jusqu'à ce qu'un résultat soit atteint ; ils gèrent le contrôle logique des nœuds, les processus d'exécution asynchrones (execution flows) et les interruptions (interrupts) par le biais de signaux réguliers (généralement appelés "tick") envoyés de la racine (root) de l'arbre vers ses feuilles (leaves). 1

Le concept le plus vital et distinctif dans le fonctionnement de cette architecture est que chaque nœud, à la suite d'une opération de "tick" qu'il reçoit, renvoie obligatoirement un état logique (status) à son nœud parent (parent node). Ces états de retour se composent de trois types universels :

1. Success (Succès) : Le nœud a terminé sa tâche complètement et sans problème, ou la condition testée est vraie.

2. Failure (Échec) : Le nœud n'a pas pu accomplir sa tâche, s'est heurté à un obstacle ou la condition testée est fausse.

3. Running (En cours) : L'opération n'est pas encore terminée ; plusieurs cycles temporels (tick/frame) sont nécessaires pour achever l'action. 8

C'est précisément l'existence de cet état "Running" qui constitue un saut technologique distinguant les Arbres de Comportement de toutes les autres structures arborescentes classiques. 27 On ne peut pas s'attendre à ce qu'un robot physique termine l'ordre "Marcher vers la cible" en un dixième de seconde ou qu'un personnage de jeu vidéo complète instantanément l'animation "Ouvrir le coffre". L'état Running permet à cette branche spécifique de l'arbre de poursuivre l'action de manière asynchrone en arrière-plan, tout en empêchant le système de se bloquer et de se figer (blocking the execution thread). 27

Structurellement, les arbres de comportement se composent de trois grandes catégories de nœuds : les Compositeurs, les Décorateurs et les Feuilles. 28

1. Nœuds Composites (Composite Nodes)

Les nœuds composites sont les points de ramification de l'arbre. Ce sont les blocs de construction qui possèdent plusieurs nœuds enfants (children) et décident dans quel ordre, sous quelle condition ou de manière synchrone ces nœuds enfants qui leur sont rattachés doivent être exécutés. 28

• Sélecteurs (Selector / Fallback Nodes) : C'est le reflet de l'opérateur OR (OU) de la logique de programmation fondamentale. Ils exécutent les nœuds enfants qui leur sont rattachés séquentiellement de gauche à droite. Si l'un des nœuds enfants renvoie Success ou Running, le nœud Sélecteur arrête immédiatement de tester les autres enfants et transmet cet état à son propre nœud parent. Le seul moyen pour un nœud Sélecteur de renvoyer Failure (Échec) est que tous les nœuds enfants qui lui sont rattachés échouent. Cette structure est parfaite pour déterminer les priorités de survie ou les plans de rechange (fallback) d'un agent : le système essaie d'abord l'option "Se soigner", en cas d'échec il passe à l'option "Se mettre à couvert", et si cela échoue également, il essaie l'option "Fuir". Dès qu'un élément réussit, la chaîne d'action est satisfaite. 8

• Séquences (Sequence Nodes) : C'est l'équivalent de l'opérateur AND (ET) de la programmation fondamentale pour les arbres de comportement. Ils testent les nœuds enfants de gauche à droite. Cependant, contrairement aux Sélecteurs, si l'un des nœuds enfants renvoie Failure, les Séquences interrompent immédiatement l'opération et renvoient Failure au nœud parent. Pour qu'une Séquence renvoie Success, il est impératif que tous les nœuds enfants qu'elle contient réussissent sans exception. Ce nœud est utilisé pour établir la chaîne logique des étapes d'une tâche : la chaîne nécessaire pour qu'un PNJ franchisse une porte est configurée comme suit : "Marcher vers la porte", puis "Déverrouiller", puis "Baisser la poignée", puis "Entrer". Si la porte est verrouillée et que le personnage ne peut pas ouvrir la serrure (Failure), il n'y a aucune logique à passer aux étapes suivantes ; la séquence échoue et le personnage abandonne son plan de traverser la porte. 8

• Nœuds Parallèles (Parallel Nodes) : Ce sont l'un des membres les plus complexes de la famille des composites. Ils exécutent leurs nœuds enfants non pas séquentiellement de gauche à droite, mais en même temps (de manière synchrone). Ils renvoient un résultat à l'arbre selon une politique de succès ou d'échec spécifique (par exemple, "terminer l'opération dès que l'un des nœuds enfants réussit" ou "attendre que tous réussissent"). Ils sont utilisés pour contrôler des tâches simultanées telles que "Le personnage fait des gestes de la main tout en parlant" ou "Un véhicule robotique avance vers la cible tout en effectuant un balayage radar". 30

2. Nœuds Décorateurs (Decorator Nodes)

Tout comme le patron de conception Decorator dans les patrons de conception, ce sont des nœuds qui ne peuvent posséder qu'un seul nœud enfant et qui modifient le résultat renvoyé par cet enfant selon diverses politiques ou conditionnent son exécution. 8

• Inverter (Inverseur) : C'est l'opérateur NOT de la programmation classique. Il convertit le résultat Success du nœud enfant en Failure, et le résultat Failure en Success.

• Limiter (Limiteur) : Il permet au nœud enfant de ne s'exécuter qu'un nombre déterminé de fois par seconde ou sur l'ensemble de son cycle de vie ; il renvoie un échec dans les cas qui dépassent ce quota.

• Timer (Minuteur) : Il retarde l'action du nœud enfant pendant une durée déterminée au lieu de l'exécuter immédiatement. 8

3. Nœuds Feuilles (Leaf Nodes)

Ce sont les nœuds d'exécution situés au niveau le plus haut, le plus bas de l'arbre, qui, par nature, ne peuvent posséder aucun nœud enfant. 29 Les feuilles sont les points d'extrémité du système où l'on interagit directement avec le monde virtuel du jeu ou les capteurs du robot réel, produisant des effets tangibles. 22

• Actions (Actions/Tasks) : Ce sont les blocs de code réels qui créent un changement physique ou logique dans le monde, jouent une animation, émettent un son ou envoient de la puissance aux moteurs ("Tirer", "Marcher vers la cible", "Arrêter les moteurs").

• Conditions (Conditions/Queries) : Ce sont des contrôles instantanés de la logique et des requêtes de capteurs qui renvoient généralement Success ou Failure sans effectuer aucune action ("L'ennemi est-il à portée de vue ?", "Me reste-t-il des munitions ?", "Le niveau de la batterie est-il inférieur à 20 % ?"). 8

Arbres de Comportement pilotés par les Événements (Event-Driven) et Observateurs (Observers)

Les anciens BT classiques fonctionnaient selon une logique de scrutin (polling) où, à chaque opération de "tick" (généralement à chaque frame visuelle), l'arbre était constamment réévalué de haut en bas en partant de la racine. 19 Bien que cette situation fût irréprochable en termes de réactivité, elle générait une surcharge processeur (CPU) massive lors du calcul de chaque frame. Plus un arbre devenait profond, plus le coût de tester à nouveau toutes les conditions du sommet vers le bas à chaque frame cessait d'être viable. 9

Les moteurs de jeux modernes tels que Unreal Engine et les standards de l'industrie ont fait évoluer l'architecture vers le modèle des "Arbres de Comportement pilotés par les événements" (Event-Driven Behavior Trees) pour surmonter ce goulot d'étranglement matériel. 32 Dans cette structure innovante, au lieu de contrôler les conditions du début à la fin comme un agent de police à chaque "tick", le système utilise des décorateurs réactifs appelés "Annulations d'observateur" (Observer Aborts). Par exemple, si l'IA d'un chat chasse une souris, un nœud parallèle classique demande chaque seconde si la souris est entrée dans son trou. Dans la structure pilotée par les événements, la condition "La souris est-elle observable ?" est placée dans l'arbre en tant qu'Observateur. Dès que la souris s'enfuit dans le trou (event), cet événement est déclenché et l'Observateur annule instantanément (abort) la séquence "Courir" et "Sauter" du chat en cours. Ainsi, l'intelligence artificielle ne recalcule que lorsque sa situation change réellement, des économies massives de puissance de processeur sont réalisées, les chemins d'exécution simultanée dans les arbres complexes sont minimisés et l'optimisation du système est incroyablement facilitée. De plus, dans le système Unreal Engine, des nœuds spéciaux appelés "Services" (Services) peuvent être ajoutés aux nœuds Composites. Les Services fonctionnent à des périodes définies tant que le sous-arbre est actif (par exemple toutes les 2 secondes), remplaçant les actions périodiques "during" des FSM et mettant continuellement à jour des données telles que le suivi des ennemis.

Problème de Mémoire et Mécanisme du Tableau Noir (Blackboard)

L'immense modularité des Arbres de Comportement a un prix : par conception, les nœuds BT sont complètement isolés et sans état (stateless). C'est-à-dire qu'un nœud d'action "Marcher vers la cible" ignore totalement ce que le nœud de condition "Trouver l'ennemi" situé immédiatement à sa gauche a trouvé ou quelles décisions ont été prises lors des cycles précédents. Contrairement aux FSM, les BT n'enregistrent pas les décisions passées ou les données de capteurs instantanées dans leurs propres structures internes.

Pour combler ce vide de communication vital et doter l'arbre d'une sorte de "mémoire à court terme", le patron de conception Blackboard (Tableau Noir) est utilisé. Le Blackboard est un pool de données externe et partagé que tous les nœuds de l'arbre peuvent lire et écrire pendant l'exécution (généralement configuré sous forme de dictionnaire, de table de hachage ou de structure de données de type Variant dans les langages de programmation).

Le fonctionnement est le suivant : lorsqu'un arbre atteint le nœud de condition "Voir l'ennemi", ce nœud détecte les coordonnées de l'ennemi mais ne conserve pas cette information pour lui-même ; il l'écrit directement sur le Blackboard sous la forme TargetPosition = . Lorsque le flux de l'arbre atteint l'étape suivante, à savoir le nœud d'action "Aller là-bas", le nœud d'action se connecte au Blackboard, lit la donnée TargetPosition et trace son itinéraire.

L'architecture du Tableau Noir construit un pont de données incroyablement puissant, flexible et rapide entre les nœuds et les branches, sans compromettre la modularité pure et l'isolation des nœuds des Arbres de Comportement.

Analyse comparative : Le choc entre les machines à états finis et les arbres de comportement

Pour les architectes qui se préparent à poser les fondations d'un système d'intelligence artificielle à partir de zéro, le choix entre les machines à états finis (FSM) et les arbres de comportement (BT) n'est pas un simple choix de syntaxe ou de moteur, mais une décision architecturale vitale qui affectera profondément tout le cycle de vie du projet. Les actes de la Game Developers Conference (GDC), les études de cas industrielles et les simulations robotiques académiques publiées ces dernières années comparent de manière exhaustive les performances structurelles de ces deux systèmes sous les angles de la prise de décision, de la modularité, de la réactivité, de la lisibilité et de l'évolutivité.

1. Prise de décision (Decision-Making) vs. Contrôle des états (State Control)

Le consensus le plus fort de l'industrie du logiciel est que les BT se spécialisent dans les processus de « prise de décision », tandis que les FSM se spécialisent dans les processus de « contrôle des états ».

Les arbres de comportement sont spécialement optimisés pour prendre des décisions cognitives (« Que doit faire l'agent maintenant ? ») qui sont dynamiques, réagissent à des conditions environnementales en constante évolution, impliquent de nombreuses branches logiques et nécessitent une priorisation. Les FSM quant à elles sont taillées sur mesure pour contrôler avec des frontières précises la manière dont une décision déjà prise est mise en œuvre, la gestion des modes physiques cohérents et isolés du système, et les flux séquentiels (« Comment et par quelles étapes l'agent doit-il exécuter cette action ? »).

Le tableau ci-dessous résume systématiquement ces différences philosophiques fondamentales :

2. Crise de la modularité et du couplage (Coupling)

Les BT sont, comme il est admis dans l'industrie, des architectures à « faible couplage » (low-dependency). Un nœud feuille de BT (par exemple l'action « Courir vers la cible ») est un objet encapsulé et autonome, totalement indépendant de l'endroit où il se trouve dans l'arbre. Ce nœud peut être dupliqué et glissé dans une branche complètement différente intitulée « Mode de défense à mitrailleuse lourde », et il fonctionnera sans problème sans qu'aucun code source ne soit modifié.

En revanche, dans les FSM, un « état » (state) doit définir en lui-même ou dans son propre gestionnaire vers quels états spécifiques il peut passer par la suite, et à quelles conditions cette approche de « couplage fort » (tight coupling) rend presque impossible la copie d'un bloc de code écrit hors du projet pour l'isoler vers une autre intelligence artificielle. Chaque modification mineure ou ajout d'un nouvel état dans une FSM nécessite de recalibrer un par un tous les flèches d'entrée et de sortie (transitions) reliées à cet état. Il a été statistiquement prouvé que l'ajout de nouveaux comportements de tolérance aux pannes (par exemple, retourner à la recharge autonome lorsque la batterie est vide) dans les systèmes basés sur les FSM est exponentiellement plus difficile que dans les systèmes basés sur les BT.

3. Conflit entre puissance d'expression (Expressiveness) et réactivité

Les comparaisons de laboratoire réalisées dans les architectures de contrôle robotique révèlent la différence philosophique inhérente à ces deux architectures avec des métriques extrêmement frappantes.

Puissance d'expression (Expressiveness) : Contrairement aux attentes, des études académiques ont prouvé que les FSM sont plus « expressives » que les BT. L'état actif dans lequel se trouve une FSM est une accumulation physique concrète des décisions prises dans le passé. Si une FSM émet le signal « Je suis actuellement en état d'alarme », cette information contient intrinsèquement le fait qu'une menace a été détectée dans le passé, que le système a validé cette menace et qu'il a initié une série d'actions. Les BT, en revanche, sont totalement amnésiques. À chaque nouveau cycle de « tick », l'arbre commence à balayer depuis le nœud racine comme si le monde venait d'être créé. Pour se souvenir des actions ou des modes passés, ils dépendent entièrement de données externes sur le Blackboard.

Réactivité : En contrepartie de la modularité, la réactivité est faible dans les FSM. Si le concepteur de la FSM n'a pas dessiné une flèche de transition telle que « Si le robot entend soudainement une alarme incendie en transportant un objet, passer à cet état », le robot ne lâchera jamais la boîte qu'il tient pour s'enfuir. Les BT, quant à eux, sont infiniment plus réactifs que les FSM. Étant donné que le monde est vérifié depuis le début à chaque cycle ou que des observateurs sont utilisés, le moindre changement environnemental permet à l'arbre de s'orienter instantanément vers la branche ayant la plus haute priorité (par exemple « Fuite d'urgence ») et d'annuler (preempt) l'action de transport d'objets qui était alors au statut « Running ».

4. Coût d'installation, débogage (Debugging) et maintenance

Dans les systèmes de prise de décision, le coût de maintenance est le domaine où les développeurs passent le plus clair de leur temps. Les FSM peuvent être construites à partir de zéro en quelques minutes avec un coût initial extrêmement faible, à l'aide de quelques énumérations (enum) et instructions switch-case. Cependant, à mesure que le système grandit avec le temps, cet avantage s'évapore et le débogage se transforme en un véritable chaos.

Les arbres de comportement, en revanche, commencent dès le départ avec une lourde charge de « boilerplate » (code passe-partout). Entre les mécanismes de racine, les systèmes de Tick et l'intégration du Blackboard, le simple fait de mettre le système sur pied représente un investissement architectural sérieux. Cependant, une fois ce prix payé, les capacités de débogage visuel en temps réel qu'ils offrent sont formidables. Dans des systèmes tels que les outils BT intégrés d'Unreal Engine ou le plugin Beehave développé pour Godot, le développeur peut surveiller en temps réel les flux de données sur l'arbre pendant que le jeu ou la simulation s'exécute (statuts vert et rouge lumineux) et identifier en quelques secondes pourquoi un nœud d'action a échoué. Trouver visuellement la source d'une erreur dans des « toile d'araignée » basées sur les FSM prend en revanche souvent des heures.

Applications d'architectures hybrides avancées et systèmes orientés objectifs

Se cantonner à un seul modèle architectural conduit souvent à l'échec dans les projets de systèmes autonomes. Alors qu'une approche FSM pure se heurte au mur de l'évolutivité, essayer de concevoir ne serait-ce que le moindre cycle de mouvement ou algorithme de saut à l'aide d'un BT crée un nombre excessif d'"Observateurs", entraînant une vérification superflue des conditions et un coût CPU massif. C'est pourquoi, dans les jeux AAA modernes et les solutions robotiques industrielles, le "Standard d'Or" réside dans des conceptions hybrides où ces deux architectures sont astucieusement intégrées de manière à masquer les faiblesses de l'autre.

Fusion d'un arbre de comportement et d'une machine à états (Layered AI)

Dans les conceptions hybrides les plus efficaces et reconnues par l'industrie, le système d'intelligence artificielle est divisé en couches (layers). Les décisions cognitives de haut niveau concernant ce que le personnage doit faire sont prises par l'Arbre de Comportement, qui est hiérarchique et propice aux embranchements par nature, tandis que la tâche d'exécuter physiquement et algorithmiquement cette décision choisie sur le terrain est déléguée à une FSM ou HFSM sous-jacente.

Par exemple, dans une IA ennemie avancée ou un agent de surveillance autonome, le système fonctionne de la

manière suivante :

1. Couche de décision (BT - Cerveau stratégique) : lit le nombre de menaces autour du personnage, sa propre valeur de santé et ses munitions via le Blackboard. À la suite de l'évaluation sélective effectuée, la décision de "Retraite tactique" est prise.35

2. Couche d'exécution (FSM - Compétences motrices) : L'ordre de "Retraite tactique" est transmis comme déclencheur (trigger) à une machine d'états intégrée au système squelettique du personnage. La FSM fait immédiatement sortir le personnage de son état d' "Animation d'attaque" actuel pour le faire passer de manière fluide à un état de "Course rapide", puis à un état d'animation de "Accroupissement" derrière un abri.

Grâce à cette approche en couches, le BT ne s'encombre pas inutilement à chaque image (frame) de détails d'exécution tels que "Est-ce que le pied gauche du personnage est en avant ou le droit ?" ; et la FSM n'a pas à se poser de questions macro-stratégiques telles que "Où est l'ennemi ?".22

Dans le domaine de la robotique, la situation présente un parallélisme similaire. Les changements de mode de plus haut niveau d'un robot de transport guidé autonome (AGV) travaillant dans un entrepôt logistique (Contrôle manuel humain, Mode de mission autonome, Mode d'erreur matérielle/urgence) sont coordonnés par une HFSM macro pour garantir la compréhensibilité.27 Cependant, lorsque le robot entre en "Mode de mission autonome", des opérations telles que l'évitement d'obstacles dynamiques sur la route vers la destination, la manipulation d'objets sensibles et les retours de capteurs instantanés sont confiées à la réactivité hiérarchique unique des BT.27 Dans la littérature, des solutions avancées où des arbres de comportement autonomes sont générés dynamiquement à partir de zéro par le chaînage de conditions en partant d'un objectif (backward-chaining) sont également appliquées avec succès.27

Autres dimensions de la prise de décision autonome : le contexte du GOAP

Afin de bien comprendre la complexité des architectures, il est également important de mentionner le concept de "Planification d'actions orientée vers les buts" (Goal-Oriented Action Planning - GOAP), qui va au-delà des systèmes FSM et BT dans l'industrie. Basé sur la théorie de planification académique STRIPS de 1971 et popularisé par Jeff Orkin, l'architecte de la légendaire IA ennemie du jeu F.E.A.R., le GOAP a apporté une dimension totalement différente aux processus de prise de décision.13

Dans un système GOAP, les actions ne sont pas combinées au préalable dans un arbre rigide. On fournit simplement au système une liste "d'Actions" (Actions - Ex. : Ouvrir la porte), de "Préconditions" (Preconditions - Ex. : Être près de la porte) et d'"Effets" (Effects - Ex. : La porte est maintenant ouverte). Le système (en utilisant généralement un algorithme de recherche A*) combine ces actions au moment de l'exécution (runtime) pour atteindre l'état "Cible" souhaité et crée automatiquement le plan le plus idéal. Le génie de F.E.A.R. réside dans le fait qu'il utilise en réalité une FSM très simple et minimaliste possédant seulement 3 états (GoTo, Animate, Use Smart Object) pour exécuter les plans produits par ce gigantesque moteur de planification autonome en arrière-plan.13 Tout comme dans les hybrides BT modernes, alors que le cerveau est un algorithme complexe, les muscles consistent toujours en une FSM solide.

Écosystèmes de moteurs de jeux de nouvelle génération : la vision "State Trees" (Arbres d'états) d'Unreal Engine

Épic Games, un pionnier mondial de la technologie des moteurs de jeux et des simulations de systèmes autonomes, a présenté à l'industrie un outil visionnaire visant à mettre fin à la décennie de rivalité entre les arbres de comportement et les machines à états grâce à la structure révolutionnaire d'Unreal Engine 5 (plus particulièrement sous la forme précisée dans la mise à jour 5.5) : les "State Trees" (Arbres d'états).36

La nature "sans état" (stateless) des arbres de comportement traditionnels (BT), qui a tendance à s'alourdir après une certaine échelle, et les limites strictes des FSM, qui manquent de flexibilité et sont enclines à produire du code spaghetti, ont été intelligemment mélangées dans le concept des State Trees.36 Epic Games élimine les vulnérabilités structurelles des anciens types de BT grâce à l'architecture State Tree et dote la puissance linéaire des FSM d'un mécanisme de décision moderne.

Les fonctionnalités phares de l'architecture State Tree sont les suivantes :

● En tant que flux de traitement principal, au lieu de la structure ennemie du processeur des BT qui effectue des ticks continus et "vérifie les conditions sans arrêt", elle s'appuie sur la performance de contrôle d'état optimisée (state flow) offerte par les FSM.36 ● Lors de la définition des transitions entre les états, au lieu d'utiliser des "transitions complexes et étroitement imbriquées", qui constituent le point faible des FSM, elle bénéficie de la flexibilité des nœuds de repli (Fallback) utilisés par les Arbres de Comportement. ● Elle va un paso más allá en l'intégrant directement les algorithmes d'utilité (Utility - Évaluation de pondération/poids) dans la sélection des états.38 Au lieu de dessiner des flèches de transition statiques et fragiles pour les actions "Combattre" ou "Fuir" vers une cible, le développeur peut définir des paramètres de poids mathématiques et des distributions de probabilité pour chaque état. À mesure que la santé du personnage diminue, le score d'utilité de la fonction calculant l'état "Fuir" dépasse celui de l'état "Combattre".38 De cette façon, l'arbre effectue une transition organique d'un état à l'autre, avec l'élégance d'un arbre de décision, sans avoir besoin d'innombrables flèches de transition.38

Cette nouvelle vague technologique est une étape qui va changer la donne dans le domaine de la prise de décision autonome. Le fait que les ingénieurs d'Epic Games se concentrent directement sur l'architecture State Tree dans la construction de nouveaux matériels et systèmes dessine la projection claire que les Arbres de Comportement classiques pures seront progressivement abandonnés à l'avenir pour laisser la place à des "State Trees" hybrides, dotés des performances des FSM et enrichis de fonctions d'utilité.36

Conclusion

Lors de la conception de l'épine dorsale décisionnelle des personnages autonomes, des bras robotiques, des véhicules sans conducteur et des agents d'IA avancés dans les jeux vidéo, il n'y a pas de réponse théorique absolue et unique à la question "Quelle architecture est supérieure ?". Chaque décision architecturale prise en informatique et en génie logiciel s'accompagne d'un calcul de compromis (trade-off) approfondi.

Les machines à états finis (FSM), grâce à leur haute vitesse d'exécution dans les transitions d'états déterministes, à la facilité de compréhension logique qu'elles offrent au développeur et à leur nature dotée de limites matérielles strictes, continueront d'être une pierre angulaire indispensable, en particulier dans les contrôles de jeux de bas niveau, les jeux de combat, les mécaniques d'arcade et les systèmes d'animation complexes. Cependant, dans les scénarios cognitifs où le nombre de variables représentées augmente et où les conditions environnementales changent instantanément, l'"explosion d'états" provoquée par la FSM se transforme en une crise structurelle dangereuse qui condamne rapidement le projet à un code spaghetti impossible à maintenir.

Les arbres de comportement (Behavior Trees), quant à eux, ont véritablement fait entrer l'IA des jeux et l'autonomie robotique dans une nouvelle ère en apportant à l'industrie les paradigmes de la souplesse, de l'ultra-modularité, de la réutilisation basée sur les composants et de la haute réactivité. L'existence du concept "Running", qui permet d'exécuter de manière asynchrone des actions s'étalant sur le temps, et la modélisation de codes comme des pièces de LEGO indépendantes pouvant être ajoutées à d'autres agents sans plus jamais y toucher, ont fait des BT le cerveau incontesté des simulations massives en monde ouvert. Cependant, le sans-état (statelessness), contrepartie de cette flexibilité, oblige les concepteurs de systèmes à établir des ponts de mémoire externe tels que le Blackboard et impose la mise en œuvre de conceptions lourdes orientées événements (event-driven) pour assurer l'optimisation des performances.

En fin de compte, la conception réussie d'un système autonome moderne dépend du niveau d'abstraction auquel l'architecte préfère gérer le projet. Les applications pratiques de l'industrie prouvent un fait indiscutable : les architectures hybrides hiérarchiques, où les objectifs des systèmes autonomes sont déterminés et les décisions réactives sur l'action à choisir sont prises par des Arbres de Comportement, tandis que la coordination physique, les étapes d'animation et les transitions de mode de l'action choisie sont gérées par des FSM, représentent le point le plus élégant et le plus sophistiqué atteint par le logiciel d'aujourd'hui. Les mécanismes de décision du futur continueront d'être le théâtre d'évolutions de systèmes de nouvelle génération où les frontières s'estompent encore davantage et où les architectures fusionnent les FSM et les BT en un seul corps (comme dans l'exemple des Unreal Engine State Trees).

*Note : Les visuels ont été générés par Google Gemini.