A Problem with the Current Methodology for Comparing Search Algorithms and a Proposed Solution

Abstract

This paper explores how incompletely described tie-break policies can invalidate the experimental results reported in papers on optimal bidirectional heuristic search (BiHS). Experiments usually use a single implementation of an algorithm with its specific tie-break policy. When the tie-breaks are insufficiently described, we show that the results can be irreproducible, vary dramatically under different implementations, and lead to misleading assessments of an algorithm’s performance. To ensure reproducible and representative results, papers should either provide a description of the algorithm’s implementation, i.e., the complete tie-break policy, or alternatively, give results as a summary statistic representative of all possible tie-break implementations. We developed a software tool for this purpose.