Back to Catalog
Agentic AI
Planning & Control Flow
Distributed Constraint Optimization
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.
Intent & Description
🎯 Intent
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.
💡 Solution
- Cast the problem as a DCOP: each agent owns variables; constraints are factored across agents. - Run a distributed solver: ADOPT for optimal solutions; DPOP, Max-Sum, or local-search heuristics for cheaper approximate solutions. - Each agent communicates only with its 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.
Real-world Use Case
- Several agents hold variables/constraints that cannot be centralised.
- Global cost depends on the joint assignment.
- Some algorithm in the DCOP family fits the cost/quality budget.
Source
Advantages
- Global optimisation without centralising private data.
- Information boundaries respected by construction.
- Algorithm choice tunes communication cost vs solution quality.
Disadvantages
- Optimal algorithms (ADOPT) have exponential worst-case message complexity.
- Constraint factorisation is itself a design problem.
- Heuristic solvers may stall in local optima.