L' anomalie de Sussman est un problème d'intelligence artificielle, initialement décrit par Gerald Sussman. Il illustre une faiblesse des algorithmes de planification non entrelacés, très répandus au début des années 1970. La plupart des systèmes de planification modernes ne sont pas limités à la planification non entrelacée et peuvent donc gérer cette anomalie. Bien que l'importance de ce problème soit désormais historique, il reste utile pour expliquer la complexité de la planification. Dans ce problème, situé dans un environnement de type monde des blocs, trois blocs (A, B et C) reposent sur une table. L'agent doit empiler les blocs de sorte que A soit sur B, et B soit sur C. Cependant, il ne peut déplacer qu'un seul bloc à la fois. Le problème initial présente B sur la table, C sur A et A sur la table: centré|300x300px Cependant, les planificateurs non entrelacés séparent généralement l'objectif (empiler A sur B sur C) en sous-objectifs, tels que :
placer A au-dessus de B placer B au-dessus de C
Supposons que le planificateur commence par poursuivre l'objectif 1. La solution la plus simple consiste à déplacer C ni sur B ni sur A, puis à placer A au-dessus de B. Mais si cette séquence permet d'atteindre l'objectif 1, l'agent ne peut plus poursuivre l'objectif 2 sans annuler l'objectif 1, puisque A et B doivent tous deux être placés au-dessus de C. centré|300x300px Cependant, commencer par l'objectif 2 ne permet pas de passer outre ce problème. Poursuivre l'objectif 1 annule forcément l'objectif 2 : centré|300x300px Le problème a été initialement identifié par Sussman dans le cadre de ses recherches doctorales. Sussman (et son directeur de thèse, Marvin Minsky ) pensaient que l'intelligence nécessitait une liste d'exceptions ou d'astuces, et ont développé un système de planification modulaire pour « déboguer » les plans.
Voir aussi BANDES Planification automatisée Algorithme glouton
Bibliographie
G.J. Sussman (1975) A Computer Model of Skill Acquisition Elsevier Science Inc. New York, NY, USA. Book version of his PhD thesis.
Notes et références
Liens externes
Catégorie:Nouveauté en 1975