Code, benchmarks, and experiment data for the SoCS 2026 paper "Open List Implementations in A*"

This record contains all the code, scripts, data, and benchmarks used in the experimental evaluation of the paper "Open List Implementations in A*" presented at SoCS 2026.

christen-et-al-socs2026-code.tar.xz

This archive contains sub-archives for all the revisions of Fast Downward used in the experiments. They are built on top of the upstream commit with the hash 680573a5b from June 16, 2025. The different open list implementations are (nearly) each implemented in their own revision, so we map the names of the sub-archives to the configuration they implement:

• delayed-pair: delayed detection with (default) FIFO
• delayed-pair-lifo: delayed detection with enforced LIFO
• *-default: early detection with the {binary, fibonacci, pairing} heap and its respective default tie-breaking
• *-fifo: early detection with the {binary, fibonacci, pairing} heap and enforced FIFO tie-breaking
• *-lifo: early detection with the {binary, fibonacci, pairing} heap and enforced LIFO tie-breaking
• early-bucket-default: early detection with bucket queue and its default tie-breaking
• early-bucket-fifo: early detection with bucket queue and enforced FIFO tie-breaking
• early-bucket-lifo: early detection with bucket queue and enforced LIFO tie-breaking
• early-bucket-default-lifo: early detection with bucket queue and default tie-breaking with LIFO bias

christen-et-al-socs2026-data.tar.xz

This archive contains the run logs and properties extracted by Lab, separately for runs using the blind (zero) heuristic and runs using LM-cut. The *-eval sub-directories contain an HTML table summarizing the results and a properties file containing the underlying information in JSON format. The configuration names (i.e. the algorithm field in properties and the HTML table headers) correspond to the sub-directory names in christen-et-al-socs2026-code.tar.xz. The sub-directories without the *-eval suffix contain logs and properties of individual runs.

christen-et-al-socs2026-benchmarks.tar.xz

This archive contains the PDDL files used in the evaluation, originally from Downward Benchmarks.

christen-et-al-socs2026-scripts.tar.xz

This archive contains scripts used in the evaluation.

The lab sub-directory contains the main Lab scripts used to generate the data in christen-et-al-socs2026-data.tar.xz. The scripts that were run are 2026-05-30_consolidated-blind.py and 2026-05-30_consolidated-lmcut.py, the rest helper files. The file requirements.txt defines the Python module versions of dependencies necessary to run the Lab scripts.

The significance sub-directory contains the script used to calculate p-values. Its dependencies are again listed in requirementents.txt and does its calculations based on properties files, in particular the ones in the *-eval sub-directories of christen-et-al-socs2026-data.tar.xz.