Distributed Problem Solving

Distributed problem solving studies how a problem can be solved by multiple agents, each holding part of the information or responsibility, that communicate and combine their partial results into a global solution.

Definition

Distributed problem solving is the cooperative solution of a problem by a group of agents, each with local knowledge or subproblems, that coordinate through communication to produce a coherent overall solution.

Scope

This topic covers cooperative problem solving across agents that share no central controller: task and result sharing, distributed constraint satisfaction and optimization (DCSP/DCOP) with algorithms such as asynchronous backtracking, and the coordination of partial solutions under communication and privacy constraints. It addresses how decomposition, local computation, and message passing yield globally consistent solutions. Purely competitive interaction and incentive design are covered under game theory and mechanism design.

Core questions

• How is a problem decomposed and distributed among agents with partial views?
• How do agents share tasks and intermediate results to build a global solution?
• How is a constraint problem solved when variables and constraints are spread across agents?
• How are communication cost and local autonomy balanced against solution quality?

Key concepts

• problem decomposition
• task sharing and result sharing
• distributed constraint satisfaction (DCSP)
• distributed constraint optimization (DCOP)
• asynchronous backtracking
• message passing
• local autonomy and privacy
• global consistency

Key theories

Distributed constraint satisfaction and optimization

Distributed constraint satisfaction (DCSP) and optimization (DCOP) generalize constraint problems to settings where variables and constraints are held by different agents, solved by algorithms in which agents asynchronously exchange value assignments and conflict information.

Task sharing and result sharing

Cooperative distributed problem solving proceeds by decomposing and distributing tasks and by exchanging partial results that agents integrate, allowing a group to solve problems no single agent could solve alone.

Asynchronous distributed search

Algorithms such as asynchronous backtracking let agents search for a consistent global assignment without central control, using prioritized message passing to resolve conflicts while preserving local autonomy.

Clinical relevance

Distributed problem solving applies to multi-sensor surveillance and tracking, distributed scheduling and meeting coordination, power-grid and traffic management, and any setting where data or responsibility is naturally spread across agents that must jointly find a consistent solution while limiting communication.

History

Cooperative distributed problem solving was a founding theme of distributed AI, exemplified by the 1980s work on distributed sensor networks and blackboard systems. Yokoo and colleagues formalized distributed constraint satisfaction in the 1990s, and distributed constraint optimization later became a major framework for cooperative multi-agent decision making.

Key figures

• Edmund H. Durfee
• Victor R. Lesser
• Makoto Yokoo
• Daniel D. Corkill

Seminal works

• yokoo1998
• durfee1989

Frequently asked questions

How is distributed problem solving different from parallel computing?

Parallel computing typically splits a problem across processors under central control to go faster. Distributed problem solving assumes autonomous agents with their own local knowledge and possibly privacy or communication constraints, so the challenge is coordination and reaching a coherent solution, not just speed.

What is a distributed constraint optimization problem?

It is a constraint problem in which the variables and constraints are owned by different agents, and the agents must cooperatively assign values to optimize a global objective (such as minimizing total cost) while communicating only locally. It models many cooperative coordination tasks among agents.