Quality Guarantees on k-Optimal Solutions for Distributed Constraint Optimization Problems
Quality Guarantees on k-Optimal Solutions for Distributed Constraint Optimization Problems
复制标题
分布式约束优化问题k-最优解的质量保证
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Milind Tambe
中科院分区：
文献类型：
--
作者：
J. Pearce;Milind Tambe
分布式约束优化问题（DCOP）是一种形式主义，它捕获代理团队内局部交互的回报和成本。由于求解DCOP的完全算法不适用于某些动态或任意时间域，研究人员探索了导致局部最优解的不完全DCOP算法。这种算法的一种分类，以及它们产生的解决方案，是k-最优性; k-最优解决方案是不能通过k个或更少的代理的任何偏差来改进的解决方案。本文提出了第一个已知的保证解决方案的质量k-最优解决方案。该保证独立于DCOP中的成本和回报，并且一旦计算就可以用于给定约束图结构的任何DCOP。
A distributed constraint optimization problem (DCOP) is a formalism that captures the rewards and costs of local interactions within a team of agents. Because complete algorithms to solve DCOPs are unsuitable for some dynamic or anytime domains, researchers have explored incomplete DCOP algorithms that result in locally optimal solutions. One type of categorization of such algorithms, and the solutions they produce, is k- optimality; a k-optimal solution is one that cannot be improved by any deviation by k or fewer agents. This paper presents the first known guarantees on solution quality for k-optimal solutions. The guarantees are independent of the costs and rewards in the DCOP, and once computed can be used for any DCOP of a given constraint graph structure.