A modular portfolio solver for planning

Abstract

Planning is an important research area of artificial intelligence. The goal of planning is to deliver a sequence of actions leading from an initial state to a goal state. The main goal of this master thesis is to implement a portfolio solver that delivers optimal solutions for planning problems as fast as possible. The portfolio solver is based on the fact, that algorithms outperform other algorithms for problem instances with specific characteristics. The implementation of a portfolio solver requires a solution for the sub-problem of extracting the right characteristics called features from planning problem instances and analysis of problem instances. Machine learning is used to find the correlations between characteristic features that describe problem instances and an optimal solver. The approach of introducing machine learning into planning is not entirely new, but it is not getting enough attention in the field of planning. Furthermore this thesis will cover analysis of the correlation of features that describe the planning problem instances and the most effective solver. The last aspect will be the creation of decision rules also called classification model. A good classification model can select with high probability an effective solver for any problem instance. At the end the implemented portfolio solver is empirically tested.