Voronoi boundary based global Path planning?

[robotics-qc]

Hello Guys!

So I have been using Nav2 to projects for a while and use different local planners (such as DWB or Regulated Pure pursuit etc).

But for situations where the there are narrow corridors, cubicles etc (like an office environment) i thought having a global path that plans with maximum distance from all obstacles might be useful

Wondering if there is a planner or plugin that could be used to generate a global path that is more akin to a voronoi boundary -

A smoothed version of the above for example?

If not, is there a use case to add this feature?

Thanks!

[SteveMacenski]

Right now, there is not!

There was a Voronoi planner in ROS 1, but my understanding is that it was pretty slow and it was not really maintained. If you'd be open to developing an efficient / performant version, that could be something we'd consider merging into Nav2 (or at least nav2 auxiliary or its own repository under the ros-navigation org).

I think the struggle was to efficiently generate the voronoi diagram each iteration since it should consider the cost changes due to obstacles inserted in the costmap from sensor data. I'm not sure if it was actually all that difficult, if scaling with larger maps is difficult given the size of the map, or this was a case where research code wasn't particularly well optimized. Thinking about Voronoi again, I'd want to make sure that we have some methodology for how we compute the Voronoi field so that we don't compute the full map and limit it to where the planning is needed and/or make incremental updates to the voronoi map each iteration so the full thing is only computed once on initialization of the static map.

I think if you were open to developing and refining something like this, that would be a great contribution. It might be worth looking at more modern literature on Voronoi planners / using voronoi diagrams for planning & control to see if there's any tips / tricks we should consider in implementation to make it more powerful.

For example, just a quick search came up with https://arxiv.org/html/2201.12981v4 from 2018 (which I only vaguely scanned through, not sure if there's anything particular in this one but we should look at several).

For another example, maybe we generate a really nice voronoi library and we can use it for multiple things. For example: Do grad descent on the distance field it generates for an A* or kinematically feasible search primitives. Or do a more traditional Voronoi graph connection like your image. Or even use as part of the cost function for MPC or optimization-based techniques. Or do multi-resolution voronoi so that we can scale better for larger spaces. Or a number of other potential things.

[robotics-qc]

That is interesting, let me think about that, and research some more!

Regarding compute efficiency - yes I see having a global planner that needs to constantly re-plan on a new map will need some good optimization to make it efficient.

Just thinking aloud here,
There are many applications where the constantly updating global costmap is not required - ( I have often disabled the obstacle layer myself in very dynamic environments to stop noise/dynamic objects from leaving artifacts on the global costmap)

I have had discussions with my peers and colleagues who also use Nav2 - we discussed how if there was a means to use a 'roadmap' based planner that can compute a graph/roadmap based on requirements (PRM, Voronoi boundaries, cost or custom defined potential fields etc etc) - this makes the path planning very deterministic and compute efficient and provide the ability to pre-produce paths and possible filter them as needed.

Particularly in many mobile ground robots - especially for warehouses, parking lot, factories, office corridors etc I believe this may be useful

On or before launch we can provide time to compute (either online or apriori) a path network in the provided map and then runtime becomes fast, easy on the compute, smoother trajectories etc.

The local planner will take care of sudden obstacles anyway, and the global planner will only need to compute paths to join/exit the roadmap graph.

Thoughts?

[SteveMacenski]

There are many applications where the constantly updating global costmap is not required - ( I have often disabled the obstacle layer myself in very dynamic environments to stop noise/dynamic objects from leaving artifacts on the global costmap)

I think that's a useful special case to support, but I would like things in Nav2-main source to support dynamically updating environmental models since those are the most common use-case with autonomous navigation (PS sounds like you might need different obstacle layers!). I'd still want it usable with just the cost map, but we could add in a feature parameter to use only the static map (TBD how to obtain it). Either way, the functions used to process the static map vs the costmap would be identical.

we discussed how if there was a means to use a 'roadmap' based planner that can compute a graph/roadmap

There's an open ticket and some early draft work for that in Nav2: Nav2 Route Server. This is something I'm actually working on again starting next month (if I can ever get ahead of my emails and github reviews 😆 ). But this is another topic :-)