Emergent Constraint Satisfaction through Multi-Agent Coordinated Interaction

August 1993

Emergent Constraint Satisfaction through Multi-Agent Coordinated Interaction


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 specialised 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 specialised constraint agents. We have applied the methodology to job shop scheduling, an NP-complete constraint satisfaction problem. Utility of different types of coordination information in CP&CR was investigated. In addition, experimental results on a benchmark suite of problems show that CP&CR performed considerably well as compared to other centralised search scheduling techniques, in both computational cost and number of problems solved.
@workshop{Liu-1993-15957,
author = {Jyi Shane Liu And Katia Sycara},
title = {Emergent Constraint Satisfaction through Multi-Agent Coordinated Interaction},
booktitle = {Proceedings of European Workshop on Modeling Autonomous Agents in a Multi-Agent World (MAAMAW '93)},
year = {1993},
month = {August},
pages = {105 - 121},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.