Subset Selection of Search Heuristics
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.
@inproceedings{ijcai2013p101,
title = {Subset Selection of Search Heuristics},
author = {Rayner, D. Chris and Sturtevant, Nathan R. and Bowling, Michael H.},
booktitle = {Proceedings of the Twenty-Third International Joint Conference on
Artificial Intelligence, {IJCAI-13}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Francesca Rossi},
pages = {637--642},
year = {2013},
month = {8},
url = {https://ijcai.org/proceedings/2013/101},
}
TY - CPAPER TI - Subset Selection of Search Heuristics AU - Rayner, D. Chris AU - Sturtevant, Nathan R. AU - Bowling, Michael H. T2 - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2013 SP - 637 EP - 642 UR - https://ijcai.org/proceedings/2013/101 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
