Combining Myopic Optimization and Tree Search: Application to MineSweeper

Michèle Sebag 1, 2 Olivier Teytaud 1, 2
2 TAO - Machine Learning and Optimisation
CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique
Abstract : Many reactive planning tasks are tackled by optimization combined with shrinking horizon at each time step: the problem is sim- plified to a non-reactive (myopic) optimization problem, based on the available information at the current time step and an estimate of future behavior, then it is solved; and the simplified problem is updated at each time step thanks to new information. This is in particular suitable when fast off-the-shelf components are available for the simplified problem - optimality stricto sensu is not possible, but good results are obtained at a reasonnable computational cost for highly untractable problems. As machines get more powerful, it makes sense however to go beyond the inherent limitations of this approach. Yet, a brute-force solving of the complete problem is often impossible; we here propose a methodology for embedding a solver inside a consistent reactive planning solver. Our methodology consists in embedding the solver in an Upper- Confidence-Tree algorithm, both in the nodes and as a Monte-Carlo simulator. We show the mathematical consistency of the approach, and then we apply it to a classical success of the myopic approach: the MineSweeper game.
Type de document :
Communication dans un congrès
Youssef Hamadi and Marc Schoenauer. LION6, Learning and Intelligent Optimization, 2012, Paris, France. Sringer Verlag, 7219, pp.222-236, 2012, LNCS
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00712417
Contributeur : Olivier Teytaud <>
Soumis le : mardi 19 février 2013 - 16:34:48
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14
Document(s) archivé(s) le : lundi 20 mai 2013 - 04:04:30

Fichier

mines2.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00712417, version 2

Citation

Michèle Sebag, Olivier Teytaud. Combining Myopic Optimization and Tree Search: Application to MineSweeper. Youssef Hamadi and Marc Schoenauer. LION6, Learning and Intelligent Optimization, 2012, Paris, France. Sringer Verlag, 7219, pp.222-236, 2012, LNCS. 〈hal-00712417v2〉

Partager

Métriques

Consultations de la notice

706

Téléchargements de fichiers

340