Qualitative reasoning about fit (abstract only)

The main goal of this research is to discover the knowledge structures, control strategy, and problem-solving behavior required to determine how two objects best fit together. This sort of reasoning arises in many contexts and can involve any combination of objects, making it difficult to formalize. We therefore restrict the problem space to a particular class of objects. Each object is composed of a base, with features such as pegs, blocks, and holes of various shapes and sizes projecting inward and outward from its surfaces. A fit occurs when surfaces from any two objects can be brought close together by inserting the projections on either surface into the holes on the other. The degree of fit is determined by how tightly the projections fit into the holes and by how close the surfaces lie as a result.We recognize four stages in this reasoning process. The Grouping and Orientation stages select a particular juxtaposition between two objects that could lead to a fit. The Grouping stage identifies relevant features on an object's surface and forms a feature group. The Orientation stage selects two feature groups that appear to be compatible, based on the relative locations of features within them. If necessary, one object may be rotated to bring the feature group surfaces into opposition, or to line up the features.The Matching and Confirmation stages test the fit proposed by the two preceding stages. The Matching stage examines the surfaces region by region, matching features that are roughly complementary in shape and in corresponding positions. Only regions with features are considered. The Confirmation stage examines each feature pair in detail, analyzing the size, shape, and orientation of each member to determine how well they fit. If all the feature pairs are confirmed, the fit itself is confirmed.This decomposition into stages reduces the search space of potential fits. The Grouping stage narrows the focus from all features to the set of features relevant to a fit. The Orientation stage selects a single orientation. The Matching stage confines the search for mating features to localized regions on the object's surface. The Confirmation stage is thus able to examine features one pair at a time.Much of this reasoning is qualitative. Qualitative reasoning involves the analysis of how systems make the transition between discrete, qualitatively different states as their parameters reach certain critical values (Bobrow, 1985). Typically only ordinal relationships among values are considered. We treat knowledge about fit as a qualitative state. As new knowledge about fit is discovered, different and increasingly specific types of reasoning are applied. Eventually the knowledge of fit becomes sufficiently complete to indicate the specific measurements needed to test fit quantitatively.We have developed an implementation that currently covers the Matching and Confirmation stages. Input consists of a pair of objects that have already been Grouped and Oriented, as shown in the figure. In this example, the Matching procedures pair the features from corresponding corners since these features match in location and are of complementary shape. The Confirmation procedures examine each of these four pairs in turn. F1A is found to be smaller than F1B, and this is confirmed as a loose fit. In cross-section F2A fits into F2B, but since F2A is too long the fit is not confirmed. The radius of F3A exceeds that of F3B, and again fit is not confirmed. The radius and length of F4A are found to be smaller than those of F4B, resulting in a loose fit.We have identified several types of knowledge and control strategies that are important for reasoning about fit. We are currently working on representations for storing knowledge about the geometric and spatial relationships that accumulates as this reasoning proceeds. We are also interested in incorporating non-geometric properties, such as object functionality, into our model. Such extensions provide new avenues for reasoning about fit, and facilitate the exploration of such important areas as inferring function from structure (Stanfill, 1983) and the compilation of routine design knowledge (Brown, 1985).