D* lite: what heuristic function should I use?

Question

I'm trying to implement the D*-Lite pathfinding algorithm, as described in the 2002 article by Koenig and Likhachev for grid based navgraph.

But I don't see any heuristic functions in that paper. So, what functions should I choose? Can I use straight line distance or manhattan distance?

Answer 1

It depends on the graph. It should satisfy the regular triangle equality for the admissibility of a heuristic just like the one for A* search. Euclidean distance would work well in most cases. Just a difference from A* is that the distances are calculated between the current node that we are searching and the start node (Since the best first search is done from goal to start for D* lite).