ODPOP: An Algorithm For Open/Distributed Constraint Optimization

Adrian Petcu, Boi Faltings

We propose ODPOP, a new distributed algorithm for open multiagent combinatorial optimization that feature unbounded domains. The ODPOP algorithm explores the same search space as the dynamic programming algorithm DPOP or ADOPT, 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 best-first order, it avoids incurring always the worst case complexity as DPOP, and on average it saves a significant amount of computation and information exchange. To show the merits of our approach, we report on experiments with practically sized distributed meeting scheduling problems in a multiagent system.

Subjects: 15.2 Constraint Satisfaction; 7. Distributed AI

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.