Comparison of Adaptive Behaviors of an Animat in Different Markovian 2-D Environments Using XCS Classifier Systems
Armin Najarpour-Foroushani · PolyPublie (École Polytechnique de Montréal) · 2013
Le mot "Animat" fut introduit par Stewart W. Wilson en 1985 et a rapidement gagné en popularité dans la lignée des conférences SAB (Simulation of Adaptive Behavior: From Animals to Animats) qui se sont tenues entre 1991 à 2010.Comme la signification du terme "animat" a passablement évoluée au cours de ces années, il est important de préciser que nous avons choisi d'étudier l'animat tel que proposée originellement par Wilson.La recherche sur les animats est un sous-domaine du calcul évolutif, de l'apprentissage machine, du comportement adaptatif et de la vie artificielle.Le but ultime des recherches sur les animats est de construire des animaux artificiels avec des capacités sensorimotrices limitées, mais capables d'adopter un comportement adaptatif pour survivre dans un environnement imprévisible.Différents scénarios d'interaction entre un animat et un environnement donné ont été étudiés et rapportés dans la littérature.Un de ces scénario est de considérer un problème d'animat comme un problème d'apprentissage par renforcement (tel que les processus de décision markovien) et de le résoudre par l'apprentissage de systèmes de classeurs (LCS, Learning Classification Systems) possédant une certaine capacité de généralisation.L'apprentissage d'un système de classification LCS est équivalent à un système qui peut apprendre des chaînes simples de règles en interagissant avec l'environnement et en reçevant diverses récompenses.Le XCS (eXtended Classification System) introduit par Wilson en 1995 est le LCS le plus populaire actuellement.Il utilise le Q-Learning pour résoudre les problèmes d'affectation de crédit (récompense), et il sépare les variables d'adaptation de l'algorithme génétique de celles reliées au mécanisme d'attribution des récompenses.Dans notre recherche, nous avons étudié les performances de XCS, et plusieurs de ses variantes, pour gérer un animat explorant différents types d'environnements 2D à la recherche de nourriture.Les environnements 2D traditionnellement nommés WOODS1, WOODS2 et MAZE5 ont été étudiés, de même que des environnements S2DM (Square 2D Maze) que nous avons conçus pour notre étude.Les variantes de XCS sont XCSS (avec l'opérateur "Specify" qui permet de diminuer la portée de certains classificateurs), et XCSG (avec la descente du gradient en fonction des valeurs de prédiction).Nous avons constaté une amélioration sensible de leur performance d'apprentissage.vi Nous avons proposé une version combinant XCSS et XCSG, appelée XCSSG.La comparaison des résultats montre que pour des environnements simples tels que WOODS1 et WOODS2, les performances de tous les algorithmes (soit le nombre d'étapes que l'animat doit faire pour atteindre la nourriture) déjà proposés sont très proches, mais que dans des environnements plus complexes tels que MAZE5, l'approche XCSSG converge rapidement près de la solution optimale (nombre minimum d'étapes).Pour étudier la capacité d'apprentissage de XCS et ses variantes sur une plus grande variété d'environnements (markoviens et non markoviens) que les environnements classiques WOODSx et MAZEy, nous avons conçu un générateur d'environnements S2DM.Les différents algorithmes XCS étudiés ont été testés sur ces environnements et les résultats montrent clairement que les capacités d'apprentissage des différents XCS s'approchent toutes des performances optimales.De plus, une analyse de l'évolution du nombre de classificateurs/règles d'une population a également été faite pour mieux illustrer les capacités de généralisation de chacun des algorithmes XCS.Nous avons finalement proposés trois nouveaux scénario pour étudier les variations de populations de classificateurs des différents XCS.D'abord, un scénario où les ressources se déplacent légèrement.Puis, un scénario compétitif inter-espèces (XCS vs XCSSG) pour le partage d'une ressource commune.Ce scénario est basé sur les équations de Lotka-Volterra et permet de comparer dynamiquement les performances des deux algorithmes.Un troisième scénario a été proposé faisant intervenir un animat ayant des capacités supérieures de vision afin d'étudier la possibilité d'apprendre dans des environnements non-markoviens pour un animat classique, mais markoviens pour un animat moins myope.Les résultats de ce troisième scénario ne sont pas ceux auxquels nous nous attendions.En effet, l'animat n'a pas su profiter de cette supériorité pour améliorer ses performances.C'est pour nous un problème ouvert que nous nous proposons d'explorer dans une nouvelle recherche.