Minding the Gap

Gap-based planners are a family of local planners that parse incoming sensor data (laser or LiDAR scans) and discretize it into polar regions of free space called gaps (purple arcs in the gifs below). This is a computationally efficient departure from traditional methods of discretizing the environment into Cartesian regions such as grid maps or voxel grids. Gaps have been proven to be quite effective in static environments on wheeled robots. However, extending These approaches to (a) dynamic environments, and (b) legged robots, is non-trivial. Let's talk about what needs to be done!

Dynamic Gap: Safe Gap-based Navigation in Dynamic Environments

In this work, we take our prior perception-informed gap-based planner and extend it to dynamic environments. This means that we must now detect the gaps in our environment and predict how they will evolve over time. We leverage some robust tracking algorithms to estimate gap dynamics, and we track intercepting trajectories through model predictive control (MPC). A diagram of our overall workflow is shown below.

We tested our planner out against state-of-the-art benchmarks, and we found that our planner was able to navigate through complex dynamic environments while suffering very few collisions.

Check out the gifs below to see our planner in action.

Want to learn more? Check out the following links:

Paper

Video

Code