Issue578

Title Limit time spent in iPDB dominance pruning
Priority feature Status resolved
Superseder Nosy List florian, jendrik, malte, silvan
Assigned To silvan Keywords
Optional summary

Created on 2015-10-08.21:56:13 by florian, last changed by silvan.

Messages
msg6853 (view) Author: silvan Date: 2018-03-15.12:04:32
Happy with this, merged.
msg6851 (view) Author: malte Date: 2018-03-15.11:54:27
Thanks! If we use the 60 seconds timeout as a reference point, the only domain
where the timeout hurts is Pegsol (of which there are to benchmark sets, but I
think one is actually a subset of the other). The timeout helps marginally in a
few domains, but not by that much.

There is quite a lot of benchmark selection bias here: almost all Pegsol
instances have roughly the same size (they differ mainly in plan length), so 48
of the 50 tasks behave identically w.r.t. dominance pruning (416318 subsets pruned).

Given that the current behaviour is no time limit, I see nothing wrong with
merging this now. To me a default timeout makes sense in principle, but less so
if we don't also have a timeout for hill climbing. So I'm fine with merging this
now and having the general timeout discussion separately.
msg6849 (view) Author: silvan Date: 2018-03-15.11:23:00
Here are results for hill climbing (with 900s time limit, called hc900) and
systematic generation of patterns of size 2 (sys2), with different time limits
for dominance pruning:

http://ai.cs.unibas.ch/_tmp_files/sieverss/issue578-v1.html

For HC, there is no impact, because dominance pruning is usually *very* fast,
with the exception of a few tasks in a few domains. For sys2, the picture is
different: dominance pruning usually takes quite long, and setting short time
limits (30 and 60 seconds) actually hurts coverage. Longer time limits (300-900)
result in slightly higher coverage, although they obviously increase the number
of tasks for which dominance pruning cannot be finished within the overall time
limit of 30 minutes.

Regarding useful default values, I suggest to wait for today's discussion at the
Fast Downward meeting. For the meantime, the question is whether we just want to
close this issue as is, introducing the new option, or wait after the discussion.
msg6827 (view) Author: jendrik Date: 2018-03-14.14:14:49
I left some comments on Bitbucket.
msg6826 (view) Author: silvan Date: 2018-03-14.14:09:38
issue735 shows enough values: with pattern collections from hillclimbing, the
dominance pruning mostly happens within milliseconds, and sometimes may take
10-15 seconds. In woodworking, it fails on quite a few tasks or uses very much
runtime.

With pattern collections from systematic(2), dominance pruning often fails due
to running out of time. There, a limit would definitely make sense.

I'll run experiments with 30, 60, and 300 seconds for both pattern generation
methods.
msg6824 (view) Author: malte Date: 2018-03-14.13:49:03
Not sure. Perhaps run the old code first and do a report that shows how long it
takes on the benchmarks so that we have something to start from? Or perhaps the
issue735 experiments already contain enough information for this.

I have some comments on the documentation in the pull request that we can
perhaps discuss later (after the AI course).

Regarding time limits in general, we are currently a bit inconsistent regarding
having a "good" value as a default or infinity as a default. For example,
invariant synthesis has a five-minute timeout, but iPDB pattern generation has
no timeout. I would suggest discussing this some time during the sprint.
msg6823 (view) Author: silvan Date: 2018-03-14.13:41:57
What would be a reasonable time limit to try?
msg6822 (view) Author: malte Date: 2018-03-14.13:39:32
I think we should run experiments to see how much difference this makes and how
often it fires.
msg6821 (view) Author: silvan Date: 2018-03-14.13:36:22
I added an option to limit time spent in dominance pruning.

Any volunteers for reviewing? Should be quick:
https://bitbucket.org/SilvanS/fd-dev/pull-requests/32/issue578/diff

I would even say that we don't necessarily experiments.
msg6725 (view) Author: malte Date: 2017-12-05.13:51:21
Based on issue735, we know that there are still some cases where dominance
pruning is time-critical, and this issue would be quite easy to implement.
msg4650 (view) Author: florian Date: 2015-10-08.21:56:13
On 08.10.2015 17:35, Santiago Franco wrote:
> I noticed that in problem Woodworking-17, sequential optimal, ipc 2011, 
>   iPDB is finishing after around 760 secs even though I set the max_time 
> to 200.  When I looked at the code, I noticed that it did exit the hill 
> climbing phase at around 200 seconds, but then it goes ,without checking 
> the global timer, into dominance prunning.  Dominance prunning did not 
> prune anything but it took around 500 secs.
> [...]
> In my code, I am now checking the global timer before iPDB does 
> dominance pruning.  Just wanted to know what you think about that, and 
> whether dominance pruning should be done even after iPDB has reached the 
> specified max_time.

Dominance pruning is currently called after catching the timeout exception, so
it is not affected by the time limit for hill-climbing. I think it would make
sense to give it its own time limit: its not really part of hill-climbing and
could still be time-effective to run, even if hill-climbing took to long, but we
don't want to run it for too long. Instead of not running it at all, I would
suggest to add a separate time limit just for dominance pruning and change the
pruning code so it still does something useful based on the information it has
at the time it reaches the time limit (half the pruning might still have a
significant impact).
History
Date User Action Args
2018-03-15 12:04:32silvansetstatus: reviewing -> resolved
messages: + msg6853
2018-03-15 11:54:27maltesetmessages: + msg6851
2018-03-15 11:23:00silvansetmessages: + msg6849
2018-03-14 14:14:49jendriksetmessages: + msg6827
2018-03-14 14:09:38silvansetmessages: + msg6826
2018-03-14 13:49:03maltesetmessages: + msg6824
2018-03-14 13:41:57silvansetstatus: in-progress -> reviewing
messages: + msg6823
2018-03-14 13:39:32maltesetmessages: + msg6822
2018-03-14 13:36:22silvansetmessages: + msg6821
2018-03-14 12:28:14silvansetstatus: chatting -> in-progress
assignedto: silvan
2017-12-05 13:51:21maltesetstatus: unread -> chatting
messages: + msg6725
2015-10-09 10:02:39silvansetnosy: + silvan
2015-10-08 22:00:06jendriksetnosy: + jendrik
2015-10-08 21:56:13floriancreate