Variational Multi-Objective Coordination



Roijers, Diederik M, Whiteson, Shimon, Ihler, Alex and Oliehoek, Frans A ORCID: 0000-0003-4372-5055
(2015) Variational Multi-Objective Coordination. .

[img] Text
Roijers15LICMAS.pdf - Unspecified

Download (1MB)

Abstract

In this paper, we propose variational optimistic linear support (VOLS), a novel algorithm that finds bounded approximate solutions for multi-objective coordination graphs (MO-CoGs). VOLS builds and improves upon an existing exact algorithm called variable elimination linear support (VELS). Like VELS, VOLS solves a MO-CoG as a series of scalarized single-objective coordination graphs. We improve upon VELS in two important ways. Firstly, where VELS uses a single-objective solver called variable elimination (VE) as a subroutine, VOLS uses a variational method called weighted mini-buckets (WMB). Because variational methods scale much better than VE, VOLS can be used to solve much larger MO-CoGs than was previously possible. Furthermore, we show that because WMB computes bounded approximations, so does VOLS. Secondly, we leverage the insight that VOLS can hot-start each call to WMB by reusing the reparameterizations output by WMB on earlier calls. We show empirically that VOLS scales much better than VELS and introduces only negligle error. Our experimental results indicate that the reuse of reparameterizations keeps the runtime low and the approximation quality high.

Item Type: Conference or Workshop Item (Unspecified)
Additional Information: bib2html_pubtype: Refereed Workshop bib2html_rescat: Multiobjective Decision Making
Depositing User: Symplectic Admin
Date Deposited: 04 May 2016 15:38
Last Modified: 17 Dec 2022 02:28
URI: https://livrepository.liverpool.ac.uk/id/eprint/3000445