Recherche heuristique pour jeux stochastiques (à somme nulle)

Olivier Buffet 1, 2 Jilles Dibangoye 3 Abdallah Saffidine 4 Vincent Thomas 1
1 LARSEN - Lifelong Autonomy and interaction skills for Robots in a Sensing ENvironment
Inria Nancy - Grand Est, LORIA - AIS - Department of Complex Systems, Artificial Intelligence & Robotics
3 CHROMA - Robots coopératifs et adaptés à la présence humaine en environnements dynamiques
CITI - CITI Centre of Innovation in Telecommunications and Integration of services, Inria Grenoble - Rhône-Alpes
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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [29 references]  Display  Hide  Download

https://hal.inria.fr/hal-01840591
Contributor : Olivier Buffet <>
Submitted on : Monday, July 16, 2018 - 3:04:11 PM
Last modification on : Tuesday, November 19, 2019 - 2:06:46 AM
Long-term archiving on: Wednesday, October 17, 2018 - 3:10:27 PM

File

JFPDA_2018_paper_3.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01840591, version 1

Citation

Olivier Buffet, Jilles 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⟩

Share

Metrics

Record views

238

Files downloads

86