Astar reopens nodes with consistent heuristics

[Junkyu Lee]

Hello, 

I was running a* with a consistent heuristic on some problems.

a* search reopened nodes in several problems in the data-network-opt18-strips domain including the first instance p01.pddl

For example, I cloned the main branch of downward and ran the following cases

  ./downward --search "astar(cegar())" < p01.sas

  ./downward --search "astar(blind())" < p01.sas

It's not reopening the closed node, so it doesn't increase statistics.inc_reopened();

but it enters code block inside 

  else if (succ_node.get_g() > node->get_g() + get_adjusted_cost(op) ) 

Is this expected behavior?

Or is it because of some default options that I didn't pass correctly?

Best,

Junkyu

[Malte Helmert]

Hi Junkyu,

this is expected behavior. Consistent heuristics do not require
reopening because the g value at the time a node is first expanded is
guaranteed to be minimal.

I think the confusion here is about what exactly is meant by
"reopening". The code block you mention is entered whenever we reach a
state on a path that is cheaper than the cheapest path to that state we
have seen previously. But this is only "reopening" *if a node with that
state has already previously been closed*.

Example:

I have states s0 (initial), s1, s2 and transitions s0 -> s1 with cost 1,
s0 -> s2 with cost 3 and s1 -> s2 with cost 1.

Initially, we expand the initial node with state s0 and generate nodes
for the two successors: to s1 with g value 1, and to s2 with g value 3.
Expanding this node closes it, the other two nodes are open.

Next, we expand the node for s1 and see that there is already a node for
the successor s2. We also see that we now have a cheaper path (g value
2) than previously. So we enter the code block you mention above, update
the g value for the node (reusing it for this new, cheaper path), and
push it to the open list again with its new priority. This is not
reopening because the node we're updating wasn't closed.

Does this help?

Best,
Malte

[Junkyu Lee]

Dear Malte,

Yes, thanks for your explanation.

Best,

Junkyu