Publications

Sorted by DateClassified by Publication TypeClassified by Research Category

Heuristic Search of Multiagent Influence Space

Frans A. Oliehoek, Stefan Witwicki, and Leslie P. Kaelbling. Heuristic Search of Multiagent Influence Space. In Proceedings of the 9th European Workshop on Multi-agent Systems (EUMAS 2011), 2011.

Download

pdf [4.4MB]  

Abstract

Two techniques have substantially advanced efficiency and scalability of multiagent planning. First, heuristic search gains traction by pruning large portions of the joint policy space. Second, influence- based abstraction reformulates the search space of joint policies into a smaller space of influences, which represent the probabilistic effects that agents' policies may exert on one another. These techniques have been used independently, but never together, to solve solve larger problems (for Dec-POMDPs and subclasses) than was previously possible. In this paper, we combine multiagent A* search and influence-based abstraction into a single algorithm. This enables an initial investigation into whether the two techniques bring complementary gains. Our results indicate that A* can provide significant computational savings on top of those already afforded by influence-space search, thereby bringing a significant contri- bution to the field of multiagent planning under uncertainty.

BibTeX Entry

@inproceedings{Oliehoek11EUMAS,
    title =     {Heuristic Search of Multiagent Influence Space},
    author =    {Frans A. Oliehoek and Stefan Witwicki and Leslie P. Kaelbling},
    booktitle = EUMAS11,
    year =      {2011},
    keywords =  {workshop},
    abstract = 	 {
    Two techniques have substantially advanced efficiency and
    scalability of multiagent planning. First, heuristic search gains traction
    by pruning large portions of the joint policy space. Second, influence-
    based abstraction reformulates the search space of joint policies into a
    smaller space of influences, which represent the probabilistic effects that
    agents' policies may exert on one another. These techniques have been
    used independently, but never together, to solve solve larger problems
    (for Dec-POMDPs and subclasses) than was previously possible. In this
    paper, we combine multiagent A* search and influence-based abstraction
    into a single algorithm. This enables an initial investigation into whether
    the two techniques bring complementary gains. Our results indicate that
    A* can provide significant computational savings on top of those already
    afforded by influence-space search, thereby bringing a significant contri-
    bution to the field of multiagent planning under uncertainty.
    }
}

Generated by bib2html.pl (written by Patrick Riley) on Wed Nov 07, 2018 15:16:44 UTC