BnB-ADOPT: an asynchronous branch-and-bound DCOP algorithm. Yeoh, W., Felner, A., & Koenig, S. Journal of Artificial Intelligence Research, 38:85-133, International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 2010.
Paper doi abstract bibtex Distributed constraint optimization (DCOP) problems are a popular way of formulating and solving agent-coordination problems. It is often desirable to solve DCOP problems optimally with memory-bounded and asynchronous algorithms. We introduce Branch-and-Bound ADOPT (BnB-ADOPT), a memory-bounded asynchronous DCOP algorithm that uses the message passing and communication framework of ADOPT, a well known memory-bounded asynchronous DCOP algorithm, but changes the search strategy of ADOPT from best-first search to depth-first branch-and-bound search. Our experimental results show that BnB-ADOPT is up to one order of magnitude faster than ADOPT on a variety of large DCOP problems and faster than NCBB, a memory-bounded synchronous DCOP algorithm, on most of these DCOP problems.
@article {Yeoh:2008:BAB:1402298.1402307,
title = {BnB-ADOPT: an asynchronous branch-and-bound DCOP algorithm},
journal = {Journal of Artificial Intelligence Research},
volume = {38},
year = {2010},
pages = {85-133},
publisher = {International Foundation for Autonomous Agents and Multiagent Systems},
address = {Richland, SC},
abstract = {Distributed constraint optimization (DCOP) problems are a popular way of formulating and solving agent-coordination problems. It is often desirable to solve DCOP problems optimally with memory-bounded and asynchronous algorithms. We introduce Branch-and-Bound ADOPT (BnB-ADOPT), a memory-bounded asynchronous DCOP algorithm that uses the message passing and communication framework of ADOPT, a well known memory-bounded asynchronous DCOP algorithm, but changes the search strategy of ADOPT from best-first search to depth-first branch-and-bound search. Our experimental results show that BnB-ADOPT is up to one order of magnitude faster than ADOPT on a variety of large DCOP problems and faster than NCBB, a memory-bounded synchronous DCOP algorithm, on most of these DCOP problems.},
keywords = {agent cooperation, BnB-ADOPT, DCOP, distributed constraint optimization, distributed problem solving},
issn = {1076-9757},
doi = {10.1613/jair.2849},
url = {http://www.jair.org/papers/paper2849.html},
author = {Yeoh, William and Felner, Ariel and Koenig, Sven}
}
Downloads: 0
{"_id":"nu8ACMaor9ZK89WHA","bibbaseid":"yeoh-felner-koenig-bnbadoptanasynchronousbranchandbounddcopalgorithm-2010","downloads":0,"creationDate":"2018-07-03T04:50:27.718Z","title":"BnB-ADOPT: an asynchronous branch-and-bound DCOP algorithm","author_short":["Yeoh, W.","Felner, A.","Koenig, S."],"year":2010,"bibtype":"article","biburl":"https://gnunet.org/bibliography/export/bibtex","bibdata":{"bibtype":"article","type":"article","title":"BnB-ADOPT: an asynchronous branch-and-bound DCOP algorithm","journal":"Journal of Artificial Intelligence Research","volume":"38","year":"2010","pages":"85-133","publisher":"International Foundation for Autonomous Agents and Multiagent Systems","address":"Richland, SC","abstract":"Distributed constraint optimization (DCOP) problems are a popular way of formulating and solving agent-coordination problems. It is often desirable to solve DCOP problems optimally with memory-bounded and asynchronous algorithms. We introduce Branch-and-Bound ADOPT (BnB-ADOPT), a memory-bounded asynchronous DCOP algorithm that uses the message passing and communication framework of ADOPT, a well known memory-bounded asynchronous DCOP algorithm, but changes the search strategy of ADOPT from best-first search to depth-first branch-and-bound search. Our experimental results show that BnB-ADOPT is up to one order of magnitude faster than ADOPT on a variety of large DCOP problems and faster than NCBB, a memory-bounded synchronous DCOP algorithm, on most of these DCOP problems.","keywords":"agent cooperation, BnB-ADOPT, DCOP, distributed constraint optimization, distributed problem solving","issn":"1076-9757","doi":"10.1613/jair.2849","url":"http://www.jair.org/papers/paper2849.html","author":[{"propositions":[],"lastnames":["Yeoh"],"firstnames":["William"],"suffixes":[]},{"propositions":[],"lastnames":["Felner"],"firstnames":["Ariel"],"suffixes":[]},{"propositions":[],"lastnames":["Koenig"],"firstnames":["Sven"],"suffixes":[]}],"bibtex":"@article {Yeoh:2008:BAB:1402298.1402307,\n\ttitle = {BnB-ADOPT: an asynchronous branch-and-bound DCOP algorithm},\n\tjournal = {Journal of Artificial Intelligence Research},\n\tvolume = {38},\n\tyear = {2010},\n\tpages = {85-133},\n\tpublisher = {International Foundation for Autonomous Agents and Multiagent Systems},\n\taddress = {Richland, SC},\n\tabstract = {Distributed constraint optimization (DCOP) problems are a popular way of formulating and solving agent-coordination problems. It is often desirable to solve DCOP problems optimally with memory-bounded and asynchronous algorithms. We introduce Branch-and-Bound ADOPT (BnB-ADOPT), a memory-bounded asynchronous DCOP algorithm that uses the message passing and communication framework of ADOPT, a well known memory-bounded asynchronous DCOP algorithm, but changes the search strategy of ADOPT from best-first search to depth-first branch-and-bound search. Our experimental results show that BnB-ADOPT is up to one order of magnitude faster than ADOPT on a variety of large DCOP problems and faster than NCBB, a memory-bounded synchronous DCOP algorithm, on most of these DCOP problems.},\n\tkeywords = {agent cooperation, BnB-ADOPT, DCOP, distributed constraint optimization, distributed problem solving},\n\tissn = {1076-9757},\n\tdoi = {10.1613/jair.2849},\n\turl = {http://www.jair.org/papers/paper2849.html},\n\tauthor = {Yeoh, William and Felner, Ariel and Koenig, Sven}\n}\n","author_short":["Yeoh, W.","Felner, A.","Koenig, S."],"key":"Yeoh:2008:BAB:1402298.1402307","id":"Yeoh:2008:BAB:1402298.1402307","bibbaseid":"yeoh-felner-koenig-bnbadoptanasynchronousbranchandbounddcopalgorithm-2010","role":"author","urls":{"Paper":"http://www.jair.org/papers/paper2849.html"},"keyword":["agent cooperation","BnB-ADOPT","DCOP","distributed constraint optimization","distributed problem solving"],"downloads":0},"search_terms":["bnb","adopt","asynchronous","branch","bound","dcop","algorithm","yeoh","felner","koenig"],"keywords":["agent cooperation","bnb-adopt","dcop","distributed constraint optimization","distributed problem solving"],"authorIDs":[],"dataSources":["FWsPTwsmjtrBtRS3B"]}