BnB-ADOPT: an asynchronous branch-and-bound DCOP algorithm
BnB-ADOPT: an asynchronous branch-and-bound DCOP algorithm
复制标题
DOI：
10.1613/jair.2849
复制
发表时间：
2008-05
期刊：
影响因子：
--
通讯作者：
W. Yeoh;Ariel Felner;Sven Koenig
中科院分区：
文献类型：
--
作者：
W. Yeoh;Ariel Felner;Sven Koenig
分布式约束优化（DCOP）问题是制定和解决代理协调问题的流行方式。通常希望通过内存和异步算法最佳地解决DCOP问题。我们介绍了分支机构的采用（BNB-Adopt），这是一种由内存的异步DCOP算法，它使用采用的消息传递和通信框架，一种已知的内存的异步DCOP算法，但会从中从中采用的搜索策略从最好的优先搜索到深度优先的分支和结合搜索。我们的实验结果表明，BNB-Adopt的数量级比在各种大型DCOP问题上采用的速度要快，并且比NCBB更快，而NCBB（在大多数DCOP问题上都是由内存的同步DCOP算法）。
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.