Learning inadmissible heuristics during search

Suboptimal search algorithms offer shorter solving times by sacrificing guaranteed solution optimality. While opti-mal search algorithms like A * and IDA * require admissible heuristics, suboptimal search algorithms need not constrain their guidance in this way. Previous work has explored us-ing off-line training to transform admissible heuristics into more effective inadmissible ones. In this paper we demon-strate that this transformation can be performed on-line, dur-ing search. In addition to not requiring training instances and extensive pre-computation, an on-line approach allows the learned heuristic to be tailored to a specific problem instance. We evaluate our techniques in four different benchmark do-mains using both greedy best-first search and bounded sub-optimal search. We find that heuristics learned on-line result in both faster search and better solutions while relying only on information readily available in any best-first search