Model Clusters

Solutions to realistic problems tend to cluster. For example, having decided to solve the problem of what to do about dinner by eating out, the choice of restaurant, time, and what to eat are all relatively unconstrained. Moreover, these choices don't change the basic solution -- eating out.

Surprisingly, even problems constructed specifically to be random (and hence, intuitively, not to have grouped solutions) exhibit a large degree of clustering among their solutions. These clusters can be exponentially large, and the clustering can be exploited in a number of ways.

CIRL

When an automated agent solves a problem of some kind, it must provide solutions that are robust, that are qualitatively different from one another, and that have well understood limiting factors. We are addressing all these goals by exploring the ramifications of the fact that solutions cluster.

The key insight needed to address these issues is the recognition that all of these concepts can be described in terms of the distribution of problem solutions in the overall search space. Solutions tend to cluster; the larger the cluster in which any particular solution appears, the more robust the solution is likely to be. Solutions appearing in different clusters are qualitatively different; limiting factors correspond to situational changes that move one outside of a solution cluster entirely.

Important problems include finding mechanisms for identifying solution clusters, for recognizing when a search is in a failed cluster (a cluster of non-solutions) and moving outside the cluster, and for moving within a cluster to a more desirable (e.g., more robust or more optimal) representative.

Pointers

Clustering at the Phase Transition
Demonstrates the existence of solution clustering in computationally hard random problems, as well as the existence of clusters of failed solutions. Written by Andrew Parkes. In Proc. AAAI in 1997. Compressed postscript document.

Parent areas:
Structure

Subareas:
Robust Solutions

Back to the CIRL Overview Page.