Publications

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

Heuristic Search of Multiagent Influence Space

Stefan Witwicki, Frans A. Oliehoek, and Leslie P. Kaelbling. Heuristic Search of Multiagent Influence Space. In Proceedings of the Eleventh International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 973–981, June 2012.

Download

pdf [583.5kB]  

Abstract

Multiagent planning under uncertainty has seen important progress in recent years. Two techniques, in particular, have substantially advanced efficiency and scalability of planning. Multiagent heuristic search gains traction by pruning large portions of the joint policy space deemed suboptimal by heuristic bounds. Alternatively, 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 take the logical albeit nontrivial next step of combining multiagent A* search and influence-based abstraction into a single algorithm. The mathematical foundation that we provide, such as partially-specified influence evaluation and admissible heuristic definition, enables an investigation into whether the two techniques bring complementary gains. Our empirical results indicate that A* can provide significant computational savings on top of those already afforded by influence-space search, thereby bringing a significant contribution to the field of multiagent planning under uncertainty.

BibTeX Entry

@InProceedings{Witwicki12AAMAS,
    author =    {Stefan Witwicki and
                 Frans A. Oliehoek and 
                 Leslie P. Kaelbling},
    title =     {Heuristic Search of Multiagent Influence Space},
    booktitle = AAMAS12,
    month =     jun,
    year =      2012,
    pages =     {973--981},
    url =       {www.ifaamas.org/Proceedings/aamas2012/papers/1F_2.pdf},
    abstract = 	 {
        Multiagent planning under uncertainty has seen important progress in
        recent years.  Two techniques, in particular, have substantially
        advanced efficiency and scalability of planning. Multiagent heuristic
        search gains traction by pruning large portions of the joint policy
        space deemed suboptimal by heuristic bounds.  Alternatively,
        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 take the logical albeit
        nontrivial next step of combining multiagent A* search and
        influence-based abstraction into a single algorithm.  The mathematical
        foundation that we provide, such as partially-specified influence
        evaluation and admissible heuristic definition, enables an
        investigation into whether the two techniques bring complementary
        gains. Our empirical results indicate that A* can provide significant
        computational savings on top of those already afforded by
        influence-space search, thereby bringing a significant contribution to
        the field of multiagent planning under uncertainty.
    }
}

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