title: Bounded Decentralised Coordination over Multiple  Objectives
creator: Delle Fave, Francesco
creator: Stranders, Ruben
creator: Rogers, Alex
creator: Jennings, Nicholas R
subject: Agent-based Computing
subject: Agile Teaming
description: 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
type: Conference or Workshop Item
type: PeerReviewed
format: application/pdf
identifier: http://www.orchid.ac.uk/eprints/2/1/bounded_decentralised_coordination.pdf
identifier:   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.     
relation: http://www.orchid.ac.uk/eprints/2/