Abstract
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.
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 language | English |
|---|---|
| Title of host publication | Proceedings of the 31 Conference on Artificial Intelligence , AAAI 2017 |
| Publisher | American Association for Artificial Intelligence (AAAI) |
| Pages | 3944-3950 |
| Number of pages | 7 |
| Publication status | Published - 4 Feb 2017 |
| Event | 31st AAAI Conference on Artificial Intelligence: AAAI 2017 - Hilton San Francisco Union Square, San Francisco, United States Duration: 4 Feb 2017 → 10 Feb 2017 Conference number: 31 https://aaai.org/Conferences/AAAI/aaai17.php |
Conference
| Conference | 31st AAAI Conference on Artificial Intelligence |
|---|---|
| Abbreviated title | AAAI Conference on Artificial Intelligence |
| Country/Territory | United States |
| City | San Francisco |
| Period | 4/02/17 → 10/02/17 |
| Internet address |
Keywords
- DCOP
- Constraint Satisfaction
- Incomplete
- Non-iterative