Le monde des blocs est un domaine abstrait et simplifié de la recherche en intelligence artificielle (IA), introduit pour la première fois dans les années 1960, dans lequel un bras robotique manipule un ensemble de blocs cubiques posés sur une table. L'objectif est généralement de réorganiser les blocs d'une configuration initiale vers une configuration cible, sous réserve de contraintes telles que déplacer un seul bloc à la fois et ne pas déplacer un bloc qui en supporte un autre. En raison de sa simplicité et de ses règles bien définies, le monde des blocs est devenu un banc d'essai standard pour les premiers systèmes de planification et de résolution de problèmes en IA, et il reste un outil pédagogique dans les cours d'IA ainsi qu'un benchmark pour les algorithmes de planification.
Le domaine a été popularisé par des chercheurs d'institutions telles que le MIT et SRI International (non inclus dans la liste fournie, mais historiquement pertinent) dans les années 1960 et 1970. Il a été utilisé pour explorer des concepts fondamentaux de l'IA, notamment la recherche dans l'espace d'états, la recherche heuristique et la représentation des actions et des objectifs. Le monde des blocs a également servi de plateforme pour développer les premiers systèmes de compréhension du langage naturel, où les utilisateurs pouvaient donner des commandes comme « mets le bloc rouge sur le bloc vert » et le système planifiait et exécutait l'action.
Développement historique
Le monde des blocs est issu des premières recherches en IA sur la résolution de problèmes. En 1963, le système STRIPS (Stanford Research Institute Problem Solver), développé à SRI, a utilisé un environnement de type monde des blocs pour démontrer la planification automatisée. STRIPS représentait les états comme des conjonctions de prédicats logiques (par exemple, on(A,B), clear(A)) et les actions avec des préconditions et des effets. Ce formalisme est devenu fondamental pour la planification en IA.
Un autre système influent a été le monde des blocs tel qu'implémenté dans le programme SHRDLU par Terry Winograd au MIT en 1972. SHRDLU permettait aux utilisateurs d'interagir avec un monde des blocs virtuel en langage naturel, en répondant à des questions et en exécutant des commandes. Il intégrait l'analyse syntaxique, l'analyse sémantique et la planification, et a été une étape marquante dans la compréhension du langage naturel. Bien que SHRDLU fût limité à un micro-monde, il a démontré le potentiel de combiner langage et raisonnement.
Formalisation et complexité
Dans le monde des blocs, un état est généralement décrit par un ensemble de prédicats : on(X,Y) signifie que le bloc X est directement sur le bloc Y, on-table(X) signifie que le bloc X est sur la table, et clear(X) signifie que le bloc X n'a aucun bloc au-dessus. L'objectif est une conjonction de tels prédicats. Les actions incluent move(X,Y) (déplacer le bloc X sur le bloc Y, nécessitant que X et Y soient dégagés) et move-to-table(X) (déplacer X sur la table, nécessitant que X soit dégagé).
La planification dans le monde des blocs est NP-complète en général, ce qui signifie que trouver un plan optimal (avec le moins de mouvements) est computationnellement difficile. Cependant, le domaine est souvent utilisé pour illustrer des techniques de recherche heuristique telles que l'algorithme A et l'analyse des moyens et des fins*. Une heuristique courante est le nombre de blocs qui ne sont pas dans leur position finale correcte, ce qui est admissible et aide à guider la recherche.
Applications et influence
Le monde des blocs a été largement utilisé dans la recherche et l'enseignement en IA. Il sert de benchmark pour les algorithmes de planification, y compris ceux basés sur Graphplan (non inclus dans la liste) et la planification par ordre partiel. Il apparaît également dans des expériences d'apprentissage par renforcement, où un agent apprend à manipuler des blocs par essais et erreurs. En robotique, le monde des blocs est une version simplifiée des tâches de préhension et de placement, et les systèmes modernes utilisent souvent des techniques de Deep learning et de Machine learning pour gérer des variantes plus complexes.
Le domaine a influencé d'autres domaines, tels que le Natural language processing (non inclus dans la liste) et les sciences cognitives (non incluses dans la liste), où il est utilisé pour étudier la résolution de problèmes humaine et les modèles mentaux. La simplicité du monde des blocs permet aux chercheurs d'isoler des processus cognitifs spécifiques, tels que la planification et le raisonnement spatial.
Pertinence moderne
Bien que le monde des blocs soit souvent considéré comme un problème jouet, il reste pertinent dans l'IA contemporaine. Il est utilisé pour tester de nouvelles approches de planification, y compris celles basées sur les grands modèles de langage et les transformeurs. Par exemple, des chercheurs ont exploré l'utilisation de grands modèles de langage pour générer des plans pour des tâches du monde des blocs, en tirant parti de leur capacité à comprendre des instructions en langage naturel. Cependant, ces modèles ont souvent du mal avec la nature combinatoire du domaine, ce qui souligne la nécessité d'approches hybrides combinant réseaux neuronaux et raisonnement symbolique.
Dans l'enseignement, le monde des blocs est un exercice standard dans les cours d'IA, aidant les étudiants à comprendre la recherche dans l'espace d'états, la planification et l'importance de la représentation. Il est également utilisé dans des compétitions et des benchmarks, tels que la Conférence internationale sur la planification, où il apparaît comme un domaine classique.
Voir aussi
- intelligence artificielle
- apprentissage automatique
- apprentissage profond
- réseau neuronal
- grand modèle de langage
- transformeur
- MIT-CSAIL
- Xerox-PARC (bien que non directement lié, c'est un centre de recherche)
Références
- Fikes, R. E., & Nilsson, N. J. (1971). STRIPS: A new approach to the application of theorem proving to problem solving. Artificial Intelligence, 2(3-4), 189-208.
- Winograd, T. (1972). Understanding natural language. Cognitive Psychology, 3(1), 1-191.
- Gupta, N., & Nau, D. S. (1992). On the complexity of blocks-world planning. Artificial Intelligence, 56(2-3), 223-254.