Directing a Portfolio with Learning

Contents

Algorithm portfolios are one approach designed to harness algorithm bias to increase robustness across a range of problems. We conjecture that learning based on the previous performance of a suite of planning systems can direct a portfolio strategy at each of three stages: selecting which planners to run; ranking the order to run the selected planners; and allocating computational time to them. Our specific focus in this paper is to examine ways to inform portfolio strategy by exploiting learned performance models. We cull the planners to the non-dominated subset and rank them based on the models. Allocation is especially challenging for hard problems because the run-time distributions typically exhibit heavy-tails and high variance, both of which lower confidence for run-time prediction. We examine a round robin allocation strategy based on the run-time distributions of the planners. Our results show that the portfolio can solve more problems than any single planner and that it is faster than the average successful planner.