Collective Problem Solving through Coordination in a Society of Reactive Agents

Abstract

We present a methodology, called Constraint Partition and Coordinated Reaction (CPCR), where a problem solution emerges from the evolving computational process of a group a 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1994
Accession Number
ADA283008

Entities

People

  • Jyi-Shane Liu

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Autonomy
  • C4I
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Artificial Intelligence
  • Boundaries
  • Convergence
  • Decomposition
  • Efficiency
  • Environment
  • Frequency
  • Job Shop Scheduling
  • Lisp Programming Language
  • Multiagent Systems
  • Operations Research
  • Parallel Computing
  • Parallel Processing
  • Reliability
  • Scheduling (Production)
  • Self Organizing Systems

Readers

  • Artificial Intelligence
  • Economics
  • Parallel and Distributed Computing.

Technology Areas

  • Space