Skip to Main content Skip to Navigation
Conference papers

Solving Infinite Horizon DEC-POMDPs by Best-First Search

Daniel Szer 1 François Charpillet 1
1 MAIA - Autonomous intelligent machine
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We present a first search algorithm for solving decentralized partially-observable Markov decision problems (DEC-POMDPs) with infinite horizon. The algorithm is suitable for computing optimal controllers for a cooperative group of agents that operate in a stochastic environment such as multi-robot coordination or network traffic control. Solving such problems effectively is a major challenge in the area of planning under uncertainty. Our solution is based on a synthesis of classical best-first search techniques and decentralized control theory. We believe it to be the first optimal search algorithm for this kind of problems, and we present some experimental results on a simple multi-agent coordination task.
Complete list of metadata
Contributor : Daniel Szer <>
Submitted on : Monday, September 12, 2005 - 10:04:00 AM
Last modification on : Friday, February 26, 2021 - 3:28:04 PM


  • HAL Id : inria-00000203, version 1



Daniel Szer, François Charpillet. Solving Infinite Horizon DEC-POMDPs by Best-First Search. 8th Biennial Israeli Symposium on the Foundations of AI - BISFAI -05, Jun 2005, Haifa/Israel. ⟨inria-00000203⟩



Record views