Learning from Multiple Heuristics

Abstract

Heuristic functions for single-agent search applications esti-mate the cost of the optimal solution. When multiple heuris-tics exist, taking their maximum is an effective way to com-bine them. A new technique is introduced for combining mul-tiple heuristic values. Inspired by the evaluation functions used in two-player games, the different heuristics in a single-agent application are treated as features of the problem do-main. An ANN is used to combine these features into a sin-gle heuristic value. This idea has been implemented for the sliding-tile puzzle and the 4-peg Towers of Hanoi, two clas-sic single-agent search domains. Experimental results show that this technique can lead to a large reduction in the search effort at a small cost in the quality of the solution obtained.