# Leveraging Experience in Lazy Search

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Imitation learning methods, one of 13 directions in Offline RL and imitation learning from data.
- Builds on 17 of its 47 references that are in the map.
- First posted on arXiv 10 Oct 2021.

## Placed in

- Offline RL and imitation learning from data / [Imitation learning methods](https://mlsanity.com/offlinerl/imitation-learning-methods/)

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

- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Reinforcement and Imitation Learning via Interactive No-Regret Learning](https://mlsanity.com/paper/1406.5979/) (2014)
- [Deeply AggreVaTeD: Differentiable Imitation Learning for Sequential Prediction](https://mlsanity.com/paper/1703.01030/) (2017)
- [Shared Autonomy via Hindsight Optimization](https://mlsanity.com/paper/1503.07619/) (2015)
- [Truncated Horizon Policy Search: Combining Reinforcement Learning & Imitation Learning](https://mlsanity.com/paper/1805.11240/) (2018)
- [Data-driven Planning via Imitation Learning](https://mlsanity.com/paper/1711.06391/) (2017)
- [Learning Heuristic Search via Imitation](https://mlsanity.com/paper/1707.03034/) (2017)
- [Fast Policy Learning through Imitation and Reinforcement](https://mlsanity.com/paper/1805.10413/) (2018)
- [PLATO: Policy Learning using Adaptive Trajectory Optimization](https://mlsanity.com/paper/1603.00622/) (2016)
- [Learning from the Hindsight Plan -- Episodic MPC Improvement](https://mlsanity.com/paper/1609.09001/) (2016)
- [Near Optimal Bayesian Active Learning for Decision Making](https://mlsanity.com/paper/1402.5886/) (2014)
- [A Unifying Formalism for Shortest Path Problems with Expensive Edge Evaluations via Lazy Best-First Search over Paths with Edge Selectors](https://mlsanity.com/paper/1603.03490/) (2016)
- [Lazy Receding Horizon A* for Efficient Path Planning in Graphs with Expensive-to-Evaluate Edges](https://mlsanity.com/paper/1803.04998/) (2018)
- [The Provable Virtue of Laziness in Motion Planning](https://mlsanity.com/paper/1710.04101/) (2017)
- [Free-configuration Biased Sampling for Motion Planning: Errata](https://mlsanity.com/paper/1311.0541/) (2013)
- [Near-Optimal Edge Evaluation in Explicit Generalized Binomial Graphs](https://mlsanity.com/paper/1706.09351/) (2017)
- [Bayesian Active Edge Evaluation on Expensive Graphs](https://mlsanity.com/paper/1711.07329/) (2017)

## Abstract (arXiv)

Lazy graph search algorithms are efficient at solving motion planning problems where edge evaluation is the computational bottleneck. These algorithms work by lazily computing the shortest potentially feasible path, evaluating edges along that path, and repeating until a feasible path is found. The order in which edges are selected is critical to minimizing the total number of edge evaluations: a good edge selector chooses edges that are not only likely to be invalid, but also eliminates future paths from consideration. We wish to learn such a selector by leveraging prior experience. We formulate this problem as a Markov Decision Process (MDP) on the state of the search problem. While solving this large MDP is generally intractable, we show that we can compute oracular selectors that can solve the MDP during training. With access to such oracles, we use imitation learning to find effective policies. If new search problems are sufficiently similar to problems solved during training, the learned policy will choose a good edge evaluation ordering and solve the motion planning problem quickly. We evaluate our algorithms on a wide range of 2D and 7D problems and show that the learned selector outperforms baseline commonly used heuristics. We further provide a novel theoretical analysis of lazy search in a Bayesian framework as well as regret guarantees on our imitation learning based approach to motion planning.