# LEA*: An A* Variant Algorithm with Improved Edge Efficiency for Robot Motion Planning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 17 references that are in the map.
- First posted on arXiv 19 Sep 2023.

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

- [Batch Informed Trees (BIT*): Informed Asymptotically Optimal Anytime Search](https://mlsanity.com/paper/1707.01888/) (2017)
- [Generalized Lazy Search for Robot Motion Planning: Interleaving Search and Edge Evaluation via Event-based Toggles](https://mlsanity.com/paper/1904.02795/) (2019)
- [Search-based Motion Planning for Quadrotors using Linear Quadratic Minimum Time Control](https://mlsanity.com/paper/1709.05401/) (2017)
- [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)
- [Lazy Lifelong Planning for Efficient Replanning in Graphs with Expensive Edge Evaluation](https://mlsanity.com/paper/2105.12076/) (2021)

## Abstract (arXiv)

In this work, we introduce a new graph search algorithm, lazy edged based A* (LEA*), for robot motion planning. By using an edge queue and exploiting the idea of lazy search, LEA* is optimally vertex efficient similar to A*, and has improved edge efficiency compared to A*. LEA* is simple and easy to implement with minimum modification to A*, resulting in a very small overhead compared to previous lazy search algorithms. We also explore the effect of inflated heuristics, which results in the weighted LEA* (wLEA*). We show that the edge efficiency of wLEA* becomes close to LazySP and, thus is near-optimal. We test LEA* and wLEA* on 2D planning problems and planning of a 7-DOF manipulator. We perform a thorough comparison with previous algorithms by considering sparse, medium, and cluttered random worlds and small, medium, and large graph sizes. Our results show that LEA* and wLEA* are the fastest algorithms to find the plan compared to previous algorithms.