FAR Planner: Fast, Attemptable Route Planner Using Dynamic Visibility Update

Abstract

We present our work on a visibility graph-based planning framework. The planner constructs a polygonal representation of the environment 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 dynamic obstacles. The planner is capable of dealing with navigation tasks in both known and unknown environments. In the latter case, the method is attemptable in discovering a way to the goal by picking up the environment layout on the fly and fast re-planning to account for the newly observed environment. We evaluate the method in both simulated and real-world settings. The method shows the capability to navigate through unknown environments and reduces the travel time by up to 12-47% from search-based methods: A*, D* Lite, and more than 24-35% than sampling-based methods: RRT*, BIT*, and SPARS.