The 14. Annual Symposium on Combinatorial Search (SoCS 2021) is a leading conference on the field of heuristic and other forms of combinatorial search. This includes topics such as bioinformatics, operations research, constraint programming, AI planning, multi agent planning, and robotics.

The “Best SoCS21 Paper Award” was awarded to ZIB members Robert Clausecker and Florian Schintke for their paper “A Measure of Quality for IDA* Heuristics.”  In their work, the authors publish a performance analysis of the IDA* search algorithm, an adaption of iterative deepening search to heuristic search. As a novel result, this performance analysis provides a way to measure the impact of the heuristic function to search performance independent of any specific problem instance.

With this novel measure of heuristic quality, it is then possible to procedurally optimise the parameters of IDA* heuristics, tweaking them for ideal search performance.

The full paper can be found here (https://ojs.aaai.org/index.php/SOCS/article/view/18551).