Planning in Multi-Agent Systems

Planning a team project means deciding both what must happen and who should do each part. Multi-agent planning adds dependencies, ownership, budgets, and merge points to an ordinary plan.

Goal → task graph → assign owners → execute → observe → replan

What You Will Learn

How a task graph represents steps and dependencies.
How planning and delegation connect without becoming the same concept.
How partial results and failures trigger safe replanning.

Your previous course covered single-agent planning — decomposing a task before diving into individual actions, replanning when new information invalidates the original approach. This module asks what changes once a plan has to account for multiple agents, not just multiple steps.

The difference is worth stating precisely. A single agent’s plan answers “what needs to happen, in what order.” A multi-agent plan answers that same question plus “which agent does each piece, and what happens when one piece fails while the others are still running.”

The shape of a multi-agent plan versus a single-agent one

Single-agent plan

Goal
 ↓
Step 1 → Step 2 → Step 3

Multi-agent plan

Goal
 ↓
Decompose into subtasks, WITH agent assignment
 ↓
┌─────────────┬─────────────┬─────────────┐
Subtask A     Subtask B     Subtask C
(Agent 1)     (Agent 2)     (Agent 3)
     ↓             ↓             ↓
  succeeds      FAILS        succeeds
                   ↓
        Local recovery attempted first
                   ↓
         (only if that fails too)
                   ↓
          Global replan triggered

Notice the multi-agent version has a branch a single-agent plan never needs: when one piece fails, the plan has to decide whether that failure is contained to one agent’s own scope, or whether it changes what every other agent should be doing. That decision — covered in depth later in this module — doesn’t exist at all in a single-agent plan, because there’s only ever one agent whose failure could possibly matter.

Hierarchical Task Networks: the formal foundation

It’s worth knowing the actual, formal planning technique underneath most real multi-agent decomposition, rather than treating “break the task into subtasks” as an informal habit.

Hierarchical Task Network (HTN) planning works with three distinct task types: primitive tasks (directly executable, no further decomposition needed), compound tasks (composed of a set of simpler tasks), and goal tasks (the overall objective). A solution is an executable sequence of primitive tasks, reached by repeatedly decomposing compound tasks into simpler ones until everything left is directly executable. (Multi-agent planning system for controlling non-player agents, USPTO)

A useful property of HTN planning: it can postpone decomposing a subtask until it’s actually about to be executed, rather than fully expanding the entire plan upfront. (Hierarchical Task Network, ScienceDirect) This matters directly for multi-agent systems specifically — if an early subtask’s result might change what a later compound task should even decompose into, fully expanding that later task before you have the information to do it well is wasted planning effort. Lazy decomposition means the plan only gets specific about a piece of work once there’s enough information to do it correctly.

Why this matters concretely, not just in principle

Consider a compound task like “resolve customer complaint,” sitting at the top of a plan before any investigation has happened. Fully decomposing this upfront would require guessing at subtasks — “process refund,” “escalate to manager,” “send apology email” — before knowing which of these the actual complaint requires. Most of that guessed decomposition would be wasted work, and worse, a plan already committed to specific subtasks upfront creates real pressure to force the actual situation to fit them, rather than reassessing once real information arrives.

HTN’s lazy decomposition avoids this specific trap. “Resolve customer complaint” stays a compound task, undecomposed, until an investigation subtask — which can be planned immediately, since it doesn’t depend on anything not yet known — actually runs and returns a real finding. Only then does the plan decompose “resolve customer complaint” into whatever specific subtasks the actual finding warrants. The planning effort spent decomposing happens exactly once, on the version of the problem that’s actually real, not on every version that might have been true before the investigation ran.

It’s worth being honest about a real limitation too: HTN planning is more expressive than simpler planning formalisms in theory, but no hierarchical planner actually achieves that full expressiveness in practice. (ScienceDirect) The formal foundation is useful; it’s not a solved, complete answer, and treating it as one is precisely the kind of overselling this course has tried to avoid at every architectural layer covered so far.

Why a single centralized planner doesn’t scale

This is directly Module 7 and 8’s scaling argument, now applied specifically to the planning step rather than execution generally.

Current research on multi-robot task planning states the problem plainly: relying on “a single centralized LLM planner… leads to computational bottlenecks and a lack of scalability as the number of robots or tasks increases.” (Hierarchical LLM-Based Multi-Agent Framework, arXiv)

This is worth connecting directly to Module 7’s four-worker threshold. A single supervisor’s context overflowing past roughly four workers isn’t just an execution-coordination problem — the planner sitting at the top of that supervisor, trying to reason about every subtask’s decomposition for every worker simultaneously, hits the same wall from the planning side, often before execution coordination does.

The important fix: validate LLM-generated plans with a real planner

This is worth knowing precisely, because it’s a real, concrete answer to a risk this course has warned about since your previous course’s Module 4: an LLM can generate something that looks correct without actually being correct.

Applied to planning specifically: “language models can produce syntactically valid but logically inconsistent [plan specifications] that fail at runtime.” (Hierarchical LLM-Based Multi-Agent Framework, arXiv)

The elegant fix current research uses: LLM agents generate plan specifications in PDDL (Planning Domain Definition Language) — a formal, symbolic representation with precise, checkable semantics — and hand that specification to a classical planner (specifically, one called Fast Downward) to actually compute and validate the plan. The classical planner either returns a executable plan or indicates failure — and critically, if a plan is returned, it’s separately validated by confirming that applying its actions from the initial state achieves the goal. Only after every sub-plan both plans successfully and validates does the overall method terminate successfully. (Hierarchical LLM-Based Multi-Agent Framework, arXiv)

This is worth holding as a general principle beyond this specific implementation: an LLM’s flexible reasoning is excellent at proposing a plan’s shape. A classical, symbolic system’s rigor is what actually confirms that shape is executable — combining them catches exactly the “looked right, wasn’t” failure a purely LLM-generated plan can’t reliably catch on its own.

Local recovery versus global replanning

This is an important distinction most simpler treatments of “replanning” skip entirely, and it’s worth understanding precisely.

Existing multi-agent systems, per recent research, handle failure coarsely — when something breaks, they typically retry the same strategy, reassign the subtask, or revise the entire global plan, without distinguishing failures that could be fixed locally from those that actually require rethinking the whole approach. (Beyond Global Replanning: Hierarchical Recovery for Cross-Device Agent Systems, arXiv)

The fix current research proposes, called H-RePlan, separates these into two distinct layers: device-local strategy recovery — trying an alternative approach within the same agent’s own scope, without touching the broader plan at all — and orchestrator-level global replanning, reserved specifically for failures that can’t be resolved locally. The distinction is enforced through what the researchers call a compact cross-layer failure abstraction — a deliberately minimal signal passed upward only when local recovery has been exhausted, rather than every local hiccup automatically escalating to the orchestrator by default.

Why this distinction matters concretely: a full global replan means re-examining the entire task decomposition, potentially re-delegating work that was already proceeding correctly elsewhere. If an Executor agent’s specific approach to one subtask fails, but a different approach within that same agent’s own scope would fix it, forcing a full global replan is real, unnecessary cost — every other agent’s already-correct work gets needlessly re-evaluated for a problem that was never actually theirs.

A real, named system: dynamic planning with built-in cross-verification

It’s worth grounding this in a concrete, working system rather than only principles. AgentOrchestra runs a top-level Planning Agent that doesn’t execute anything itself — its entire job is high-level reasoning, task decomposition, and adaptive planning, coordinating specialized sub-agents beneath it. (AgentOrchestra, arXiv)

Its Planning Agent maintains a global perspective throughout execution — aggregating feedback from every sub-agent and monitoring progress against the overall objective, which lets it perform dynamic plan updates in real time as intermediate results, unexpected obstacles, or shifting requirements come in, rather than committing to one fixed decomposition upfront. This is worth distinguishing from H-RePlan’s local-recovery layer covered above — AgentOrchestra’s dynamic updates operate at the same global level H-RePlan reserves for plan-shape changes, while local recovery within a single sub-agent’s scope is handled separately, without necessarily surfacing to the Planning Agent at all.

A specific, concrete design choice worth knowing: AgentOrchestra deliberately routes the same underlying question through both a Browser Use Agent (information retrieval) and a Deep Researcher Agent (verification), specifically to enable cross-verification of candidate answers — the paper reports this substantially reduces hallucination risk. This is directly Module 13’s arbitration principle, built into the planning architecture itself rather than added as an afterthought: the plan doesn’t just decompose the work, it deliberately builds in an independent check on itself.

Applying this to the recurring scenario

The legal-contract pipeline’s Planner currently produces one fixed checklist upfront — payment terms, liability, termination — and doesn’t revisit that decomposition once Executors begin work. Running this module’s findings against that design honestly reveals a real gap.

HTN-style lazy decomposition would mean the Planner doesn’t need to fully specify every checklist item’s exact scope upfront — it could postpone deciding exactly how to decompose “liability review” until the contract’s actual liability section is examined, since a unusual liability clause might warrant a different, more granular decomposition than a boilerplate one.

Local versus global replanning applies directly to the pipeline’s actual failure handling from earlier modules. If a single Executor’s approach to one clause fails — say, it can’t parse an unusually formatted payment schedule — a local recovery (the same Executor trying a different extraction approach) is the right first response, not a full replan of the entire checklist. A global replan should be reserved for something that changes the shape of the whole task — discovering, for instance, that the document isn’t actually the contract type the Planner assumed when it built the original checklist.

**Cross-verification, applied deliberately. ** AgentOrchestra’s design choice — routing the same question through two independent agents specifically to catch hallucination — has a direct, natural fit in this pipeline that hasn’t been used yet: for a contract clause carrying high stakes (an unusually large liability cap, say), the Planner could deliberately route that specific clause through two independent Executors rather than one, reserving the Critic’s arbitration authority specifically for reconciling their two readings rather than checking a single Executor’s unverified work.

This wouldn’t be worth the added cost for every clause — Module 6’s aggregation-strategy discipline still applies — but for the highest-stakes items, the same principle that reduces hallucination in AgentOrchestra’s research pipeline applies just as directly here.

Interview-relevant framing

Q: Why does a single centralized planner become a bottleneck as a multi-agent system scales?

Ans: For the same reason a single supervisor does — the planner’s context has to hold enough information about every subtask’s decomposition simultaneously, and that doesn’t scale past a certain point. Current multi-robot planning research names this directly: a single centralized LLM planner leads to computational bottlenecks as the number of agents or tasks grows. The fix mirrors Module 8’s hierarchical answer — distribute planning reasoning across multiple planning agents rather than forcing one planner to hold the entire task’s decomposition at once.

Q: How would you prevent an LLM-generated plan from failing at runtime despite looking correct?

Ans: By not trusting the LLM’s plan as final on its own. Current research has LLM agents generate plan specifications in a formal language like PDDL, then hands that specification to a classical, symbolic planner to actually compute and validate the plan — confirming the proposed actions achieve the goal from the initial state, not just that they read as plausible. This catches exactly the failure mode where a plan is syntactically valid but logically inconsistent, which an LLM alone has no reliable way to self-detect.

A third question worth preparing for:

Q: When should a plan failure trigger local recovery instead of a full global replan?

Ans: When the failure is contained to what one agent is responsible for, and a different approach within that same agent’s scope would plausibly fix it — an Executor trying an alternate extraction method for an oddly-formatted field, say. A full global replan should be reserved for failures that change the actual shape of the task itself, like discovering a fundamental assumption the original decomposition was built on turned out to be wrong.

Treating every failure as grounds for a global replan means re-evaluating every other agent’s already-correct work for a problem that was never theirs — real, unnecessary cost H-RePlan’s two-layer approach was specifically designed to avoid.

Common Misconception

Incorrect idea: A planner can create the complete correct plan before work begins.

Why it is incorrect: Tool results, failures, and discoveries change dependencies. Plans should guide work while remaining observable and revisable.

Key takeaways

A multi-agent plan answers a harder question than a single-agent plan — not just what needs to happen, but which agent does each piece and what happens when one piece fails while others continue.
Hierarchical Task Network planning formalizes decomposition into primitive, compound, and goal tasks, with a useful lazy-decomposition property — postponing a subtask’s detailed planning until it’s actually about to execute, rather than fully expanding everything upfront.
A single centralized LLM planner hits the same scaling wall Module 7 and 8 already described for supervisors — computational bottlenecks and reduced scalability as agent or task count grows.
LLM-generated plans can be syntactically valid but logically inconsistent — current research addresses this by having LLMs generate formal PDDL specifications, validated by a classical planner before execution, rather than trusting the LLM’s plan directly.
Existing systems handle plan failures too coarsely by default — retrying, reassigning, or fully replanning without distinguishing failures fixable locally from those requiring a global replan.
H-RePlan’s two-layer approach — device-local recovery separated from orchestrator-level global replanning — avoids the real cost of re-evaluating already-correct work across the entire system for a problem that was contained to one agent.
AgentOrchestra’s real Planning Agent maintains dynamic plan updates in real time and deliberately routes questions through multiple sub-agents for cross-verification — building Module 13’s arbitration principle directly into the planning architecture itself.

Taken together, these findings point at a unifying lesson: planning in a multi-agent system is not simply single-agent planning done several times over. It’s a distinct discipline with its own formal foundations, its own scaling limits, and its own failure taxonomy — worth the same deliberate design attention this course has already given to communication, coordination, and delegation.

Module 15 turns from the two dominant architectures already covered — supervisor and hierarchical — to the rest of the named pattern catalog: pipeline, debate, voting, critic/reviewer, planner/executor, blackboard, event-driven, and hybrid architectures — each with its own niche where it outperforms the patterns you already know well.

Author: TechByteByByte Editorial Team
Reviewed by: TechByteByByte Admin
Published: August 31, 2026
Last reviewed: August 31, 2026