Exploiting Portfolio Strategy to Explore the Interaction of Problems and Algorithms in AI Planning ∗

It is well known that a problem-specific approach can lead to an algorithm that does well on one problem but fails on other problems with a markedly different structure ((Wolpert & Macready 1997) consider the discrete case). Portfolios are a general way to overcome algorithm bias and maintain robustness across a range of problems. A portfolio controls the run time of a suite of algorithms with a strategy consisting of: selecting which algorithms to run; ranking the selected algorithms; and allocating computational time to them. An ideal strategy maximizes success and minimizes total computation. This means the strategy must be accurate and fast. Previous portfolios used a variety of strategies. One of the first formulations calculated the risk of selecting an algorithm (Huberman, Lukose, & Hogg 1997). Gomes and Selman (1997) explicitly computed the value of multiple restarts of the same algorithm. The Bus meta-planner (Howe et al. 1999) used a round robin allocation based on a tradeoff between a simple model of success and expected cost