DesignWIKI

Fil Salustri's Design Site

Site Tools


research:design_mereotopology

Design Mereotopology

Mereology is the logic of parts; topology is the logic of connectivity or, alternatively, wholes. Mereotopology involves the combination of these two kinds of logics to describe formally the kinds of physical and other structures that we use, build, design, and reason about. As a logical theory of structure, mereotopology offers certain distinct advantages over set theory and it is being investigated as an alternative to set theory for AIMD.

Overview

Basic Issues and Questions

The AI Perspective

AI-ers, like logicians, try to capture common sense about MT. But unlike logicians, AI-ers seem to take one of two perspectives both of which are different from the logicians' approach.

Perspective 1: Per e.g. [Sow92] and [Gru92], there is only one, transitive part-of primitive predicate, and that various predicates can be used to resolve any problems, such as the transivity problem, that may arise.

  • It follows from this perspective that the most rational world view consists of a hierarchy of only two levels: an object, and all its atomic parts.
  • This “realist” perspective is based on the notion that all distinctions between kinds of parthood are purely cognitive and thus not actual, and should not be part of the formalization.
  • This approach is elegant in the general case, but rather clumsy when used to explain the intricate parthood relations that can occur in product modeling research.

Perspective 2: Per e.g. [BGM96b] and [#4], distinctions are made between kinds of parthood are fundamental aspects of knowledge representation. After all, knowledge is something that is only cognitive anyways; knowledge of something should include the cognitive structures employed in reasoning.

  • This approach is more suitable for use in product modeling research, but still suffers from the problem of addressing a common-sense universe. It is also incomplete because there is no way to know that the set of parthood relations are necessarily all-inclusive.

The Linguistics Perspective

Mereology also plays a role in the study of language constructs. The problem here is that the goal is to categorize the constructs without necessarily considering their semantic implications.

That is, linguists are not necessarily concerned with the implications of the meanings they attribute to parthood relations in the larger sense.

For example, in a classic work of mereology that takes a linguistic perspective, Winston et al. [WCH87] suggest that statements like “The bicycle is partly steel.” can be taken to mean that “Steel is part of the bicycle,” but not “The bicycle has steel parts.” The former interpretation is a legitimate linguistic one, the latter is a legitimate engineering one.

Because of the mismatch between possible semantic (mis)interpretations, the linguistic perspective of mereology is of limited use in engineering.

From MNE92

See [MNE92].

They suggest (at least) four basic relations: functional component, member of set, subset, and piece.

Note the “at least”; their argument is inductive, so we never know if we have a full enumeration. This can severely limit reasoning because the resulting formalism is necessarily incomplete.

From GP95

See [GP95].

Some basic questions in mereology:

  • What kind of entities can be segmented into parts?
  • What kind of part-whole relations can be distinguished?
  • In what kinds of entities does the partition result?
  • How are the different relations processed?

Mereology has been considered a fundamental ontological relation since the time of the ancient Greeks. It is therefore surprising that there has been so little work in the area.

Part-whole relations are treated in philosophy, logic, cognitive science, mathematics, visual perception research, linguistics, and AI and knowledge representation. All these areas impact design to one degree or another. One would therefore expect the results of this research to impact our understanding of design in some fashion.

A partonomy is similar to a taxonomy, and consists of a tree of only three levels: the whole, its parts, and parts of its parts.

This is quite close to the three level division in AIM-D of assemblies, parts, and features.

There is concensus that mereology is strongly related to functionality.

The “transitivity problem” is also acknowledged in different research communities.

This suggests, as I have written elsewhere, that a connection between [Function modelling] and mereology is fundamental to an integrated understanding of knowledge in design.

An ontology that includes part-whole relations takes the form of a graph in that there are multiple overlapping part-whole relations that can be simultaneously occurring.

There's a very good example on page 869 of the reference about damage to an automobile. This argument is consistent with my idea that multiple part-of relations are possible, but distinguishable by context. This is also reinforced by the authors' discussion about modules and conceptual sub-systems to treat mereology (page 871).

From AFG96

See [AFG96].

This paper describes why part-whole relations are important in conceptual modelling and KBS development, and discusses several currently open issues.

“…part-whole relations should not be modelled by ordinary attributes in an Object-Oriented formalism like a Description Logic.”

A brief but good history of attempts to formalize part-whole relations is given.

If a part-whole relation is well-founded, there are no infinite chains in it; it must be finite, antisymmetric, irreflexive and transitive. It is argued from this, however, that a well-founded transitive relation leads to an undecidable logic, which in means that a primitive direct part relation cannot satisfy the property of immediate inferiority.

I'm not sure I agree with this. The argument given runs like this: (a) to discard non-intended models (like, apparently, a < b, a < c, b < c), an axiom is inserted; (b) the resulting logic is undecidable; © therefore, it isn't possible for the primitive part relation to satisfy the immediate inferior property of lattice theory. My problem is this: their unintended model is eliminated from set theory by the axiom of foundation, so does this mean that set theory is undecidable?

“…interactions between the various [part/whole] relations…” need to be addressed too.

However, as in other papers by the same authors, there's some trouble with regards to the generality of expressiveness, and some of the ontological commitments implied by their work. For example, “…we do not see the usefulness of having the direct part-whole relation in an ontology of the physical world.” Inclusion of a direct part-whole relation in a model of the real world seems very natural from the perspective of engineering design. But design is a subset of the perspective of common sense and intuition as suggested by the authors.

I note that there is potential for set theory to be very useful here. For example, antisymmetry is available if one maps sets to entities, via the axiom of foundation. Since set theory is more foundational than description logics, one may consider the possibility of a cleaner, more robust theory being developed from set theoretic considerations than from description logics, especially in terms of developing a general formal theory (not necessarily an ontology) of real-world objects.

The authors do express the importance of being able to describe how the whole is related to the parts and how the parts are “glued together” to form the whole. This is essential in design. But the authors then talk about dependent (part depends on whole) versus exclusive (one whole at most containing a part) versus essential (the whole depends on the part) parts.

It is shown that though these notions above can be represented with qualified number restrictions on complex roles, there are a number of problems that prevent the approach from representing only and all intended models.

The authors spend some time talking about downward/upward distributivity, but do not see that the kinds of examples they suggest are only meaningful when the relation has certain restricted semantics. For example, “In general, it is also true that the location of a car is the same of its engine.” Not from a design perspective, it isn't, unless we assume a none-standard semantics (with respect to design) of “location”.

The example is really dealing with the notion of nested regions of space, not of the things that might be those regions. That is, it is reasonable to say that the region (say a 3d convex hull) of the engine is contained by the region of the car.

The general case of distributivity is more difficult to treat, if one cannot find real, meaningful (wrt design) examples, but it does need to be treated.

From AFG96b

See [AFG96b].

An excellent paper discussing the particular issues relating to capturing the semantics of the part-whole relation, with substantial critical examination of many current systems, discussion of minimal requirements for a proper representation of parts and wholes, and a comparative description of how knowledge representation, description logics, conceptual modelling, and object-oriented technologies can treat mereology.

MT compared to ST

Mereotopological theories offer distinct advantages over set theory for certain categories of applications. Mereotopology was devised in particular to deal with common sense representation and reasoning about space and spatial entities. This makes it very well suited to representing and reasoning about designed products.

Mereology is regarded by many as a theory of membership that is in competition with set theory. Perhaps the most fundamental philosophical difference between mereology and set theory is that sets contain only other sets, which contain other sets, and so on, whereas mereology allows an entity to have as parts all subparts, subsubparts, etc. Set theory places strict hierarchical limits on how entities can be arranged (via the Axiom of Foundation, for example), whereas mereology allows for a “flatter” arrangement of entities. It appears that the simplified formal aspects and logical robustness of mereology versus set theory arise from this distinction. This is perhaps best exemplified by considering the relation of mereological sums.

A mereological sum typically involves only a sum of all the atomic elements. This is interesting in design. While a car is assembled out of an engine and other subassemblies, those subassemblies essentially vanish in the completed car; they only exist conceptually. This fits well with the notion of mereological sums.

Proponents of mereology (e.g. [Smi96][CG94a]) usually argue for its superiority based the relative complexity of providing direct representations of parthood in set theoretic frameworks and the restricted universe to which such formalizations can be applied.

MT in Engineering

Virtually no research in mereology exists in the engineering literature.

Each field that does study mereology has its own perspective, none of which are well-matched to the requirements of engineering design. However, each perspective may contribute at least to a degree to an engineering-specific mereological framework.

Pertinence to design

The following argument justifies an interest in mereology for engineering.

  • We cannot directly be aware of reality.
  • We are aware only of our models of reality, which are based on our (direct and indirect) perceptions of reality.
  • Therefore, all knowledge is knowledge about models, not about reality.
  • A model that is assumed to be true constitutes an axiom (system)in a cognitive structure (in humans) or knowledge-based (in computers).
  • Parthood relations constitute an important and complex component of an engineer's cognitive structures.
  • Therefore, understanding mereology's role will
    • increase our understanding of
      • design in general
      • of the cognitive structures of engineers
    • facilitate engineering education by structuring knowledge about designing in forms that are “natural” to the cognitive abilities of engineers and engineering students
    • aid in the development of more effective and efficient knowledge-based systems.

Many products are treated as composites during their design, manufacturing, operation, and disposal. The nature of the compositional relations, however, can vary widely. These relations, that describe how, when, and why one item is a part, constituent, or component of another, are all mereological relations. Some of the kinds of mereological relations that are pertinent in engineering include:

  • part-assembly relations, such as piston-motor, wheel-car, window-house, resistor-circuit, etc.
  • feature-part relations such as thread-bolt, flange-beam, hole-plate, etc.
  • function-subfunction relations create a hierarchy indicating which functions (move, energize, burn, lift, etc.) are needed to provide some higher level function (e.g. power).
  • component-system relations such as robot-cell, room-house, etc.
  • piece-whole relations such as that between a piece of steel rod and the stock length of rod from which the piece was cut.

Each of these relations have individual important characteristics that are relevant to various engineering tasks. Understanding the relations allows engineers to reason about the artifacts described with them. Not being able to reason about the relationships that hold between various parts and the wholes that contain them can be detrimental to effective and efficient product models and design processes.

However, no formal theory of these relations has yet been demonstrated to represent artifact information adequately in engineering environments to support formalized reasoning.

Possible application domains

There are various engineering domains in which mereological systems can find application.

Design Validation: By providing the means to reason about parts and wholes of products, an alternative means exists to validate (note: not necessarily verify) those models.

Design Automation: One can envision configuration design proceeding in a semi-automated manner if a KBS can reason about the parts from a catalog in a way that allows the system to relate them to the whole (the product being designed).

Assembly Planning: A system that “understands” the relationships between parts and assemblies can aid in planning and validating assembly operations.

Inventory Control, MRP, and SCM: The relationships between wholes and parts can be used to automatically generate plans for materials procurement, supply chain management and inventory control based on estimated product (rather than part) quantities.

Function Modelling, Analysis, and Reasoning: It seems that mereological relations are intimately tied to function modelling, at least at the conceptual level. As such, having mereological information available should facilitate advanced function modelling, analysis, and reasoning capabilities.

Systems Engineering: A system component is connected to other components via interfaces, and form a topological structure. A full system is defined by all the state variables of all the subsystems (i.e. the mereological sum of system components down to the 'atomic' level of state variables). Granularity, (i.e. different kinds of region predicates) allow subsystems to be made opaque (turned into topological points). Connection is defined with respect to the interface variables (inputs and outputs) between systems.

Workflow: In graphical representations of workflow such as Gantt charts, the representation space has two dimensions: task identity and time. These can be used to define mereotopological regions. Note the importance of overlap and reasoning about overlap, with respect to concurrency of tasks. Obviously, there is potential for MT to contribute to methods for scheduling work.

  • Additionally, what other dimensions could be used to augment the space? A third axis for resouces (manpower, etc.) could be very useful.

From general MT to a design MT

Based on my reading of the literature, it appears that most MT work, like most work on qualitative spatial reasoning, is based on a common sense understanding of the universe.

In logic, the concern is to build incrementally richer logical systems for symbolic manipulation, independent of the applicability of those systems to the “real” world. For example, various theories of Clarke [Cla81][Cla85] are developed having notions of regions but not of boundaries. From an engineering perspective, how can one reason about regions without knowing their boundaries? For the purposes of representing engineering knowledge and explaining design using mereology, the philosophical/logical perspective is too restricted.

However, engineers do not use common sense. They use “engineering sense” (see product centred modelling, which sits between the very strict sense of physical scientists and the relatively lax sense of the “common folk”. This is a serious problem, because MT theories are based on capturing intended models that engineers would never intend.

So we need to establish the characteristics of an MT theory for design - we need to flesh out the aspects of engineering sense that apply to MT. Design Mereotopology (DMT) is my MT theory for product modelling.

Some characteristics of mereotopological models of products include:

  • The domain includes all product models. There are two kinds. A concrete product model is the kind needed by manufacturers to fabricate a product; it includes shape, size, dimension, material specifications, tolerances, assembly and manufacturing information, etc. (Obviously, only the qualitative characteristics are of interest here). An abstract product model is any other model, including block diagrams, schematics, function diagrams, flowcharts, architecture specifications, etc.
  • Regions should be 'all of one piece' (i.e. self-connected)
  • Parthood should imply topological enclosure, but enclosure should not necessarily imply parthood.
    • For example, a passenger is enclosed by a car, but is not part of the car.
    • This raises the interesting possibility: is it just a matter of distinguishing exactly what we mean by parthood in a particular case beyond the MT aspects? From a variety of system-based perspectives, it is perfectly reasonable to consider the passenger to be a part of the car (e.g. ergonomics, instrumentation design, usability analysis, human-centred design, and a simple systems/functional description of the operation of the car). The difference is in the context in which the parthood relation exists.
  • The theory should be 1st order only.
  • The theory should support regions without commitment to their interpretation as conventional 3D spaces.
  • The theory should be extensional – i.e. two things are identical if they have the same parts connected in the same way.
    • Not sure about this one – also, what is strong extension?

Current State Summary of DMT

Assume:

  • $xPy$ means x is a part of y.
  • $xCy$ means x is connected to y.

D1: definition of proper part

  • $xPPy := xPy \wedge yPx$

D2: definition of overlap (sharing parts)

  • $xOy := \exists{z} (zPx \wedge zPy)$

D3: definition of mereological complement

  • $x = y\prime := \forall z (xOz \Leftrightarrow zPy)$

D4: definition of mereological binary sum

  • $x = y + z := \forall v (xOv \Leftrightarrow yOv \vee zOv)$

D5: definition of mereological sum of many entities satisying predicate p

  • $x = Sy[p(y)] := \forall z (xOz \Leftrightarrow \exists{y} (p(y) \wedge yOz))$
  • Predicate p does not contain quantifiers.

ATTENTION TODO Alot remains to be added here from the papers.

Open Issues and Action Items

  • Incorporate corrections from Ivo's emails.
  • How can we treat vagueness (of parthood, or connection, or boundaries) in the theory?
  • Can distinguishing /contexts/ help separate different mereologic relations?
  • Is there a place for fuzzy logic?
  • Once preliminary base theory is set up, take a close look at [Var96] and see what can be derived from it that would be useful here.
  • In [CV98], a 3-dimensional space of MT theories is constructed, with axes to indicate the kind of connection primitive, parthood primitive, and fusion principle used. Can we study this framework in closer detail to discover other relationships between families of theories?
  • In [CV98], page 151, a long list of many MT relations is given with definitions. Look through this list, see how many can be absorbed into our theory.
  • In [CV98], section 4 (page 152), some conclusions are drawn regarding the suitability of various families of theories. I'm not sure that all the discounted families are in fact unsuitable in design. It's all a matter of interpretation. Go through this section and the results therein, looking for consistency between the authors' conclusions and my ideas for design.
  • Is it necessary for my theory to assert that everything has an interior part? This would eliminate boundaries from the model's domain (though not necessarily from the topological space [CV98] [Esc94]).
    • Consider my C relation. Is it based on open regions, per [CV98] p154? If so, this should lead to the universe being disconnected in my theory. Is this good?
    • There are a number of issues arising from the discrete space MT in [Gal99]:
      • A good overview of topology is given and should be absorbed here
      • good set of constraints to limit the universe of my theory (p 4)
      • Galton's “unit cells” may be simulated with Eschenbach's “atoms;” if this is reasonable, I can simulate discreteness with a continuous framework - best of both worlds? Also I can use Galton's notion of “distance”
      • Galton's comments on self-connected universes are important too.
      • The use of conceptual neighborhood diagrams is, I think, very important and should be incorporated here.
  • In [CV97]:
    • Whitehead's Problem is discussed: ie. x & y are not connected unless the overlaying piece z is assumed to be (self-)connected. How do I take this into account in my theory?
    • Re holes and shadows and other oddities, the decision is whether these constitute actual parts of things (the cheese has holes, the wall has a shadow on it) or only properties of things (the cheese is holed, but there are no holes; the wall is dark, but there are no shadows). I think I prefer the property-based approach. How do I build this into the theory?

Notes & Ideas

Papers to read:

Foundational idea: boundaries, not parts, are primitive:

  • We see parts because we see the boundary between them. The brain processes colour, shape, motion separately. It makes sense that to distinguish two colours, or shapes, or motions, the brain is recognising where the properties change: a boundary. Can we build a MT taking a boundary as the primitive?

Granularity: Axiom 8 [Esc94] says that coarse regions are fine regions, but a fine region is not necessarily still a region at the coarse level. If it is not a region, then it's internal structure vanishes (information hiding).

Boundaries and Connection:

  • Boundaries are relationships
  • Relationships are connections (in some space)
  • Connections are topological
  • If X connects only to Y, then X is inside Y doubleright parthood.

Possible Research Areas:

  • Artefact Theory: Artefact theory is quite strong in Europe, and treats the artefacts that are producted by design processes. Conduct a survey of the state of the art in artefact theory, and consider how MT might contribute to it.
  • Search google for spatiotemporal logic and consider what was done.

See Also

References

Sow92. a J. Sowa. 1992. Discussions about KIF and related issues (Interlingua Mailing List, 20 July).
BGM96b. a S. Borgo, N. Guarino and C. Masolo. 1996. A Pointless Theory of Space Based On Strong Connection and Congruence. In Principles of Knowledge Representation and Reasoning - KR96/ (ed. L. C. Aiello and J. Doyle); Morgan Kaufmann, Boston. pages 220-229.
#4. a AFG96+
MNE92. a J. Markowitz, T. Nutter and M. Evans. 1992. Beyond IS-A and part-whole: more semantic network links. In Semantic Networks (ed. F. Lehmann); Pergamon Press. pages 377-390.
GP95. a P. Gerstl and S. Pribbenow. 1995. Midwinters, end games, and body parts: a classification of part-whole relations. Intl. J. Human-Computer Studies, 43:865-889.
AFG96. a A. Artale, E. Franconi and N. Guarino. 1996. Open Problems with Part-Whole Relations. In Proceedings of 1996 International Workshop on Description Logics, Boston, MA. pages 70-73.
AFG96b. a A. Artale, E. Franconi, N. Guarino and L. Pazzi. 1996. Part-Whole Relations in Object-Centered Systems: An Overview. Data and Knowledge Engineering, 20:347-383.
Smi96. a B. Smith. 1996. Mereotopology: A theory of parts and boundaries. Data and Knowledge Engineering, 20:287-303.
CG94a. a A. G. Cohn and N. M. Gotts. 1994. A Theory of Spatial Regions with Undetermined Boundaries. In Proc. w/s Topological Foundations of Cognitive Science/ (ed. C. Eschenbach and C. Habel and B. Smith)
Cla81. a B. L. Clarke. 1981. A calculus of individuals based on connection. Notre Dame J. of Formal Logic, 22:204-218.
Cla85. a B. L. Clarke. 1985. Individuals and points. Notre Dame J. of Formal Logic, 26:61-75.
CV98. a, b, c, d, e A.G. Cohn and A.C. Varzi. 1998. Connection relations in mereotopology. In Proc. ECAI-98/ (ed. H. Prade); John Wiley, Chichester. pages 150-154. (link)
Esc94. a, b C. Eschenbach. 1994. A mereotopological definition of Point. In Proc. w/s Topological Foundations of Cognitive Science/ (ed. C. Eschenbach and C. Habel and B. Smith), Buffalo, NY. pages 63-80.
Gal99. a P. Galle. 1999. Design as intentional action: a conceptual analysis. Design Studies, 20:57-81.
CV97. a R. Casati and A.C. Varzi. 1997. Spatial Entities. In Spatial and Temporal Reasoning/ (ed. O. Stock); Kluwer, Dordrecht. pages 73-96.
research/design_mereotopology.txt · Last modified: 2020.03.12 13:30 (external edit)