Algorithm Selection in Optimization and Application to Angry Birds

Authors

  • Shahaf S. Shperberg Ben-Gurion University
  • Solomon Eyal Shimony Ben-Gurion University
  • Avinoam Yehezkel Ben-Gurion University

DOI:

https://doi.org/10.1609/icaps.v29i1.3508

Abstract

Consider the MaxScore algorithm selection problem: given some optimization problem instances, a set of algorithms that solve them, and a time limit, what is the optimal policy for selecting (algorithm, instance) runs so as to maximize the sum of solution qualities for all problem instances?

We analyze the computational complexity of restrictions of MaxScore (NP-hard), and provide a dynamic programming approximation algorithm. This algorithm, as well as new greedy algorithms, are evaluated empirically on data from agent runs on Angry Birds problem instances. Results show a significant improvement over a hyper-agent greedy scheme from related work.

Solomon Eyal Shimony

Avinoam Yehezkel

ICAPS 2019 Proceedings Cover, Berkeley, California USA

Downloads

Published

2019-07-05

How to Cite

Shperberg, S. S., Eyal Shimony, S., & Yehezkel, A. (2019). Algorithm Selection in Optimization and Application to Angry Birds. Proceedings of the International Conference on Automated Planning and Scheduling, 29(1), 437-445. https://doi.org/10.1609/icaps.v29i1.3508

Issue

Vol. 29 (2019): Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling

Section

Main Track