Requirements for navigation and path planning in uneven, three-dimensional, (outdoor) environments differ from those on level ground. In such environments, feasible trajectories can span across multiple floors, e.g. passing below or above a bridge, and are likely to involve sections which can be traversed in one direction but not the other, e.g. driving down/up a slope.
@smac: Nav2 is widely used for navigation on planar ground. The Spatio-Temporal Voxel Layer package, based on OpenVDB, seems to allow for the creation of costmaps which take 3D measurements into account during path planning. Would it be suitable to represent 3D terrains for planning?
@fmrico: You recently posted a solution using Octomap and Grid Map to localize in a simulated 3D terrain. Are Octomap and Grid Map your recommended go-to solutions to represent 3D (respectively 2.5D) terrains in the future?
ANYbotics has released Robot-Centric Elevation Mapping which appears to be built on top of Grid Map (also ANYbotics). Would this mapping framework be suitable to create (larger) 3D terrain maps suitable for path planning and navigation?
rtabmap_ros seems to be a frequently used package to perform 3D SLAM and generate 2D occupancy grids from it. Can it also be used to represent 3D terrains? I am aware of many other popular SLAM packages, e.g. R3LIVE. Is the main difference to rtabmap_ros that it can generate the 2D occupancy grid from its 3D measurements? How is the generated occupancy grid related to Grid Map?
@spuetz: You have worked on Mesh Navigation for outdoor navigation in 3D terrains. It appears to implement its own versions of costmaps and costmap layers to represent 3D terrains. Does it use some of the above mentioned packages?
vox_nav, inspired by Nav2, relies on Octomap and sets out to solve the problem of navigation in rough, uneven terrain. Is Octomap thus the way to represent 3D terrains?
This is probably a non-extensive summary of the prior work on navigation in uneven, three-dimensional, outdoor terrains. Which packages and projects have I missed?
Are there any personal or community plans moving forward? Which packages make sense to rely on for 3D (or maybe 2.5D) map representation and path planning and which are (likely) deprecated?
These is quite a number of questions. I am curious to learn more about the state of map representation, path planning and navigation in uneven, three-dimensional, (outdoor) terrains. Thank you for your inputs and pointers.
While I won’t argue with that statement, I’d like to also point out that a large number of Nav2 users also do outdoor navigation on uneven terrain and odd settings. I hope that’s clear by one our of great sponsors of Nav2, Polymath Robotics, who’s robots I’m not sure have ever seen a planar environment
This hasn’t been a top-top priority for me or Open Navigation since getting the core planning, control, behavior, reliability, and quality items up have been considered higher. This is since any updates to offer more modern perception or environmental modeling techniques are going to share that same base. Though, as evidenced by Polymath and many others, folks are able to make the modifications required with custom perception plugins and such to make it work fine. So that’s proof that it can and has been done.
We are starting to hit the point where this is becoming increasingly a target of development for us, but given the number of AI-centric methods on this area, we’re still mulling over the best options so we can (1) be “the” solution, not a research-quality implementation and (2) can work for a broad set of situations without massive GPU compute (or making that a requirement) and (3) make sure it can be well maintained with high quality standards consistent with the rest of Nav2.
On the other projects:
Grid Maps was top of mind for this work, but Anybotics still hasn’t moved to ROS 2 and the ROS 2 port that I led the community to developing has stagnated as a result and none of the changes to the ROS 1 version were ported forward. I’ve more or less stopped considering this an option for a Nav2-solution due to this poor maintenance.
RTabMap / Octomap had their time in the sunshine, but SOTA has moved far forward since and I don’t think any solution in the future should be based on 10+ year old technologies. They’re popular because they broadly work, are open-source, and well integrated into the ROS ecosystem. But if we’re willing to put in engineering time to build something, we can do better. But I definitely solute them for their service!
I’ll say though that if this is something of priority to your organization, it might be worth shooting an email over to my at Open Navigation and discussing how we can work together to make this move forward in a well-maintained and functional way.
Which packages make sense to rely on for 3D (or maybe 2.5D) map representation and path planning and which are (likely) deprecated?
I have used OctoMap as a full 3D map representation in the past, but I don’t think this matters too much. I think some good questions to ask before deciding on a proper environment representation are; what sort of planning capabilities do you need or what sort of existing state-of-the-art planning algorithms you would like to use? In the end, the purpose of environmental representation is to provide convenience for efficient planning capabilities.
For instance, if you are planning to use a Sampling-Based approach do you need full volumetric representation? Perhaps not, you can implement a simple collision check function on bare point-cloud maps, which are the output from the most of existing 3D SLAM algorithms. A more fierce challenge of the outdoors in my opinion is robustly determining what is traversable and what is not. You can then exploit these traversability measures to feed sampling-based approaches with the heuristics they need for fast convergence to optimal plans. I would aim for bare point-cloud maps but again that really depends on the specific use-case.
Re 3. You can also check out Jaeyoung’s work on grid_map_geo, an implementation of grid_map that works on GeoTIF data.
In principle, and in practice through their research, at the scales his lab operates at, it works well. It’s also based on gdal, which is a popular library for managing this kind of data.
That said, the approach of loading a single raster tile in memory is not scalable for the size of terrain and resolution of maps that some aerial vehicles cover.
As far as I have researched, there is not any open-source implementation that can take multiple raster tiles of data and plan against it. The use case here is when the robot is supplied pre-fetched map data. A simple version of this terrain fetching has already been implemented, through a custom protocol, on ArduPilot, however the flight controller is currently incapable of performing any planning.
Such support in the ROS community could allow platforms like ArduPilot to start solving the SmartRTL use cases by using a companion computer with more processing to run a ROS 2 planner, and generate a feasible plan that the drone can follow.
@facontidavide: Coincidentally, you posted yesterday about Bonxai on X. It seems necessary to mention in this thread.
I didn’t know about Bonxai yet, but it seems to have similar scope as Octomap and maybe Spatio-Temporal Voxel Layer? How does it compare to those two? Is Bonxai suitable as map representation to eventually do path planning and navigation in uneven, three-dimensional, (outdoor) terrains?
Octomap is a library used in many applications, such as: navigation (wheeled robots), obstacle avoidance (drones), path planning (robotic arms). It served the community well for over a decade, but it is also known to be considerably slow. Bonxai is a drop-in replacement that is almost 1 order of magnitude faster. it can be used in the context of ROS/ROS 2 or as a standalone C++ library with no dependencies.
A ROS integration has not yet been published and the README says “Bonxai is currently under development and I am building this mostly for fun and for educational purposes. Don’t expect any API stability for the time being.”
So yes, it could be used to store your 3D data, but it won’t be as simple as sending an occupancy grid to Nav2. You’ll have to do some development to convert the volumetric data to a usable ROS map. Maybe the ROSCon presentation will generate community interest in such work.
A lot of things changed since I wrote that “the API is unstable”.
I added ROS support recently, but the best way to use it is as a library inside your application, not a ROS node.
I think now it is the perfect moment to discuss how bonxai could be used in nav2.
Said that, it is not meant to be used for 2.5D maps, even if it “could” .
I would rather create a 2D version for that… Maybe 1day of work?
I don’t want to spoil my ROSCon presentation, but I am sharing here some of my benchmark of Bonxai VS Octomap. This is how many times Bonxai is faster than Octomap, when creating the map. On the horizontal axis there is the ID of the Kitti dataset used:
Curious if you could also share Bonxai vs costmap. I expect it to be slower, but the question is how much slower if it could be a replacement for not just an individual layer’s internal structures, but the shared structure for all layers in some future framework. For insert, raycast clearing, and such.
Though, even for instance a comparison with the Voxel Layer which also does 3D raycasting would be enlightening. I have -100% love for the fact that we have a voxel grid implementation in Nav2. Its very clever and I’m happy its been there, but I think we can do better in the modern age. Even if you said that the compute times and memory where on par with each other (not even better) I’d go with Bonxai since that would remove ~a thousand lines of code from the codebase. Which sounds awesome.
FYI: most of those dense vision techniques are only useful in the local time horizon (e.g. local costmaps). Once you scale up to large spaces larger than, lets say a corner store, the updates start to lag and things can’t keep up on embedded memory.
I the ideas of nvblox, voxblox and similar, but its important to note where they can be most useful in context and their limitations. Local costmaps global costmaps (for now). Something like the OpenVDB / Bonxai approach is its sparsity which gives it scalability to larger environments. But that’s also more a topic of the kind of data we’re sticking into them (e.g. depth, voxelized) rather than really dense vision-based meshes. So to a degree, its could be less about data structures and more about what’s being done with them in those contexts.
I educated myself today about voxblox (reading a couple of papers) and I think that the safe bet for Nav2 would be to use voxblox, if your algorithms need Truncated Signed Distance Fields!
I will see if I can create a version of voxblox that uses Bonxai as core voxel storage, and if that brings any benefit
Not sure if that would be true for voxblox to be fair (according to what I read). But take it with a grain of salt.
I’m basing the info on things “like” voxblox that I’ve had conversations with the vendor about. They all use the same kinds of widgets (maybe a little different from one to another, but generally same idea). Happy to be proven wrong about that one in particular, but its notable the demos are also about the scale I would expect if you couldn’t do much, much larger spaces in one-go
the ideas of nvblox, voxblox and similar, but its important to note where they can be most useful in context and their limitations. Local costmaps 
global costmaps 
(for now). Something like the OpenVDB / Bonxai approach is its sparsity which gives it scalability to larger environments. But that’s also more a topic of the kind of data we’re sticking into them (e.g. depth, voxelized) rather than really dense vision-based meshes. So to a degree, its could be less about data structures and more about what’s being done with them in those contexts.
