---
title: "Subset Selection of Search Heuristics"
authors:
  - "D. Chris Rayner"
  - "Nathan R. Sturtevant"
  - "Michael H. Bowling"
doi: ""
url: "https://ijcai.org/proceedings/2013/101"
pdf: "https://ijcai.org/proceedings/2013/0101.pdf"
venue: "Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence"
year: 2013
pages: "637-642"
track: ""
keywords:
---

# Subset Selection of Search Heuristics

D. Chris Rayner, Nathan R. Sturtevant, Michael H. Bowling

*Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence*, pages 637-642.

## 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.