Hillclimbing in a hierarchy of abstraction spaces

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 implemented along with a program to synthesize the required abstraction hierarchies and evaluation functions. The synthesis program and the HHC algorithm have been tested in the domains of uniprocessor scheduling and two dimensional tile packing. Results show HHC to improve in two ways on ordinary hillclimbing without abstraction: HHC requires less computation time to complete a single climb. In addition, when the abstraction hierarchy is chosen with care HHC is more likely to find a solution on a single climb.Technical report LCSR-TR-19