Learning while solving problems in best first search

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 h*set. If we relax the optimality guarantee, and tolerate a risk factor, the distribution of h*set 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 h*set 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