Title h^add heuristic (and hence also h^FF) overflows on reasonably-sized instances
Priority bug Status resolved
Superseder Nosy List erez, malte, moritz, patrik, rpgoldman
Assigned To malte Keywords
Optional summary

Created on 2011-05-18.09:12:53 by patrik, last changed by malte.

File name Uploaded Type Edit Remove
log1-FDTrans.pre patrik, 2011-05-18.09:12:52 application/octet-stream
robert-tony-domain.pddl malte, 2011-06-29.16:31:31 application/octet-stream
robert-tony-problem.pddl malte, 2011-06-29.16:32:01 application/octet-stream
robert-tony.soln malte, 2011-06-29.16:32:08 application/octet-stream
msg1395 (view) Author: malte Date: 2011-06-29.18:44:17
The new issue is issue247. I've tentatively added some of you to the nosy list
there, but not all of you. As always, feel free to add yourself as interested.

Marking this one as resolved.
msg1392 (view) Author: malte Date: 2011-06-29.18:23:21
OK, the original issue is resolved. However, I can still not solve Robert and
Tony's instance with the configuration they have been using. It looks like there
is a second, unrelated issue with the landmark heuristic. I will open a separate
issue for that.
msg1391 (view) Author: malte Date: 2011-06-29.17:58:28
I added overflow checking to the additive heuristic, but not yet to the
implementation used by the LAMA-FF synergy.

What the code does is check if cost value become larger than 100M; if so, we
clamp it to that value. The threshold is chosen somewhat arbitrarily so that we
will still stay comfortably below the magic 2 billion even when using something
like Weighted A* with a weight of 10. Since the clamping is nasty and
unexpected, it prints a warning message to stderr and stdout the first time it

Here's what it looks like:

Will now extend it to the LAMA-FF synergy.
msg1390 (view) Author: malte Date: 2011-06-29.16:31:31
Robert Goldman and Tony Schneider report another instances of the same
phenomenon. Their problem files, along with a plan, is attached.
msg1357 (view) Author: malte Date: 2011-05-19.12:46:29
64 bit won't make much difference -- we have an exponential growth in some input
parameter here; making the problem twice as large would make it exceed 64 bits
if it currently exceeds 32 bit. Actually, the h^add costs at the moment in
Patrik's example appear to grow up to 3018190115017 = 1.37 * 2^41, so even
something only about 50% larger would hit the next ceiling.

Patrik, the reason we're using FF/add is partly historical and partly because in
my experience h^add tends to be a better heuristic than h^max in most
experiments I've seen.

I'd try to avoid switching to floating point, but the other two options Patrik
suggests (adding an implementation of FF/max and adding tests against overflow)
should also be easily implementable. Actually, for the assert-fail suggestion,
we have such an assertion already -- that's the one that Moritz mentioned in
this email to the dev list. However,

 a) assertions are disabled in the release build,
 b) when the assertion fails, it's not obvious that it's due to an overflow, and
 c) I think it may be possible to create a task that bypasses the assertion,
    since it only checks the h^add values of reached facts, but overflows
    can also happen in intermediate value computations. The lines to check
    are the two lines in that use "+=".
msg1356 (view) Author: erez Date: 2011-05-19.09:01:44
We can also go to 64 bit.
It won't solve the problem, but will certainly make it harder to reproduce.

Also - checking all the places an overflow could occur in the code would be a lot 
of work.
msg1355 (view) Author: patrik Date: 2011-05-19.04:19:48
No idea ;)

Is there a reason why you use FF/add rather than FF/max?

One possibility is to provide both implementations, with an option to select
which underlying cost estimate to use.

Another (more complicated) is to use floating-point, or some emulation of it,
for h^add; if the numbers are so large they overflow a 32-bit int, then
truncing a couple of least significant digits is probably not going to make
that much difference to the informedness of the heuristic... But this is
probably difficult to implement in an efficient way.

Of course, the easiest solution is to just assert-fail when numbers get too
large... (I've had similar issues with the rational numbers in hsp*, and
that's how I "solved" it ;))
msg1354 (view) Author: malte Date: 2011-05-19.01:06:31
Analysis of what's going on:

With cost_type = 1, the heuristic treats all operators as if they had unit cost.
In this case, this leads to extraordinarily high h^add values. (In case it's not
clear, our FF heuristic is FF/h^add.) h^add values quickly become high enough to
overflow a 32-bit signed int, causing negative values, which we don't handle

So the underlying problem is that we don't handle h^add value >= 2^31
gracefully, and that these can actually occur for fairly small problems (which
is not a surprise in theory, but not something I've seen actually happen before).

This does not happen when considering the original action costs (cost_type = 0),
since then all h^add values are of course also 0 (or infinite for unreachable

Not sure how to best resolve this. Patrik, any suggestions?
msg1353 (view) Author: patrik Date: 2011-05-18.09:12:52
On attached problem, running

downward-1 --heuristic 'h=ff(cost_type=0)' --search 'astar(h)' < log1-FDTrans.pre

produces a plan (with cost 0), but running

downward-1 --heuristic 'h=ff(cost_type=1)' --search 'astar(h)' < log1-FDTrans.pre

results in "Completely explored state space -- no solution!".

Tried it with some other search algorithms as well (lazy_greedy and eager_greedy).

This is with a freshly updated, unmodified copy from the repository.

The pre-file is produced by the FD translator + preprocessor.
Date User Action Args
2011-06-29 18:44:17maltesetstatus: chatting -> resolved
messages: + msg1395
2011-06-29 18:23:21maltesetmessages: + msg1392
2011-06-29 17:58:28maltesetmessages: + msg1391
2011-06-29 17:06:19rpgoldmansetnosy: + rpgoldman
2011-06-29 16:32:08maltesetfiles: + robert-tony.soln
2011-06-29 16:32:01maltesetfiles: + robert-tony-problem.pddl
title: h^add heuristic overflows on reasonably-sized instances -> h^add heuristic (and hence also h^FF) overflows on reasonably-sized instances
2011-06-29 16:31:32maltesetfiles: + robert-tony-domain.pddl
messages: + msg1390
title: FF heuristic with cost_type=1 not safe -> h^add heuristic overflows on reasonably-sized instances
2011-05-19 12:46:29maltesetassignedto: malte
messages: + msg1357
2011-05-19 09:01:44erezsetnosy: + erez
messages: + msg1356
2011-05-19 04:19:49patriksetmessages: + msg1355
2011-05-19 01:20:53moritzsetnosy: + moritz
2011-05-19 01:06:32maltesetstatus: unread -> chatting
messages: + msg1354
2011-05-18 09:12:53patrikcreate