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 e-prints, arXiv:1502.05443, February 2015.

Download

pdf [686.9kB]  

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

@article{Oliehoek15arxiv_UBs,
    author =    {Frans A. Oliehoek 
                 and Matthijs T. J. Spaan 
                 and Stefan Witwicki},
    title =     {Influence-Optimistic Local Values for 
                 Multiagent Planning --- Extended Version},
    journal =   {ArXiv e-prints},
    volume =    {arXiv:1502.05443},
    year =      2015,
    month =     feb,
    archivePrefix = "arXiv",
    eprint =    {1502.05443},
    primaryClass = "cs.AI",
    keywords =   {nonrefereed, arxiv},
    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.        
    }
}

Generated by bib2html.pl (written by Patrick Riley) on Tue Nov 05, 2024 16:13:37 UTC