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.
https://hal.inria.fr/inria-00000203
Contributor : Daniel Szer <>
Submitted on : Monday, September 12, 2005 - 10:04:00 AM Last modification on : Friday, February 26, 2021 - 3:28:04 PM
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⟩