# HBTP: Heuristic Behavior Tree Planning with Large Language Model Reasoning

arXiv: https://arxiv.org/abs/2406.00965 · HTML: https://mlsanity.com/paper/2406.00965/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Placed in Spatial and embodied reasoning, one of 17 directions in LLM reasoning.
- Builds on 26 of its 47 references that are in the map.
- First posted on arXiv 3 Jun 2024.

## Placed in

- LLM reasoning / [Spatial and embodied reasoning](https://mlsanity.com/lr/spatial-and-embodied-reasoning/)

## Builds on (most cited first, 26 of 26)

- [Do As I Can, Not As I Say: Grounding Language in Robotic Affordances](https://mlsanity.com/paper/2204.01691/) (2022)
- [Voyager: An Open-Ended Embodied Agent with Large Language Models](https://mlsanity.com/paper/2305.16291/) (2023)
- [ProgPrompt: Generating Situated Robot Task Plans using Large Language Models](https://mlsanity.com/paper/2209.11302/) (2022)
- [Towards Reasoning in Large Language Models: A Survey](https://mlsanity.com/paper/2212.10403/) (2022)
- [LLM+P: Empowering Large Language Models with Optimal Planning Proficiency](https://mlsanity.com/paper/2304.11477/) (2023)
- [LLM-Planner: Few-Shot Grounded Planning for Embodied Agents with Large Language Models](https://mlsanity.com/paper/2212.04088/) (2022)
- [VirtualHome: Simulating Household Activities via Programs](https://mlsanity.com/paper/1806.07011/) (2018)
- [PlanBench: An Extensible Benchmark for Evaluating Large Language Models on Planning and Reasoning about Change](https://mlsanity.com/paper/2206.10498/) (2022)
- [On the Planning Abilities of Large Language Models : A Critical Investigation](https://mlsanity.com/paper/2305.15771/) (2023)
- [Teaching Large Language Models to Reason with Reinforcement Learning](https://mlsanity.com/paper/2403.04642/) (2024)
- [Behavior Trees in Robotics and AI: An Introduction](https://mlsanity.com/paper/1709.00084/) (2017)
- [SayCanPay: Heuristic Planning with Large Language Models using Learnable Domain Knowledge](https://mlsanity.com/paper/2308.12682/) (2023)
- [Learning Domain-Independent Heuristics for Grounded and Lifted Planning](https://mlsanity.com/paper/2312.11143/) (2023)
- [GeRM: A Generalist Robotic Model with Mixture-of-experts for Quadruped Robot](https://mlsanity.com/paper/2403.13358/) (2024)
- [LLM-BRAIn: AI-driven Fast Generation of Robot Behaviour Tree based on Large Language Model](https://mlsanity.com/paper/2305.19352/) (2023)
- [Towards Blended Reactive Planning and Acting using Behavior Trees](https://mlsanity.com/paper/1611.00230/) (2016)
- [LLM-MARS: Large Language Model for Behavior Tree Generation and NLP-enhanced Dialogue in Multi-Agent Robot Systems](https://mlsanity.com/paper/2312.09348/) (2023)
- [Learning of Behavior Trees for Autonomous Agents](https://mlsanity.com/paper/1504.05811/) (2015)
- [Behavior Trees in Robot Control Systems](https://mlsanity.com/paper/2203.13083/) (2022)
- [Integrating Intent Understanding and Optimal Behavior Planning for Behavior Tree Generation from Human Instructions](https://mlsanity.com/paper/2405.07474/) (2024)
- [A Framework for Constrained and Adaptive Behavior-Based Agents](https://mlsanity.com/paper/1506.02312/) (2015)
- [Efficient Model-agnostic Alignment via Bayesian Persuasion](https://mlsanity.com/paper/2405.18718/) (2024)
- [Designing Behavior Trees from Goal-Oriented LTLf Formulas](https://mlsanity.com/paper/2307.06399/) (2023)
- [Task2Morph: Differentiable Task-inspired Framework for Contact-Aware Robot Design](https://mlsanity.com/paper/2403.19093/) (2024)
- [Heuristics for Planning, Plan Recognition and Parsing](https://mlsanity.com/paper/1605.05807/) (2016)
- [Meta-Reinforcement Learning for Heuristic Planning](https://mlsanity.com/paper/2107.02603/) (2021)

## Built on by (most cited first, 4 of 4)

- [From Prompts to Pavement: LMMs-based Agentic Behavior-Tree Generation Framework for Autonomous Vehicles](https://mlsanity.com/paper/2601.12358/) (2026)
- [Decoupled Travel Planning with Behavior Forest](https://mlsanity.com/paper/2604.21354/) (2026)
- [CABTO: Context-Aware Behavior Tree Grounding for Robot Manipulation](https://mlsanity.com/paper/2603.16809/) (2026)
- [SharedKV-BT: Node-Local Typed Decisions for Behavior-Tree Agents](https://mlsanity.com/paper/2610.07327/) (2026)

## Abstract (arXiv)

Behavior Trees (BTs) are increasingly becoming a popular control structure in robotics due to their modularity, reactivity, and robustness. In terms of BT generation methods, BT planning shows promise for generating reliable BTs. However, the scalability of BT planning is often constrained by prolonged planning times in complex scenarios, largely due to a lack of domain knowledge. In contrast, pre-trained Large Language Models (LLMs) have demonstrated task reasoning capabilities across various domains, though the correctness and safety of their planning remain uncertain. This paper proposes integrating BT planning with LLM reasoning, introducing Heuristic Behavior Tree Planning (HBTP)-a reliable and efficient framework for BT generation. The key idea in HBTP is to leverage LLMs for task-specific reasoning to generate a heuristic path, which BT planning can then follow to expand efficiently. We first introduce the heuristic BT expansion process, along with two heuristic variants designed for optimal planning and satisficing planning, respectively. Then, we propose methods to address the inaccuracies of LLM reasoning, including action space pruning and reflective feedback, to further enhance both reasoning accuracy and planning efficiency. Experiments demonstrate the theoretical bounds of HBTP, and results from four datasets confirm its practical effectiveness in everyday service robot applications.