Publications• Sorted by Date • Classified by Publication Type • Classified by Research Category • Computing Convex Coverage Sets for Multi-Objective Coordination GraphsDiederik 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. DownloadAbstractMany 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 Oct 07, 2024 14:17:04 UTC |