The pancake puzzle is a standard benchmark domain used to test search algorithms, and the gap heuristic is the state-of-the-art heuristic function most often used in such tests. In this work, we analyze the accuracy of this heuristic and identify ways to enhance it. We begin by showing that in the worst-case, the amount that the gap heuristic underestimates the optimal cost of a pancake puzzle state can be linear in the number of pancakes in the stack. However, empirical analysis suggests that it is extremely rare that the gap heuristic underestimates the optimal cost by more than two. We then identify several simple methods that can be used to generate large sets of problems on which the gap heuristic underestimates the optimal cost by a larger amount than it typically does on random permutations. In doing so, we provide new pancake puzzle test sets that can be used to evaluate how search algorithms behave when the heuristic is inaccurate. We also formally characterize states according to the size of the heuristic plateaus around them. This characterization allows us to efficiently compute a two-step look ahead of the gap heuristic on any state, which we can use alongside a state's dual to further improve heuristic accuracy. These enhancements substantially improve the performance of an IDA*-based pancake problem solver on both the existing benchmarks and the new ones proposed in this paper.

In this paper we present a lossless technique to compress pattern databases (PDBs) in the Pancake Sorting problems. This compression technique together with the choice of zero-cost operators in the construction of additive PDBs reduces the memory requirement for PDBs in these problems to a great extent, thus making otherwise intractable problems able to be efficiently handled. Also, using this method, we can construct some problem-size independent PDBs. This precludes the necessity of constructing new PDBs for new problems with different numbers of pancakes. In addition to our compression technique, by maximizing over the heuristic value of additive PDBs and the modified version of the gap heuristic, we have obtained powerful heuristics for the burnt pancake problem.

The Pancake problem has become a classical combinatorial problem. Different attempts have been made to optimally solve it and/or to derive tighter bounds on the diameter of its state space for a different number of discs. Until very recently, the most successful technique for solving different instances optimally was based on Pattern Databases. Although different approaches have been tried, solutions with Pattern Databases on Pancakes with more than 19 discs have never been reported. In this work, a new technique is introduced which allows the definition of Additive Pattern Databases for solving Pancakes of an arbitrary length. As a result, this technique solves Pancake problems with twice as many discs as the largest ones solved nowadays with other techniques based on Pattern Databases saving up to two orders of magnitude of space.

We describe the gap heuristic for the pancake problem, which dramatically outperforms current abstraction-based heuristics for this problem. The gap heuristic belongs to a family of landmark heuristics that have recently been very successfully applied to planning problems.