ROS Resources: Documentation | Support | Discussion Forum | Index | Service Status | Q&A
Ask Your Question

Scaning for changed edge costs in global planning?

asked 2022-10-07 10:15:28 -0500

OverDemon gravatar image

I'm working on a global planner using the D* Lite algorithm ( 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.

Thanks in advance.

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2022-10-08 09:06:28 -0500

Mike Scheutzow gravatar image
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.

edit flag offensive delete link 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 ^^

OverDemon gravatar image OverDemon  ( 2022-10-10 04:00:51 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2022-10-07 10:15:28 -0500

Seen: 26 times

Last updated: Oct 08 '22