Name
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 epsilon-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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1613/jair.4550 | JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH |
Field | DocType | Volume |
Correctness,Theoretical computer science,Artificial intelligence,Graph,Mathematical optimization,Variable elimination,Weight,Regular polygon,Solution set,Machine learning,Mathematics,Pareto principle,Scalability | Journal | 52 |
Issue | ISSN | Citations |
1 | 1076-9757 | 10 |
PageRank | References | Authors |
0.51 | 27 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Diederik Marijn Roijers | 1 | 22 | 1.79 |
| Shimon Whiteson | 2 | 1460 | 99.00 |
| Frans A. Oliehoek | 3 | 397 | 40.32 |