2007 · 110 citations · 11 references
ComputingComputer ScienceAlgorithmsDistributed SystemsOptimizationCombinatorial OptimizationConstrained OptimizationConstraint SatisfactionDiscrete OptimizationDistributed AlgorithmsDistributed ComputingConstraint OptimizationConstraint Optimization ProblemsDistributed Constraint OptimizationDistributed Constraint SolvingDistributed OptimizationGraph OptimizationMulti-agent OptimizationSolution Generation
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 koptimality; 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.
11
Adopt: asynchronous distributed constraint optimization with quality guarantees
Pragnesh Jay Modi, Wei‐Min Shen, Milind Tambe et al. · Artificial Intelligence · 2004 · 762 citations
Networked distributed POMDPs: a synthesis of distributed constraint optimization and POMDPs
Ranjit Nair, Pradeep Varakantham, Milind Tambe et al. · Institutional Knowledge (InK) - Institutional Knowledge at Singapore Management University (Singapore Management University) · 2005 · 212 citations · Full text