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.

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.

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
happens.

Here's what it looks like: http://codereview.appspot.com/4627076

Will now extend it to the LAMA-FF synergy.

Robert Goldman and Tony Schneider report another instances of the same
phenomenon. Their problem files, along with a plan, is attached.

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 additive_heuristic.cc that use "+=".

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.

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 ;))

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
gracefully.

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
propositions).

Not sure how to best resolve this. Patrik, any suggestions?

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.