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.
[Please see the extended version for proofs.]

Download

pdf [2.7MB]  

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.

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 Tue Nov 05, 2024 16:13:37 UTC