Distributed Constraint Satisfaction through Constraint Partition and Coordinated Reaction

Abstract

We present a methodology, called Constraint Partition and Coordinated Reaction (CP&CR), for distributed constraint satisfaction based on partitioning the set of constraints into subsets of different constraint types. Associated with each constraint type is a set of specialized agents, each of which is responsible for enforcing constraints of the specified type for the set of variables under its jurisdiction. Variable instantiation is the joint responsibility of a set of agents, each of which has a different perspective on the instantiation according to a particular constraint type and can revise the instantiation in response to violations of the specific constraint type. The final solution emerges through incremental local revisions of an initial, possibly inconsistent, instantiation of all variables. Solution revision is the result of coordinated local reaction of the specialized constraint agents. We have applied the methodology to job shop scheduling, an NP-complete constraint satisfaction problem. Experimental results on a benchmark suite of problems show that CP&CR outperformed three other state-of-the-art scheduling techniques, in both efficiency and number of problems solved. In addition, we experimentally tested the utility and effectiveness of various types of coordination information that the agents exchange. Themes: Distributed constraint satisfaction, agent societies, emergent system behavior.