Collective Problem Solving through Coordination in a Society of Reactive Agents.

摘要

We present a methodology, called Constraint Partition and Coordinated Reaction (CPCR), 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 satisfactions. 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 CPCR was investigated. In addition, experimental results on a benchmark suite of problems show that CPCR performed considerably well as compared to other centralized search scheduling techniques, in both computational cost and number of problems solved. (Author).