# Hybrid Search for Efficient Planning with Completeness Guarantees

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 45 references that are in the map.
- First posted on arXiv 19 Oct 2023.

## Builds on (most cited first, 30 of 34)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Neural Discrete Representation Learning](https://mlsanity.com/paper/1711.00937/) (2017)
- [PaLM-E: An Embodied Multimodal Language Model](https://mlsanity.com/paper/2303.03378/) (2023)
- [Conservative Q-Learning for Offline Reinforcement Learning](https://mlsanity.com/paper/2006.04779/) (2020)
- [Decision Transformer: Reinforcement Learning via Sequence Modeling](https://mlsanity.com/paper/2106.01345/) (2021)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Generative Language Modeling for Automated Theorem Proving](https://mlsanity.com/paper/2009.03393/) (2020)
- [Semi-parametric Topological Memory for Navigation](https://mlsanity.com/paper/1803.00653/) (2018)
- [Planning with Goal-Conditioned Policies](https://mlsanity.com/paper/1911.08453/) (2019)
- [Hierarchical Foresight: Self-Supervised Learning of Long-Horizon Tasks via Visual Subgoal Generation](https://mlsanity.com/paper/1909.05829/) (2019)
- [COG: Connecting New Skills to Past Experience with Offline Reinforcement Learning](https://mlsanity.com/paper/2010.14500/) (2020)
- [Relational Deep Reinforcement Learning](https://mlsanity.com/paper/1806.01830/) (2018)
- [Offline Q-Learning on Diverse Multi-Task Data Both Scales And Generalizes](https://mlsanity.com/paper/2211.15144/) (2022)
- [World Model as a Graph: Learning Latent Landmarks for Planning](https://mlsanity.com/paper/2011.12491/) (2020)
- [Long-Horizon Visual Planning with Goal-Conditioned Hierarchical Predictors](https://mlsanity.com/paper/2006.13205/) (2020)
- [Learning Plannable Representations with Causal InfoGAN](https://mlsanity.com/paper/1807.09341/) (2018)
- [Hierarchical Planning Through Goal-Conditioned Offline Reinforcement Learning](https://mlsanity.com/paper/2205.11790/) (2022)
- [Vector Quantized Models for Planning](https://mlsanity.com/paper/2106.04615/) (2021)
- [Landmark-Guided Subgoal Generation in Hierarchical Reinforcement Learning](https://mlsanity.com/paper/2110.13625/) (2021)
- [Variational Temporal Abstraction](https://mlsanity.com/paper/1910.00775/) (2019)
- [Time-Agnostic Prediction: Predicting Predictable Video Frames](https://mlsanity.com/paper/1808.07784/) (2018)
- [Sub-Goal Trees -- a Framework for Goal-Based Reinforcement Learning](https://mlsanity.com/paper/2002.12361/) (2020)
- [Don't Start From Scratch: Leveraging Prior Data to Automate Robotic Reinforcement Learning](https://mlsanity.com/paper/2207.04703/) (2022)
- [MuZero with Self-competition for Rate Control in VP9 Video Compression](https://mlsanity.com/paper/2202.06626/) (2022)
- [Hallucinative Topological Memory for Zero-Shot Visual Planning](https://mlsanity.com/paper/2002.12336/) (2020)
- [Dynamics Learning with Cascaded Variational Inference for Multi-Step Manipulation](https://mlsanity.com/paper/1910.13395/) (2019)
- [Single-Agent Policy Tree Search With Guarantees](https://mlsanity.com/paper/1811.10928/) (2018)
- [Subgoal Search For Complex Reasoning Tasks](https://mlsanity.com/paper/2108.11204/) (2021)
- [Intention-Net: Integrating Planning and Deep Learning for Goal-Directed Autonomous Navigation](https://mlsanity.com/paper/1710.05627/) (2017)
- [Policy-Guided Heuristic Search with Guarantees](https://mlsanity.com/paper/2103.11505/) (2021)

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

- [WorldCoder, a Model-Based LLM Agent: Building World Models by Writing Code and Interacting with the Environment](https://mlsanity.com/paper/2402.12275/) (2024)
- [Navigation with QPHIL: Quantizing Planner for Hierarchical Implicit Q-Learning](https://mlsanity.com/paper/2411.07760/) (2024)
- [OptionZero: Planning with Learned Options](https://mlsanity.com/paper/2502.16634/) (2025)
- [What Matters in Hierarchical Search for Combinatorial Reasoning Problems?](https://mlsanity.com/paper/2406.03361/) (2024)
- [Subgoal-Guided Policy Heuristic Search with Learned Subgoals](https://mlsanity.com/paper/2506.07255/) (2025)
- [Structure-Induced Information for Rerooting Levin Tree Search](https://mlsanity.com/paper/2605.30664/) (2026)

## Abstract (arXiv)

Solving complex planning problems has been a long-standing challenge in computer science. Learning-based subgoal search methods have shown promise in tackling these problems, but they often suffer from a lack of completeness guarantees, meaning that they may fail to find a solution even if one exists. In this paper, we propose an efficient approach to augment a subgoal search method to achieve completeness in discrete action spaces. Specifically, we augment the high-level search with low-level actions to execute a multi-level (hybrid) search, which we call complete subgoal search. This solution achieves the best of both worlds: the practical efficiency of high-level search and the completeness of low-level search. We apply the proposed search method to a recently proposed subgoal search algorithm and evaluate the algorithm trained on offline data on complex planning problems. We demonstrate that our complete subgoal search not only guarantees completeness but can even improve performance in terms of search expansions for instances that the high-level could solve without low-level augmentations. Our approach makes it possible to apply subgoal-level planning for systems where completeness is a critical requirement.