Single-agent planning searches over one action space. Multi-agent planning must handle interleaved actions, shared resources, and agents whose private information limits what can be centrally optimized. The joint action space grows exponentially with the number of agents. Practical systems cope by decomposing problems, communicating partial plans, and negotiating where conflicts arise. Without structure, planning degenerates into brute-force enumeration or unconstrained chat that never converges.

Hierarchical task networks (HTN) and partial-order planning let you break a goal into subtasks with ordering constraints but flexibility in scheduling. Each agent receives a subplan with preconditions and effects that must mesh with neighbors. In LLM stacks, the orchestrator can produce a DAG of subtasks (JSON), assign owners, and track status. Partial ordering allows parallelism where no dependency exists.

In many settings, agents have private beliefs or goals they cannot or should not reveal (competitive bidding, user privacy, proprietary data). Planning under incomplete information requires either communication protocols that elicit just enough to coordinate, or robust plans that work across plausible private states. In LLM systems, this maps to scoped context: each agent sees only what policy allows, and the orchestrator merges sanitized summaries.

Negotiation lets agents resolve conflicts over resources, schedules, or design choices through iterative proposals. A simple protocol: Agent A proposes, Agent B accepts or counter-proposes, repeat until agreement or deadline. Key parameters: reservation value (walk-away point), concession rate, and deadline pressure. For LLM agents, bound the number of rounds and require structured proposals (JSON with changed fields highlighted) so progress is measurable.

Auctions are structured negotiation: agents bid, a rule picks winners and prices. First-price sealed-bid, Vickrey (second-price), and combinatorial auctions each have different incentive properties. Vickrey encourages truthful bidding (dominant strategy). For multi-agent task allocation, auction rounds can assign jobs to the agent with the lowest cost or highest capability score. Implement as a microservice the orchestrator calls, not as free-form chat.

After agents plan locally, a merge step checks for resource conflicts (two agents booking the same API slot), causal threats (one agent undoing another’s precondition), and ordering violations. Resolution strategies: priority rules, temporal separation, resource duplication, or re-planning the conflicting subgraph. Automate conflict detection with a constraint checker over the merged DAG before execution begins.

Plans fail: tools error, APIs change, teammates crash. Replanning triggers when a monitor detects deviation beyond a threshold. Options: local patch (swap one step), subgraph replan (redo the failing branch), or full replan (expensive, last resort). In LLM multi-agent systems, keep a plan version counter and broadcast invalidation events so all agents know the current truth. Stale plans cause cascading failures.

Multi-agent planning decomposes goals, assigns via negotiation or auction, merges partial plans with conflict checks, and replans when reality drifts. Next chapter: emergence, game theory, and incentives — what happens when agents have their own utility functions and the system’s behavior is more than the sum of its parts.