ODPOP: An algorithm for Open/Distributed Constraint Optimization

We propose ODPOP, a new distributed algorithm for \textit{open multiagent combinatorial optimization} \cite{Faltings2005c}. The ODOP algorithm explores the same search space as the dynamic programming algorithm DPOP~\cite{Petcu2005} or the AND/OR search algorithm AOBB~\cite{Dechter2003}, 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.