LEARNING WHILE SOLVING PROBLEMS IN BEST FIRST SEARCH

We investigate the role of learning in search-based systems for solvin g optimization problems. Many AI problem solving systems solve problem s 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 c an be used to solve subsequent problems faster. We use a learning mode l, where the values of a set of features can be used to induce a clust ering of the problem state space. The feasible set of h values corres ponding to each cluster is called hset. If we relax the optimality gu arantee, and tolerate a risk factor, the distribution of hset can be used to expedite search and produce results within a given risk of sub optimality. The offline learning method consists of solving a batch of problems by using A to learn the distribution of the h*set in the le arning phase. This distribution can be used to solve the-rest of the p roblems effectively. We show how the knowledge acquisition phase can b e integrated with the problem solving phase. We present a continuous o n-line learning scheme that uses an ''anytime'' algorithm to learn con tinuously while solving problems. The system starts with initial assum ed distributions of hset which are used to solve the initial problems . The results are used to update the distributions continuously and wi th time the distributions converge.