Hierarchical Task Network Planning with LLM-Generated Heuristics

• URL: http://arxiv.org/abs/2605.07707v1
• Date: Fri, 08 May 2026 13:14:31 GMT
• Title: Hierarchical Task Network Planning with LLM-Generated Heuristics
• Abstract summary: We investigate whether large language models (LLMs) can generate effective search algorithms for HTN planning.<n>LLMs nearly match the coverage of the best available HTN planner, while substantially reducing search effort on 83% of shared problems.
• Score: 45.222898125439286
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: HTN planning is a variation of classical planning where, instead of searching for a linear sequence of actions, an algorithm decomposes higher-level tasks using a method library until only executable actions remain. On one hand, this allows one to introduce domain knowledge that can speed up the search for a solution through the method library. On the other hand, it creates challenges that go beyond those of classical state-space search. While recent research produced a number of heuristics and novel algorithms that speed up HTN planning, these heuristics are not yet as informative as those available in classical planning algorithms. We investigate whether large language models (LLMs) can generate effective search heuristics for HTN planning, extending the methodology of Corrêa, Pereira, and Seipp (2025) from classical to hierarchical planning. Using the Pytrich planner on six standard total-order HTN benchmark domains, we evaluate heuristics generated by nine LLMs under domain-specific prompting and compare them against the TDG and LMCount domain-independent baselines and the PANDA planner. Our results show that LLM-generated heuristics nearly match the coverage of the best available HTN planner, while substantially reducing search effort on 83% of shared problems.

Related papers

• LLM-Evolved Pattern Generators for Optimal Classical Planning [2.432409923443071]
  We present the first method for learning domain-dependentmisss that are admissible by design and thus the optimality guarantees of A* search.<n>We use an evolutionary program-synthesis framework to obtain, for each domain, a program that produces a pattern collection for any task in that domain, and we combine the resulting patterns admissibly via saturated cost.
  arXiv  Detail & Related papers  (2026-06-01T16:10:20Z)
• Closing the Train-Test Gap in World Models for Gradient-Based Planning [64.36544881136405]
  We propose improved methods for training world models that enable efficient gradient-based planning.<n>At test time, our approach outperforms or matches the classical gradient-free cross-entropy method.
  arXiv  Detail & Related papers  (2025-12-10T18:59:45Z)
• GridRoute: A Benchmark for LLM-Based Route Planning with Cardinal Movement in Grid Environments [14.584687937592536]
  Large Language Models (LLMs) have demonstrated their potential in planning and reasoning tasks.<n>We propose a comprehensive evaluation benchmark GridRoute to assess how LLMs can take advantage of traditional algorithms.<n>We also propose a novel hybrid prompting technique called Algorithm of Thought (AoT) which introduces traditional algorithms' guidance into prompting.
  arXiv  Detail & Related papers  (2025-05-30T07:40:59Z)
• Leveraging Action Relational Structures for Integrated Learning and Planning [0.0]
  We introduce partial-space search, a new search space for classical planning.<n>To guide partial-space search, we introduce action sets that evaluate sets of actions in a state.<n>Our new planner, LazyLifted, exploits our better integrated search and learnings and outperforms the state-of-the-art ML-based on IPC 2023 benchmarks.
  arXiv  Detail & Related papers  (2025-04-29T00:10:14Z)
• Classical Planning with LLM-Generated Heuristics: Challenging the State of the Art with Python Code [6.88204255655161]
  Large language models (LLMs) fail to plan reliably, even when prompted with a detailed definition of a planning task.<n>We show how to use LLMs to generate correct plans, even for out-of-distribution tasks of increasing size.
  arXiv  Detail & Related papers  (2025-03-24T15:50:20Z)
• Parallel Strategies for Best-First Generalized Planning [51.713634067802104]
  Generalized planning (GP) is a research area of AI that studies the automated synthesis of algorithmic-like solutions capable of solving multiple classical planning instances. One of the current advancements has been the introduction of Best-First Generalized Planning (BFGP), a GP algorithm based on a novel solution space that can be explored with search. This paper evaluates the application of parallel search techniques to BFGP, another critical component in closing the performance gap.
  arXiv  Detail & Related papers  (2024-07-31T09:50:22Z)
• Exploring and Benchmarking the Planning Capabilities of Large Language Models [57.23454975238014]
  This work lays the foundations for improving planning capabilities of large language models (LLMs) We construct a comprehensive benchmark suite encompassing both classical planning benchmarks and natural language scenarios. We investigate the use of many-shot in-context learning to enhance LLM planning, exploring the relationship between increased context length and improved planning performance.
  arXiv  Detail & Related papers  (2024-06-18T22:57:06Z)
• Sequence-Based Plan Feasibility Prediction for Efficient Task and Motion Planning [36.300564378022315]
  We present a learning-enabled Task and Motion Planning (TAMP) algorithm for solving mobile manipulation problems in environments with many articulated and movable obstacles. The core of our algorithm is PIGINet, a novel Transformer-based learning method that takes in a task plan, the goal, and the initial state, and predicts the probability of finding motion trajectories associated with the task plan.
  arXiv  Detail & Related papers  (2022-11-03T04:12:04Z)
• TaSPM: Targeted Sequential Pattern Mining [53.234101208024335]
  We propose a generic framework namely TaSPM, based on the fast CM-SPAM algorithm. We also propose several pruning strategies to reduce meaningless operations in mining processes. Experiments show that the novel targeted mining algorithm TaSPM can achieve faster running time and less memory consumption.
  arXiv  Detail & Related papers  (2022-02-26T17:49:47Z)
• Divide-and-Conquer Monte Carlo Tree Search For Goal-Directed Planning [78.65083326918351]
  We consider alternatives to an implicit sequential planning assumption. We propose Divide-and-Conquer Monte Carlo Tree Search (DC-MCTS) for approximating the optimal plan. We show that this algorithmic flexibility over planning order leads to improved results in navigation tasks in grid-worlds.
  arXiv  Detail & Related papers  (2020-04-23T18:08:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.