SIFT researchers win Best Student Paper Award at SoCS 2012

SIFT researchers Jordan Thayer and J. Benton won the Best Student Paper Award at the 2012 Symposium on Combinatorial Search for their paper titled "Better Parameter-free Anytime Search by Minimizing Time Between Solutions." This paper, written with Malte Helmert defines the "ideal" performance of anytime search algorithms and defines a new anytime search algorithm that conforms this. The abstract follows:


This paper presents a new anytime search algorithm, any- time explicit estimation search (AEES). AEES is an anytime search algorithm which attempts to minimize the time be- tween improvements to its incumbent solution by taking ad- vantage of the differences between solution cost and length. We provide an argument that minimizing the time between solutions is the right thing to do for an anytime search algo- rithm and show that when actions have differing costs, many state-of-the-art search algorithms, including the search strat- egy of LAMA11 and anytime nonparametric A*, do not min- imize the time between solutions. An empirical evaluation on seven domains shows that AEES often has both the short- est time between incumbent solutions and the best solution in hand for a wide variety of cutoffs.