Highest Utility First Search Across Multiple Levels of
Stochastic Design
Full Paper (8 pages)
Publisher
Version,
Local Postscript (210KB),
Local PDF (177KB)
Louis Steinberg,
J. Storrs Hall, and
Brian D. Davison
Abstract
Many design problems are solved using multiple levels of abstraction,
where a design at one level has combinatorially many children at the
next level. A stochastic optimization methods, such as simulated
annealing, genetic algorithms and multi-start hill climbing, is often
used in such cases to generate the children of a design. This gives
rise to a search tree for the overall problem characterized by a large
branching factor, objects at different levels that are hard to
compare, and a child-generator that is too expensive to run more than
a few times at each level. We present the Highest Utility First
Search (HUFS) control algorithm for searching such trees. HUFS is
based on an estimate we derive for the expected utility of starting
the design process from any given design alternative, where utility
reflects both the intrinsic value of the final result and the cost in
computing resources it will take to get that result. We also present
an empirical study applying HUFS to the problem of VLSI module
placement, in which HUFS demonstrates significantly better performance
than the common "waterfall" control method.
Published in the
Proceedings of the
Fifteenth National Conference on Artificial Intelligence,
pp. 477-484,
July 26-30, 1998,
Madison, WI: AAAI Press.
A version of this paper was also presented at the
Symposium on Abstraction, Reformulation and Approximation (SARA-98),
May 9-12, Pacific Grove, CA.
Back
to Brian Davison's publications
Last modified: 31 January 2009
Brian D. Davison