Publications

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

Tree-based Pruning for Multiagent POMDPs with Delayed Communication

Frans A. Oliehoek and Matthijs T. J. Spaan. Tree-based Pruning for Multiagent POMDPs with Delayed Communication. In Proceedings of the Eleventh International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 1229–1230, June 2012.
Extended abstract.

Download

pdf [95.6kB]  

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. Such an assumption is in fact more appropriate for applications in which response time is critical. From a technical point of view, MPOMDP-DCs are quite similar to MPOMDPs. However, value function backups are significantly more costly, and naive application of incremental pruning, the core of many state-of-the-art POMDP techniques, is intractable. In this paper, we show how to 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 tree 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{Oliehoek12AAMAS,
    author =    {Frans A. Oliehoek and 
                Matthijs T. J. Spaan},
    title =     {Tree-based Pruning for Multiagent {POMDPs}
                with Delayed Communication},
    booktitle = AAMAS12,
    month =     jun,
    year =      2012,
    pages =     {1229--1230},
    wwwnote =     {Extended abstract.},
    url =       {www.ifaamas.org/Proceedings/aamas2012/papers/Z1_5.pdf},
    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. Such an assumption is in fact more appropriate for applications
    in which response time is critical. From a technical point of view,
    MPOMDP-DCs are quite similar to MPOMDPs. However, value function backups
    are significantly more costly, and naive application of incremental
    pruning, the core of many state-of-the-art POMDP techniques, is
    intractable. In this paper, we show how to 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 tree 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