Air-FAR: 大規模複雑未知環境における航空ナビゲーションのための高速で適応的な経路計画
Air-FAR: Fast and Adaptable Routing for Aerial Navigation in Large-scale Complex Unknown Environments
階層的3D可視性グラフを用いて、大規模で複雑な未知環境をリアルタイムに飛行する経路計画手法を提案し、従来手法より大幅に高速かつ効率的な経路生成を実現した。
著者: Botao He, Guofei Chen, Cornelia Fermuller, Yiannis Aloimonos, Ji Zhang
分類: cs.RO
原文アブストラクト
This paper presents a novel method for real-time 3D navigation in large-scale, complex environments using a hierarchical 3D visibility graph (V-graph). The proposed algorithm addresses the computational challenges of V-graph construction and shortest path search on the graph simultaneously. By introducing hierarchical 3D V-graph construction with heuristic visibility update, the 3D V-graph is constructed in O(K*n^2logn) time, which guarantees real-time performance. The proposed iterative divide-and-conquer path search method can achieve near-optimal path solutions within the constraints of real-time operations. The algorithm ensures efficient 3D V-graph construction and path search. Extensive simulated and real-world environments validated that our algorithm reduces the travel time by 42%, achieves up to 24.8% higher trajectory efficiency, and runs faster than most benchmarks by orders of magnitude in complex environments. The code and developed simulator have been open-sourced to facilitate future research.
