Publications

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

Computing Convex Coverage Sets for Multi-Objective Coordination Graphs

Diederik M. Roijers, Shimon Whiteson, and Frans A. Oliehoek. Computing Convex Coverage Sets for Multi-Objective Coordination Graphs. In Proceedings of the Third International Conference on Algorithmic Decision Theory (ADT), pp. 309–323, November 2013.

Download

pdf [1.2MB]  ps.gz ps HTML 

Abstract

Many real-world decision problems require making trade-offs between multiple objectives. However, in some cases, the relative importance of the objectives is not known when the problem is solved, precluding the use of single-objective methods. Instead, multi-objective methods, which compute the set of all potentially useful solutions, are required. This paper proposes new multi-objective algorithms for cooperative multi-agent settings. Following previous approaches, we exploit loose couplings, as expressed in graphical models, to coordinate efficiently. Existing methods, however, calculate only the Pareto coverage set (PCS), which we argue is inappropriate for stochastic strategies and unnecessarily large when the objectives are weighted in a linear fashion. In these cases, the typically much smaller convex coverage set (CCS) should be computed instead. A key insight of this paper is that, while computing the CCS is more expensive in unstructured problems, in many loosely coupled settings it is in fact cheaper to compute because the local solutions are more compact. We propose convex multi-objective variable elimination, which exploits this insight. We analyze its correctness and complexity and demonstrate empirically that it scales much better in the number of agents and objectives than alternatives that compute the PCS.

BibTeX Entry

@InProceedings{Roijers13ADT,
    author =    {Diederik M. Roijers and Shimon Whiteson and Frans A. Oliehoek},
    title =     {Computing Convex Coverage Sets for Multi-Objective Coordination Graphs},
    booktitle = ADT13,
    month =     nov,
    pages =     {309--323}, 
    note =      {},
    year =      2013,
    doi =       {10.1007/978-3-642-41575-3\_24},
    abstract = {
    Many real-world decision problems require making trade-offs between
    multiple objectives. However, in some cases, the relative
    importance of the objectives is not known when the problem is
    solved, precluding the use of single-objective methods. Instead,
    multi-objective methods, which compute the set of all potentially
    useful solutions, are required. This paper proposes new
    multi-objective algorithms for cooperative multi-agent settings.
    Following previous approaches, we exploit loose couplings, as
    expressed in graphical models, to coordinate efficiently. Existing
    methods, however, calculate only the Pareto coverage set (PCS),
    which we argue is inappropriate for stochastic strategies and
    unnecessarily large when the objectives are weighted in a linear
    fashion. In these cases, the typically much smaller convex
    coverage set (CCS) should be computed instead.  A key insight of
    this paper is that, while computing the CCS is more expensive in
    unstructured problems, in many loosely coupled settings it is in
    fact cheaper to compute because the local solutions are more
    compact. We propose convex multi-objective variable elimination,
    which exploits this insight. We analyze its correctness and complexity
    and demonstrate empirically that it scales much better in the
    number of agents and objectives than alternatives that compute the
    PCS.
    }
}

Generated by bib2html.pl (written by Patrick Riley) on Mon Apr 08, 2024 20:28:07 UTC