# Learning Space Partitions for Path Planning

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 62 references that are in the map.
- First posted on arXiv 19 Jun 2021.

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Density estimation using Real NVP](https://mlsanity.com/paper/1605.08803/) (2016)
- [Dream to Control: Learning Behaviors by Latent Imagination](https://mlsanity.com/paper/1912.01603/) (2019)
- [Learning Latent Dynamics for Planning from Pixels](https://mlsanity.com/paper/1811.04551/) (2018)
- [Deep Image Prior](https://mlsanity.com/paper/1711.10925/) (2017)
- [Mastering Atari with Discrete World Models](https://mlsanity.com/paper/2010.02193/) (2020)
- [Deep Reinforcement Learning in a Handful of Trials using Probabilistic Dynamics Models](https://mlsanity.com/paper/1805.12114/) (2018)
- [Automatic chemical design using a data-driven continuous representation of molecules](https://mlsanity.com/paper/1610.02415/) (2016)
- [Junction Tree Variational Autoencoder for Molecular Graph Generation](https://mlsanity.com/paper/1802.04364/) (2018)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [The CMA Evolution Strategy: A Tutorial](https://mlsanity.com/paper/1604.00772/) (2016)
- [Analyzing Learned Molecular Representations for Property Prediction](https://mlsanity.com/paper/1904.01561/) (2019)
- [Scalable Global Optimization via Local Bayesian Optimization](https://mlsanity.com/paper/1910.01739/) (2019)
- [Graph Convolutional Policy Network for Goal-Directed Molecular Graph Generation](https://mlsanity.com/paper/1806.02473/) (2018)
- [Grammar Variational Autoencoder](https://mlsanity.com/paper/1703.01925/) (2017)
- [Molecular De Novo Design through Deep Reinforcement Learning](https://mlsanity.com/paper/1704.07555/) (2017)
- [Hierarchical Generation of Molecular Graphs using Structural Motifs](https://mlsanity.com/paper/2002.03230/) (2020)
- [Learning to Plan Chemical Syntheses](https://mlsanity.com/paper/1708.04202/) (2017)
- [Syntax-Directed Variational Autoencoder for Structured Data](https://mlsanity.com/paper/1802.08786/) (2018)
- [Exploring Model-based Planning with Policy Networks](https://mlsanity.com/paper/1906.08649/) (2019)
- [Learning Search Space Partition for Black-box Optimization using Monte Carlo Tree Search](https://mlsanity.com/paper/2007.00708/) (2020)
- [Learning Multimodal Graph-to-Graph Translation for Molecular Optimization](https://mlsanity.com/paper/1812.01070/) (2018)
- [Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.4758/) (2014)
- [AutoPhase: Juggling HLS Phase Orderings in Random Forests with Deep Reinforcement Learning](https://mlsanity.com/paper/2003.00671/) (2020)
- [Improving Molecular Design by Stochastic Iterative Target Augmentation](https://mlsanity.com/paper/2002.04720/) (2020)
- [Solving Black-Box Optimization Challenge via Learning Search Space Partition for Local Bayesian Optimization](https://mlsanity.com/paper/2012.10335/) (2020)
- [Adaptive Local Bayesian Optimization Over Multiple Discrete Variables](https://mlsanity.com/paper/2012.03501/) (2020)

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

- [Efficient Planning in a Compact Latent Action Space](https://mlsanity.com/paper/2208.10291/) (2022)
- [SurCo: Learning Linear Surrogates For Combinatorial Nonlinear Optimization Problems](https://mlsanity.com/paper/2210.12547/) (2022)
- [Efficient Planning with Latent Diffusion](https://mlsanity.com/paper/2310.00311/) (2023)
- [Improving Small Molecule Generation using Mutual Information Machine](https://mlsanity.com/paper/2208.09016/) (2022)
- [Multi-objective Optimization by Learning Space Partitions](https://mlsanity.com/paper/2110.03173/) (2021)
- [Improving LLM-based Global Optimization with Search Space Partitioning](https://mlsanity.com/paper/2505.21372/) (2025)

## Abstract (arXiv)

Path planning, the problem of efficiently discovering high-reward trajectories, often requires optimizing a high-dimensional and multimodal reward function. Popular approaches like CEM and CMA-ES greedily focus on promising regions of the search space and may get trapped in local maxima. DOO and VOOT balance exploration and exploitation, but use space partitioning strategies independent of the reward function to be optimized. Recently, LaMCTS empirically learns to partition the search space in a reward-sensitive manner for black-box optimization. In this paper, we develop a novel formal regret analysis for when and why such an adaptive region partitioning scheme works. We also propose a new path planning method LaP3 which improves the function value estimation within each sub-region, and uses a latent representation of the search space. Empirically, LaP3 outperforms existing path planning methods in 2D navigation tasks, especially in the presence of difficult-to-escape local optima, and shows benefits when plugged into the planning components of model-based RL such as PETS. These gains transfer to highly multimodal real-world tasks, where we outperform strong baselines in compiler phase ordering by up to 39% on average across 9 tasks, and in molecular design by up to 0.4 on properties on a 0-1 scale. Code is available at https://github.com/yangkevin2/neurips2021-lap3.