Searching Stochastically-Generated Multi-Abstraction-Level Design Spaces

Search Techniques for Problem Solving Under Uncertainty and Incomplete Information

Volume

Search Techniques for Problem Solving Under Uncertainty and Incomplete Information

Contents

We present a new algorithm called Highest Utility First Search (HUFS) for searching trees characterized by 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 such as microprocessor design 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. This report explains the HUFS algorithm and presents experimental results demonstrating the advantages of HUFS over alternative methods.