IROS 2022 Talk: FAR Planner: Fast, Attemptable Route Planner using Dynamic Visibility Update

Abstract
Path planning in unknown environments remains a challenging problem, as the environment is gradually observed during the navigation, the underlying planner has to update the environment representation and replan, promptly and constantly, to account for the new observations. In this paper, we present a visibility graph-based planning framework capable of dealing with navigation tasks in both known and unknown environments. The planner employs a polygonal representation of the environment and constructs the representation by extracting edge points around obstacles to form enclosed polygons. With that, the method dynamically updates a global visibility graph using a two-layered data structure, expanding the visibility edges along with the navigation, and removing edges that become occluded by newly observed obstacles. When navigating in unknown environments, the method is attemptable in discovering a way to the goal by picking up the environment layout on the fly, updating the visibility graph, and fast re-planning corresponding to the newly observed environment. We evaluate the method in simulated and real-world settings. The method shows the capability to attempt and navigate through unknown environments, reducing travel time by up to 12-47% from search-based methods: A*, D* Lite, and more than 24-35% from sampling-based methods: RRT*, BIT*, and SPARS.

Authors
Fan Yang: https://github.com/MichaelFYang
Chao Cao: http://caochao.me
Hongbiao Zhu: http://www.hongbiaoz.com
Jean Oh: https://www.cs.cmu.edu/~./jeanoh
Ji Zhang: https://frc.ri.cmu.edu/~zhangji

Paper
https://frc.ri.cmu.edu/~zhangji/publi...

Autonomous Exploration Development Environment
https://www.cmu-exploration.com

TARE Planner for Autonomous Exploration
https://www.cmu-exploration.com/tare-...

FAR Planner for Route Planning
https://github.com/MichaelFYang/far_p...

Other Related Work
C. Cao, H. Zhu, Z. Ren, H. Choset, and J. Zhang. Representation Granularity Enables Time-Efficient Autonomous Exploration in Large, Complex Worlds. Science Robotics. vol. 8, no. 80, 2023.
C. Cao, H. Zhu, F. Yang, Y. Xia, H. Choset, J. Oh, and J. Zhang. Autonomous Exploration Development Environment and the Planning Algorithms. IEEE Intl. Conf. on Robotics and Automation (ICRA). Philadelphia, PA, May 2022.
C. Cao, H. Zhu, H. Choset, and J. Zhang. TARE: A Hierarchical Framework for Efficiently Exploring Complex 3D Environments. Robotics: Science and Systems Conference (RSS). Virtual, July 2021.
J. Zhang, C. Hu, R. Gupta Chadha, and S. Singh. Falco: Fast Likelihood-based Collision Avoidance with Extension to Human-guided Navigation. Journal of Field Robotics. vol. 37, no. 8, pp. 1300–1313, 2020.
J. Zhang and S. Singh. Laser-visual-inertial Odometry and Mapping with High Robustness and Low Drift. Journal of Field Robotics. vol. 35, no. 8, pp. 1242–1264, 2018.