Issue181

Title Implement max of several heuristics
Priority feature Status resolved
Superseder Nosy List erez, gabi, malte
Assigned To malte Keywords
Optional summary

Created on 2011-01-04.20:08:57 by erez, last changed by malte.

Messages
msg1100 (view) Author: malte Date: 2011-01-07.01:57:42
Merged.

I made some tests with the following configurations:

1) --heuristic "h=lmcut()" --search "astar(h)"
2) --heuristic "h=lmcut()" --search "astar(max(h))"
3) --heuristic "h=lmcut()" --search "astar(max(h, h))"
4) --heuristic "h=lmcut()" --search "astar(max(h, hmax(), goalcount(),
                                     lmcount(lm_rhw(),admissible=true)))"

They all seem to work properly. In particular, 1) and 2) behave very similarly
as expected. Setting 3) highlights the problem with the current approach that
we'll need to fix eventually: this evaluates the heuristics twice and hence
takes twice as much time. The evaluator approach will fix that eventually, but
we'll have to fix the search algorithms first.
msg1099 (view) Author: malte Date: 2011-01-07.01:54:08
Reopening this to merge Erez's code as well (as IPCMaxHeuristic) since
evaluators cannot be used together with A* in the way we want at the moment.
This has to be resolved properly in some other way eventually, but for now we'll
need the heuristic-based solution for the IPC.
msg1036 (view) Author: gabi Date: 2011-01-05.12:45:29
I reviewed the changes and they look fine to me. The only thing I do not fully
understand is the plugin mechanism. Malte, maybe you could explain it to me
after the IPC deadline?

I mark the issue as resolved.
msg1024 (view) Author: malte Date: 2011-01-05.02:11:08
Actually, I have changed my mind and merged my code already, since whether or
not it works, it should be at least as good as what we had previously. Still, if
someone could review the issue181 changes, that would be great.
msg1017 (view) Author: malte Date: 2011-01-05.00:25:30
I've implemented my own version of this, using evaluators. I've pushed it to the
IPC repository, but not yet merged (it's in the issue181 branch), since it'd be
good if someone else could take a look at this (relevant classes:
CombiningEvaluator, SumEvaluator, MaxEvaluator).

I observed some strange output while testing this (see issue182), but that
doesn't seem to be new; it already happens with the old sum evaluator code.
msg1014 (view) Author: malte Date: 2011-01-04.21:59:46
Maybe you didn't implement get_involved_heuristics? That could cause
inadmissibility later on during search due to LM information not being updated.
msg1013 (view) Author: erez Date: 2011-01-04.21:48:07
I tried that before, but it caused some issues (such as inadmissibility).
However, I might have done something wrong, so I will look into this approach 
again tomorrow.
msg1012 (view) Author: malte Date: 2011-01-04.21:36:20
Adding Gabi as our resident evaluator expert.

I think the implementation is on the wrong track; it should be more along the
lines of how sum_evaluator works.

Specifically:
1) I think we should be able to perform the max of scalar evaluators, not
   just heuristics. For example, we may want to compute the max(h1+h2, h1+h3),
   but the current implementation won't let us do that because h1+h2 is not
   a heuristic.
2) I don't think we should call reach_state and evaluate for the component
   heuristics/evaluators. Rather, we should implement get_involved_heuristics
   (or what that was called) and let it do a magic. Otherwise, in situations
   like alt(f, h, max(f, h)), some heuristics will be recomputed and reach_state
   be implemented multiple times.
msg1007 (view) Author: erez Date: 2011-01-04.20:33:44
pushed to my repository
msg1006 (view) Author: erez Date: 2011-01-04.20:08:57
Implement Max of several heuristics
History
Date User Action Args
2011-01-07 01:57:42maltesetstatus: chatting -> resolved
messages: + msg1100
2011-01-07 01:54:08maltesetstatus: resolved -> chatting
messages: + msg1099
2011-01-05 12:45:29gabisetstatus: reviewing -> resolved
messages: + msg1036
2011-01-05 02:11:08maltesetassignedto: erez -> malte
messages: + msg1024
2011-01-05 00:25:30maltesetmessages: + msg1017
2011-01-04 21:59:46maltesetmessages: + msg1014
2011-01-04 21:48:08erezsetmessages: + msg1013
2011-01-04 21:36:21maltesetnosy: + gabi
messages: + msg1012
title: Implement Max of several heuristics -> Implement max of several heuristics
2011-01-04 20:33:44erezsetstatus: in-progress -> reviewing
messages: + msg1007
2011-01-04 20:08:57erezcreate