FAR Planner: A Visibility Graph That Keeps Changing While the Robot Drives

A Visibility Graph That Changes While the Robot Drives

FAR Planner uses a dynamically updated visibility graph for fast replanning. The planner models the environment with polygons and builds a global visibility graph along with the navigation.

The idea is a specific one. A visibility graph is a graph whose vertices are the corners of the obstacles and whose edges connect pairs of vertices that can see each other, so a path through the graph is a collision free route. The classical version is computed once from a known map. Here it is maintained while the vehicle moves, and it grows as the vehicle discovers space.

That growth is what makes the unknown environment case work. Areas covered by the visibility graph become free space. When navigating in free space, the planner uses the built visibility graph, and when navigating in unknown space, the planner attempts to discover a way to the goal.

The word attempting is the key to the name, which stands for Fast, Attemptable Route Planner. In an unknown space there is no graph to plan on, so the planner tries a set of candidate paths and follows the environment as it observes it, updating the graph with what it learns. The graph is therefore both the planning structure and the map, which is why it has to be maintained continuously rather than computed once.

Known and Unknown Space, and the Attemptable Switch

The planner handles both a known environment and an unknown one, and the README describes the difference in terms of what the path is based on. In a known environment, paths are planned based on a prior map. In an unknown environment, multiple paths are attempted to guide the vehicle to goal based on the environment observed during the navigation.

The behaviour is controlled from the RViz control panel, and the setting is called Planning Attemptable. By unchecking it, the planner will first try to find a path through the free space, and that path shows in green. If such a path does not exist, the planner will consider unknown space together, and the path shows in blue.

So the checkbox is a mode switch between the two worlds, and the colour of the planned path tells you which one produced it. Green is a path through space the robot already knows, blue is a path that goes through space it has not seen.

The same panel has an Update Visibility Graph checkbox, and unchecking it stops the planner from updating the visibility graph. That is the debugging control, because the graph update is the part of the system that reacts to the world changing, and a wrong path is often a wrong graph.

There is also a Reset Visibility Graph button that reinitialises the graph, and a Read and Save pair that writes the graph to a file and reads it back, with an example indoor environment file provided in the source tree.

Dynamic Obstacles Are Edge Disconnections

The handling of dynamic obstacles is the most elegant idea in the description, and it is worth stating precisely because it is not the usual approach.

When dynamic obstacles are present, FAR Planner disconnects visibility edges blocked by the dynamic obstacles and reconnects them after regaining visibility.

So the graph stays a static structure and the dynamic world is expressed as edits to it. An obstacle moves into a line of sight, the edge is removed, the path search no longer routes through it, and when the obstacle moves away the edge comes back.

The usual alternative is to rebuild the graph from scratch each time the world changes, which is expensive, or to keep the obstacle geometry in the path search and re-plan around it each cycle, which is also expensive and additionally makes the graph a moving target for the planner. The disconnect approach keeps both the graph and the planner simple, at the cost of maintaining the edge set.

This is also why the environment has to be modelled with polygons, since the visibility edges are computed between polygon corners, and why the configuration has an is_static_env switch. That switch defaults to true, and the README says to set it to false if the environment contains dynamic obstacles, which is the setting that tells the planner it is dealing with a world that moves.

Two Threads and a Three Millisecond Budget

The implementation splits the work across two CPU threads. One thread dynamically updates the visibility graph using about twenty percent of that thread, and the other performs the path search, which can find a path within three milliseconds as evaluated on an i7 computer.

The ratio is the interesting number. The graph update is the expensive part, because it means testing visibility between new candidate vertices, and it is given a fifth of a thread because it does not need to keep up with the control loop. The path search is the latency sensitive part, because it has to produce an answer inside the planning cycle, and it gets the rest.

The three millisecond figure is stated with its hardware, an i7, and it is a result for the path search specifically rather than for a full navigation cycle, so it should be read that way rather than as an end to end latency claim.

For a robotics project, that budget is the design constraint that shapes everything else. A planner that takes a second is useless on a vehicle, and a visibility graph is attractive here precisely because re-planning on it is cheap, since the expensive work of understanding the space has already been done.

Running It Under ROS Melodic and Noetic

The repository has been tested in Ubuntu 18.04 with ROS Melodic and Ubuntu 20.04 with ROS Noetic, and the setup instructions assume the Autonomous Exploration Development Environment, which the README points to for the environment setup.

The first step is to clone the repository and compile it on the branch that matches the computer setup:

git clone https://github.com/MichaelFYang/far_planner
cd far_planner
git checkout melodic-noetic
catkin_make

The default branch of the repository is melodic-noetic, so the checkout is what a fresh clone needs anyway.

Running it takes two terminals, because the simulator and the planner are separate launches. In the first, from the development environment folder, you source the workspace and start the simulator:

source devel/setup.sh
roslaunch vehicle_simulator system_indoor.launch

In the second, from the FAR Planner folder, you source the workspace and launch the planner:

source devel/setup.sh
roslaunch far_planner far_planner.launch

Other environments are selected by replacing the environment name in the launch file, with the names being campus, indoor, garage, tunnel and forest. The campus environment needs one extra step, since checkTerrainConn has to be set to true in the system_campus.launch file in the vehicle simulator source of the development environment, because the campus has terrain connectivity that the other environments do not.

RViz Controls, Matterport and the Visibility Graph File

The interactive controls are all in RViz, and they are what you use for a run rather than for setup.

You send a goal by pressing the Goalpoint button and clicking a point to set it. The vehicle navigates to the goal and builds a visibility graph along the way, shown in cyan, and the areas covered by the graph become free space. There is a Reset Visibility Graph button to reinitialise the graph, and Read and Save buttons to write the graph to a file and load it back, with an example visibility graph file for the indoor environment provided in the source tree.

There is a manual override for any point during navigation. Using the control panel to click inside the black box switches the system to smart joystick mode, where the vehicle tries to follow the virtual joystick command and avoid collisions at the same time, and pressing the Resume Navigation to Goal button or setting a new goal returns it to planner control. A PS3 or PS4 controller or an Xbox controller can be used instead of the virtual joystick.

For Matterport3D environments there is a separate configuration, and the launch takes a config argument:

roslaunch vehicle_simulator system_matterport.launch
roslaunch far_planner far_planner.launch config:=matterport

The settings for Matterport3D live in a matterport.yaml file in the configuration folder, alongside the default.yaml used elsewhere.

Custom Boundaries and the Four Settings That Matter

Custom navigation boundaries are supported, and they are defined by two files in the source data folder, an example boundary.ply and an example trajectory.txt, both of which are plain text and can be read in an editor.

The boundary file holds user defined polygons, each with an index. The trajectory file holds poses, one per row, with x, y and z in metres, roll, pitch and yaw in radians, and the time duration from the start of the run in seconds, in the same format the development environment saves. The trajectory file needs at least one pose, and its purpose is to determine which side of the navigation boundary is traversable, which is the information a polygon on its own cannot carry.

A visibility graph file is then generated for the boundaries, written as boundary_graph.vgh in the same folder, and it is loaded into the planner with the Read button:

roslaunch boundary_handler boundary_handler.launch

The configuration itself lives in default.yaml in the configuration folder, and four settings carry most of the behaviour. is_static_env defaults to true and should be set to false if the environment contains dynamic obstacles. is_attempt_autoswitch defaults to true and controls the automatic switch from non-attemptable navigation, for a known environment, to attemptable navigation, for an unknown one. is_viewpoint_extend defaults to true and stops the planner from extending visibility graph vertices away from objects to gain better viewpoints when set to false. And is_pub_boundary defaults to false, and setting it to true sends the custom navigation boundaries to the local planner in the development environment.

The repository is small, with the source under src/ and the images in an img/ directory, it publishes no GitHub releases, it has no stated licence, and the last push was on 2026-05-25.

Editorial conclusion

FAR Planner fits a robotics research group working on exploration in partially known spaces, especially one already inside the CMU Autonomous Exploration Development Environment with ROS Melodic or Noetic, since the simulation, the vehicle simulator and the RViz control panel are the whole workflow rather than a library you integrate. It is a poor fit for a commercial robot stack, since it is a research codebase with no releases, no package metadata and a ROS 1 dependency. Before trying it, read the configuration file, because is_static_env and is_attempt_autoswitch change the planner's behaviour substantially, and note that the campus environment needs checkTerrainConn set to true. The repository is not archived, the last push was on 2026-05-25, and the code is published without a stated licence.

Frequently asked questions

Official sources

1. Issues
2. MichaelFYang/far_planner on GitHub
3. README