Learning while solving problems in best first search

We investigate the role of learning in search-based systems for solving optimization problems. Many AI problem solving systems solve problems repeatedly from the same domain. If the problems come from the same distribution in the learning phase and the problem solving phase, the problem solver can acquire information while solving problems, which can be used to solve subsequent problems faster. 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 offline 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 on-line learning scheme that uses an "anytime" algorithm to learn continuously while solving problems. The system starts with initial assumed distributions of h*set which are used to solve the initial problems. The results are used to update the distributions continuously and with time the distributions converge.