1995 · 71 citations · 12 references
ComputingComputer ScienceDistributed SystemsOptimizationSchedulingConstraint SatisfactionDistributed SchedulingJob SchedulingJob Shop SchedulingMachine SchedulingComplexityConstraint OptimizationConstraintsCoordinationDistributed Constraint OptimizationDistributed Constraint SatisfactionLocal SearchScheduling Problems
Distributed constraint optimization imposes considerable complexity in agents' coordinated search for an optimal solution. However, in many application domains, problems often exhibit special structures that can be exploited to facilitate more efficient problem solving. One of the most recurrent structures involves disparity among subproblems. We present a coordination mechanism, Anchor&Ascend, for distributed constraint optimization that takes advantage of disparity among subproblems to efficiently guide distributed local search for global optimality. The coordination mechanism assigns different overlapping subproblems to agents who must interact and iteratively converge on a solution. In particular, an anchor agent who conducts local best first search to optimize its subsolution interacts with the rest of the agents who perform distributed constraint satisfaction to enforce problem constraints and constraints imposed by the anchor agent. We focus our study on the well-known NP-comple...
12
Where the really hard problems are
Peter Cheeseman, Bob Kanefsky, William M. Taylor · 1991 · 1K citations
Distributed constraint satisfaction for formalizing distributed problem solving
Makoto Yokoo, Toru Ishida, Edmund H. Durfee et al. · 2003 · 335 citations
Distributed constrained heuristic search
Katia Sycara, Steven F. Roth, Norman Sadeh et al. · IEEE Transactions on Systems Man and Cybernetics · 1991 · 208 citations