Title Use new task interface in PDB Heuristic
Priority feature Status resolved
Superseder Nosy List florian, gabi, jendrik, malte
Assigned To florian Keywords
Optional summary

Created on 2015-05-05.15:01:35 by florian, last changed by jendrik.

msg4401 (view) Author: jendrik Date: 2015-07-18.01:56:12
OK, I went with the first one.
msg4398 (view) Author: malte Date: 2015-07-17.23:58:44
I don't think I know enough about the internal workings of help mode to give a
qualified answer. :-) Pick whatever solution you like.
msg4397 (view) Author: jendrik Date: 2015-07-17.23:42:06
My reasoning was that since we don't store the valid keys in help mode, we cannot 
test whether keys are valid. I agree that this is not a good reason to always 
return true. Another option would be to only test for valid keys if we're not in 
help mode:

if (!parser.help_mode())

Or we could store the keys in help mode. Which one do you prefer? I think I 
prefer the former because it seems we try to only do the things we definitely 
have to do for printing the help text in help mode.
msg4396 (view) Author: malte Date: 2015-07-17.23:31:21
> To find bugs like this automatically in the future I will let the buildbot
> run the planner tests in debug mode as well.

I think this is a great idea.

> I have fixed this in the following commit and hope you don't have
> any objections: 

Well, I'm not convinced this is the correct fix. Why is it the correct design to
have "is_valid_option()" always return true in help mode?
msg4394 (view) Author: jendrik Date: 2015-07-17.22:08:58
The patch asserts that the "transform" option has been set before trying to 
parse PDB patterns. This only works if we're not in help mode. I have fixed 
this in the following commit and hope you don't have any objections:

To find bugs like this automatically in the future I will let the buildbot run 
the planner tests in debug mode as well.
msg4336 (view) Author: florian Date: 2015-07-07.21:23:46
Merged. Thanks everyone.

(The windows build still fails because our temporary cmake file was not up to
date. It is now, but the buildbot only builds on new pushes.)
msg4335 (view) Author: malte Date: 2015-07-07.20:12:10
msg4334 (view) Author: florian Date: 2015-07-07.20:10:47
Well, its easy to check if a key is valid for the parser; I did not understand
how to check whether the key actually has the correct type. I think for the
assertion, testing if the key is valid is sufficient.
msg4333 (view) Author: malte Date: 2015-07-07.19:14:38
If it's easy to add, yes.
msg4332 (view) Author: florian Date: 2015-07-07.19:13:31
Ok, I added documentation and removed the TODOs
Unfortunately, the parser has no way to query the available keys right now.
Should I add one for the assertion?
msg4331 (view) Author: malte Date: 2015-07-07.18:45:33
I think this is fine, but I think the requirement should be documented at the
top of the two methods, and if possible it would be good to guard it with an
assertion at the top of the two methods (i.e., that a "transform" attribute has
been added to the option parser). I don't know if this kind of test is currently
possible, though. We would not test for presence of the option in the input, but
in the *parser*.
msg4330 (view) Author: florian Date: 2015-07-07.18:06:06
There is still one thing that is a bit messy in parse_pattern and parse_patterns
(pdbs/ There, we expect that someone else added a task transformation
to the options. Could you have a look at that file?

Apart from that, I think we could merge this, if you are ok with the performance
msg4329 (view) Author: malte Date: 2015-07-07.17:59:28
To rephrase my previous comment: I'm fine to see this merged now if you think
it's OK to merge. It's a large change, so there is a benefit in landing it soon.
It would be good to then work on the performance regressions without much delay,

Regarding the unpack() option, I think that in general it's a clearer design to
have an abstract interface that is supported by two classes than having an
object that can be in two different internal states that have quite different
performance characteristics. In cases where we care about using either of the
two representations, seeing an "UnpackedState" instance or a "PackedState"
instance in the code communicates the intent more clearly than just using
documentation or assertions. But of course there's also an overhead for using
virtual methods.
msg4328 (view) Author: malte Date: 2015-07-07.16:29:28
Do you think this issue is ready to merge?
msg4327 (view) Author: florian Date: 2015-07-07.16:14:29
Sounds good. I think we (or Jendrik and me) also previously discussed the
possibility of a state class that access data without unpacking by default but
has an unpack() method that can be called if the caller expects to access most
of the variables. Once unpack() is called, the state will be unpacked internally
and all subsequent queries for values will use the unpacked data.

I think this should be part of issue348. How do you want to handle this issue?
Should we wait for the new state class?
msg4326 (view) Author: malte Date: 2015-07-07.15:53:33
I looked at that task. The used pattern has 4 variables; the task has 525.

Our new code completely unpacks the state, our old one only looked at the state
variables used in the pattern. I guess this is a case where it would be good to
never unpack the state.

Generally speaking, in some contexts unpacking a state is a good idea and in
others it is not. The blind heuristic is another example where you don't want to
unpack. Our current task interface currently doesn't have a way to avoid
unpacking. One possibility is to replace the current concrete State class with
an abstract interface with unpacking and non-unpacking implementations.
msg4325 (view) Author: florian Date: 2015-07-07.15:37:01
In te airport task, we mostly lose the time in the search (preprocessing only
takes 0.04s/0.06s and search takes 19.48s/29.32s). The old heuristic computation
only did

    int h = distances[hash_index(state)];

where the new implementation does 

    State state = convert_global_state(global_state);
    int h = pdb.get_value(state);

Since pdb.get_value(state) only calles distances[hash_index(state)], the
overhead seems to be convert_global_state(). The rest of the method (test for
dead end) is the same in both revisions.
msg4324 (view) Author: florian Date: 2015-07-07.15:16:56
I was just surprised that the changes are so large (>30%) in both directions. In
some of the plots I didn't even recognize a trend. I expected the change to have
less effect and the effect to be mostly negative, because of the additional

I'll have a look at the airport and pipesworld-notankage instances where the
pdb() config loses most time and try to figure out why.
msg4323 (view) Author: malte Date: 2015-07-07.09:50:21
I don't think it's a surprise that runtime changes when we use the new task
interface. Didn't that happen for other heuristics, too?

I guess the improvement in iPDB in peg solitaire is because we compute the
heuristic values directly now; at around 3 solved tasks, coverage is still very
low (apparently it used to be 19, see issue536), which hopefully will improve
once we do the faster hill-climbing again.

Just to be on the safe side, it would be interesting to know where the extra
time in the pdb() config is spent. If it's for the precomputation, there's a lot
of code that we might have to check for performance regressions, but if it's for
the main search, there's only a tiny code path that needs looking at.
msg4322 (view) Author: florian Date: 2015-07-07.02:57:12
Results are in and look somewhat unexpected.

Except for iPDB, memory changes by less than 1%, expansions, evaluations and
costs stay the same.
But run times are all over the place, even for other configs:

Scatterplots show total_time of the base config on the x axis and
(total_time[v1] / total_time[base]) on the y axis (only commonly solved tasks).
msg4319 (view) Author: malte Date: 2015-07-03.12:58:32
Sure, please run the experiments.
msg4318 (view) Author: jendrik Date: 2015-07-03.12:18:49
Florian and I think it would be best to try to merge this issue as soon as 
possible. We propose to run experiments for all touched configurations and ignore 
runtime regressions in ipdb. When issue547 is done, we should check that the 
random walk speed in ipdb is up to par with the old implementation.
msg4317 (view) Author: florian Date: 2015-07-03.11:59:35
Ok, i did steps 1. and 2. and created issue547 for the remaining steps.

How should we proceed with this issue? By now, its a very large diff and for
iPDB it will be hard to evaluate the performance, because the temporary
implementation of the successor generator will slow it down. I could still run
experiments on all other heuristics that I touched here.
msg4314 (view) Author: malte Date: 2015-07-02.18:46:27
> One open problem is that the sampling for iPDB now also uses the task
> interface to do random walks. Since there is no
> successor generator for the State class, we currently loop through all
> operators on each step of the random walk.

OK, this is a problem indeed. :-) Let's use this as an opportunity to go forward
on moving the successor generator from preprocessing to search. (More llama

We need a a new successor generator class that has a public method to generate
the applicable operators and is constructed from a Task object (or TaskInterface
or whatever). The random walk code should use this. For consistent naming, I
guess the new class should be called "SuccessorGenerator" and the old one
"GlobalSuccessorGenerator". As a first step, it's OK for this new
SuccessorGenerator to just loop over all operators like the your code does, so
it's just a matter of introducing and using the interface. We should then open
an issue to implement the new successor generator properly.

I would make this five steps:

1. Introduce the new SuccessorGenerator, but without the clever implementation.
2. Use it in the iPDB code.
3. Provide a decent implementation for the new SucessorGenerator.
4. Use the new SuccessorGenerator in the places where we currently use the old one.
5. Get rid of the old SuccessorGenerator.

I would prefer to have 1.+2. already done in this issue so that we don't have to
touch the iPDB code in the separate successor geneator issue, but I'm also fine
with keeping all these steps out of the iPDB issue. In any case, we need a new
issue for the successor generator.

Can you open it? I don't know how soon I can find time, but I can try to look
into the successor generator implemenation (steps 3.-5. above).

Please let me know how you would like to proceed.
msg4313 (view) Author: florian Date: 2015-07-02.18:29:26
I uploaded a first draft on bitbucket. One open problem is that the sampling for
iPDB now also uses the task interface to do random walks. Since there is no
successor generator for the State class, we currently loop through all operators
on each step of the random walk.
msg4236 (view) Author: florian Date: 2015-06-03.19:04:29
We managed to deal with most of these problems: we assume that the caller was
involved in the creation of the PDBHeuristic object and knows the correct task
to use (usually this is because the caller created teh PDBHeuristic by
forwarding its own task). Calling the method with a Proxy from the wrong task is
a usage error that we can test for in the method.

Another problem that came up is how to deal with sampling: iPDB currently
generates a list of samples by doing random walks and then evaluates its
canonical heuristic on these samples. Currently, the samples are GlobalState
objects because the state registry can only generate such states (by applying
operators). Also, the evaluation function of the canonical heuristic expects a
GlobalState as its parameter. I'm not sure how we could use State objects
(states from the local task) to do the sampling and evaluation. I'm also not
100% convinced that we should do this.
msg4211 (view) Author: florian Date: 2015-05-18.20:05:08
This seems a bit more complicated than I thought originally: the PDB heuristic
has some public methods that accept parts of the task (an operator, a pattern,
etc.). If the PDB heuristic is based on an internal task, how should the caller
know with which operator, variable index, etc. to call the functions.

For example, there is is_operator_relevant(op), which (I guess) should take an
OperatorProxy or an operator ID. But the caller has no access to the task these
operators should come from.

Any suggestions?
msg4182 (view) Author: florian Date: 2015-05-05.15:01:35
The PDB heuristic should use the task it get from the options object (as a
TaskProxy) instead of the global task.

Once this is done, we can continue with issue527.
Date User Action Args
2015-07-18 01:56:12jendriksetmessages: + msg4401
2015-07-17 23:58:44maltesetmessages: + msg4398
2015-07-17 23:42:06jendriksetmessages: + msg4397
2015-07-17 23:31:21maltesetmessages: + msg4396
2015-07-17 22:08:58jendriksetmessages: + msg4394
2015-07-07 21:23:46floriansetstatus: chatting -> resolved
messages: + msg4336
2015-07-07 20:12:10maltesetmessages: + msg4335
2015-07-07 20:10:47floriansetmessages: + msg4334
2015-07-07 19:14:38maltesetmessages: + msg4333
2015-07-07 19:13:31floriansetmessages: + msg4332
2015-07-07 18:45:33maltesetmessages: + msg4331
2015-07-07 18:06:06floriansetmessages: + msg4330
2015-07-07 17:59:28maltesetmessages: + msg4329
2015-07-07 16:29:28maltesetmessages: + msg4328
2015-07-07 16:14:29floriansetmessages: + msg4327
2015-07-07 15:53:33maltesetmessages: + msg4326
2015-07-07 15:37:01floriansetmessages: + msg4325
2015-07-07 15:16:56floriansetmessages: + msg4324
2015-07-07 09:50:21maltesetmessages: + msg4323
2015-07-07 02:57:12floriansetmessages: + msg4322
2015-07-03 12:58:32maltesetmessages: + msg4319
2015-07-03 12:18:49jendriksetmessages: + msg4318
2015-07-03 11:59:35floriansetmessages: + msg4317
2015-07-03 11:21:02gabisetnosy: + gabi
2015-07-02 18:46:27maltesetmessages: + msg4314
2015-07-02 18:29:26floriansetmessages: + msg4313
2015-06-03 19:04:29floriansetmessages: + msg4236
2015-05-18 20:05:08floriansetstatus: unread -> chatting
messages: + msg4211
2015-05-05 15:01:35floriancreate