Publications

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

Tree-Based Solution Methods for Multiagent POMDPs with Delayed Communication

Frans A. Oliehoek and Matthijs T. J. Spaan. Tree-Based Solution Methods for Multiagent POMDPs with Delayed Communication. In Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence (AAAI), pp. 1415–1421, July 2012.

Download

pdf [145.0kB]  

Abstract

Multiagent Partially Observable Markov Decision Processes (MPOMDPs) provide a powerful framework for optimal decision making under the assumption of instantaneous communication. We focus on a delayed communication setting (MPOMDP-DC), in which broadcasted information is delayed by at most one time step. This model allows agents to act on their most recent (private) observation. Such an assumption is a strict generalization over having agents wait until the global information is available and is more appropriate for applications in which response time is critical. In this setting, however, value function backups are significantly more costly, and naive application of incremental pruning, the core of many state-of-the-art optimal POMDP techniques, is intractable. In this paper, we overcome this problem by demonstrating that computation of the MPOMDP-DC backup can be structured as a tree and introducing two novel tree-based pruning techniques that exploit this structure in an effective way. We experimentally show that these methods have the potential to outperform naive incremental pruning by orders of magnitude, allowing for the solution of larger problems.

BibTeX Entry

@InProceedings{Oliehoek12AAAI_TBP,
    author =    {Frans A. Oliehoek and 
                 Matthijs T. J. Spaan},
    title =     {Tree-Based Solution Methods for Multiagent {POMDPs}
                 with Delayed Communication},
    booktitle = AAAI12,
    month =     jul,
    year =      2012,
    pages =     {1415--1421},
    url =       {https://www.aaai.org/ocs/index.php/AAAI/AAAI12/paper/view/5066},
    abstract = 	 {
        Multiagent Partially Observable Markov Decision Processes
        (MPOMDPs) provide a powerful framework for optimal decision
        making under the assumption of instantaneous communication.
        We focus on a delayed communication setting (MPOMDP-DC), in
        which broadcasted information is delayed by at most one time
        step. This model allows agents to act on their most recent
        (private) observation. Such an assumption is a strict
        generalization over having agents wait until the global
        information is available and is more appropriate for
        applications in which response time is critical.  In this
        setting, however, value function backups are significantly
        more costly, and naive application of incremental pruning, the
        core of many state-of-the-art optimal POMDP techniques, is
        intractable.  In this paper, we  overcome this problem by
        demonstrating that computation of the MPOMDP-DC backup can be
        structured as a tree and introducing two novel tree-based
        pruning techniques that exploit this structure in an effective
        way. We experimentally show that these methods have the
        potential to outperform naive incremental pruning by orders of
        magnitude, allowing for the solution of larger problems.
    }
}

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