Multi-robot task planning requires decomposing natural-language instructions into executable actions for heterogeneous robot teams. Conventional Planning Domain Definition Language (PDDL) planners provide rigorous guarantees but struggle to handle ambiguous or long-horizon missions, while large language models (LLMs) can interpret instructions and propose plans but may hallucinate or produce infeasible actions. We present a hierarchical multi-agent LLM-based planner with prompt optimization: an upper layer decomposes tasks and assigns them to lower-layer agents, which generate PDDL problems solved by a classical planner. When plans fail, the system applies TextGrad-inspired textual-gradient updates to optimize each agent's prompt and thereby improve planning accuracy. In addition, meta-prompts are learned and shared across agents within the same layer, enabling efficient prompt optimization in multi-agent settings. On the MAT-THOR benchmark, our planner achieves success rates of 0.95 on compound tasks, 0.84 on complex tasks, and 0.60 on vague tasks, improving over the previous state-of-the-art LaMMA-P by 2, 7, and 15 percentage points respectively. An ablation study shows that the hierarchical structure, prompt optimization, and meta-prompt sharing contribute roughly +59, +37, and +4 percentage points to the overall success rate.
Figures & tables
Fig. 1 : Multi-robot task planning in home environments. Forward step : Decomposing long-horizon tasks using a hierarchical LLM agent structure. Feedback step : Optimizing LLM agent prompts based on results verified by the planner.
Fig. 2 : Overview of the hierarchical MAP framework. The red flows indicate prompt optimization for each agent , while the blue flows denote meta-prompt optimization across layers .
Step
Description
Inputs
Task instruction u ; agents E with prompts θEl,i and meta-prompts θ^l ; maximum iterations Kmax .
Data structures
Plan list Φ , task map Ψ , set of sub-plans (PDDL specifications).
Initialization
Set iteration counter k←0 , Φ←[E0,0] , Ψ(E0,0)←u .
Top-down reasoning
For each layer l=0 to L−1 : each agent El,i decomposes its task into subtasks; leaf agents generate PDDL problems.
Classical planning
Each PDDL problem is solved with a planner; success/failure recorded.
Replanning
Failed agents climb hierarchy by LLM decision (“self” vs. “parent”).
TABLE I : Algorithm overview
Method
Compound
Complex
Vague
SR
GCR
RU
Eff
SR
GCR
RU
Eff
SR
GCR
RU
Eff
CoT [ 23 ] (GPT-4o)
0.32
0.40
0.72
0.59
0.00
0.12
0.47
0.38
0.00
0.00
0.00
0.00
SMART-LLM [ 6 ] (GPT-4o)
0.70
0.82
0.78
0.64
0.20
0.33
0.65
0.56
0.06
0.42
0.68
0.42
LaMMA-P [ 13 ] (GPT-4o)
0.93
0.94
0.91
0.90
0.77
0.83
0.87
0.67
0.45
0.48
0.71
0.65
Ours (GPT-4o)
0.95
0.95
1.00
0.90
0.84
0.84
1.00
0.75
0.60
0.60
1.00
0.75
TABLE II : Performance comparison on MAT-THOR. Higher values are better for all metrics.
Variant
SR
Time
Full method (H+P+M)
0.84
173 s
–H (single-LLM agent)
0.25 (-59.3%)
140 s (-18.9%)
–M (no meta-prompt optimization)
0.80 (-4.2%)
116 s (-33.1%)
–(P, M) (no prompt optimization)
0.47 (-37.0%)
32 s (-81.3%)
TABLE III : Ablation study on our method (GPT-4o). Values are averages over the entire dataset. Both SR (success rate) and Time are reported relative to the full method (H+P+M).
Long-horizon task planning for heterogeneous multi-robot systems is essential for deploying collaborative teams in real-world environments; yet, it remains challenging due to the large volume of perceptual information, much of which is irrelevant to task objectives and burdens planning. Traditional symbolic planners rely on manually constructed problem specifications, limiting scalability and adaptability, while recent large language model (LLM)-based approaches often suffer from hallucinations and weak grounding-i.e., poor alignment between generated plans and actual environmental objects and constraints-in object-rich settings. We present Scale-Plan, a scalable LLM-assisted framework that generates compact, task-relevant problem representations from natural language instructions. Given a PDDL domain specification, Scale-Plan constructs an action graph capturing domain structure and uses shallow LLM reasoning to guide a structured graph search that identifies a minimal subset of relevant actions and objects. By filtering irrelevant information prior to planning, Scale-Plan enables efficient decomposition, allocation, and long-horizon plan generation. We evaluate our approach on complex multi-agent tasks and introduce MAT2-THOR, a cleaned benchmark built on AI2-THOR for reliable evaluation of multi-robot planning systems. Scale-Plan outperforms pure LLM and hybrid LLM-PDDL baselines across all metrics, improving scalability and reliability. Project website: https://github.com/honda-research-institute/Scale_Plan
Piyush Gupta, Sangjae Bae, Jiachen Li +1
Honda Research Institute, San Jose, CA 95134, USA. · Georgia Institute of Technology, Atlanta, GA 30332, USA.
Large Language Models (LLMs) can reason over complex instructions but often fail to satisfy the physical and spatial constraints required for robotic task planning. Recent LLM-based planners directly translate text into action sequences, yet they lack structured reasoning about feasibility, reachability, and logical order, resulting in invalid or incomplete plans. We present a heterogeneous multi-LLM framework that decomposes instructions into atomic reasoning tasks and allocates them to role-specialized expert agents under a token budget for real-world computational and communicational constraints. By combining role-oriented reasoning from heterogeneous agents followed by constraint-driven plan synthesis, HEART validates capability, reachability, and constraint conditions before planning and helps produce physically executable plans while maintaining efficiency. Experiments across different household benchmarks show that HEART consistently improves plan success compared to single-LLM and rule-based planners, demonstrating that heterogeneous LLM collaboration enables robust and scalable robotic task planning under resource constraints.
Junho Lee, Seabin Lee, Wonjong Lee +3
Dept. of Electronic Engineering, Sogang University, Seoul, Korea
Task planning, the problem of sequencing actions to reach a goal from an initial state, is a core capability requirement for autonomous robotic systems. Whether large language models (LLMs) can serve as viable planners alongside classical symbolic methods remains an open question. We present PyPDDLEngine, an open-source Planning Domain Definition Language (PDDL) simulation engine that exposes planning operations as LLM tool calls through a Model Context Protocol (MCP) interface. Rather than committing to a complete action sequence upfront, the LLM acts as an interactive search policy that selects one action at a time, observes each resulting state, and can reset and retry. We evaluate four approaches on 102 International Planning Competition (IPC) Blocksworld instances under a uniform 180-second budget: Fast Downward lama-first and seq-sat-lama-2011 as classical baselines, direct LLM planning (Claude Haiku 4.5), and agentic LLM planning via PyPDDLEngine. Fast Downward achieves 85.3% success. The direct and agentic LLM approaches achieve 63.7% and 66.7%, respectively, a consistent but modest three-percentage-point advantage for the agentic approach at 5.7× higher token cost per solution. Across most co-solved difficulty blocks, both LLM approaches produce shorter plans than seq-sat-lama-2011 despite its iterative quality improvement, a result consistent with training-data recall rather than generalisable planning. These results suggest that agentic gains depend on the nature of environmental feedback. Coding agents benefit from externally grounded signals such as compiler errors and test failures, whereas PDDL step feedback is self-assessed, leaving the agent to evaluate its own progress without external verification.
Kai Göbel, Pierrick Lorang, Patrik Zips +1
AIT Austrian Institute of Technology GmbH, Vienna, Austria