Subset Selection of Search Heuristics

Chris Rayner, Nathan Sturtevant, and Michael Bowling. Subset Selection of Search Heuristics. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI), pp. 637–643, 2013.

Download

[PDF] 

Abstract

Constructing a strong heuristic function is a central problem in heuristic search. A common approach is to combine a number of heuristics by maximizing over the values from each. If a limit is placed on this number, then a subset selection problem arises. We treat this as an optimization problem, and proceed by translating a natural loss function into a submodular and monotonic utility function under which greedy selection is guaranteed to be near-optimal. We then extend this approach with a sampling scheme that retains provable optimality. Our empirical results show large improvements over existing methods, and give new insight into building heuristics for directed domains.

BibTeX

@InProceedings(13ijcai-hsubset,
  Title = "Subset Selection of Search Heuristics",
  Author = "Chris Rayner and Nathan Sturtevant and Michael Bowling",
  Booktitle = "Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI)",
  Pages = "637--643",
  Year = "2013",
  AcceptRate = "28\%",
  AcceptNumbers = "413 of 1473"
)

Generated by bib2html.pl (written by Patrick Riley) on Fri Feb 13, 2015 15:54:26