HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

A Heuristic Approach for Solving Decentralized-POMDP : Assessment on the Pursuit Problem

Iadine Chadès 1 Bruno Scherrer 1 François Charpillet 1
1 MAIA - Autonomous intelligent machine
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Defining the behaviour of a set of situated agents, such that a collaborative problem can be solved is a key issue in multi-agent systems. In this paper, we formulate this problem from the decision theoretic perspective using the framework of Decentralized Partially Observable Markov Decision Processes (DEC-POMDP). Formulating the coordination problem in this way provides a formal foundation for study of cooperation activities. But, as it has been recently shown solving DEC-POMDP is NEXP-complete and thus it is not a realistic approach for the design of agent cooperation policies. However, we demonstrate in this paper that it is not completely desperate. Indeed, we propose an heuristic approach for solving DEC-POMDP when agents are memoryless and when the global reward function can be broken up into a sum of local reward functions. We demonstrate experimentally on an example (the so-called pursuit problem) that this heuristic is efficient within a few iteration steps.
Document type :
Conference papers
Complete list of metadata

Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 2:50:06 PM
Last modification on : Wednesday, February 2, 2022 - 3:51:34 PM


  • HAL Id : inria-00100729, version 1



Iadine Chadès, Bruno Scherrer, François Charpillet. A Heuristic Approach for Solving Decentralized-POMDP : Assessment on the Pursuit Problem. ACM Symposium on Applied Computing - SAC'2002, Mar 2002, Madrid, Spain, 6 p. ⟨inria-00100729⟩



Record views