Des abstractions d'action évolutives pour la planification en temps réel dans les jeux de forme extensive.

Un défi majeur pour les systèmes de planification dans les domaines multi-agents en temps réel est de rechercher dans de grands espaces d'action pour décider de la prochaine action d'un agent. Des travaux antérieurs ont montré que les abstractions d'actions fabriquées à la main permettent aux systèmes de planification de concentrer leur recherche sur un sous-ensemble d'actions prometteuses. Dans cet article, nous montrons que le problème de la génération d'abstractions d'actions peut être considéré comme un problème de sélection d'un sous-ensemble de stratégies pures parmi un ensemble d'options. Nous modélisons la sélection d'un sous-ensemble de stratégies pures comme un jeu à deux joueurs dans lequel l'ensemble des stratégies des joueurs est l'ensemble des puissances du pool d'options - nous appelons ce jeu le jeu de sélection de sous-ensembles. Nous présentons ensuite un algorithme évolutionnaire pour résoudre un tel jeu. Des résultats empiriques sur de petits matchs de µRTSmontrent que notre approche évolutionnaire est capable de converger vers un équilibre de Nash pour le jeu de sélection de sous-ensembles. De plus, les résultats sur des matchs plus importants montrent que les algorithmes de recherche utilisant des abstractions d'action dérivées de notre approche évolutionnaire sont capables de surpasser substantiellement tous les systèmes de planification de pointe testés.

Remerciements

Cette recherche a été partiellement soutenue par CNPq, Capes, et FAPEMIG. La recherche a été réalisée en utilisant les ressources informatiques du Centre de sciences mathématiques appliquées à l'industrie (CeMEAI) financé par la FAPESP (subvention 2013/07375-0), et le cluster Jupiter de l'Universidade Federal de Vic¸osa. Nous remercions les réviseurs anonymes pour leurs excellentes suggestions.