Computing Convex Coverage Sets for Faster Multi-objective Coordination

Diederik Marijn Roijers, Shimon Whiteson, Frans A. OliehoekJAIR 2015 · DOI · OpenReview

TL;DR

This paper introduces new algorithms (CMOVE and VELS) for efficiently computing Convex Coverage Sets (CCSs) in multi-objective coordination problems. By focusing on CCSs instead of the more general Pareto Coverage Sets (PCSs), these methods achieve significantly better scalability in terms of agents and objectives, outperforming existing approaches.

What Problem Does This Paper Address?

Many real-world problems involve multiple agents that need to coordinate their actions to achieve several objectives simultaneously. Examples include optimizing network performance while minimizing power consumption, or managing traffic lights to maximize flow and minimize delays. These multi-objective coordination problems are often modeled as Multi-Objective Coordination Graphs (MO-CoGs). A key challenge is finding a set of "good" joint actions that can be selected from, especially when the relative importance of objectives (represented by weights) is not known in advance or can change. Traditional methods often compute Pareto Coverage Sets (PCSs), which can be computationally expensive. This paper addresses the need for more efficient methods to find a sufficient solution set, specifically by focusing on Convex Coverage Sets (CCSs), which are sufficient for linear scalarization functions and are often smaller than PCSs.

Methods

The paper proposes two main algorithms for computing CCSs:

  • Convex Multi-Objective Variable Elimination (CMOVE): This algorithm extends existing variable elimination techniques. Instead of computing local Pareto sets, it computes local Convex Coverage Sets (LCCSs) during agent elimination. This "inner loop" approach pushes pruning operations into the subproblems, leading to smaller intermediate sets and improved efficiency.
  • Variable Elimination Linear Support (VELS): This algorithm takes an "outer loop" approach. It iteratively identifies a single weight vector that offers the maximal possible improvement to a partial CCS. It then uses Variable Elimination (VE) as a subroutine to solve the resulting single-objective problem for that specific weight. VELS is an "anytime algorithm," meaning it can provide an approximate CCS (ε-CCS) in a fraction of the time, making it suitable for scenarios with limited computational budgets.

The authors also propose memory-efficient variants of these methods using AND/OR tree search instead of Variable Elimination.

Datasets

The authors evaluate their methods on:

  • Random MO-CoGs: These are generated with controllable parameters (number of agents, objectives, local payoff functions, action space size) to systematically analyze scalability.
  • Mining Day Benchmark: A more realistic, structured but still randomized benchmark inspired by a mining company scenario, involving agents (vans) coordinating to mine resources with fluctuating prices.
  • Mining Field: A variation of the Mining Day benchmark with a grid-based structure, designed to test memory efficiency under different induced widths.

Key Insights and Ideas

  • CCS is Sufficient and Smaller: For problems with linear scalarization functions, a CCS is sufficient to find optimal solutions for any set of weights. Crucially, CCSs are often significantly smaller than PCSs, leading to computational advantages.
  • Inner vs. Outer Loop for CCS: CMOVE uses an "inner loop" approach by computing LCCSs during agent elimination, while VELS uses an "outer loop" approach by iteratively finding optimal weights and solving single-objective subproblems. This difference leads to complementary strengths: CMOVE scales better with objectives, while VELS scales better with agents and offers anytime approximation.
  • Pruning is Key: The efficiency gains of CMOVE and VELS stem from effectively pruning dominated solutions at various stages, both locally (LCCSs) and globally.
  • Memory Efficiency Matters: For problems with limited memory, outer-loop methods like VELS and TSLS (an AND/OR tree search variant) offer significant advantages over inner-loop methods like CMOVE.

Key Results

  • Scalability: CMOVE and VELS demonstrate much better scalability in the number of agents and objectives compared to naive baselines and existing PCS methods.
  • CMOVE vs. VELS: CMOVE scales better with the number of objectives, while VELS scales better with the number of agents. VELS is also more memory-efficient.
  • VELS Approximation: VELS can compute an ε-CCS, achieving substantial speedups (e.g., a factor of 57 with 99% accuracy) by allowing a small error margin. For 110 agents, VELS with ε=0.01 was 109 times faster than CMOVE on a similar problem.
  • Memory Efficiency: TSLS, a memory-efficient variant, can handle significantly more agents than CMOVE and PMOVE under memory constraints.
  • Runtime Improvements: For example, in a 2-objective setting with 75 agents, basic CMOVE had a maximum runtime of 132s, while incremental CMOVE took 136s, and PMOVE timed out at 5000s.

Limitations and Future Work

  • Complexity: While the proposed methods are more efficient than prior art, their worst-case complexity can still be exponential in certain problem parameters (e.g., induced width for CMOVE, number of corner weights for VELS).
  • Future Work: The authors suggest exploring ε-approximate methods for MO-CoGs using LP-relaxation techniques, finding the optimal balance between approximation and runtime, and extending the work to sequential decision-making problems (e.g., multi-agent multi-objective MDPs). They also propose investigating inner/outer loop methods based on other single-objective algorithms.

Summary updated

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
@article{roijers2015computing,
  author = {Diederik Marijn Roijers and Shimon Whiteson and Frans A. Oliehoek},
  title = {{Computing Convex Coverage Sets for Faster Multi-objective Coordination}},
  journal = {J. Artif. Intell. Res.},
  year = {2015},
  doi = {10.1613/jair.4550},
}
Figure