Coordination Theory

Our research in Coordination Theory has explored two paths:

Constraint-Directed Coordination: This research views coordination among agents as occuring as the result of the communication of constraints and related information such as relaxations, utitlities, etc. Constraints express both needs and limitations. Our earliest work explored the communication of constraints in a resource re-allocation problem (Sathi, A., and Fox, M.S., (1989), “Constraint-Directed Negotiation of Resource Re-Allocations”, Distributed Artificial Intelligence II, M. Huhns, (Ed.), Los Altos CA: Morgan Kaufmann Pub., pp. 163-193.), and a distributed factory scheduling problem (Sycara, K., Roth, S., Sadeh, N., and Fox, M.S., (1991), “Distributed Constrained Heuristic Search“, IEEE Transactions on Systems, Man and Cybernetics, Vol. 21, No. 6, pp. 1446-1461.)A later work explored how a mediation agent would approach the relaxation of constraints in order to achieve a more satisfactory global result (Beck, J.C. (1994) “A Schema for Constraint Relaxation with Instantiations for Partial Constraint Satisfaction and Schedule Optimization” Master’s Thesis, University of Toronto.)

Coordination Languages: As the basic component of our Agent Building Shell Research, we developed the COOL language for expressing coordination in a distributed agent environment, it allows programmers to build multiagent applications by defining:

  • Distributed execution environments that manage the execution of agents.
  • The agents themselves, together with their behavior and interaction patterns.
  • The communication language used by agents (a form of KQML).
  • Specifications of agent interaction by means of conversation plans and conversation rules. Conversation plans are specifications of how agents act, react and interact in specific situations. A conversation plan consists of states and transitions. Transitions are expressed by several types of conversation rules. A conversation rule specifies patterns of received messages that may trigger it as well as patterns of messages that will be transmitted in response by the agent. Conversation rules also specify the local decision making and action taken by agents. In particular, this includes the use of legacy software the agent has access to.

Online Resources

User’s Guide to the Coordination Language

Publications

Applications, Source code, Screens

Simplest example: the nqueens problem.
Source codetrace of exchanged messages

The coordination knowledge acquisition process. Screen dumps illustrating various interfaces.
Main knowledge acquisition interface for conversation rules
conversation plan editorKQML messaging interface