Cooperative distributed problem solving

Cooperative Distributed Problem Solving is a network of semi-autonomous processing nodes working together to solve a problem, typically in a Multi-Agent system. Each node is a sophisticated problem solving system that can modify its behavior as circumstances change and plan its own communication and cooperation strategies with other nodes. Research under the direction of Professor Victor R. Lesser focuses on how to achieve effective cooperation among the agents, balancing several interdependent criteria including efficient use of processor and communication resources, responsiveness to unexpected situations and real-time deadlines, and reliability. This "effective" cooperation must be able to resolve both the uncertainty and the inconsistencies that can arise among the long-term and short-term knowledge held by agents and also to exploit the interdependencies among the subproblems being solved by agents. Three conceptual ideas motivate Lesser's approach to achieving effective coordination: satisficing versus optimality, tolerance of inconsistency, and control intelligence.

The concept of satisficing versus optimality motivates the search for proper balance within problem solving systems. It is impossible to achieve coordination strategies that optimize all the interdependent criteria that go into evaluating the effectiveness of network performance. Rather, what is needed are strategies that achieve an acceptable balance among these criteria: efficient use of communication and processing resources, high reliability, responsiveness to unanticipated situations, and solution optimality. The emphasis is shifted from optimizing the activities in the network to achieving an acceptable performance level of the network as a whole. This approach to viewing effective network problem solving as a balance among a diverse set of criteria is based on the concept of "satisficing" developed by March and Simon to describe human organizational problem solving.

Tolerance of inconsistency allows for the problem-solving task to be undertaken in spite of the state of the knowledge base. An agent's problem solving can be structured so that it is not necessary for its local knowledge bases to be complete, consistent, and up-to-date in order to make progress in its problem solving tasks. Agents do the best they can with their current information and are organized so that error resolution becomes an integral part of network problem solving.

The more sophisticated an agent can be in reasoning about its problem-solving plans, the status of its beliefs, and the implications of its actions on other agents' plans and beliefs, the easier it is to achieve coordinated behavior among agents. The interplay between network and local control is an important ingredient in designing effective coordination strategies. Control intelligence addresses this issue. An important aspect of this research is its empirical orientation. Because of the infancy of the field, there are few existent systems from which ideas and intuitions can be drawn to understand what strategies will be most effective in given situations. Therefore, it is very important for proposed coordination strategies for CDPS to be empirically evaluated.

External link

• http://dis.cs.umass.edu/research/cdps/