Hierarchical Task Network Planning with LLM-Generated Heuristics

Researchers demonstrate that large language models can generate effective heuristics for hierarchical task network (HTN) planning, achieving near-optimal performance compared to state-of-the-art planners. LLM-generated heuristics reduce search effort on 83% of benchmark problems, suggesting AI models can enhance algorithmic planning efficiency beyond classical approaches.

This research advances automated planning methodology by leveraging LLMs to generate domain-specific heuristics for HTN planning, a computational approach more complex than classical planning. HTN planning decomposes high-level tasks into executable actions using method libraries, introducing both opportunities for domain knowledge incorporation and computational challenges. Traditional HTN heuristics lag behind classical planning alternatives, creating a performance gap that LLMs appear uniquely positioned to address. The study extends prior work by Corrêa, Pereira, and Seipp from classical to hierarchical planning contexts, using nine different LLMs across six benchmark domains with the Pytrich planner. Results demonstrate that LLM-generated heuristics nearly match the coverage of PANDA, a leading HTN planner, while substantially reducing computational search effort on the majority of shared test problems. This finding suggests LLMs possess latent understanding of domain structure and problem decomposition that translates into practical algorithmic improvements. The methodology relies on domain-specific prompting rather than generic instructions, indicating that carefully crafted prompts unlock LLM capabilities for specialized technical domains. The work has implications for automated planning systems used in robotics, logistics, and autonomous agents, where HTN planning provides interpretable solution paths. However, questions remain regarding computational overhead of LLM inference, scalability to novel domains, and whether improvements justify deployment costs. The research validates that LLMs function effectively as heuristic generators beyond their primary language tasks, opening avenues for applying foundation models to classical computer science problems.

• →LLM-generated heuristics achieve near-optimal HTN planning performance on standard benchmarks
• →Domain-specific prompting enables LLMs to substantially reduce search effort on 83% of planning problems
• →The approach extends classical planning methodology to hierarchical planning, closing a performance gap in existing heuristics
• →Results suggest LLMs possess latent understanding of domain structure applicable to algorithmic optimization
• →Practical deployment requires evaluating LLM inference overhead against computational savings in planning tasks