Adopt: asynchronous distributed constraint optimization with quality guarantees
Adopt: asynchronous distributed constraint optimization with quality guarantees
复制标题
DOI：
10.1016/j.artint.2004.09.003
复制
发表时间：
2005-01-01
影响因子：
14.4
通讯作者：
Yokoo, M
中科院分区：
文献类型：
--
作者：
Modi, PJ;Shen, WM;Yokoo, M
分布式约束优化问题（DCOP）是建模在多基因系统中出现的分布式推理任务的有前途的方法。不幸的是，现有的DCOP方法无法为全球解决方案质量提供理论保证，同时允许代理商异步运行。我们通过允许代理商根据保守的成本估算做出本地决策，而不是像以前的方法一样依靠全球确定性来纠正这种失败。这种新颖的方法导致一种名为DCOP的多项式空间算法采用，该算法可以保证找到全球最佳解决方案，同时允许代理人异步和并行执行。详细的实验结果表明，在基准问题上采用了其他方法比其他方法获得了几个数量级的加速。采用还可以执行有限的错误近似值 - 它具有快速找到近似解决方案的能力，并且与启发式搜索方法不同，仍然对解决方案质量保持理论保证。 （c）2004 Elsevier B.V.保留所有权利。
The Distributed Constraint Optimization Problem (DCOP) is a promising approach for modeling distributed reasoning tasks that arise in multiagent systems. Unfortunately, existing methods for DCOP are not able to provide theoretical guarantees on global solution quality while allowing agents to operate asynchronously. We show how this failure can be remedied by allowing agents to make local decisions based on conservative cost estimates rather than relying on global certainty as previous approaches have done. This novel approach results in a polynomial-space algorithm for DCOP named Adopt that is guaranteed to find the globally optimal solution while allowing agents to execute asynchronously and in parallel. Detailed experimental results show that on benchmark problems Adopt obtains speedups of several orders of magnitude over other approaches. Adopt can also perform bounded-error approximation-it has the ability to quickly find approximate solutions and, unlike heuristic search methods, still maintain a theoretical guarantee on solution quality. (C) 2004 Elsevier B.V. All rights reserved.