Roijers, Diederik M, Whiteson, Shimon and Oliehoek, Frans A 
ORCID: 0000-0003-4372-5055
(2014)
Linear Support for Multi-Objective Coordination Graphs.
.
![[img]](https://livrepository.liverpool.ac.uk/style/images/fileicons/text.png) |
Text
Roijers14AAMAS.pdf - Unspecified Download (519kB) |
Abstract
Many real-world decision problems require making tradeoffs among multiple objectives. However, in some cases, the relative importance of these 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 variable elimination linear support (VELS), a new multi-objective algorithm for multi-agent coordination that exploits loose couplings to compute the convex coverage set (CCS): the set of optimal solutions for all possible weights for linearly weighted objectives. Unlike existing methods, VELS exploits insights from POMDP solution methods to build the CCS incrementally. We prove the correctness of VELS and show that for moderate numbers of objectives its complexity is better than that of previous methods. Furthermore, we present empirical results showing that VELS can tackle both random and realistic problems with many more agents than was previously feasible. The incremental nature of VELS also makes it an anytime algorithm, i.e., its intermediate results constitute ε-optimal approximations of the CCS, with e decreasing the longer it runs. Our empirical results show that, by allowing even very small ε, VELS can enable large additional speedups.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Additional Information: | bib2html_pubtype: Refereed Conference (International) bib2html_rescat: Multiobjective Decision Making |
| Uncontrolled Keywords: | Multiple objectives, game theory, coordination graphs |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 11 May 2016 15:40 |
| Last Modified: | 15 Dec 2022 22:06 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3000448 |
Altmetric
Altmetric
