II · Planning & Control FlowExperimental·

Distributed Constraint Optimization

also known as DCOP, ADOPT, Distributed Constraint Reasoning

A group of agents jointly assigns values to shared variables to minimise (or maximise) a global cost defined by inter-agent constraints, exchanging only the messages needed.

Context

Several agents each hold private variables and constraints — meeting scheduling across users who don't want to expose calendars, resource allocation across teams that don't share budgets, sensor coordination across nodes that can't centralise. The global cost depends on all variables, but no single agent has the right to see them all.

Problem

Centralising the whole problem is the easy answer but often illegal, expensive, or politically infeasible. Each agent solving locally produces solutions that violate global constraints. Without a distributed coordination algorithm that respects information boundaries, the team cannot find a global-cost-minimising assignment without surrendering privacy or autonomy.

Forces

  • Information cannot or should not be fully centralised.
  • Local optima may violate global constraints.
  • Message-passing has cost; communication must be bounded.
  • Some algorithms guarantee global optimum (ADOPT) at high message cost; others are heuristic and faster.

Example

Five team-calendar agents schedule a recurring cross-team meeting without exposing individual calendars. Each agent owns a variable (proposed slot) constrained by no-overlap with its team's commitments. They run Max-Sum: each agent proposes locally, exchanges aggregate cost messages with neighbours, and converges on a slot that minimises total conflict across teams without anyone seeing another team's calendar.

Diagram

Solution

Therefore:

Cast the problem as a DCOP: each agent owns variables; constraints are factored across agents. Run a distributed solver (ADOPT for optimal, DPOP, Max-Sum, or local-search heuristics for cheaper). Each agent communicates only with constraint-neighbours. The algorithm terminates with each agent holding an assignment that is consistent with the others and minimises (or approximately minimises) global cost. For LLM-agent applications, the LLM may serve as a propose-and-evaluate step at each agent, with a small DCOP-like backbone enforcing global consistency.

What this pattern forbids. Joint problems must not be centralised when information boundaries forbid it; agents exchange only the messages a distributed solver requires.

And the patterns that stand alongside it, or against it —

  • complementsPartial Global Planning·— Each agent maintains a partial view of others' plans and incrementally merges local plans into a shared partial global plan, interleaving coordination with execution.
  • alternative-toBlackboard·— Give multiple agents a shared, queryable workspace they can read from and write to as they collaborate.
  • alternative-toSupervisor★★— Place a coordinating agent above a set of specialised agents and route work to them.
  • complementsContract Net Protocol★★— Classical bid-based multi-agent task allocation: a manager broadcasts a task announcement, contractors submit bids, and the manager awards the contract to the best bid.
  • alternative-toWorld Model as Tool·— Let a planning agent invoke a generative world model as a tool to roll out hypothetical futures before committing to an action, treating the world model as a callable simulator rather than a training target.
  • alternative-toStigmergic Coordination★★— Agents coordinate indirectly by leaving and reading marks in a shared environment (files, queues, scratchpads, world model) so that one agent's trace stimulates another's next action, with no direct messaging.

Neighbourhood

Click any neighbour to follow the language. Scroll to zoom, drag to pan.

Used in recipes

References

Provenance