Representing, matching, and generalising structural descriptions of complex physical objects.

by David Brian Andreae

A thesis submitted to the Victoria University of Wellington in fulfillment of the requirements for the degree of Doctor of Philosophy Victoria University of Wellington



This thesis addresses the problem of representing, matching, and generalising descriptions of complex structured physical objects, in the absence of functional and domain-specific knowledge. A system called GRAM is described, which includes a representation scheme, an instance-constructor, a matcher, and a generaliser. These components incorporate and extend ideas from a number of other structured-object learning systems, as well as introducing several new ideas. A central contribution of this thesis is to show that descriptions of complex physical objects can be matched and generalised effectively and efficiently by exploiting their structure. GRAM does this by a number of means, such as by representing objects at multiple levels of detail; using `neighbour relationships' to allow a more flexible traversal of object graphs during matching; explicitly distinguishing between substructure and context to allow partial matching and a simple form of disjunction; and using an explicit representation of groups to describe several similar objects as a single descriptive entity. A second contribution is to show that complex objects can be matched without having to enforce consistency between object correspondences. This is possible partly because of the richness of physical objects, and partly because GRAM represents concepts as simple entities defined by relationships with other concepts, rather than as a complete set of subcomponents defined locally within the concept description itself. This scheme leads to greater simplicity, efficiency, and robustness.