# Extended Tree Search for Robot Task and Motion Planning

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 31 references that are in the map.
- First posted on arXiv 9 Mar 2021.

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

- [Integrated Task and Motion Planning](https://mlsanity.com/paper/2010.01083/) (2020)
- [PDDLStream: Integrating Symbolic Planners and Blackbox Samplers via Optimistic Adaptive Planning](https://mlsanity.com/paper/1802.08705/) (2018)
- [FFRob: Leveraging Symbolic Planning for Efficient Task and Motion Planning](https://mlsanity.com/paper/1608.01335/) (2016)
- [Anytime Integrated Task and Motion Policies for Stochastic Environments](https://mlsanity.com/paper/1904.13006/) (2019)

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

- [Learning Neuro-Symbolic Skills for Bilevel Planning](https://mlsanity.com/paper/2206.10680/) (2022)
- [Predicate Invention for Bilevel Planning](https://mlsanity.com/paper/2203.09634/) (2022)
- [Sequence-Based Plan Feasibility Prediction for Efficient Task and Motion Planning](https://mlsanity.com/paper/2211.01576/) (2022)
- [Learning to Reason over Scene Graphs: A Case Study of Finetuning GPT-2 into a Robot Language Model for Grounded Task Planning](https://mlsanity.com/paper/2305.07716/) (2023)
- [VerifyLLM: LLM-Based Pre-Execution Task Plan Verification for Robots](https://mlsanity.com/paper/2507.05118/) (2025)
- [Learning to Search in Task and Motion Planning with Streams](https://mlsanity.com/paper/2111.13144/) (2021)
- [Accelerating Integrated Task and Motion Planning with Neural Feasibility Checking](https://mlsanity.com/paper/2203.10568/) (2022)
- [Coarse-to-fine Q-attention with Tree Expansion](https://mlsanity.com/paper/2204.12471/) (2022)
- [Graph-based Reinforcement Learning meets Mixed Integer Programs: An application to 3D robot assembly discovery](https://mlsanity.com/paper/2203.04120/) (2022)
- [STAMP: Differentiable Task and Motion Planning via Stein Variational Gradient Descent](https://mlsanity.com/paper/2310.01775/) (2023)
- [Prime the search: Using large language models for guiding geometric task and motion planning by warm-starting tree search](https://mlsanity.com/paper/2506.07062/) (2025)
- [EMMOE: A Comprehensive Benchmark for Embodied Mobile Manipulation in Open Environments](https://mlsanity.com/paper/2503.08604/) (2025)
- [Policy-Guided Lazy Search with Feedback for Task and Motion Planning](https://mlsanity.com/paper/2210.14055/) (2022)
- [Bidirectional Task-Motion Planning Based on Hierarchical Reinforcement Learning for Strategic Confrontation](https://mlsanity.com/paper/2504.15876/) (2025)

## Abstract (arXiv)

Integrated task and motion planning (TAMP) is desirable for generalized autonomy robots but it is challenging at the same time. TAMP requires the planner to not only search in both the large symbolic task space and the high-dimension motion space but also deal with the infeasible task actions due to its intrinsic hierarchical process. We propose a novel decision-making framework for TAMP by constructing an extended decision tree for both symbolic task planning and high-dimension motion variable binding. We integrate top-k planning for generating explicitly a skeleton space where a variety of candidate skeleton plans are at disposal. Moreover, we effectively combine this skeleton space with the resultant motion variable spaces into a single extended decision space. Accordingly, we use Monte-Carlo Tree Search (MCTS) to ensure an exploration-exploitation balance at each decision node and optimize globally to produce optimal solutions. The proposed seamless combination of symbolic top-k planning with streams, with the proved optimality of MCTS, leads to a powerful planning algorithm that can handle the combinatorial complexity of long-horizon manipulation tasks. We empirically evaluate our proposed algorithm in challenging robot tasks with different domains that require multi-stage decisions and show how our method can overcome the large task space and motion space through its effective tree search compared to its most competitive baseline method.