Searching stochastically generated multi-abstraction-level design spaces

We present a new algorithm called Highest Utility First Search (HUFS) for searching trees characterized by a large branching factor, the absence of a heuristic to compare nodes at different levels of the tree, and a child generator that is both expensive to run and stochastic in nature. Such trees arise naturally, for instance, in problems which involve candidate designs at several levels of abstraction and which use stochastic optimizers such as genetic algorithms or simulated annealing to generate a candidate at one level from a parent at the previous level. HUFS is applicable when there is a class of related problems, from which many specific problems will need to be solved. This paper explains the HUFS algorithm and presents experimental results comparing HUFS with alternative methods.