Title issues when using multiple heuristics
Priority bug Status chatting
Superseder Nosy List erez, gabi, jendrik, malte, salome
Assigned To salome Keywords 1.0
Optional summary

Created on 2011-01-07.02:00:05 by malte, last changed by jendrik.

msg6874 (view) Author: jendrik Date: 2018-03-15.19:50:17
I'm done with this round of comments. I can have a look again later, if you like.
msg6870 (view) Author: salome Date: 2018-03-15.17:35:01
I created a pull request:

Instead of specifying the mpd option, a "lazy_evaluator" can now be passed to
"A*" search which will be reevaluated on states before they get pulled out on
the open list. Furthermore, all path-dependent evaluators will now always be
notified of state transitions, regardless of whether or not a lazy evaluator is set.

Note that the expansion order can change with the new implementation: Since we
removed last_key we have no way of knowing with what h-value a node was inserted
into the open list. We only know if the h-value of the state changed between the
last time we evaluated that state and when we (possibly) reevaluate the state
when pulling it out of open.
For example: a state was the first time inserted with g=4,h=3. Then it was
reached over a different path and inserted with g=3,h=3 (at this point the
heuristic is not reevaluated). When we remove the node with g=3,h=3, h gets
reevaluated to lets say 5 and the node will be reeinserted with g=3,h=5. When
the node with g=4,h=3 gets removed, the heuristic will not be reevaluted since
no new path to the state has been found. The old code would however still see
that it was inserted with h=3 but now has h=5 and it would reinsert the node
with g=4,h=5, while the new code will expand the node at this point.
I did run some preliminary tests that suggest that this change does not hit
performance much, but we should keep this in mind when evaluating the actual
msg6264 (view) Author: erez Date: 2017-04-28.11:48:11
I wish I had the time to do it... But I would 
be happy to help (maybe by reviewing the 
msg6263 (view) Author: salome Date: 2017-04-28.11:47:00
I had a look into the mpd code a while back already, so I'd be interested in
tackling it.
msg6262 (view) Author: malte Date: 2017-04-28.11:40:45
Anyone interested in tackling this? It's somewhat in the way of completing the
Evaluator/Heuristic unification, and I think the current sprint would be a good
opportunity to come up with a solution. I think that now that the h values are
no longer stored messily by the search, we are in a much better position to
resolve this than we used to be.
msg6260 (view) Author: jendrik Date: 2017-04-28.10:12:38
We stumbled over heuristics[0] again yesterday. The only remaining code that still 
uses heuristics[0] is the multi-path-dependence code. This code also uses the 
last_key_removed hack. We believe that both hacks could be removed by passing a 
dedicated heuristic that is evaluated instead of using these two hacks. This 
heuristic could replace the "mpd" parameter.
msg2248 (view) Author: malte Date: 2012-06-01.11:33:45
See also issue339.
msg1101 (view) Author: malte Date: 2011-01-07.02:00:05
Our search algorithms currently do some special-casing of heuristics[0], which
causes various problems. For example, the max evaluators and sum evaluators
don't work properly; see e.g. issue181 and issue182.

This needs to be fixed by rethinking the way that the search algorithms store
data about the search space.
Date User Action Args
2018-03-15 19:50:17jendriksetmessages: + msg6874
2018-03-15 17:35:01salomesetmessages: + msg6870
2017-11-28 12:56:58maltesetassignedto: salome
2017-04-28 11:48:11erezsetmessages: + msg6264
2017-04-28 11:47:00salomesetmessages: + msg6263
2017-04-28 11:40:45maltesetmessages: + msg6262
2017-04-28 10:12:38jendriksetnosy: + salome, jendrik
messages: + msg6260
2012-06-01 11:33:46maltesetmessages: + msg2248
2011-01-20 03:09:27maltesetkeyword: + 1.0
2011-01-07 02:00:05maltecreate