mlsanityData to 14 Oct 2026

Hybrid Search for Efficient Planning with Completeness Guarantees

arXiv 2310.12819 ↗First posted 19 Oct 2023cs.AI cs.LGcited by 6

Not on the map. Why?

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.

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

34 of 45 references.

References · 34

  1. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  2. 2017Neural Discrete Representation Learningcited by 4,712
  3. 2023PaLM-E: An Embodied Multimodal Language Modelcited by 2,071
  4. 2020Conservative Q-Learning for Offline Reinforcement Learningcited by 1,809
  5. 2021Decision Transformer: Reinforcement Learning via Sequence Modelingcited by 1,546
  6. 2019Mastering Atari, Go, Chess and Shogi by Planning with a Learned Modelcited by 1,353
  7. 2020Generative Language Modeling for Automated Theorem Provingcited by 388
  8. 2018Semi-parametric Topological Memory for Navigationcited by 209
  9. 2019Planning with Goal-Conditioned Policiescited by 149
  10. 2019Hierarchical Foresight: Self-Supervised Learning of Long-Horizon Tasks via Visual Subgoal Generationcited by 83
  11. 2020COG: Connecting New Skills to Past Experience with Offline Reinforcement Learningcited by 83
  12. 2018Relational Deep Reinforcement Learningcited by 73
22 more
  1. 2022Offline Q-Learning on Diverse Multi-Task Data Both Scales And Generalizescited by 73
  2. 2020World Model as a Graph: Learning Latent Landmarks for Planningcited by 69
  3. 2020Long-Horizon Visual Planning with Goal-Conditioned Hierarchical Predictorscited by 62
  4. 2018Learning Plannable Representations with Causal InfoGANcited by 57
  5. 2022Hierarchical Planning Through Goal-Conditioned Offline Reinforcement Learningcited by 50
  6. 2021Vector Quantized Models for Planningcited by 48
  7. 2021Landmark-Guided Subgoal Generation in Hierarchical Reinforcement Learningcited by 47
  8. 2019Variational Temporal Abstractioncited by 38
  9. 2018Time-Agnostic Prediction: Predicting Predictable Video Framescited by 37
  10. 2020Sub-Goal Trees -- a Framework for Goal-Based Reinforcement Learningcited by 29
  11. 2022Don't Start From Scratch: Leveraging Prior Data to Automate Robotic Reinforcement Learningcited by 29
  12. 2022MuZero with Self-competition for Rate Control in VP9 Video Compressioncited by 28
  13. 2020Hallucinative Topological Memory for Zero-Shot Visual Planningcited by 25
  14. 2019Dynamics Learning with Cascaded Variational Inference for Multi-Step Manipulationcited by 24
  15. 2018Single-Agent Policy Tree Search With Guaranteescited by 22
  16. 2021Subgoal Search For Complex Reasoning Taskscited by 21
  17. 2017Intention-Net: Integrating Planning and Deep Learning for Goal-Directed Autonomous Navigationcited by 20
  18. 2021Policy-Guided Heuristic Search with Guaranteescited by 20
  19. 2020Divide-and-Conquer Monte Carlo Tree Search For Goal-Directed Planningcited by 19
  20. 2023Hierarchical Imitation Learning with Vector Quantized Modelscited by 15
  21. 2022Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Searchcited by 12
  22. 2020Efficient Black-Box Planning Using Macro-Actions with Focused Effectscited by 9

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 3; 2025: 2; 2026: 1.

6 papers.

  1. 2024WorldCoder, a Model-Based LLM Agent: Building World Models by Writing Code and Interacting with the Environmentcited by 107
  2. 2024Navigation with QPHIL: Quantizing Planner for Hierarchical Implicit Q-Learningcited by 2
  3. 2025OptionZero: Planning with Learned Optionscited by 2
  4. 2024What Matters in Hierarchical Search for Combinatorial Reasoning Problems?cited by 1
  5. 2025Subgoal-Guided Policy Heuristic Search with Learned Subgoalscited by 1
  6. 2026Structure-Induced Information for Rerooting Levin Tree Searchcited by 0