Vidal's library
Title: ODPOP: An algorithm for Open/Distributed Constraint Optimization
Author: Adrian Petcu and Boi Faltings
Book Tittle: Proceedings of the National Conference on Artificial Intelligence, AAAI-06
Pages: 703--708
Month: July
Year: 2006
Abstract: We propose ODPOP, a new distributed algorithm for open multiagent combinatorial optimization. The ODOP algorithm explores the same search space as the dynamic programming algorithm DPOP or the AND/OR search algorithm AOBB, but does so in an incremental, best-first fashion suitable for open problems. ODPOP has several advantages over DPOP. First, it uses messages whose size only grows linearly with the treewidth of the problem. Second, by letting agents explore values in a non-increasing order of preference, it saves a significant amount of messages and computation over the basic DPOP algorithm. To show the merits of our approach, we report on experiments with practically sized distributed meeting scheduling problems in a multiagent system.



@InProceedings{petcu06a,
  author =	 {Adrian Petcu and Boi Faltings},
  title =	 {{ODPOP}: An algorithm for Open/Distributed
                  Constraint Optimization},
  booktitle =	 {Proceedings of the National Conference on Artificial
                  Intelligence, AAAI-06},
  year =	 2006,
  address =	 {Boston, USA},
  month =	 {July},
  pages =	 {703--708},
  abstract =	 {We propose ODPOP, a new distributed algorithm for
                  open multiagent combinatorial optimization. The ODOP
                  algorithm explores the same search space as the
                  dynamic programming algorithm DPOP or the AND/OR
                  search algorithm AOBB, but does so in an
                  incremental, best-first fashion suitable for open
                  problems. ODPOP has several advantages over
                  DPOP. First, it uses messages whose size only grows
                  linearly with the treewidth of the problem. Second,
                  by letting agents explore values in a non-increasing
                  order of preference, it saves a significant amount
                  of messages and computation over the basic DPOP
                  algorithm. To show the merits of our approach, we
                  report on experiments with practically sized
                  distributed meeting scheduling problems in a
                  multiagent system.},
  url =		 {http://jmvidal.cse.sc.edu/library/petcu06a.pdf},
  keywords = 	 {multiagent dcop}
}
Last modified: Wed Mar 9 10:16:36 EST 2011