Exploiting the Structure of Distributed Constraint Optimization Problems

Distributed Constraint Optimization Problems (DCOPs) have emerged as one of the prominent multi-agent architectures to govern the agents' autonomous behavior in a Multi-Agent System (MAS), where several agents coordinate with each other to optimize a global cost function. They represent a powerful approach to the description and resolution of many practical problems, and serve several applications such as distributed scheduling, coordination of unmanned air vehicles, smart grid electric networks, and sensor networks. Typical real world applications are characterized by complex dynamics and interactions among a large number of entities, which translate into hard combinatorial problems, posing significant challenges from a computational point of view. The adoption of DCOPs on large instances of problems faces two main limitations: (1) Modeling limitations, as current resolution methods detach the model from the resolution process, imposing limiting assumptions on the capabilities of an agent (e.g., that it controls a single variable of the problem, and that it operates solely on the resolution of a global problem, ignoring the presence of private objectives); and (2) Solving capabilities, as the inability of current approaches to capitalize on the presence of structural information which may allow incoherent/unnecessary data to reticulate among the agents as well as to exploit latent structure of the agent's local problems, and/or of the problem of interest. The objective of the proposed dissertation is to address such limitations, studying how to adapt and integrate insights gained from centralized solving techniques, and from General Purpose Graphic Processing Units (GPGPUs) parallel architectures, in order to design practical algorithms to efficiently solve large, complex, DCOPs, enabling their use for the resolution of real-world problems. To do so, we hypothesize that one can exploit the latent structure of DCOPs in both problem modeling and problem resolution phases