Recherche heuristique pour jeux stochastiques (à somme nulle)

Olivier Buffet (1, 2) , Jilles S Dibangoye (3) , Abdallah Saffidine (4) , Vincent Thomas (1)

1 LARSEN - Lifelong Autonomy and interaction skills for Robots in a Sensing ENvironment
2 LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
3 CHROMA - Robots coopératifs et adaptés à la présence humaine en environnements dynamiques
4 ANU - Australian National University

In various types of problems, such as sequential decision-making, heuristic search algorithms allow exploiting the knowledge of the initial situation and of an admissible heuristic to efficiently search for an optimal solution. Such algorithms exist including in case of uncertain dynamics, of partial observability, of multiple criteria, or of multiple collaborating agents. Here we propose a heuristic search algorithm for two-player zero-sum stochastic games with discounted criterion. This algorithm relies on HSVI—hence on generating trajectories. We demonstrate that, each player acting in an optimistic manner, and employing simple heuristic initializations, the resulting algorithm converges in finite time to an-optimal solution.

Dans divers types de problèmes, par exemple de prise de décision séquentielle, les algorithmes de recherche heuristique permettent d'exploiter la connaissance d'une situation initiale et d'une heuristique admissible pour rechercher efficacement une solution optimale. De tels algorithmes existent y compris en cas de dynamique incertaine, d'observabilité partielle, de critères multiples, ou d'agents multiples collaborant. Nous proposons ici un algorithme de recherche heuristique pour jeux stochastiques à deux joueurs et à somme nulle, et avec critère décompté, algorithme reposant sur HSVI—donc sur la génération de trajectoires. Nous démontrons que, chaque joueur agissant de manière optimiste, et en employant des initialisations heuristiques simples, l'algorithme obtenu converge vers une solution-optimale en temps fini.

Mots clés: Stochastic Games; Heuristic Search

Mots clés: Jeux stochastiques; HSVI; Recherche heuristique

Domaines: Intelligence artificielle [cs.AI]

Olivier Buffet, Jilles S Dibangoye, Abdallah Saffidine, Vincent Thomas. Recherche heuristique pour jeux stochastiques (à somme nulle). JFPDA 2018 - Journées Francophones sur la Planification, la Décision et l'Apprentissage pour la conduite de systèmes, Jul 2018, Nancy, France. pp.1-8. ⟨hal-01840591⟩