2.5.1 Contract Net Protocol
Almost certainly, the most commonly employed coordination mechanism for controlling the problem-solving behavior of a collection of distributed agents is the contract net protocol [33]. This is concerned with the dynamic configuration and coordination of agents to form hierarchies that can achieve complex, distributed tasks.
In the examples of architectures above, there is generally no consideration of issues of coordination. In many systems in which agents interact, the forms of interaction and the relationships between agents are static, representing an unalterable structure. Since much of the value of agent-based computing derives from its ability to address the issues that arise from dynamic and open environments, however, this is inadequate. By contrast, the contract net protocol (CNP), proposed by Smith and Davis [33], provides a mechanism by which nodes (or agents) can dynamically create relationships in response to the current processing requirements of the system as a whole, thereby enabling opportunistic task allocation.
In the contract net framework, a node with a task to be achieved forms contracts with others who proceed to accomplish this task. The steps to forming and maintaining a contract are defined by the contract net protocol, described as follows, and shown in Figure 2.5:
A node decomposes a task into a number of subtasks. For each subtask, the node issues a task announcement describing what needs to be performed, along with eligibility requirements detailing the necessary processing requirements to complete the task.
Once a node receives a task announcement, if it fulfills the eligibility specification, it may bid for the task. Essentially, nodes evaluate their interest using task evaluation procedures specific to the problem at hand. If a node has sufficient interest in a task announcement, it will submit a bid to undertake to perform the task. A node will not bid unless it is free to perform the task.
Once all bids have been received by the original (potential manager) node, it ranks them according to criteria associated with the task, and awards a contract to the bidder with the highest ranked bid.
There is now a contract between the manager who made the task announcement and the bidder (the contractor) with the highest ranked bid. Over time, the manager monitors the problem-solving of the contractor, requesting progress reports or canceling the contract if necessary. The manager also integrates partial results from completed contracts to provide a complete solution to the original task.
The contractors issue reports to the manager, which may be interim reports, or final reports containing a result description. Finally, the manager terminates a contract with a termination message.
Figure 2.5: The contract net protocol.
The messages passed between the agents include information relating to the task, so that other nodes can evaluate whether they are suited to perform that task. For example, when the CNP is applied to the simulation of a distributed sensing system, a task announcement includes three types of information [34], as follows:
The Task Abstraction Slot specifies the identity and position of the manager that enables potential contractors to reply to the task announcement;
The Eligibility Specification specifies the location and capabilities required by any bidders;
The Bid Specification indicates that a bidder must specify its position and its sensing capabilities.
Contractor nodes may, in turn, subcontract parts of their task by announcing their own task announcements. In this way, the CNP is repeated with the contractor eventually becoming a manager for these subcontracts. This leads to a hierarchical configuration in the contract net, as shown in Figure 2.6.
Figure 2.6: The contract net manager-contractor hierarchy.
The contract net protocol was a novel means for dynamically allocating tasks in distributed systems, and it is still commonly found in many agent systems. However, it should be pointed out that it offers a very simple coordination mechanism, and does not provide any strategies for global coherence. It is thus only suited to situations in which the tasks are easily decomposable into independent subtasks. In addition, it is only suitable if agents are not in conflict, since it does not support mechanisms for bargaining or negotiating in general. However, it does serve to illustrate the general principles involved when considering the design of systems from the macrolevel perspective.
2.5.2 Agentis
Agent communication languages (ACLs) occupy a central position in the field of multiagent systems, underpinning the ability of different and heterogeneous agents to effectively interact. Efforts to develop and specify such languages continue, with perhaps the most significant languages to date being FIPA's ACL (see Chapter 5) and KQML, which have received much attention and interest for the last few years. At a basic level, communication languages do not encode information about how a particular message is received and used by a recipient in the context of a broader interaction—the higher-level structure that is required for effective and coherent agent interaction also needs to be investigated. (Some languages, such as FIPA ACL, are also tied to particular interaction protocols; Chapter 5 considers this further.)
The Agentis system is a framework for building interactive applications, and employs a set of just such protocols to ensure the reliable concurrent request and provision of services and tasks from and to agents. This is achieved in the context of an underlying asynchronous point-to-point messaging infrastructure (i.e., the standard one provided by dMARS [35]).
Agentis incorporates an agent interaction model that is based on well-defined notions of services and tasks. Services are units of work performed by Agentis agents. The usual flow of control is that a human user of the system requests one or more services, via a user interface process, from an agent dedicated to serving that user. Agents may also request and provide services from and to other agents, or from other interface processes such as database servers. Tasks are smaller units of work whose performance is part of the service contract that is created when an agent accepts a service request. For example, a user may be obliged to perform one or more information provision tasks to enable an agent to successfully complete a service.
In an Agentis system, a set of standard agents provide predefined services for process control and monitoring, user login and session management, and event logging. There are also user-configurable agents that provide user-defined services (specified in a high-level, dMARS-like, graphical process description language). In addition, a system may contain nonagent interface processes, such as user, database, or WWW interfaces that can request services from, or provide services to, Agentis agents. The framework is designed to be flexible and scalable, and to decouple the specification of custom application-dependent behavior from standard functionality. This makes it easy to design, configure, modify, and extend application systems whose key characteristic is that their behavior may be specified as sets of interactive event-driven or goal-driven processes.
The protocol set provides the ability to request, accept, or decline services and tasks, to return execution status information and output values progressively as they become available, and to cancel, suspend and resume services and tasks prior to completion. In addition, it is designed to guarantee that protocol message collisions are benign, that deadlocks do not occur, and that other constraints, such as the requirement that a task request only occurs in the context of a service provision, are enforced. It also includes a registration facility that provides service description, access control, and the ability for a service provider to inform a requestor about changes in service availability, as well as the ability to send simple notices or queries.
2.5.3 Other Approaches to Macrolevel Organization
Building agents that work together in a society for both individual and social value is clearly fundamental to building robust and effective multiagent systems in general. One such architecture, mentioned earlier, is DECAF, a software environment for the rapid design, development, and execution of intelligent agents to function together effectively in complex domains. This platform provides a means to evaluate such key social concepts as communication, planning, action scheduling, execution monitoring, coordination, and learning [30] The focus of DECAF is not on implementing specific agent architectures nor on building the basic communication primitives but rather on how generic behaviors can be reused, how plans can be easily built using a graphical editor, and how various existing middle-agents can be used.
Similarly, RETSINA [36] is a multiagent infrastructure that comprises a set of services, conventions, and knowledge that enable complex social interactions such as negotiation to take place. In this infrastructure the architecture of the individual agent is not considered, and all that is required is that the agent be "socially aware" and can communicate and interact with others and with the various infrastructural components supplied by RETSINA. It is claimed that the infrastructure can support any coordination scheme such as team behavior (see below), negotiation, and contract nets. What is deliberately not included in the architecture is any notion of social norms [37] [38] [39] [40], which are rules or conventions that a society of agents abide by such as, for example, driving on the correct side of the road in a particular locality. RETSINA does not consider such norms as part of the infrastructure but as being particular to the design of specific multiagent systems. RETSINA is considered in more detail in Chapter 3 in terms of its role as a toolkit.
A final example of macrolevel approaches can be seen in Teamcore. The key motivating principle behind the Teamcore architecture is that an agent integration infrastructure (a set of services and conventions) based on theoretical principles of coordination can automate robust coordination among heterogeneous agents in distributed systems [41]. Existing theories of teamwork on joint intentions and shared plans provide the analytical model for designing coordination that can be used to provide certain guarantees of system behavior. Even with a set of diverse heterogeneous agents, as long as they act as team members, each member acts responsibly to others, covers for execution failures, and exchanges key information as required. Other related work includes the open agent architecture (OAA) [42], a centralized integration architecture, and the adaptive agent architecture (AAA) [43], which provides a distributed extension to OAA.
No comments:
Post a Comment