Publications

Sorted by DateClassified by Publication TypeClassified by Research Category

Dec-POMDPs with delayed communication

Frans A. Oliehoek, Matthijs T. J. Spaan, and Nikos Vlassis. Dec-POMDPs with delayed communication. In Proceedings of the Second AAMAS Workshop on Multi-Agent Sequential Decision Making in Uncertain Domains (MSDM), May 2007.

Download

pdf [146.0kB]  ps.gz [107.9kB]  

Abstract

In this work we consider the problem of multiagent planning under sensing and acting uncertainty with a one time-step delay in communication. We adopt decentralized partially observable Markov processes (Dec-POMDPs) as our planning framework. When instantaneous and noise-free communication is available, agents can instantly share local observations. This effectively reduces the decentralized planning problem to a centralized one, with a significant decrease in planning complexity. However, instantaneous communication is a strong assumption, as it requires the agents to synchronize at every time step. Therefore, we explore planning in Dec-POMDP settings in which communication is delayed by one time step. We show that such situations can be modeled by Bayesian games in which the types of the agents are defined by their last private observation. We will apply Bayesian games to define a value function $\QBG$ on the joint belief space, and we will show that it is the optimal payoff function for our Dec-POMDP setting with one time-step delayed communication. The $\QBG$-value function is piecewise linear and convex over the joint belief space, which we will use to define $\QBG$-value iteration. Finally, we will adapt Perseus, an approximate POMDP solver, to compute $\QBG$-value functions, and we will use it to perform some proof-of-concept experiments.

BibTeX Entry

@InProceedings{Oliehoek07MSDM,
    author =       {Frans A. Oliehoek and Matthijs T. J. Spaan and Nikos
                    Vlassis},
    title =        {{Dec-POMDPs} with delayed communication},
    booktitle =    MSDM07,
    year =         2007,
    month =        may,
    keywords =  {workshop},
    abstract = {
    In this work we consider the problem of multiagent planning under
    sensing and acting uncertainty with a one time-step delay in
    communication. We adopt decentralized partially observable Markov
    processes (Dec-POMDPs) as our planning framework. When instantaneous
    and noise-free communication is available, agents can instantly
    share local observations. This effectively reduces the decentralized
    planning problem to a centralized one, with a significant decrease
    in planning complexity.  However, instantaneous communication is a
    strong assumption, as it requires the agents to synchronize at every
    time step. Therefore, we explore planning in Dec-POMDP settings in
    which communication is delayed by one time step. We show that such
    situations can be modeled by Bayesian games in which the types of the
    agents are defined by their last private observation. We will apply
    Bayesian games to define a value function $\QBG$ on the joint belief
    space, and we will show that it is the optimal payoff function for
    our Dec-POMDP setting with one time-step delayed communication. The
    $\QBG$-value function is piecewise linear and convex over the joint
    belief space, which we will use to define $\QBG$-value iteration.
    Finally, we will adapt Perseus, an approximate POMDP solver, to compute
    $\QBG$-value functions, and we will use it to perform some
    proof-of-concept experiments.
  }
}

Generated by bib2html.pl (written by Patrick Riley) on Mon Feb 12, 2024 16:22:35 UTC