Collective Problem Solving through Coordination in a Society of Reactive Agents

June 1994

Collective Problem Solving through Coordination in a Society of Reactive Agents

Authors:

Jyi Shane Liu
Technical Report
CMU-RI-TR-94-23

Abstract:

We present a methodology, called Constraint Partition and Coordinated Reaction (CP&CR), where a problem solution emerges from the evolving computational process of a group of diverse, interacting reactive agents. Problem characteristics are utilized to achieve problem solving by asynchronous and well coordinated local interactions. The coordination mechanisms guide the search space exploration by the society of interacting agents, facilitating rapid convergence to a solution. Our domain of problem solving is constraint satisfaction. We have applied the methodology to job shop scheduling with non-relaxable time windows, 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 centralized search scheduling techniques, in both computational cost and number of problems solved.
@techreport{Liu-1994-13728,
author = {Jyi Shane Liu},
title = {Collective Problem Solving through Coordination in a Society of Reactive Agents},
year = {1994},
month = {June},
institute = {Carnegie Mellon University},
address = {Pittsburgh, PA},
number = {CMU-RI-TR-94-23},
keywords = {collective problem solving, distributed problem solving, coordination mechanism, reactive agents, constraint satisfaction, job shop scheduling},
}
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.