Skip to Main content Skip to Navigation
Journal articles

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
Document type :
Journal articles
Complete list of metadata
https://hal.inria.fr/inria-00119482
Contributor : François Charpillet <>
Submitted on : Saturday, December 9, 2006 - 11:47:48 PM
Last modification on : Friday, February 26, 2021 - 3:28:04 PM

Identifiers

  • HAL Id : inria-00119482, version 1

Collections

INRIA | CNRS | 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⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

221

 

Contact                    Legal Notice                    Personal Data