3

What is the difference between g-value and rhs-value of Lifelong Planning A* algorithm?

According to this link, D* Lite, g(s) directly correspond to the g-values of an A* search, i.e. g(s) = g(s') + c(s',s), and rhs(s) is given as

$$ rhs(s) = \begin{cases}0 & s = s_{start} \\ \min_{s'\in Pred(s)}(g(s') + c(s', s)) & \text{otherwise} \end{cases} $$

where, Pred(s) denotes the set of predecessors of node 's'.

Thus, unless node 's' has more than one predecessor, its g-value and rhs-value will remain same.

So, my question is, in which case will the rhs-value and g-value of a node be different?

Ian
  • 11,013
  • 2
  • 23
  • 65
vacky
  • 417
  • 4
  • 11

2 Answers2

1

From the paper, $g(s)$ is only an estimate of the distance travelled (vs a direct measurement, which is how A* computes it).

The rhs-values are one-step lookahead values based on the g-values and thus potentially better informed than the g-values.

The calculation of $rhs$ seems to be purely a sanity check that the estimate of $g(s)$ is accurate, based on the estimate of a predecessor.

in which case will the rhs-value and g-value of a node be different

Even if there is only one predecessor, if the estimate for that predecessor has changed between 2 searches then it's possible for $rhs(s) \neq g(s)$. And based on the equation above, that can happen in only one of two ways:

  1. the minimum $c(s', s)$ has changed
  2. the minimum $g(s')$ has changed

According to the paper, this represents the case where the robot makes a move and discovers that the cost of moving between two given points has changed from what was previously believed.

Ian
  • 11,013
  • 2
  • 23
  • 65
1

To expand on @Ian 's answer :

In that context, I believe a "predecessor" of vertex $u$ refers to any vertex $v$ with a directed edge $(v,u)$, i.e any vertex "from which u is accessible".

For instance, in the typical case of a 2D grid with eight neighbors for each cell and bidirectional edges (or two opposite directed edges), you almost always have multiple predecessors for a given vertex.

$rhs(s)$ integrates information from the immediate neighborhood of $s$ ("one step lookahead") which is why $rhs-values$ propagate faster than the $g-values$ and help better discriminate between multiple vertices in the priority queue to decide which one is the most promising to expand next.

$rhs(s)$ and $g(s)$ are different - vertices are "locally inconsistent" - typically around the area where the edge costs were modified, and as the local search expands to "repair" the previous path around this area, vertices along the new shortest path are made "locally consistent", i.e $rhs(s)=g(s)$

al-dev
  • 331
  • 1
  • 6