Colin P. Williams and Tad Hogg
Dynamics of Computation Group
Xerox Palo Alto Research Center
Palo Alto, CA 94304
hogg@parc.xerox.com
@ARTICLE {,
AUTHOR = "Colin P. Williams and Tad Hogg",
TITLE = "Exploiting the Deep Structure of Constraint Problems",
JOURNAL = "Artificial Intelligence",
VOLUME = "70",
PAGES = "73-117",
YEAR = "1994"}
We introduce a technique for analyzing the behavior of sophisticated
A.I. search programs working on realistic, large-scale problems. This
approach allows us to predict where, in a space of problem instances,
the hardest problems are to be found and where the fluctuations in
difficulty are greatest. Our key insight is to shift emphasis from
modelling sophisticated algorithms directly to modelling a search space
that captures their principal effects. We compare our model's
predictions with actual data on real problems obtained independently and
show that the agreement is quite good. By systematically relaxing our
underlying modelling assumptions we identify their relative contribution
to the remaining error and then remedy it. We also discuss further
applications of our model and suggest how this type of analysis can be
generalized to other kinds of A.I. problems.
postcript (1.3M, 51 pages, available on-line only within Xerox)