I think this is a good plan.

I'll downgrade this from "bug" to "wish" because the current behaviour is not
really wrong.

It's a bit difficult to act on this because there are two different aspects that
are not so easy to separate experimentally:

1) data structure efficiency
2) tie-breaking

Many of our uses of the queue are not sensitive to tie-breaking because we get
the same result no matter how we break ties. For example, this is the case for
things like h^max, h^add and the distance computations within abstraction
heuristics (merge-and-shrink, perhaps others?). However, FF is highly sensitive
to tie-breaking.

If we want to investigate this more deeply, I suggest that we first make the
type of queue a command-line configurable parameter in a few places, i.e.,
introduce a new parameter "priority_queue" or whatever that allows selecting
between different queue implementations and then do a larger experiment with
different places that use the queue.

Depending on the result, we can then decide if we want to keep this parameter or
remove it again, and whether we want to investigate alternative options for the
queue, such as ones that are similar to the ones we currently have but do
different tie-breaking. For example, for bucket-based queues, FIFO, LIFO and
uniform random should all be easy to implement.

Your thoughts?

I was wrong with my statement that the ordering of elements of a same key not
deterministic in HeapQueue.  HeapQueue is implemented as std::priority_queue,
which ordering depends on the implementation but should be deterministic.
https://stackoverflow.com/questions/7725139/priority-queue-iterator-and-ordering

What still holds is that AdaptiveQueue can change its internal state from
BucketQueue to HeapQueue, leading to different results depending on the queue
that is active. 

We discussed offline to use either BucketQueue or HeapQueue where AdaptiveQueue
leads to inconsistent results. Inconsistent results can occur when
AdaptiveQueue is used for greedy algorithms as it is the case in the
computation of the FF heuristic.

I evaluated the FF heuristic with each of the three different queues in a 32
bit and 64 bit version of Fast Downward.

AdaptiveQueue (base) vs. HeapQueue (heap)
http://ai.cs.unibas.ch/_tmp_files/heusner/issue760-compare-32-64-queues-issue760-base-issue760-heap-compare.html#summary

BucketQueue (bucket) vs. HeapQueue (heap)
http://ai.cs.unibas.ch/_tmp_files/heusner/issue760-compare-32-64-queues-issue760-bucket-issue760-heap-compare.html#summary

32 bit vs 64 bit
http://ai.cs.unibas.ch/_tmp_files/heusner/issue760-compare-32-64-queues-32-64-compare.html#summary

HeapQueue evaluates states slightly faster that BucketQueue. However, the
difference in coverage stems primarily from the different evaluation results,
which lead to different number of expansions.

Considerably less tasks fail due to memory out with HeapQueue than with
BucketQueue.  However, when comparing the 32 bit version to the 64 bit version
of Fast Downward, memory seems to become an issue for HeapQueue.

Based on the overall results I suggest to use HeapQueue instead of
AdaptiveQueue or BucketQueue for AdditiveHeuristic, because FFHeuristic is
derived from AdditiveHeuristic, and the relaxed exploration that uses
AdaptiveQueue is done within AdditiveHeuristic. 

Moreover, it might be worth to evaluate other heuristics that use
AdaptiveQueue. I expect similar results.

The AdaptiveQueue starts with a BucketQueue and changes to a HeapQueue after a
given condition is fulfilled.

While the BucketQueue does tie-breaking (among values that are assigned to the
same key) in a lifo manner, the tie-breaking of HeapQueue is undefined and
non-deterministic, resulting in a non-deterministic behavior of AdaptiveQueue.

AdaptiveQueue is used for the computation of FF heuristic, which I expected to
assign deterministic values to states.

Is AdaptiveQueue generally expected to be deterministic?

If yes, there could be two different solutions:
1. We could pass an comparison function for values to AbstractQueue (from which
AdaptiveQueue is derived).
2. We could assign a number to each key/value pair that is inserted to
HeapQueue. The number increases with each inserted key/value pair, which allows
to store values in a fifo manner (likewise to BucketQueue) within the HeapQueue.

Both solutions result in a disadvantage for either BucketQueue (additional time
for sorting a vector) or HeapQueue (additional memory for storing the insertion
number).

If no, then we should document the non-deterministic behavior of AdaptiveQueue
and affected classes.