Vidal's library
Title: A Scalable Method for Multiagent Constraint Optimization
Author: Adrian Petcu and Boi Faltings
Book Tittle: Proceedings of the International Joint Conference on Artificial Intelligence
Pages: 266--271
Month: aug
Year: 2005
Abstract: 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.

Cited by 17  -  Google Scholar

@InProceedings{petcu05a,
  author =	 {Adrian Petcu and Boi Faltings},
  title =	 {A Scalable Method for Multiagent Constraint
                  Optimization},
  booktitle =	 {Proceedings of the International Joint Conference on
                  Artificial Intelligence},
  year =	 {2005},
  address =	 {Edinburgh, Scotland},
  month =	 aug,
  pages =	 {266--271},
  abstract =	 {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.},
  url = 	 {http://jmvidal.cse.sc.edu/library/petcu05a.pdf},
  cluster = 	 {15369336249688638382},
  keywords = 	 {multiagent dcop}
}
Last modified: Wed Mar 9 10:16:29 EST 2011