Solving DCOPs with Distributed Large Neighborhood Search
This addresses the problem of multi-agent cooperation in complex applications by offering an incremental improvement over existing incomplete DCOP algorithms with better quality guarantees and performance.
The paper tackled the challenge of solving Distributed Constraint Optimization Problems (DCOPs) optimally, which is NP-hard, by proposing a Distributed Large Neighborhood Search (D-LNS) framework that provides quality guarantees and exploits domain-dependent structures, outperforming other incomplete DCOP algorithms on structured and unstructured instances.
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.