The Robotics Institute

Carnegie Mellon Robotics Institute

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.

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, and well-coordinated 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 dierent 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.

Notes

Text Reference

Katia Sycara, "Distributed Problem Solving through Coordination in a Society of Agents," Proceedings of the 13th International Workshop on Distributed Artificial Intelligence, 1994.

BibTeX Reference

@inproceedings{Sycara_1994_2207,
   author = "Katia Sycara",
   title = "Distributed Problem Solving through Coordination in a Society of Agents",
   booktitle = "Proceedings of the 13th International Workshop on Distributed Artificial Intelligence",
   year = "1994",
}

The Robotics Institute

Menu