creators_name: Delle Fave, Francesco
creators_name: Stranders, Ruben
creators_name: Rogers, Alex
creators_name: Jennings, Nicholas R
type: conference_item
datestamp: 2011-08-10 10:26:31
lastmod: 2012-03-22 09:42:00
metadata_visibility: show
title: Bounded Decentralised Coordination over Multiple
Objectives
ispublished: pub
subjects: ABC
subjects: at
full_text_status: public
pres_type: speech
abstract: We propose the bounded multi-objective max-sum algorithm
(B-MOMS), the first decentralised coordination algorithm
for multi-objective optimisation problems. B-MOMS extends
the max-sum message-passing algorithm for decentralised
coordination to compute bounded approximate solutions
to multi-objective decentralised constraint optimisation
problems (MO-DCOPs). Specifically, we prove the
optimality of B-MOMS in acyclic constraint graphs, and derive
problem dependent bounds on its approximation ratio
when these graphs contain cycles. Furthermore, we empirically
evaluate its performance on a multi-objective extension
of the canonical graph colouring problem. In so doing, we
demonstrate that, for the settings we consider, the approximation
ratio never exceeds 2, and is typically less than 1:5
for less-constrained graphs. Moreover, the runtime required
by B-MOMS on the problem instances we considered never
exceeds 30 minutes, even for maximally constrained graphs
with 100 agents. Thus, B-MOMS brings the problem of
multi-objective optimisation well within the boundaries of
the limited capabilities of embedded agents.
date: 2011
date_type: published
pagerange: 371-378
event_title: Proc 10th Int Conf on Autonomous Agents and Multi-Agent Systems
event_location: Taipei, Taiwan
event_dates: 2 - 6 May 2011
event_type: conference
refereed: TRUE
citation:   Delle Fave, Francesco and Stranders, Ruben and Rogers, Alex and Jennings, Nicholas R  (2011) Bounded Decentralised Coordination over Multiple Objectives.  In: Proc 10th Int Conf on Autonomous Agents and Multi-Agent Systems, 2 - 6 May 2011, Taipei, Taiwan.     
document_url: http://www.orchid.ac.uk/eprints/2/1/bounded_decentralised_coordination.pdf