Distributed Constraint Handling and Optimization

Constraints pervade our everyday lives and are usually perceived as elements that limit solutions to the problems that we face (e.g., the choices we make everyday are typically constrained by limited money or time). However, from a computational point of view, constraints are key components for efficiently solving hard problems. In fact, constraints encode knowledge about the problem at hand, and so restrict the space of possible solutions that must be considered. By doing so, they greatly reduce the computational effort required to solve a problem. Here we will focus on how constraint processing can be used to address optimization problems in Multi-Agent Systems. Specifically, we will consider Dis tributed Constraint Optimization Problems (DCOPs) where a set of agents must come to some agreement, typically via some form of negotiation, about which action each agent should take in order to jointly obtain the best solution for the whole system. In more detail, this chapter aims to provide the reader with a broad knowledge of the main DCOP solution approaches describing both exact algorithms, approximate approaches and quality guarantees that can be provided in the DCOP framework.