Smith, R. G.


Negotiation as a metaphor for distributed problem solving

Classics

"We describe the concept of distributed problem solving and define it as the cooperative solution of problems by a decentralized and loosely coupled collection of problem solvers. This approach to problem solving offers the promise of increased performance and provides a useful medium for exploring and developing new problem-solving techniques.We present a framework called the contract net that specifies communication and control in a distributed problem solver. Task distribution is viewed as an interactive process, a discussion carried on between a node with a task to be executed and a group of nodes that may be able to execute the task. We describe the kinds of information that must be passed between nodes during the discussion in order to obtain effective problem-solving behavior. This discussion is the origin of the negotiation metaphor: Task distribution is viewed as a form of contract negotiation.We emphasize that protocols for distributed problem solving should help determine the content of the information transmitted, rather than simply provide a means of sending bits from one node to another.The use of the contract net framework is demonstrated in the solution of a simulated problem in area surveillance, of the sort encountered in ship or air traffic control. We discuss the mode of operation of a distributed sensing system, a network of nodes extending throughout a relatively large geographic area, whose primary aim is the formation of a dynamic map of traffic in the area.From the results of this preliminary study we abstract features of the framework applicable to problem solving in general, examining in particular transfer of control. Comparisons with PLANNER, CONNIVER, HEARSAY-II, AND PUP6 are used to demonstrate that negotiation—the two-way transfer of information—is a natural extension to the transfer of control mechanisms used in earlier problem-solving systems."Artificial Intelligence: 20:63-109


Frameworks for cooperation in distributed problem solving

Classics

"Two forms of cooperation in distributed problem solving are considered: task-sharing and result-sharing. In the former, nodes assist each other by sharing the computational load for the execution of subtasks of the overall problem. In the latter, nodes assist each other by sharing partial results which are based on somewhat different perspectives on the overall problem. Different perspectives arise because the nodes use different knowledge sources (KS’s) (e.g., syntax versus acoustics in the case of a speech-understanding system) or different data (e.g., data that is sensed at different locations in the case of a distributed sensing system). Particular attention is given to control and to internode communication for the two forms of cooperation. For each, the basic methodology is presented and systems in which it has been used are described. The two forms are then compared and the types of applications for which they are suitable are considered."Direct link to PDF.IEEE Transactions on Systems, Man, and Cybernetics, SMCll(l):61-70


The contract net protocol: High-level communication and control in a distributed problem solver

Classics

"The contract net protocol has been developed to specify problem-solving communication and control for nodes in a distributed problem solver. Task distribution is affected by a negotiation process, a discussion carried on between nodes with tasks to be executed and nodes that may be able to execute those tasks. We present the specification of the protocol and demonstrate its use in the solution of a problem in distributed sensing. The utility of negotiation as an interaction mechanism is discussed. It can be used to achieve different goals, such as distributing control and data to avoid bottlenecks and enabling a finer degree of control in making resource allocation and focus decisions than is possible with traditional mechanisms."Direct link to PDF.IEEE Transactions on Computers C-29(12):1104-1113


Models of learning systems

Classics

Data base Adaptive Concept Management control formation systems systems systems alter alter alter assertions parameters structures Figure 1. A "learning system" is an adaptive system that responds acceptably within some time interval following a change in its environment, and a "self-repairing system" is one that responds acceptably within some time interval following a change in its internal structure. This approach was designed to utilize the existing arsenal of control techniques requiring exact specification of the plant. Two broad techniques exist for establishment of convergent control parameter adaptation schemes: search methods and stability analysis.


Models of learning systems

Classics

"The terms adaptation, learning, concept-formation, induction, self-organization, and self-repair have all been used in the context of learning system (LS) research. The research has been conducted within many different scientific communities, however, and these terms have come to have a variety of meanings. It is therefore often difficult to recognize that problems which are described differently may in fact be identical. Learning system models as well are often tuned to the require- ments of a particular discipline and are not suitable for application in related disciplines."In Encyclopedia of Computer Science and Technology, Vol. 11. Dekker


A Framework for Problem Solving in a Distributed Processing Environment

Classics

"The concept of distributed problem solving, or the cooperative solution of problems by a decentralized and loosely-coupled collection of knowledge-sources that operates in a distributed processor architecture is presented. Such architectures offer high-speed, reliable computation at low cost and are an effective way to utilize the new LSI processors and the developments of the recent synthesis of computer and communications technology.A conceptual framework called the contract net framework that specifies communications, control, and knowledge organization has been developed. Task distribution is viewed as an interactive process, a discussion carried on between a node with a task to be executed and a group of nodes that may be able to execute the task. This is the origin of the contract metaphor for control, where task distribution corresponds to contract negotiation.The types of knowledge used in such a problem solver are discussed, together with the ways that the knowledge is indexed within an individual node and distributed among the collection of nodes. The use of two primary types of knowledge (referred to as task-centered and knowledge-source centered) is shown.We illustrate the kinds of information that must be passed between nodes in the distributed processor in order to carry out task and data distribution. We suggest that a common internode language is required and that the task-specific expertise required by a processsor node can be obtained by internode transfer of procedures and data.The use of the contract net framework is demonstrated with two implemented examples: search in the context of the N Queens problem and area surveillance by a Distributed Sensing System. Consideration is also given to the implementation of a number of familiar Artificial Intelligence problem solvers.Features of the framework applicable to problem solving in general are abstracted from the results of this preliminary study. Comparisons with PLANNER, CONNIVER, HEARSAY-II and PUP6 are used to demonstrate that negotiation, the two-way transfer of information combined with mutual selection prior to invocation, is a natural extension to the control mechanisms used in earlier problem-solving systems."See also: IJCAI-77 paperPh.D. thesis, Stanford University