Timezone: »

 
Poster
Learning Space Partitions for Path Planning
Kevin Yang · Tianjun Zhang · Chris Cummins · Brandon Cui · Benoit Steiner · Linnan Wang · Joseph Gonzalez · Dan Klein · Yuandong Tian

Tue Dec 07 04:30 PM -- 06:00 PM (PST) @
in Poster Session 2 »

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.

Keywords: Optimization · Reinforcement Learning and Planning

Author Information

Kevin Yang (UC Berkeley)
Tianjun Zhang (University of California, Berkeley)
Chris Cummins (Meta)

Chris Cummins is a Research Engineer at Facebook’s AI Research. His research focuses on fusing AI techniques with compilers and systems optimization. Before joining Facebook Chris was a postdoc at the University of Edinburgh where he received Ph.D. and MSc degrees. He completed his MEng degree at Aston University. He is the recipient of numerous best paper awards, the SISCA Best Scottish PhD Award, and the Institute of Engineering and Technology Prize.

Brandon Cui (Facebook AI Research)
Benoit Steiner (Facebook AI Research)
Linnan Wang (Brown University)
Joseph Gonzalez (UC Berkeley)
Dan Klein (UC Berkeley)
Yuandong Tian (Facebook AI Research)

More from the Same Authors