4
$\begingroup$

I am reading the book "Artificial Intelligence: A Modern Approach" by Stuart and Norvig. I'm having trouble understanding a step of the recursive best-first search (RBFS) algorithm.

Here's the pseudocode.

enter image description here

What does the line s.f <- max(s.g + s.h, node.f) do?

Here's a diagram of the execution of RBFS.

enter image description here

Improve this question
$\endgroup$
4
  • $\begingroup$ You don't understand only the line s.f <- max(s.g + s.h, node.f) or all the algorithm? $\endgroup$
    – nbro
    Mar 20, 2020 at 2:07
  • $\begingroup$ Only the specific line. $\endgroup$
    – Just_Alex
    Mar 20, 2020 at 2:39
  • $\begingroup$ I've edited your post to make it clearer then. Make sure that's still consistent with your original intent. $\endgroup$
    – nbro
    Mar 20, 2020 at 3:02
  • $\begingroup$ It is computing the cost for the successors, it will be max of the current incurred cost (node.f) or sum of s.g and s.h (as far as I remember, it is the edge cost+estimate cost to goal, I am not sure, the book might have used a similar notation before) $\endgroup$
    – SajanGohil
    Mar 20, 2020 at 11:46

1 Answer 1

Reset to default
1
$\begingroup$

This is probably more easily understood as the collapse/restore macro. The idea is that the previously explored state was collapsed and only the minimum f-cost from the sub-tree was stored. This represents the best unexpanded state in the subtree that was collapsed.

When restoring the portion of the collapsed tree, the f-cost of the restored node could either be the original f-cost (g+h), or it could be the stored f-cost if it is larger. By taking the max, the code ensures that states that are restored maintain at least the cost of the previously best unexpanded state. (If the g+h cost is larger, then we know the state wasn't previously expanded and it wasn't previously the state on the fringe with the minimum edge cost.)

The linked paper gives several examples where similar ideas are used during search.

Improve this answer
$\endgroup$
1
  • $\begingroup$ If the current paths is better than the previous one. E.g. heruistic cost is lower. Got it! Thanks. $\endgroup$
    – Just_Alex
    Mar 26, 2020 at 3:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .