Davis, R.


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


Knowledge-based systems in artificial intelligence

Classics

Classic Ph.D. dissertations by Randall Davis and Douglas Lenat, reprinted together in one volume. New York: McGraw-Hill.


An overview of production systems

Classics

In E. Elcock and D. Michie (Eds.), Machine intelligence 8. Chichester, England: Ellis Horwood, 300-332.