%A Francesco Delle Fave
%A Ruben Stranders
%A Alex Rogers
%A Nicholas R Jennings
%T Bounded Decentralised Coordination over Multiple
Objectives
%X 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.
%C Taipei, Taiwan
%D 2011
%P 371-378
%L orchid2