CODEWITHSUNDEEP
algorithmgraphpath-findingd-star
Arthur Ferreira
Arthur Ferreira

Reputation: 321

D* Lite and LPA* Algorithms: concept of predecessors and successors

I am trying to implement the D* Lite and LPA* algorithms (both proposed by Sven Koenig), and I am having difficulty in understanding the concept of the list of predecessors and successors contained by each node. I tried looking for answers at various sources, but I couldn't find a definitive one.

Could anyone help me out with it?

Thank you.

Upvotes: 2

Views: 1444

Answers (1)

Andrew Walker
Andrew Walker

Reputation: 42470

On a directed graph:

  • successors are those nodes that are reachable from the current node
  • predecessors are those nodes from which the current node can be reached.

On an undirected graph (common for simple examples), they will be the same.

On the (undirected) 4-connected lattice below

  • the successors of the node E are B, D, F and H (that is, if you're at E, you can reach any of the states pointed at by the arrows).
  • the predecessors of the node E are B, D, F and H (found by flipping the directions of the arrows, and seeing what arrives at E).

successor-nodes

Upvotes: 3

Related Questions