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.

Distributed Constraint Handling and Optimization

FARINELLI, Alessandro;
2013-01-01

Abstract

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.
9780262018890
Constraint Optimization; Distributed Constraint Opitimization Problems; Multi-Agents Systems
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/789773
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact