Title Update parents in lazy search when reopen_closed is switched off
Priority feature Status chatting
Superseder Nosy List malte, manuel, mkatz
Assigned To Keywords
Optional summary

Created on 2012-10-26.15:13:26 by mkatz, last changed by manuel.

msg2370 (view) Author: malte Date: 2012-10-26.15:18:30
Erez adds: "That invariant is already violated in eager GBFS, which reassigns
the parent. However, I agree it should be documented."

So we should also add some documentation in the eager search case.
msg2368 (view) Author: mkatz Date: 2012-10-26.15:13:26
As a result of a correspondence between Alex Shleyfman and Michael, in order to 
improve the quality of the plans returned by the lazy search without reopening 
closed nodes, a change was suggested, adding an update of the parent in case of 
smaller g values. Here is a part of the following email correspondence between 
Michael and Malte:

What is the reason (besides evaluation time) for not updating the parent of nodes 
reached via shorter paths when reopen_closed is switched off?

I would guess historical reasons. Most of that code is from a time when
we didn't even store g values (didn't need them at the time), and hence
we wouldn't be able to know which path was cheaper. Before Silvia
implemented lazy weighted A* for LAMA 2008, the lazy search code only
had greedy best-first search. We had g values in the A* code, but that
was a completely separate implementation.

One small disadvantage of updating the parent pointers is that the g
values are no longer correct. If I generate A with a g value of 10, then
its child B with a g value of 20, then find a shorter path to A with a g
value of 7 and update the parent pointer for A, then for consistency I
should also update the g value of B to 17 since it's affected by the
change. Without reopening, this won't happen.

However, I think that the wrong g values are a small price to pay for
actually having the shorter paths, so this is not really a good reason.
It should probably be documented though, since it might confuse people
to see the invariant "g value = cost of the path obtained by tracing
back the parent pointers" violated.
Date User Action Args
2016-09-07 12:42:32manuelsetnosy: + manuel
2012-10-26 15:18:30maltesetstatus: unread -> chatting
messages: + msg2370
2012-10-26 15:17:06maltesetnosy: + malte
2012-10-26 15:13:26mkatzcreate