Publications• Sorted by Date • Classified by Publication Type • Classified by Research Category • Influence-Optimistic Local Values for Multiagent Planning Frans A. Oliehoek, Matthijs T. J. Spaan, and Stefan Witwicki. Influence-Optimistic Local Values for Multiagent Planning. In Proceedings of the Tenth AAMAS Workshop on Multi-Agent Sequential Decision Making in Uncertain Domains (MSDM), May 2015. DownloadAbstractNowadays, methods for multiagent planning under uncertainty scale to tens or even hundreds of agents. However, most methods either make restrictive assumptions, 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. We derive bounds on very large multiagent planning problems by subdividing them in sub-problems, and 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 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@inproceedings{Oliehoek15MSDM, author = {Frans A. Oliehoek and Matthijs T. J. Spaan and Stefan Witwicki}, title = {Influence-Optimistic Local Values for Multiagent Planning}, wwwnote = {[Please see the <a href="b2hd-Oliehoek15arxiv_UBs.html">extended version</a> for proofs.]}, booktitle = MSDM15, year = 2015, month = may, keywords = {workshop}, abstract = { Nowadays, methods for multiagent planning under uncertainty scale to tens or even hundreds of agents. However, most methods either make restrictive assumptions, 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. We derive bounds on very large multiagent planning problems by subdividing them in sub-problems, and 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 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. } }
Generated by
bib2html.pl
(written by Patrick Riley) on
Mon Oct 07, 2024 14:17:04 UTC |