Learning while solving problems in best first search

Abstract

We investigate the role of learning in search-based systems for solving optimization problems. We use a learning model, where the values of a set of features can be used to induce a clustering of the problem state space. The feasible set of h values corresponding to each cluster is called hset. If we relax the optimality guarantee, and tolerate a risk factor, the distribution of hset can be used to expedite search and produce results within a given risk of suboptimality. The off-line learning method consists of solving a batch of problems by using A to learn the distribution of the hset in the learning phase. This distribution can be used to solve the rest of the problems effectively. We show how the knowledge acquisition phase can be integrated with the problem solving phase. We present a continuous online learning scheme that uses an "anytime" algorithm to learn continuously while solving problems.