Defining path directions on D*Lite

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?

Answers


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.


Need Your Help

VBA for Access 2003 - DDL for creating access file: setting the Autonumber data type

database ms-access vba ms-access-2003 ddl

So I have the below VB that creates an access file in the default workspace, creates a table, create some fields in that table...just need to know the syntax for setting the first data type/field to

Possible to map a new file extension to an existing handler in ASP.NET?

asp.net web-services asmx httphandler httpmodule

I have a scenario where my application is going to be publishing services that are consumed by both PC's and mobile devices, and I have a HTTPModule that I want to only perform work on only the mob...