1
$\begingroup$

While trying to implement LPA* (mostly based on its description in the same authors’ paper on its derivative D*Lite), I noticed it mentions predecessors and successors of a vertex without giving a full explanation.

I understand that $Pred(u)$ is the set of all vertices from which an edge leads towards $u$, and $Succ(u)$ is the set of all vertices towards which an edge leads from $u$. Predecessors and successors must be immediate neighbors (thus e.g. a predecessor of a predecessor of $u$ is not necessarily a predecessor of $u$).

In practice, however, it is quite common to have edges that are not directional, i.e. can be traversed both ways (which is equivalent to the same two nodes being connected by two antiparallel directional edges). I infer that for two vertices $u$ and $v$ connected in this way, $u$ would be both a predecessor and a successor of $v$ (and vice versa). In other words, $Pred(u) \cap Succ(u)$ is not necessarily empty.

Am I correct to assume that predecessor and successor are defined only by the existence of an edge traversable in a given direction, and are specifically not related to start cost?

$\endgroup$
2
$\begingroup$

If you have an undirected graph, you can convert it to a directed graph by including edges in both directions: for each undirected edge $(u,v)$, add directed edges $u \to v$ and $v \to u$. So, if you have undirected edges, imagine applying this transformation and then running LPA* on the resulting graph. That should make it clear what to do.

Alternatively: in an undirected graph, Pred(u) is the set of all edges incident on $u$, and so is Succ(u) (there is no distinction between them in an undirected graph). So, yes, they can overlap.

The cost of the edges are irrelevant.

$\endgroup$
2
  • $\begingroup$ Thanks for the clarification. I asked because my LPA* implementation would run into an endless loop while calculating vertext cost. I was able to rectify that by explicitly exempting the shortest-path predecessor of u from being updated in ComputeShortestPath(), even if it also is a successor. $\endgroup$ – user149408 May 29 '18 at 19:41
  • $\begingroup$ Re the fix described in my previous comment: that caused the algorithm to terminate but gave me loops in the route graph. The whole story will be a separate question. $\endgroup$ – user149408 May 31 '18 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.