In optimized D*Lite algorithm as shown in the figure below (page 5, of the paper D*Lite), when the procedure ComputeShortestPath() is called for the first time in line 31, U(list of inconsistent vertices) contains only goal vertex ($s_{goal}$). Thus in the procedure ComputeShotestPath()(line 10-28), $u = s_{goal}$. And as, $k_{old}=k_{new}$ (because $k_m=0$), condition $k_{old}\leq k_{new}$ is satisfied and $u = s_{goal}$ is again inserted in U with same value of $k_{old}=k_{new}$. Thus, it seems that line(11-15) will run forever, and the algorithm will not be able to find the shortest path from goal to start.

I know that this algorithm has been widely used and I am failing to understand it. But where am I going wrong?

enter image description here

  • $\begingroup$ $k_{new} = CalculateKey(u))$ that additional closing parenthesis at the end of this line looks wrong to me. $\endgroup$ – Bending Unit 22 Apr 10 '16 at 10:51

The first relevant line is line 6:

$$U.Insert(s_{goal}, [h(s_{start}, s_{goal});0]);$$

Basically speaking, this is an association of the goal to some vector with two values in it. Now $U$ looks like this:

$$U:s_{goal}\rightarrow \left(\begin{matrix}h(s_{start}, s_{goal})\\0\end{matrix}\right)$$

Of course, $U$ is a list of such associations, but within the context of this question there's only one element in it.

Thus in the procedure ComputeShotestPath() (line 10-28), $u = s_{goal}$

That is correct.

And as, $k_{old}=k_{new}$ (because $k_m=0$)

That is not necessarily correct. The relevant lines are 12


Looking at what $U$ is above, this line is equivalent to:

$$k_{old}=\left(\begin{matrix}h(s_{start}, s_{goal})\\0\end{matrix}\right);$$

and line 13 for $k_{new}$:


I think the extra parenthesis is a typo. I will ignore it. This value actually comes from a function call and results in the following:

$$k_{new}=\left(\begin{matrix}\min\big(g(s), rhs(s)\big) + h(s_{start}, s) +k_m\\rhs(s)\end{matrix}\right);$$

Where $s$ is the parameter passed to the function, which is actually $u$ which in turn is actually $s_{goal}$, also as you stated $k_m=0$, thus:

$$k_{new}=\left(\begin{matrix}\min\big(g(s_{goal}), rhs(s_{goal})\big) + h(s_{start}, s_{goal})\\rhs(s_{goal})\end{matrix}\right);$$

I don't know what the functions $g()$ and $rhs()$ do (look them up in the paper) and what values they return, but if $rhs(s_{goal}) = 0$ and $g(s_{goal}) > rhs(s_{goal})$ then yes it's true that $k_{new}=k_{old}$.

condition $k_{old}\leq k_{new}$ is satisfied

I think there's your problem. I for one cannot see a condition $k_{old}\leq k_{new}$ being evaluated in the code. I guess you are referring to line 14, but that line actually looks like that:

$$if(k_{old} \color{red}{\dot\lt}k_{new})$$

This is not a less-than-or-equal sign. That is a les-than sign with a dot above it. I don't think they are the same thing and I wonder if the following is actually valid way to express that: $$\le\neq\dot\lt$$

Anyway, what the heck is $\dot\lt$? I don't know. What I think it means is that it's an element wise less-than operator. In languages like Matlab or Octave it's common to add a dot to denote that an operator is applied element wise. The thing is that it doesn't make too much sense to apply a less-than operator to a vector. It's defined for scalar values, not vectors or matrices. I admit that I'm not sure about this one.

The condition in line 14 is not satisfied.

Now all of the above is under the assumption that the condition of the while loop in ComputeShotestPath() is true and the body of the loop is executed.

The (first part of the) condition looks like this:

$$U.TopKey()\dot\lt CalculateKey(s_{start})$$

With the assumptions from above this expands to:

$$\left(\begin{matrix}h(s_{start}, s_{goal})\\0\end{matrix}\right) \dot\lt \left(\begin{matrix}\min\big(g(s_{start}), rhs(s_{start})\big) + h(s_{start}, s_{start})\\rhs(s_{start})\end{matrix}\right)$$

Again, I don't know how this algorithm works exactly, I had a quick look at the paper and from what I understood is that $h(s_{start}, s_{start}) = 0$ and $rhs(s_{start}) = 0$, which makes me doubt that the condition is true.

In other words: I don't think the while loop is even running at all and if it actually does, it's not because of that part of its condition.

tl,dr; Holy cow, stop staring at nontextual pseudocode! Get yourself an implementation (or write it yourself) and use a debugger to step through the program.

Run the actual code on an actual machine, this is what matters in the end.

| improve this answer | |
  • $\begingroup$ Thanks a lot for the detailed explanation @Bending Unit 22. I misunderstood the sign <˙ to be equal to ≤. $\endgroup$ – vacky Apr 10 '16 at 18:02
  • $\begingroup$ And yes.. im going to actually implement the pseudo code, but isn't it necessary to understand it before blindly implementing? Im sorry if my approach is wrong. Im new to this coding world and so once again thanks for your explanation. @Bending Unit 22 $\endgroup$ – vacky Apr 10 '16 at 18:10
  • $\begingroup$ You are right, you need a certain amount of understanding. But if you implemented it you would have actually encounteted an endless loop. If you think there's a problem, it might be that your thinking is the actual problem. If it fails on the machine, you know that there's a real problem and you can be sure that it exists. In other (obscure) words: you cannot connect a debugger to Plato's cave. =) $\endgroup$ – Bending Unit 22 Apr 10 '16 at 18:26
  • $\begingroup$ Thanks for your advice @Bending Unit 22. I will keep this in mind. $\endgroup$ – vacky Apr 10 '16 at 19:09

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.