Date of Award
Doctor of Philosophy (PhD)
The Distributed Constraint Optimization Problem (DCOP) formulation is a powerful tool to model multi-agent coordination problems that are distributed by nature. The formulation is suitable for problems where the environment does not change over time and where agents seek their value assignment from a discrete domain. However, in many real-world applications, agents often interact in a more dynamic environment and their variables usually require a more complex domain. Thus, the DCOP formulation lacks the capabilities to model the problems in such dynamic and complex environments. To address these limitations, researchers have proposed Dynamic DCOPs (D-DCOPs) to model how DCOPs dynamically change over time and Continuous DCOPs (C-DCOPs) to model DCOPs with continuous variables. The two models address the limitations of DCOPs but in isolation, and thus, it remains a challenge to model problems that have continuous variables and are in a dynamic environment. Therefore, this dissertation investigates a novel formulation that addresses the two limitations of DCOPs together by modeling both dynamic nature of the environment and continuous nature of the variables. Firstly, we propose Proactive Dynamic DCOPs (PD-DCOPs) which model and solve DCOPs in dynamic environment in a proactive manner. Secondly, we propose several C-DCOP algorithms that are efficient and we provide quality guarantee on their solution. Finally, we propose Dynamic Continuous DCOP (DC-DCOP), a novel formulation that models the DCOPs with continuous variables in a dynamic environment.
Chien-Ju Ho, Alvitta Ottley, William Yeoh, Roie Zivan,