Publications

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

Computing Convex Coverage Sets for Faster Multi-Objective Coordination

Diederik M. Roijers, Shimon Whiteson, and Frans A. Oliehoek. Computing Convex Coverage Sets for Faster Multi-Objective Coordination. Journal of Artificial Intelligence Research, 52:399–443, AI Access Foundation, Inc., March 2015.

Download

pdf [951.4kB]  ps.gz ps HTML 

Abstract

In this article, we propose new algorithms for multi-objective coordination graphs (MO- CoGs). Key to the efficiency of these algorithms is that they compute a convex coverage set (CCS) instead of a Pareto coverage set (PCS). Not only is a CCS a sufficient solution set for a large class of problems, it also has important characteristics that facilitate more efficient solutions. We propose two main algorithms for computing a CCS in MO-CoGs. Convex multi-objective variable elimination (CMOVE) computes a CCS by performing a series of agent eliminations, which can be seen as solving a series of local multi-objective subproblems. Variable elimination linear support (VELS) iteratively identifies the single weight vector w that can lead to the maximal possible improvement on a partial CCS and calls variable elimination to solve a scalarized instance of the problem for w. VELS is faster than CMOVE for small and medium numbers of objectives and can compute an ε-approximate CCS in a fraction of the runtime. In addition, we propose variants of these methods that employ AND/OR tree search instead of variable elimination to achieve memory efficiency. We analyze the runtime and space complexities of these methods, prove their correctness, and compare them empirically against a naive baseline and an existing PCS method, both in terms of memory-usage and runtime. Our results show that, by focusing on the CCS, these methods achieve much better scalability in the number of agents than the current state of the art.

BibTeX Entry

@article{Roijers15JAIR,
    author =    {Diederik M. Roijers and Shimon Whiteson and Frans A. Oliehoek},
    title =     {Computing Convex Coverage Sets for Faster Multi-Objective Coordination},
    journal =   JAIR,
    year =      2015,
    month =     mar,
    volume =    52,
    pages =     {399--443},
    DOI =       {10.1613/jair.4550},
    publisher = {AI Access Foundation, Inc.},
    abstract =  {
    In this article, we propose new algorithms for multi-objective
    coordination graphs (MO- CoGs). Key to the efficiency of these
    algorithms is that they compute a convex coverage set (CCS) instead of
    a Pareto coverage set (PCS). Not only is a CCS a sufficient solution
    set for a large class of problems, it also has important
    characteristics that facilitate more efficient solutions. We propose
    two main algorithms for computing a CCS in MO-CoGs.  Convex
    multi-objective variable elimination (CMOVE) computes a CCS by
    performing a series of agent eliminations, which can be seen as
    solving a series of local multi-objective subproblems. Variable
    elimination linear support (VELS) iteratively identifies the single
    weight vector w that can lead to the maximal possible improvement on a
    partial CCS and calls variable elimination to solve a scalarized
    instance of the problem for w. VELS is faster than CMOVE for small and
    medium numbers of objectives and can compute an ε-approximate CCS in a
    fraction of the runtime. In addition, we propose variants of these
    methods that employ AND/OR tree search instead of variable elimination
    to achieve memory efficiency. We analyze the runtime and space
    complexities of these methods, prove their correctness, and compare
    them empirically against a naive baseline and an existing PCS method,
    both in terms of memory-usage and runtime. Our results show that, by
    focusing on the CCS, these methods achieve much better scalability
    in the number of agents than the current state of the art.
    }        
}

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