Standard

CoCoA : A Non-Iterative Approach to a Local Search (A) DCOP Solver. / van Leeuwen, Coen; Pawelczak, Przemek.

Proceedings of the 31 Conference on Artificial Intelligence , AAAI 2017. American Association for Artificial Intelligence (AAAI), 2017. p. 3944-3950.

Research output: Scientific - peer-reviewConference contribution

Harvard

van Leeuwen, C & Pawelczak, P 2017, CoCoA: A Non-Iterative Approach to a Local Search (A) DCOP Solver. in Proceedings of the 31 Conference on Artificial Intelligence , AAAI 2017. American Association for Artificial Intelligence (AAAI), pp. 3944-3950, 31st AAAI Conference on Artificial Intelligence, San Francisco, United States, 4/02/17.

APA

van Leeuwen, C., & Pawelczak, P. (2017). CoCoA: A Non-Iterative Approach to a Local Search (A) DCOP Solver. In Proceedings of the 31 Conference on Artificial Intelligence , AAAI 2017 (pp. 3944-3950). American Association for Artificial Intelligence (AAAI).

Vancouver

van Leeuwen C, Pawelczak P. CoCoA: A Non-Iterative Approach to a Local Search (A) DCOP Solver. In Proceedings of the 31 Conference on Artificial Intelligence , AAAI 2017. American Association for Artificial Intelligence (AAAI). 2017. p. 3944-3950.

Author

van Leeuwen, Coen ; Pawelczak, Przemek. / CoCoA : A Non-Iterative Approach to a Local Search (A) DCOP Solver. Proceedings of the 31 Conference on Artificial Intelligence , AAAI 2017. American Association for Artificial Intelligence (AAAI), 2017. pp. 3944-3950

BibTeX

@inbook{108d8560e41d45439862d028ff431da1,
title = "CoCoA: A Non-Iterative Approach to a Local Search (A) DCOP Solver",
abstract = "We propose a novel incomplete cooperative algorithm for distributedconstraint 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 communicationoverhead 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 thissolution faster than any other algorithm.",
keywords = "DCOP, Constraint Satisfaction, Incomplete, Non-iterative",
author = "{van Leeuwen}, Coen and Przemek Pawelczak",
year = "2017",
month = "2",
pages = "3944--3950",
booktitle = "Proceedings of the 31 Conference on Artificial Intelligence , AAAI 2017",
publisher = "American Association for Artificial Intelligence (AAAI)",
address = "United States",

}

RIS

TY - CHAP

T1 - CoCoA

T2 - A Non-Iterative Approach to a Local Search (A) DCOP Solver

AU - van Leeuwen,Coen

AU - Pawelczak,Przemek

PY - 2017/2/4

Y1 - 2017/2/4

N2 - We propose a novel incomplete cooperative algorithm for distributedconstraint 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 communicationoverhead 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 thissolution faster than any other algorithm.

AB - We propose a novel incomplete cooperative algorithm for distributedconstraint 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 communicationoverhead 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 thissolution faster than any other algorithm.

KW - DCOP

KW - Constraint Satisfaction

KW - Incomplete

KW - Non-iterative

UR - https://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14191

M3 - Conference contribution

SP - 3944

EP - 3950

BT - Proceedings of the 31 Conference on Artificial Intelligence , AAAI 2017

PB - American Association for Artificial Intelligence (AAAI)

ER -

ID: 33345080