Name
Abstract | ||
|---|---|---|
The field of Distributed Constraint Optimization has gained momentum in recent years, thanks to its ability to address various applications related to multi-agent cooperation. Nevertheless, solving Distributed Constraint Optimization Problems (DCOPs) optimally is NP-hard. Therefore, in large-scale, complex applications, incomplete DCOP algorithms are necessary. Current incomplete DCOP algorithms suffer of one or more of the following limitations: they (a) find local minima without providing quality guarantees; (b) provide loose quality assessment; or (c) are unable to benefit from the structure of the problem, such as domain-dependent knowledge and hard constraints. Therefore, capitalizing on strategies from the centralized constraint solving community, we propose a Distributed Large Neighborhood Search (D-LNS) framework to solve DCOPs. The proposed framework (with its novel repair phase) provides guarantees on solution quality, refining upper and lower bounds during the iterative process, and can exploit domain-dependent structures. Our experimental results show that D-LNS outperforms other incomplete DCOP algorithms on both structured and unstructured problem instances. |
Year | Venue | Field |
|---|---|---|
2017 | arXiv: Artificial Intelligence | Data mining,Mathematical optimization,Distributed constraint optimization problem,Iterative and incremental development,Upper and lower bounds,Computer science,Maxima and minima,Exploit,Artificial intelligence,Distributed constraint optimization,Machine learning,Large neighborhood search |
DocType | Volume | Citations |
Journal | abs/1702.06915 | 0 |
PageRank | References | Authors |
0.34 | 14 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ferdinando Fioretto | 1 | 88 | 20.13 |
| Agostino Dovier | 2 | 972 | 81.11 |
| Enrico Pontelli | 3 | 1901 | 181.26 |
| William Yeoh | 4 | 139 | 31.70 |
| Roie Zivan | 5 | 385 | 32.46 |