Michael Barley, Natasha de Kriek, Santiago Franco, Angel Garcia-Olaya, Tim Hartill, Christopher Triggs, Henry Zwart, Vidal Alcázar, Patricia Riddle

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

Introduction

A problem with the current methodology for comparing search algorithms and a proposed solution. Addresses critical flaws in search algorithm comparison methodology. Incompletely described tie-break policies invalidate BiHS results. Proposes solutions for reproducible experiments and a new tool.

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.

Review

This paper addresses a crucial methodological issue within the experimental comparison of optimal bidirectional heuristic search (BiHS) algorithms. The authors highlight how the common practice of insufficiently describing tie-break policies in algorithm implementations can fundamentally undermine the validity and reproducibility of reported experimental results. They convincingly argue that such omissions can lead to widely varying performance assessments across different implementations and, consequently, misrepresent an algorithm's true efficacy. This problem is significant, as it erodes confidence in published benchmarks and makes it difficult for researchers to build upon prior work reliably, posing a substantial challenge to the integrity of the field. To tackle this critical issue, the paper proposes two distinct yet complementary solutions. Firstly, it advocates for a rigorous standard where authors provide a complete and explicit description of their algorithm's implementation, particularly detailing the exact tie-break policy used. Alternatively, for situations where a single specific implementation might not be representative, the paper suggests reporting results as a summary statistic that effectively captures the performance across all possible tie-break implementations. The abstract indicates the development of a dedicated software tool to facilitate this latter approach, demonstrating a practical commitment to solving the identified problem and offering a concrete mechanism for researchers to adopt these improved practices. The proposed methodology and solutions presented in this paper are highly valuable and timely. By systematically exposing the inherent flaws in current comparative practices, the authors provide a much-needed call for greater transparency and rigor in experimental design for search algorithms. The development of a software tool to generate representative summary statistics is a particularly strong point, offering a tangible resource to the community. This work has the potential to significantly enhance the reproducibility, fairness, and overall scientific quality of research in optimal bidirectional heuristic search, making it an important and impactful contribution to the field.

Full Text

Comments

You need to be logged in to post a comment.