Computing Convex Coverage Sets for Multi-objective Coordination Graphs
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, mu
- PDF / 854,701 Bytes
- 15 Pages / 439.363 x 666.131 pts Page_size
- 88 Downloads / 184 Views
2
Informatics Institute, University of Amsterdam, The Netherlands {d.m.roijers,s.a.whiteson}@uva.nl Dept. of Knowledge Engineering, Maastricht University, The Netherlands [email protected]
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 singleobjective methods. Instead, multi-objective methods, which compute the set of all potentially useful solutions, are required. This paper proposes new multiobjective 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. Keywords: Multi-agent systems, Multi-objective optimization, Game theory, Coordination graphs.
1 Introduction In cooperative multi-agent systems, agents must coordinate their behavior in order to maximize their common utility. Key to making coordination efficient is exploiting the loose couplings common to such tasks: each agent’s actions directly affect only a subset of the other agents. Such independence can be captured in a graphical model called a coordination graph, and exploited using methods such as variable elimination [8,9]. This paper considers how to address cooperative multi-agent systems in which the agents have multiple objectives, i.e., the utility is vector-valued. Many real-world problems have multiple objectives, e.g., maximizing performance of a computer network while minimizing power consumption [16]. The presence of multiple objectives does not in itself necessitate special solution methods. In many cases, the vector-valued utility function can be scalarized, i.e., converted to a scalar function. Subsequently, the original problem may be solvable with existing single-objective methods. However, this approach is not applicable when the P. Perny, M. Pirlot, and A. Tsouki`as (Eds.): ADT 2013, LNAI 8176, pp. 309–323, 2013. c Springer-Verlag Berlin Heidelberg 2013
310
D.M. Roijers, S. Whiteson, and F.A. Oliehoek
parameters of the scalarization are not known in advance. For example, consider a company that produces different resources whose market prices vary.
Data Loading...
