CoCoA: A non-iterative approach to a local search (A)DCOP Solver
conference paper
We propose a novel incomplete cooperative algorithm for distributed constraint optimization problems (DCOPs) denoted as Cooperative Constraint Approximation (CoCoA). The key strategy of the algorithm is to use a semi-greedy approach in which knowledge is distributed amongst neighboring agents, and assigning a value only once instead of an iterative approach. Furthermore, CoCoA uses a unique-first approach to improve the solution quality. It is designed such that it can solve DCOPs as well as Asymmetric DCOPS, with only few messages being communicated between neighboring agents. Experimentally, through evaluating graph coloring problems, randomized (A)DCOPs, and a sensor network communication problem, we show that CoCoA is able to very quickly find solutions of high quality with a smaller communication overhead than state-of-the-art DCOP solvers such as DSA, MGM-2, ACLS, MCS-MGM and Max-Sum. In our asymmetric use case problem of a sensor network, we show that CoCoA not only finds the best solution, but also finds this solution faster than any other algorithm. Copyright © 2017, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. Amazon; Artificial Intelligence; Baidu; et al.; IBM; Tencent
Topics
Approximation algorithmsArtificial intelligenceCommunication channels (information theory)Constrained optimizationIterative methodsLocal search (optimization)OptimizationSensor networksCommunication overheadsCooperative algorithmDistributed constraint optimizationsGraph coloring problemGreedy approachesIterative approachNetwork communication problemsSolution qualityCocoa
TNO Identifier
781343
Publisher
AAAI press
Source title
31st AAAI Conference on Artificial Intelligence, AAAI 2017. 4 February 2017 through 10 February 2017
Pages
3944-3950
Files
To receive the publication files, please send an e-mail request to TNO Repository.