BiAIT*: 適応的ヒューリスティックを用いた対称双方向最適経路計画
BiAIT*: Symmetrical Bidirectional Optimal Path Planning with Adaptive Heuristic
AIT*を対称双方向探索に拡張し、初期解をより速く見つけつつ衝突時のヒューリスティック更新計算を削減した経路計画手法BiAIT*を提案した。
著者: Chenming Li, Han Ma, Peng Xu, Jiankun Wang, Max Q. -H. Meng
分類: cs.RO
原文アブストラクト
Adaptively Informed Trees (AIT*) is an algorithm that uses the problem-specific heuristic to avoid unnecessary searches, which significantly improves its performance, especially when collision checking is expensive. However, the heuristic estimation in AIT* consumes lots of computational resources, and its asymmetric bidirectional searching strategy cannot fully exploit the potential of the bidirectional method. In this article, we propose an extension of AIT* called BiAIT*. Unlike AIT*, BiAIT* uses symmetrical bidirectional search for both the heuristic and space searching. The proposed method allows BiAIT* to find the initial solution faster than AIT*, and update the heuristic with less computation when a collision occurs. We evaluated the performance of BiAIT* through simulations and experiments, and the results show that BiAIT* can find the solution faster than state-of-the-art methods. We also analyze the reasons for the different performances between BiAIT* and AIT*. Furthermore, we discuss two simple but effective modifications to fully exploit the potential of the adaptively heuristic method.
