Un arbre ET-OU est un formalisme graphique utilisé en intelligence artificielle (IA) et en informatique pour représenter des processus de résolution de problèmes et des structures de décision. Il s'agit d'un type de structure de données arborescente dans laquelle chaque nœud est étiqueté comme étant soit un nœud ET, soit un nœud OU. Dans un nœud ET, tous les sous-problèmes enfants doivent être résolus pour satisfaire l'objectif parent ; dans un nœud OU, résoudre un seul sous-problème enfant suffit. Cette distinction permet aux arbres ET-OU de modéliser des problèmes complexes qui se décomposent en sous-tâches conjonctives et disjonctives, ce qui en fait un outil fondamental dans des domaines tels que la planification automatisée, le jeu et la programmation logique.
Le concept est issu des premières recherches en IA sur la résolution de problèmes et les algorithmes de recherche. Il est étroitement lié aux arbres de jeu et aux arbres de décision, mais il s'en distingue par son traitement explicite des relations ET. Les arbres ET-OU sont souvent utilisés en conjonction avec des stratégies de recherche telles que la recherche en profondeur, la recherche en largeur et la recherche heuristique, et ils constituent la base d'algorithmes comme AO* (une recherche meilleur d'abord pour les graphes ET-OU).
Structure et sémantique
Un arbre ET-OU est un arbre enraciné où chaque nœud interne a l'un des deux types suivants :
- Nœud ET : Le nœud n'est satisfait que si tous ses enfants sont satisfaits. Cela représente une conjonction de sous-objectifs. Par exemple, pour construire une maison, il faut terminer les fondations, les murs et le toit (tous sont requis).
- Nœud OU : Le nœud est satisfait si au moins un de ses enfants est satisfait. Cela représente une disjonction d'alternatives. Par exemple, pour se rendre dans une ville, on peut prendre un train, un bus ou une voiture (un seul suffit).
Les feuilles sont généralement des objectifs primitifs ou des états terminaux qui sont soit vrais, soit faux. Le nœud racine représente le problème ou l'objectif global. Une solution au problème correspond à un sous-arbre qui satisfait la racine, ce qui signifie que pour chaque nœud ET du sous-arbre, tous les enfants sont inclus, et pour chaque nœud OU, exactement un enfant est inclus.
Contexte historique
Le formalisme des arbres ET-OU a gagné en importance dans les années 1960 et 1970 dans le domaine de l'intelligence artificielle. Les premiers systèmes d'IA, tels que le General Problem Solver (GPS) développé par Allen Newell et Herbert A. Simon, utilisaient l'analyse moyens-fins, qui impliquait implicitement une décomposition ET-OU. Cependant, la représentation explicite des arbres ET-OU est devenue standard dans les manuels et les recherches sur la résolution de problèmes. Notamment, l'algorithme AO, introduit dans les années 1970, a étendu l'algorithme de recherche A pour traiter les graphes ET-OU, permettant de trouver des solutions optimales dans des problèmes avec des sous-objectifs conjonctifs.
Applications en intelligence artificielle
Les arbres ET-OU sont largement utilisés en IA pour :
- Planification automatisée : Représenter des plans comme des décompositions hiérarchiques de tâches. Par exemple, un plan de navigation de robot peut nécessiter de se déplacer vers un emplacement (ET : éviter les obstacles, atteindre la cible) ou de choisir parmi plusieurs itinéraires (OU).
- Jeu : Modéliser des états de jeu où un joueur doit faire des mouvements (OU) et les réponses de l'adversaire (ET) sont considérées. L'algorithme minimax, utilisé aux échecs et dans d'autres jeux, peut être vu comme un cas particulier de recherche ET-OU.
- Programmation logique : En Prolog, le processus de résolution peut être visualisé comme un arbre ET-OU, où les objectifs sont combinés par ET et les clauses fournissent des alternatives OU.
- Systèmes experts : Le raisonnement basé sur des règles utilise souvent des structures ET-OU pour déduire des conclusions à partir de prémisses.
Algorithmes de recherche pour les arbres ET-OU
Plusieurs algorithmes opèrent sur les arbres ET-OU pour trouver des solutions :
- Recherche en profondeur (DFS) : Explore une branche aussi loin que possible avant de revenir en arrière. Pour les nœuds ET, tous les enfants doivent être explorés ; pour les nœuds OU, le premier enfant réussi peut suffire.
- Recherche en largeur (BFS) : Explore les nœuds niveau par niveau, garantissant que la solution la plus superficielle est trouvée.
- AO* : Un algorithme de recherche meilleur d'abord qui développe les nœuds en fonction d'une estimation de coût, en considérant à la fois les branches ET et OU. Il maintient un graphe de solution et met à jour les coûts de manière récursive.
- Minimax avec élagage alpha-bêta : Utilisé dans les arbres de jeu, qui sont un sous-ensemble des arbres ET-OU où le joueur et l'adversaire alternent les tours.
Ces algorithmes sont fondamentaux dans les cours d'IA et sont implémentés dans de nombreux systèmes d'IA.
Relation avec d'autres formalismes
Les arbres ET-OU sont étroitement liés à d'autres structures :
- Arbres de décision : Dans les arbres de décision, chaque nœud interne représente un test sur un attribut, et les branches représentent les résultats. Ils sont utilisés pour la classification et la régression, mais ils n'ont généralement pas de nœuds ET ; ils sont purement de type OU dans le sens où un seul chemin est suivi.
- Arbres de jeu : Un arbre de jeu représente tous les mouvements et réponses possibles. Il peut être vu comme un arbre ET-OU où les mouvements du joueur sont des nœuds OU (choisir un mouvement) et les mouvements de l'adversaire sont des nœuds ET (doit considérer toutes les réponses).
- Graphes ET-OU : Contrairement aux arbres, les graphes permettent le partage de sous-problèmes, évitant la duplication. Les graphes ET-OU sont plus généraux et sont utilisés dans la réduction de problèmes.
Extensions et variantes
Plusieurs extensions de l'arbre ET-OU de base ont été développées :
- Arbres ET-OU pondérés : Assignent des coûts aux nœuds ou aux arêtes, permettant une optimisation basée sur les coûts.
- Arbres ET-OU probabilistes : Incorporent des probabilités pour des résultats incertains, utilisés dans l'analyse de décision et la théorie des jeux.
- Arbres ET-OU avec contraintes : Ajoutent des contraintes qui doivent être satisfaites à travers les sous-arbres, courantes dans les problèmes de satisfaction de contraintes.
Ces variantes améliorent l'expressivité du formalisme pour des applications réelles.
Pertinence actuelle et recherche
Bien que l'IA moderne se soit orientée vers les approches de apprentissage automatique et de apprentissage profond, les arbres ET-OU restent pertinents dans l'IA symbolique et les systèmes hybrides. Ils sont utilisés dans l'IA explicable pour fournir des structures de raisonnement transparentes, et dans les architectures de réseaux de neurones qui intègrent des représentations structurées. La recherche sur l'IA neuro-symbolique combine souvent les réseaux de neurones avec le raisonnement par arbres ET-OU pour améliorer la généralisation et l'interprétabilité. De plus, les arbres ET-OU sont utilisés dans la compréhension du langage naturel pour analyser des phrases en structures hiérarchiques, et en vision par ordinateur pour la compréhension de scènes.
Voir aussi
- intelligence artificielle
- apprentissage automatique
- apprentissage profond
- réseau de neurones
- grand modèle de langage
- transformeur
- IA générative
- ordinateur d'échecs
- Waymo
- Autopilot Tesla
Références
- Nilsson, N. J. (1980). Principles of Artificial Intelligence. Tioga Publishing.
- Rich, E., & Knight, K. (1991). Artificial Intelligence. McGraw-Hill.
- Russell, S., & Norvig, P. (2021). Artificial Intelligence: A Modern Approach. Pearson.