AAAI

Association for the Advancement of Artificial Intelligence

Home > Proceedings / Proceedings of the International Conference on Automated Planning and Scheduling, 29 > Book One

Algorithm Selection in Optimization and Application to Angry Birds

Authors

Shahaf S. Shperberg,Solomon Eyal Shimony,Avinoam Yehezkel

Ben-Gurion University,Ben-Gurion University,Ben-Gurion University


Proceedings:

Book One

Volume

Issue:

Proceedings of the International Conference on Automated Planning and Scheduling, 29

Track:

Main Track

Downloads:

Download PDF

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 ShimonyAvinoam Yehezkel

DOI:

10.1609/icaps.v29i1.3508


ICAPS

Proceedings of the International Conference on Automated Planning and Scheduling, 29