Recursive Best First Search Explained

The idea of recursive best first search is to simulate A* search with \(O(bd)\) memory, where \(b\) is the branching factor and \(d\) is the solution depth.

is cost so far and

1
h

is the heuristic. The algorithm is reproduced below:

function RECURSIVE-BEST-FIRST-SEARCH(problem) returns a solution, or failure
    return RBFS(problem, MAKE-NODE(problem.INITIAL-STATE), INFINITY)

function RBFS(problem, node, f_limit) returns a solution, or failure and a new f-cost limit
    if problem.GOAL-TEST(node.STATE) then
        return SOLUTION(node)
    successors <- [ ]
    for each action in problem.ACTIONS(node.STATE) do
        add CHILD-NODE(problem,node,action) into successors
    if successors is empty then
        return failure, INFINITY
    /* update f with value from previous search, if any */
    for each s in successors do
        s.f <- max(s.g + s.h, node.f))
    loop do
        best <- the lowest f-value node in successors
        if best.f > f_limit then
            return failure, best.f
        alternative <- the second-lowest f-value among successors
        result, best.f <- RBFS(problem, best, min(f_limit, alternative))
        if result != failure then
            return result

Think of

node.f

as the best

1
bot_node.g + bot_node.h

where

1
bot_node

is a node from the bottom layer in the subtree from

1
node

The part that perplexed me the most is,

/* update f with value from previous search, if any */
for each s in successors do
    s.f <- max(s.g + s.h, node.f)

If we visit

node

1
RBFS(p_node)

, it is probable that

1
RBFS(node)

returns

1
failure, new_f

. Then the

1
f

s of

1
p_node.successors

will change their order, and in the next iteration, i.e., in the next recursive call of

1
RBFS

, we might have a different

1
min(f_limit, alternative)

. Thus, continuing to do so, it could visit

1
node

twice in

1
RBFS(p_node)

If it has already expanded

node

and got

1
failure, node.f = new_f

, we know that from

1
node

, it will reach a “barrier”, a frontier of at least

1
f = node.f

. Then each children,

1
child_node

1
node

, will meet a frontier of at least

1
f = node.f

as well. If

1
child_node

has

1
child_node.g + child_node.h

less than

1
new_f

, it is underestimating. The algorithm can safely replace its

1
f

with

1
node.f

With consistent heuristic, the instruction is perfectly fine sine each path has non-decreasing f-values and thus

1	child_node.f

won’t be replaced by

1
node.f

in first

1
RBFS(node)

. Problem is, with inconsistent heuristic, sometimes when

1
node

is expanded at the first time,

1
node.f = f.g + f.h

isn’t a value from frontier, moreover, it didn’t even reach its successors. Then the

1
max

action makes

1
child_node

get a higher

1
f

. Therefore, the algorithm doesn’t necessarily behave like naive A* search and expand the node with least

1
g + h

Recursive Best First Search Explained

September 17, 2014

An Interesting Math Problem

Hello! It’s been quite a while since my last post. This post I’ll present you a math problem, and a clever proof.

Neural Network to Predict DotA Game Results

SAT Solver with Su Doku!