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