LIA Publications

Complete list - Search - Complete list (dynamically generated)

DPOP: A Scalable Method for Multiagent Constraint Optimization

Download Petcu2005.pdf

@InProceedings{Petcu2005,
  author = 	{Petcu, Adrian and Faltings, Boi},
  title = 	{DPOP: A Scalable Method for Multiagent Constraint Optimization},
  booktitle = 	{IJCAI 05},
  year = 	{2005},
  address = 	{Edinburgh, Scotland},
  month = 	{Aug},
  pages = 	{266-271},
  annote = 	{We present in this paper a new, complete method for distributed constraint optimization, based on dynamic programming. It is a utility propagation method, inspired by the sum-product algorithm, which is correct only for tree-shaped constraint networks.
 In this paper, we show how to extend that algorithm to arbitrary topologies using a pseudotree arrangement of the problem graph.
 Our algorithm requires a linear number of messages, whose maximal size depends on the induced width along the particular pseudotree chosen.
 
 We compare our algorithm with backtracking algorithms, and present experimental results.
 For some problem types we report orders of magnitude less messages, and even the ability to deal with arbitrarily large problems.
 Our algorithm is formulated for optimization problems, but can be easily applied to satisfaction problems as well. }
}

This page is maintained by email
Generated on Fri Sep 19 08:01:25 2014

Back to LIA homepage