Defining path directions on D*Lite

Question

I'm currently working on an implementation of the D*Lite algorithm from Sven Koenig. http://idm-lab.org/bib/abstracts/papers/aaai02b.pdf. Basically I'm trying to understand all the details before starting to implement it. It seems that the algorithm works on directed graphs, that's the way to define the Pred and Succ functions.

How do I define the direction of the graphs and which the parameters decide the direction of the graphs. Should I use the value of some parameter like the g cost (which doesn't seem to be a good choice...since is the g cost along with the rhs value the one the algorithm updates) or the heuristic estimate of the distance?

Answer 1

D*, and D*-lite will both work on both directed and undirected graphs.

A graph is G = (V, E), where V is a list of configurations (or states) that can be reached. E is a list of the connections between vertices. In a directed graph, E is a set of edges which are ordered pairs (u, v), where both u and v are vertices. In an undirected graph, E is a set of unordered pairs.

Planning on an undirected graph is equivalent to planning on a directed graph, with a bidirectional edge. That is, if (u,v) is an edge (v, u) will also be an edge.

How you construct the graphs is application specific, and varies from simple grids to much more complex strategies like lattice approximations to forward kinematics.