# Generalized Lazy Search for Robot Motion Planning: Interleaving Search and Edge Evaluation via Event-based Toggles

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Apr 2019.

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

- [Learning Neuro-Symbolic Skills for Bilevel Planning](https://mlsanity.com/paper/2206.10680/) (2022)
- [Predicate Invention for Bilevel Planning](https://mlsanity.com/paper/2203.09634/) (2022)
- [Learning Efficient Abstract Planning Models that Choose What to Predict](https://mlsanity.com/paper/2208.07737/) (2022)
- [Reducing Collision Checking for Sampling-Based Motion Planning Using Graph Neural Networks](https://mlsanity.com/paper/2210.08864/) (2022)
- [A Survey on the Integration of Machine Learning with Sampling-based Motion Planning](https://mlsanity.com/paper/2211.08368/) (2022)
- [Lazy Rearrangement Planning in Confined Spaces](https://mlsanity.com/paper/2203.10379/) (2022)
- [GePA*SE: Generalized Edge-Based Parallel A* for Slow Evaluations](https://mlsanity.com/paper/2301.10347/) (2023)
- [A Generalization of the Shortest Path Problem to Graphs with Multiple Edge-Cost Estimates](https://mlsanity.com/paper/2208.11489/) (2022)
- [T*varepsilon -- Bounded-Suboptimal Efficient Motion Planning for Minimum-Time Planar Curvature-Constrained Systems](https://mlsanity.com/paper/2204.01673/) (2022)
- [Planning with Dynamically Estimated Action Costs](https://mlsanity.com/paper/2206.04166/) (2022)
- [Tightest Admissible Shortest Path](https://mlsanity.com/paper/2308.08453/) (2023)
- [LEA*: An A* Variant Algorithm with Improved Edge Efficiency for Robot Motion Planning](https://mlsanity.com/paper/2309.10722/) (2023)
- [Optimal Motion Planning using Finite Fourier Series in a Learning-based Collision Field](https://mlsanity.com/paper/2312.09073/) (2023)
- [Kinodynamic Motion Planning for Mobile Robot Navigation across Inconsistent World Models](https://mlsanity.com/paper/2509.26339/) (2025)
- [Human2Any: Human-to-Robot Transfer via Constraint-Aware Compositional Planning](https://mlsanity.com/paper/2606.28813/) (2026)
- [Conflict-Based Lazy Search for Fast Multi-Manipulator Planning](https://mlsanity.com/paper/2607.04124/) (2026)

## Abstract (arXiv)

Lazy search algorithms can efficiently solve problems where edge evaluation is the bottleneck in computation, as is the case for robotic motion planning. The optimal algorithm in this class, LazySP, lazily restricts edge evaluation to only the shortest path. Doing so comes at the expense of search effort, i.e., LazySP must recompute the search tree every time an edge is found to be invalid. This becomes prohibitively expensive when dealing with large graphs or highly cluttered environments. Our key insight is the need to balance both edge evaluation and search effort to minimize the total planning time. Our contribution is two-fold. First, we propose a framework, Generalized Lazy Search (GLS), that seamlessly toggles between search and evaluation to prevent wasted efforts. We show that for a choice of toggle, GLS is provably more efficient than LazySP. Second, we leverage prior experience of edge probabilities to derive GLS policies that minimize expected planning time. We show that GLS equipped with such priors significantly outperforms competitive baselines for many simulated environments in R2, SE(2) and 7-DoF manipulation.