Publications

Sorted by DateClassified by Publication TypeClassified by Research Category

Variational Multi-Objective Coordination

Diederik M. Roijers, Shimon Whiteson, Alex Ihler, and Frans A. Oliehoek. Variational Multi-Objective Coordination. In NIPS Workshop on Learning, Inference and Control of Multi-Agent Systems, December 2015.

Download

pdf [1.1MB]  

Abstract

In this paper, we propose variational optimistic linear support (VOLS), a novel algorithm that finds bounded approximate solutions for multi-objective coordination graphs (MO-CoGs). VOLS builds and improves upon an existing exact algorithm called variable elimination linear support (VELS). Like VELS, VOLS solves a MO-CoG as a series of scalarized single-objective coordination graphs. We improve upon VELS in two important ways. Firstly, where VELS uses a single-objective solver called variable elimination (VE) as a subroutine, VOLS uses a variational method called weighted mini-buckets (WMB). Because variational methods scale much better than VE, VOLS can be used to solve much larger MO-CoGs than was previously possible. Furthermore, we show that because WMB computes bounded approximations, so does VOLS. Secondly, we leverage the insight that VOLS can hot-start each call to WMB by reusing the reparameterizations output by WMB on earlier calls. We show empirically that VOLS scales much better than VELS and introduces only negligle error. Our experimental results indicate that the reuse of reparameterizations keeps the runtime low and the approximation quality high.

BibTeX Entry

@inproceedings{Roijers15LICMAS,
    author =    {Diederik M.  Roijers and Shimon Whiteson and 
                 Alex Ihler and Frans A. Oliehoek},
    title =     {Variational Multi-Objective Coordination},
    booktitle = {NIPS Workshop on  Learning, Inference and Control of Multi-Agent Systems},
    year =      2015,
    month =     dec,
    keywords =  {workshop},
    abstract = {
    In this paper, we propose variational optimistic linear support (VOLS), a novel
    algorithm that finds bounded approximate solutions for multi-objective
    coordination graphs (MO-CoGs). VOLS builds and improves upon an existing
    exact algorithm called variable elimination linear support (VELS). Like
    VELS, VOLS solves a MO-CoG as a series of scalarized single-objective
    coordination graphs.  We improve upon VELS in two important ways. Firstly,
    where VELS uses a single-objective solver called variable elimination (VE) as a
    subroutine, VOLS uses a variational method called weighted mini-buckets
    (WMB). Because variational methods scale much better than VE, VOLS can be
    used to solve much larger MO-CoGs than was previously possible.
    Furthermore, we show that because WMB computes bounded approximations, so
    does VOLS. Secondly, we leverage the insight that VOLS can hot-start each
    call to WMB by reusing the reparameterizations output by WMB on earlier
    calls. We show empirically that VOLS scales much better than VELS and
    introduces only negligle error. Our experimental results indicate that the
    reuse of reparameterizations keeps the runtime low and the approximation
    quality high.
    }
}

Generated by bib2html.pl (written by Patrick Riley) on Mon Oct 07, 2024 14:17:04 UTC