Machine Discovery of Effective Admissible Heuristics

Abstract

Admissible heuristics are an important class of heuristics worth discovering: they guarantee shortest path solutions in search algorithms such as A • and they guarantee less expensively produced, but boundedly longer solutions in search algorithms such as dynamic weighting. Unfortunately, effective (accurate and cheap to compute) admissible heuristics can take years for people to discover. Several researchers have suggested that abstractions of a problem can be used to gene rate admissible heuristics. This paper describes and evaluates an implemented program (Absolver II) that uses a means-ends analysis search control strategy to discover abstracted problems that result in effective admissible heuristics. Absolver II discovered several well-known and novel admissible heuristics, including the first known effective one for Rubik's Cube , thus concretely demonstrating that effective admissible heuristics can be tractably discovered by a machine.