I have a few questions about the LPA* algorithm, I think I know the answers to most of these questions, but I just wanted to be sure.
Here is the pseudocode for reference:

enter image description here

and here is the link to the pdf: https://www.cs.cmu.edu/~maxim/files/aij04.pdf

Question 1:

at Line {01} we calculate the key for each node for the priority queue. Since this key is basically the same thing as in A* where we get the min F value and break ties towards smaller g value, why do we take min(g(s), rhs) as our g value? isn't the rhs value

potentially better informed than the g-values


Question 2:
What is the intuitive reasoning for the condition U.TopKey()<CalculateKey(sGoal) at line {09}

Question 3:
Why do we set g(u) to infinity at line {15} but set g(u) to rhs(u) at line {12}.

P.S I hope asking multiple questions in one post is alright, since I didn't want to make multiple posts.

  • $\begingroup$ May I ask why the downvote? $\endgroup$
    – a a
    Mar 18 at 21:10


Your Answer

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

Browse other questions tagged or ask your own question.