2

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.

Arthur Ferreira
  • 311
  • 1
  • 6
  • 18

1 Answers1

3

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

Andrew Walker
  • 40,984
  • 8
  • 62
  • 84