II · Planning & Control FlowExperimental·

Partial Global Planning

also known as PGP, Durfee-Lesser 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.

Context

A multi-agent system coordinates on a problem where a complete global plan is impractical to compute — the problem is too large, the world is non-stationary, or agents only learn what they need to coordinate as they go. Waiting for a global plan to complete before any agent acts is unworkable.

Problem

Centralised global planning hits scaling limits and is fragile to change. Fully local planning produces inconsistent action choices that violate global constraints. Without an intermediate — a plan that is partial in coverage and global in scope, refined incrementally as agents share what they know — the team either pauses for impossible centralisation or acts inconsistently in isolation.

Forces

  • Complete global plans are often infeasible to compute or maintain.
  • Local plans alone produce inconsistent global behaviour.
  • Agents have incentives to share plan fragments only when coordination benefits exceed cost.
  • Plan revision must propagate without thrashing.

Example

A fleet of research agents investigates a sprawling open question. Each holds a partial plan over its sub-area plus the fragments it has received about adjacent sub-areas. When agent A discovers its sub-area's evidence reframes the global picture, it revises its fragment and shares with the agents whose fragments referenced it. The team never produces a single global research plan; it produces overlapping partial plans that stay consistent enough.

Diagram

Solution

Therefore:

Each agent runs a planner that produces both local actions and partial-global-plan fragments. Agents periodically exchange fragments with neighbours; merging produces consistent shared plan structure for the parts agents care about. When new observations or revisions arrive, the affected fragment is updated and shared again. The team never holds a complete global plan; it holds a sufficient partial one. Execution and planning interleave.

What this pattern forbids. Multi-agent coordination must not wait for a complete global plan; agents exchange and merge partial-global-plan fragments while continuing to act.

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

  • complementsDistributed 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.
  • complementsBlackboard·— Give multiple agents a shared, queryable workspace they can read from and write to as they collaborate.
  • complementsWorld 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-toHierarchical Agents★★— Organise agents in a tree where higher-level agents decompose tasks for lower-level agents, recursively.
  • alternative-toPlan-and-Execute★★— Plan all the steps once with a strong model, then execute each step with a cheaper model under the plan.
  • complementsJoint Commitment Team·— A team of agents adopts a shared goal plus the meta-commitment that each member will notify the others as soon as it believes the goal is achieved, impossible, or no longer relevant.

Neighbourhood

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

Used in recipes

References

Provenance