Publications

| Sorted by Date | Classified by Publication Type | Classified by Research Category |

Influence-Optimistic Local Values for Multiagent Planning --- Extended Version

Frans A. Oliehoek, Matthijs T. J. Spaan, and Stefan Witwicki. Influence-Optimistic Local Values for Multiagent Planning --- Extended Version. arXiv:1502.05443, 2015.

Download

pdf [483.4kB]  

Abstract

Recent years have seen the development of a number of methods for multiagent planning under uncertainty that scale to tens or even hundreds of agents. However, most of these methods either make restrictive assumptions on the problem domain, or provide approximate solutions without any guarantees on quality. To allow for meaningful benchmarking through measurable quality guarantees on a very general class of problems, this paper introduces a family of influence-optimistic upper bounds for factored Dec-POMDPs. Intuitively, we derive bounds on very large multiagent planning problems by subdividing them in sub-problems, and at each of these sub-problems making optimistic assumptions with respect to the influence that will be exerted by the rest of the system. We numerically compare the different upper bounds and demonstrate how, for the first time ever, we can achieve a non-trivial guarantee that the heuristic solution of problems with hundreds of agents is close to optimal. Furthermore, we provide evidence that the upper bounds may improve the effectiveness of heuristic influence search, and discuss further potential applications to multiagent planning.

BibTeX Entry

@Misc{Oliehoek15arxiv,
  author =       {Frans A. Oliehoek and Matthijs T. J. Spaan and
                  Stefan Witwicki},
  title =        {Influence-Optimistic Local Values for Multiagent
                  Planning --- Extended Version},
  howpublished = {arXiv:1502.05443},
  year =         2015
}

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 bib2html.pl (written by Patrick Riley) on Thu Feb 29, 2024 16:15:45 UTC