Recherche heuristique pour jeux stochastiques (à somme nulle) - Archive ouverte HAL Access content directly
Conference Papers Year :

Recherche heuristique pour jeux stochastiques (à somme nulle)

(1, 2) , (3) , (4) , (1)
1
2
3
4

Abstract

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.
Fichier principal
Vignette du fichier
JFPDA_2018_paper_3.pdf (271.18 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01840591 , version 1 (16-07-2018)

Identifiers

  • HAL Id : hal-01840591 , version 1

Cite

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⟩
180 View
153 Download

Share

Gmail Facebook Twitter LinkedIn More