MACHINE DISCOVERY OF EFFECTIVE ADMISSIBLE HEURISTICS

Admissible heuristics am an important class of heuristics worth discov ering: they guarantee shortest path solutions in search algorithms suc h as A and they guarantee less expensively produced, but boundedly lo nger solutions in search algorithms such as dynamic weighting. Unfortu nately, effective (accurate and cheap to compute) admissible heuristic s can take years for people to discover. Several researchers have sugg ested that certain transformations of a problem can be used to generat e admissible heuristics. This article defines a more general class of transformations, called abstractions, that are guaranteed to generate only admissible heuristics. It also describes and evaluates an impleme nted program (Absolver II) that uses a means-ends analysis search cont rol strategy to discover abstracted problems that result in effective admissible heuristics. Absolver II discovered several well-known and a few novel admissible heuristics, including the first known effective one for Rubik's Cube, thus concretely demonstrating that effective adm issible heuristics can be tractably discovered by a machine.