3D Occupancy Grid Intake
moreno-al opened this issue · 3 comments
Hey,
Has there been any interest or any development that you know of that works with D* Lite Path planning that takes in 3D maps. I am personally working in an unknown environment receiving object detection as I go, and was wondering if you know of anyone that has implemented D* for 3D spaces or what it would look like for us to contribute to use your software to expand the functionality of your current solution.
Hey, not that I know of, but I am sure it exists some examples on GitHub. I don't think it would be that hard to extend my implementation into 3D space. Instead of having a grid.py that contains a 2D grid map with various methods for updating the map, you could probably have a file voxel.py which contains a voxel grid of your world. and instead of having a vertices explained by u: (int, int), v: (int, int) you would have u: (int, int, int), v: (int, int, int). The search heuristics in utils.py would also need to be extended to 3D, so that you calculate the Manhattan distance between two points in the space and not two points in the plane. Also the method def get_movements_8n(x: int, y: int) -> List: would need to be extended as well: def get_movements_24n(x: int, y: int, z: int) -> List:.
If you are interested, I have previously implemeted an rrt_star in both 3D and 2D using r-trees for spatial queries which makes it computationally really fast. You could have a look at that rrt-star repo. I also implemented the same algorithm for a jackal robot in ROS, you could have a look at that jackal repo as well. For the jackal robot I used the 2D implementation of rrt-star.
Thank you! This was very helpful! Extending the current implementation to a 3D space was the way to go.
@moreno-al Great, however I would probably suggest implementing it in C++ instead. With the amount of computations you're dealing with, you'll probably experience a lot of delay at runtime when the voxel grid become large. You'll achieve much more performance using a low level language like C++.