Structure Exploitation
Many classes of problems of interest in AI, and of practical (e.g.,
commercial) interest, are technically ``NP-complete''. Practically,
this means that in order to solve these problems optimally one must
search a space of exponential size. One of the most important
techniques, arguably the only technique, that can be used to avoid
this exponential search is to make use of aspects of the structure of
the problem to either restrict the effective size of the search space,
or to generate near-optimal solutions with little or no search.
CIRL
CIRL members are interested in various ways of exploiting structure in
hard problems. There is work on finding and utilizing symmetries in general CSPs, and on
finding semantic clusterings in
hard problems (even in problems that appear to be completely random).
We are considering ways of using the
structure of the problem domain (e.g., the structure of the
organization facing the problem) to constrain the search for
solutions, and of exploiting clusters in solution space to produce
manageable, robust solutions.
Pointers
- Parent areas:
- Knowledge Representation
- Subareas:
- Symmetry
- Supermodels
- Model Clusters
Back to the CIRL Overview Page.