Hillclimbing in a Hierarchy of Abstraction Spaces

ion Spaces Thomas Ellman Saibal Patra Department of Computer Science Hill Center for Mathematical Sciences Rutgers University New Brunswick, New Jersey 08903 (908) 932 - 4184 fellman,patrag@cs.rutgers.edu LCSR-TR-198 Abstract Hillclimbing search has been shown to be useful for solving constraint satisfaction problems that are too large to be attacked using backtracking search. Nevertheless, hillclimbing search can be computationally expensive when the length of each climb is long, or when many climbs are required due to the presence of local, but non-global optima. "Hierarchic Hillclimbing" (HHC) is an extension of ordinary "Flat Hillclimbing " that is designed to attack such difficulties. HHC carries out hillclimbing search in a hierarchy of abstraction spaces, starting with the most abstract and proceeding to the most concrete. HHC takes as input a description of the abstraction hierarchy, as well as an evaluation function for each abstraction level. The HHC algorithm has been im..