I believe this is a half-theoretical, half-practical question as I'm working with a D* Lite planner in C++, but there'll be no code in this post, of course. Sorry in advance for perhaps not using the precisely correct technical terms ^^
D* Lite finds a path by expanding nodes backwards (aka. from goal to start) and at the end we have something as the example below. The nodes that form the shortest path have been expanded and has a rhs- and g-value (I have just given them numbers to highlight them). The (x) nodes have rhs-values since they had updateVertex called on them as they were neighbors to the nodes that formed the shortest path, but no g-values yet as they were not the nodes with the smallest keys.
Now, a path have been found from start to goal, however, suddenly an obstacle appear at (1), right in front of start before a move to start it made. So re-planning is initiated (I know that D* Lite normally move first after a path is found before scanning for changes, but for testing purposes I reset start to the original position so I can compare results). What happens in my program is that the re-planning produce a result like this:
The numbered route (1-8) is the actual route that my program ends up choosing, (*) are nodes with an rhs- and g-value (besides the route), and (x) nodes are have an rhs-value but a g-value of infinity.
What this post is about and what I'm not sure about is this: (My) D* Lite starts by updating the start node and the (Obs) node, as expected, but then it proceed to move along all the nodes adjacent to the original path (starting down around goal), aka. the (*) nodes. And I'm not sure if this is how D star Lite is supposed to work or not?
And that's basically what I'm wondering about. Whether this is how D* Lite is supposed to work or if I've missed something? On a small map like this it's no problem, but on larger maps having to basically double the amount of nodes with rhs- and g-values adds up in the time required.
I'm not sure what to think, D* Lite is not as intuitive A* or such. I'm not sure whether my test is built on a bad example. Or whether it has something to do with the fact that it's equally 'cheap' to move along the side of the original path and then move inwards as it is to move inwards first...
Any help would be appreciated.
