Jump to content

Decentralized partially observable Markov decision process

From Wikipedia, the free encyclopedia

The decentralized partially observable Markov decision process (Dec-POMDP)[1][2] is a model for coordination and decision-making among multiple agents. It is a probabilistic model that can consider uncertainty in outcomes, sensors and communication (i.e., costly, delayed, noisy or nonexistent communication).

It is a generalization of a Markov decision process (MDP) and a partially observable Markov decision process (POMDP) to consider multiple decentralized agents.[3]

Definition

[edit]

Formal definition

[edit]

A Dec-POMDP is a 7-tuple , where

  • is a set of states,
  • is a set of actions for agent , with is the set of joint actions,
  • is a set of conditional transition probabilities between states, ,
  • is the reward function.
  • is a set of observations for agent , with is the set of joint observations,
  • is a set of conditional observation probabilities , and
  • is the discount factor.

At each time step, each agent takes an action , the state updates based on the transition function (using the current state and the joint action), each agent observes an observation based on the observation function (using the next state and the joint action) and a reward is generated for the whole team based on the reward function . The goal is to maximize expected cumulative reward over a finite or infinite number of steps. These time steps repeat until some given horizon (called finite horizon) or forever (called infinite horizon). The discount factor maintains a finite sum in the infinite-horizon case ().

References

[edit]
  1. ^ Bernstein, Daniel S.; Givan, Robert; Immerman, Neil; Zilberstein, Shlomo (November 2002). "The Complexity of Decentralized Control of Markov Decision Processes". Mathematics of Operations Research. 27 (4): 819–840. arXiv:1301.3836. doi:10.1287/moor.27.4.819.297. ISSN 0364-765X. S2CID 1195261.
  2. ^ Oliehoek, Frans A.; Amato, Christopher (2016). A Concise Introduction to Decentralized POMDPs | SpringerLink (PDF). SpringerBriefs in Intelligent Systems. doi:10.1007/978-3-319-28929-8. ISBN 978-3-319-28927-4. S2CID 3263887.
  3. ^ Oliehoek, Frans A.; Amato, Christopher (2016-06-03). A Concise Introduction to Decentralized POMDPs. Springer. ISBN 978-3-319-28929-8.
[edit]