Proactive Dynamic Distributed Constraint Optimization

Current approaches that model dynamism in DCOPs solve a sequence of static problems, reacting to changes in the environment as the agents observe them. Such approaches thus ignore possible predictions on future changes. To overcome this limitation, we introduce Proactive Dynamic DCOPs (PD-DCOPs), a novel formalism to model dynamic DCOPs in the presence of exogenous uncertainty. In contrast to reactive approaches, PD-DCOPs are able to explicitly model the possible changes to the problem, and take such information into account proactively, when solving the dynamically changing problem. The additional expressivity of this formalism allows it to model a wider variety of distributed optimization problems. Our work presents both theoretical and practical contributions that advance current dynamic DCOP models: (i) we introduce the PD-DCOP model, which explicitly captures dynamic changes of the DCOP over time; (ii) we discuss the complexity of this new class of DCOPs; and (iii) we develop both exact and approximation algorithms with quality guarantees to solve PD- DCOPs proactively.

Authors

• Khoi D. Hoang
• Ferdinando Fioretto University of Virginia
• Ping Hou
• Makoto Yokoo Kyushu University
• William Yeoh Washington University in St. Louis
• Roie Zivan Ben-Gurion University

Keywords

• Distributed Constraint Optimization
• DCOP
• Dynamic DCOP