用分层可视图实现复杂空域实时3D导航，效率提升超四成。
Air-FAR: Fast and Adaptable Routing for Aerial Navigation in Large-scale Complex Unknown Environments
- 构建分层3D可视图，加速图生成与路径搜索
- 实测缩短42%航程，轨迹效率提升24.8%
- 适合无人机、机器人在复杂未知环境导航
本文提出一种用于大规模复杂未知环境中实时3D导航的新方法，采用分层3D可视图（V-graph）。通过引入启发式可视区域更新机制，该算法在O(K*n²logn)时间内完成3D V-graph构建，确保实时性能。提出的迭代分治路径搜索方法可在实时约束下获得近似最优路径解。大量仿真与真实环境验证表明，该算法相较基准方法航程减少42%，轨迹效率最高提升24.8%，运行速度在复杂场景中快数个数量级。代码与自研模拟器已开源，以促进后续研究。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。