To coordinate as an effective team, cooperating problem solvers must negotiate over their use of local resources, information, and expertise. Sometimes they negotiate to decide which local problem-solving tasks to pursue, while at other they negotiate over the decomposition and distribution of tasks. The problem solving nodes in a network should coordinate their use of distributed resources, physiscal or informational. Contracting, as intorduced by Davis and Smith (1963) solved the connection problem such that a node could decompose a large problem into subproblems, announce them to the network for bids, and awards the suproblem to the best suited node, where they might again contract recursively. However, negotiation and partial global planning evolve on this notion and introduce the concept of shared plans; improving agreement (reducing inconsistency and uncertainty) on common viewpoints through the structured exchange of relevant information. This paper describes how partial global planning provides a versatile framework for negotiating in several different ways for different reasons in order to let proplem solvers decompose and transfer tasks to improve joint performance. They also propose how their approach could be extended to capture even more of the complexity and merit of negotiation as a tool for coordination. Multiagent problems continue to be a field of development and investigation, but the notion of negotiation incorporates some of our useful economic tools from Game Theory, and in combination with more complex implementations like policies could yield some fascinating new directions.
Durfee, E.H. and Lesser, V.R. Negotiating Task Decomposition and Allocation Using Partial Global Planning. Distributed Artificial Intelligence, Volume 2, Gasser & Huhns, ed., Pitman Publishing Ltd., pp. 229-243. 1989.
The Society of Mind as developed by Marvin Minsky is both a book and a theory of natural intelligence. In his book, the principal goal is the construction of a model for human intelligence step by step, built up from the interactions of simple parts of mindless, objective agents whose interactions constitute a "society of mind". This book tries to explain how minds work, and how intelligence can emerge from nonintelligence, by building a mind from many little agents, each mindless by itself; hence the title "Society of Mind". Within this schema each mind is made of many smaller processes, where ach mental agent by itself can only do one simple thing that needs no mind or thought at all. However, when we join these agents in societies-in certain very special ways-this leads to intelligence. This is not a technical book, but it is itself a society of many small ideas; each of which applies only common sense. In this book, Minsky asks how something as solid as brain could come up with something as ghostly as thought. He posits the answer depends on how you look at it, and by using two different words, "agent" and "agency' we can say as agency, it can perform complex tasks, but as an agent, it knows nothing at all outside its immediate capability. Perhaps the only trouble with this model that the author admits up front is that his model necessitates alot of cross-connections and non-linearity, implying there is perhaps no tidy base of neatly ordered principles and that complexity is what we must expect from nature. In any case, the aim of explaining intelligence as a combination of simpler things is in many ways the very simplest definition of Artificial Intelligence, and it seems this book had a lot to do with making that happen.
STRIPS (Stanford Research Institute Problem Solver) is an automated planner developed by Richard Fikes and Nils Nilsson in 1971 at SRI International. STRIPS represents a world as a collection of first-order predicated calculus formulas, which are designed to work with models consisting of large arrays of formulas. It employs a resolution theorem prover to answer questions of particular models and uses means-ends analysis to guide itself to the desired goal-satisfying model. A STRIPS instance is composed of an initial state, the specification of the goal states – situations which the planner is trying to reach, a set of actions. For each action, the following are included: preconditions (what must be established before the action is performed); postconditions (what is established after the action is performed).Deciding whether any plan exists for a propositional STRIPS instance is PSPACE-complete. Various restrictions can be enforced in order to decide if a plan exists in polynomial time or at least make it an NP-complete problem. This sounds remarkably similar to the approach we covered here in the material regarding Classic Planning, implying that the creation of this convention is a primary moment in the foundation of AI.