TY  - CONF
ID  - orchid2
UR  - http://www.orchid.ac.uk/eprints/2/
A1  - Delle Fave, Francesco
A1  - Stranders, Ruben
A1  - Rogers, Alex
A1  - Jennings, Nicholas R
Y1  - 2011///
N2  - 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.
TI  - Bounded Decentralised Coordination over Multiple
Objectives
SP  - 371
M2  - Taipei, Taiwan
AV  - public
EP  - 378
T2  - Proc 10th Int Conf on Autonomous Agents and Multi-Agent Systems
ER  -