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.
Original languageEnglish
Title of host publicationProceedings of the 31 Conference on Artificial Intelligence , AAAI 2017
PublisherAmerican Association for Artificial Intelligence (AAAI)
Number of pages7
StatePublished - 4 Feb 2017
Event31st AAAI Conference on Artificial Intelligence - San Francisco, United States


Conference31st AAAI Conference on Artificial Intelligence
Abbreviated title AAAI Conference on Artificial Intelligence
CountryUnited States
CitySan Francisco
Internet address

    Research areas

  • DCOP, Constraint Satisfaction, Incomplete, Non-iterative

ID: 33345080