LEA*: ロボット運動計画のためのエッジ効率を改善したA*変種アルゴリズム
LEA*: An A* Variant Algorithm with Improved Edge Efficiency for Robot Motion Planning
エッジキューと遅延探索を利用してA*の頂点効率を保ちつつエッジ効率を改善したLEA*を提案し、重み付きヒューリスティック版wLEA*とともに2D計画や7自由度マニピュレータで高速性を示した。
著者: Dongliang Zheng, Panagiotis Tsiotras
分類: cs.RO, cs.AI
原文アブストラクト
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.
