Multiagent Planning under Uncertainty with Stochastic Communication Delays

Matthijs T. J. Spaan, Frans A. Oliehoek, and Nikos Vlassis. Multiagent Planning under Uncertainty with Stochastic Communication Delays. In Proc. of Int. Conf. on Automated Planning and Scheduling, pp. 338–345, 2008.


pdf [141.2kB]  


We consider the problem of cooperative multiagent planning under uncertainty, formalized as a decentralized partially observable Markov decision process (Dec-POMDP). Unfortunately, in these models optimal planning is provably intractable. By communicating their local observations before they take actions, agents synchronize their knowledge of the environment, and the planning problem reduces to a centralized POMDP. As such, relying on communication significantly reduces the complexity of planning. In the real world however, such communication might fail temporarily. We present a step towards more realistic communication models for Dec-POMDPs by proposing a model that: (1) allows that communication might be delayed by one or more time steps, and (2) explicitly considers future probabilities of successful communication. For our model, we discuss how to efficiently compute an (approximate) value function and corresponding policies, and we demonstrate our theoretical results with encouraging experiments.

BibTeX Entry

  author =       {Matthijs T. J. Spaan and Frans A. Oliehoek and Nikos
  title =        {Multiagent Planning under Uncertainty with
                  Stochastic Communication Delays},
  booktitle =    {Proc. of Int. Conf. on Automated Planning and
  year =         2008,
  pages =        {338--345}

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

Generated by (written by Patrick Riley) on Tue Sep 06, 2011 11:22:28 UTC