ROS Resources: Documentation | Support | Discussion Forum | Index | Service Status | Q&A answers.ros.org

# Scaning for changed edge costs in global planning?

I'm working on a global planner using the D* Lite algorithm (http://www.frc.ri.cmu.edu/~axs/doc/ic...) using the turtlebot3 robot which I simulate in Gazebo and rviz but have run into a potential problem with the following lines of the algorithm:

{28'} Scan graph for changed edge costs;
{29'} if any edge costs changed


While not an expert on ROS or C++, I've worked with it and built up some knowledge over the course of making an A* planner (which I'm now trying to make into a D* Lite). For A* this problem didn't exist as a new plan was simply made every time the makePlan of global planner was called (I plan to use a planner_frequency > 0, so it can react to new obstacles), but with D* Lite the whole point is to save computation by altering the existing plan when needed.

But I can't quite think of a way to 'Scan graph for changed edge costs'. So far the only idea that have come to mind is to perhaps have a bool variable in makePlan which doesn't affect the first path planning, but is set to 'true' when the first plan is found. While this bool is true the makePlan function would look through the existing plan and somehow compare whether the values of the nodes in the existing plan are free or have the same values. If yes, it wouldn't change anything, but if not it would trigger updating the vertexes and computing the alteration of the plan. It doesn't seem like the best idea.

edit retag close merge delete

Sort by ยป oldest newest most voted
But I can't quite think of a way to 'Scan graph for changed edge costs'


This seems straight-forward: keep a copy of the previous OccupancyGrid, then compare cell-by-cell against the current OccupancyGrid.

There are various cpu-reduction optimizations you could implement: for example, you might compare only cells touched by the current global path, or you could customize costmap_2d to report a list of modified cells since the last query.

more

Thanks for the help ^^ Regarding your first suggestion what comes to mind for that is a 2-layered for-loop to do the check. Not totally sure about the others yet, though I think I understand the concept. It's given me something to work with, so thanks again ^^

( 2022-10-10 04:00:51 -0500 )edit