LEA*: An A* Variant Algorithm with Improved Edge Efficiency for Robot Motion Planning
This work addresses efficiency in robot motion planning, an incremental improvement over existing A* and lazy search methods.
The paper introduces LEA*, a variant of the A* algorithm for robot motion planning that improves edge efficiency while maintaining optimal vertex efficiency, and shows that it is the fastest algorithm tested in various 2D and manipulator planning scenarios.
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.