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.
![[img]](../../style/images/fileicons/other.png)
|
PDF (Bounded Decentralised Coordination over Multiple Objectives)
Download (165Kb) | Preview |
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.
| Item Type: | Conference or Workshop Item (Speech) |
|---|---|
| Subjects: | Topics > Agent-based Computing Work Areas > Agile Teaming |
| Divisions: | University of Southampton |
| Depositing User: | Angela Westley |
| Date Deposited: | 10 Aug 2011 10:26 |
| Last Modified: | 22 Mar 2012 09:42 |
| URI: | http://www.orchid.ac.uk/eprints/id/eprint/2 |
Actions (login required)
 |
View Item |
