Air-FAR: Fast and Adaptable Routing for Aerial Navigation in Large-scale Complex Unknown Environments
<|reference_start|>Air-FAR: Fast and Adaptable Routing for Aerial Navigation in Large-scale Complex Unknown Environments: 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.<|reference_end|>
@article{he2024air-far:,
    title={Air-FAR: Fast and Adaptable Routing for Aerial Navigation in Large-scale
  Complex Unknown Environments},
    author={Botao He, Guofei Chen, Cornelia Fermuller, Yiannis Aloimonos and Ji
  Zhang},
    journal={arXiv preprint arXiv:2409.11188},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.11188},
    primaryClass={cs.RO}
}