Résolution optimale de DEC-POMDPs par recherche heuristique

Daniel Szer 1 François Charpillet 1 Shlomo Zilberstein
1 MAIA - Autonomous intelligent machine
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : RÉSUMÉ Nous présentons le premier formalisme de recherche heuristique permettant de résoudre les POMDPs décentralisés (DEC-POMDP). Notre algorithme peut être utilisé pour calculer des plans optimaux dans des domaines comme la multirobotique ou les réseaux de communication, et ceci à horizon fini comme à horizon infini. Nous présentons ici une nouvelle classe d'algorithmes qui fait le lien entre les méthodes de recherche heuristique classiques et la théorie du contrôle décentralisé. Nous prouvons l'optimalité de ce formalisme dans le cadre des politiques déterministes, et nous évaluons sa performance sur quelques exemples d'applications répandus dans le domaine du contrôle décentralisé. ABSTRACT We present the first generalized heuristic search formalism that is able to solve decentralized POMDPs of both finite and infinite horizon. Our algorithm is suitable for computing optimal plans for a cooperative group of agents that operate in a stochastic environment. These problems arise in domains such as multi-robot coordination, or network traffic control. We present a framework that is based on classical heuristic search on the one hand, and on decentralized control theory on the other hand. We prove that our approach is able to generate optimal deterministic controllers, and we study its performance on examples from the literature.
keyword : planning decentralized control Markov Decision Processes DEC-POMDP
Type de document :
Article dans une revue
Revue des Sciences et Technologies de l'Information - Série RIA : Revue d'Intelligence Artificielle, Lavoisier, 2007, Prise de décision séquentielle, 21 (1), pp. 107-128
Liste complète des métadonnées
https://hal.inria.fr/inria-00119482
Contributeur : François Charpillet <>
Soumis le : samedi 9 décembre 2006 - 23:47:48
Dernière modification le : jeudi 11 janvier 2018 - 06:19:50

Identifiants

  • HAL Id : inria-00119482, version 1

Collections

INRIA | LORIA | UNIV-LORRAINE

Citation

Daniel Szer, François Charpillet, Shlomo Zilberstein. Résolution optimale de DEC-POMDPs par recherche heuristique. Revue des Sciences et Technologies de l'Information - Série RIA : Revue d'Intelligence Artificielle, Lavoisier, 2007, Prise de décision séquentielle, 21 (1), pp. 107-128. 〈inria-00119482〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

180

Contact


archive-ouverte@inria.fr