Scaling Up Decentralized MDPs Through Heuristic Search

Jilles Steeve Dibangoye 1, * Amato Christopher 2 Doniec Arnaud 3
* Auteur correspondant
1 MAIA - Autonomous intelligent machine
Inria Nancy - Grand Est, LORIA - AIS - Department of Complex Systems, Artificial Intelligence & Robotics
Résumé : Les processus décisionnels de Markov répartis constituent un formalisme très riche pour la modélisation des systèmes coopératifs, mais leur complexité reste hors de portée (NEXP-complet). Le formalisme des Dec-MDPs avec transitions et observations indépendantes est une sous classe dont la complexité est NP, mais les algorithmes exacts pour cette classe restent ineficaces. Dans ce papier, nous offrons une nouvelle preuve de l'optimalité des politiques de Markov pour ce formalisme. Puis, nous présentons un nouvel algorithme de recherche heuristique capable explorer l'espace de recherche sur la base des techniques d'optimisation sous contraintes. Nous démontrons enfin que l'algorithme ainsi construit offre les meilleurs performances sur l'ensemble des instances testées.
Type de document :
Communication dans un congrès
Conference on Uncertainty in Artificial Intelligence, Aug 2012, Catalina, United States. 2012
Liste complète des métadonnées

https://hal.inria.fr/hal-00765221
Contributeur : Jilles Steeve Dibangoye <>
Soumis le : vendredi 14 décembre 2012 - 12:20:04
Dernière modification le : jeudi 12 avril 2018 - 16:25:34

Identifiants

  • HAL Id : hal-00765221, version 1

Citation

Jilles Steeve Dibangoye, Amato Christopher, Doniec Arnaud. Scaling Up Decentralized MDPs Through Heuristic Search. Conference on Uncertainty in Artificial Intelligence, Aug 2012, Catalina, United States. 2012. 〈hal-00765221〉

Partager

Métriques

Consultations de la notice

202