Knowledge Representation of Design in Many-Sorted Logic

ABSTRACT

The paper presents a formal tool of modelling of constructional design, where the cardinal issue is knowledge representation. It is shown that the structures of classical mathematical logic, such as t-type many-sorted models, can be applied almost directly to represent the world of a certain design­ ing task. Using the PROLOG programming system, the logical representation of the task yields, at the same time, its automated solution. The most impor­ tant moment of modelling a task of this kind is fixing the appropriate type of the structures. A PROLOG program for designing many-storied buildings is taken as an example.

I INTRODUCTION

The aim of this paper is to show a logic-based method for modelling certain tasks of constructional design ~hich helps to develop ready-to-run Computer Aided Design (CAD) systems. The main idea of this method is the applicatioh of t-type many-sorted mo­ dels of classical mathematical logic to represent designing problems. The final form of the logical representation is written in a very high level language ca lled PROLOG, which can be directly run on a computer.

The problem-solving method described below is the generalization of the experience gained by solv­ ing a few technical designing tasks in PROLOG (5, 6, 7 , 8]. We shall illustrate the application of this method on a concrete architectured CAD task, namely designing many-storied apartment houses.

II MANY-SORTED MODELS

A language L of the classical mathematical lo­ gic is a triple

where Ft is the syntax (set of well-formed formulas)

The models are relational structures of a fix­ ed type. Th~ type t is a pair of functions,

tR and tF define the arity of the relation and func­ tion symbols, respectively. See [1] .

Zsuzsanna MArkusz

Computer and Automation Institute Hungarian Academy of Sciences

The many-sorted models are modification of these t-type models. The fundamental difference between many-sorted models and t-type models is that the universe of the many-sorted models is not homogeneous but consists of disjunct sets of differ­ ent sorts. Thus, when defining the types of functions and relations, we have to give not only the number of the arguments but the sort of every argument as well.

Let s = ~ Ji. . : i <w} be the set of sorts of the 1 elements of the universe.

Then the universe of the many-sorted model

The type (sigPature) of the many-sorted model ~ (see in [3))

iii) to every n-ary relation symbol rn' n<UJ

a pair, (rn, (.J.. 1 , ... , ..(n>> is assigned,

where rn is the relation symbol

(.( 1 , ... , ..( ) is the sequence of the sorts of

n the arguments of the r e lation.

Thus the t-type of a many-sorted model is a triple

The syntax of many-sorted languages is basical­ ly the same as that of the classical ones , with the following exception: The signature determines the sort of terms occuring as arguments of the relation or function symbols.

is

III MODELLING ~ CONSTRUCTIONAL DESIGNING ~

Let us consider a technical designing task whose aim is to crea~e a complex construction using basic units, according to a given set of rules: e.g. to compose many-storied houses of apartments or ma­ chines of spare parts. The basic units are repre­ sented by constants, while the partial constructions and the final construction by compound expressions. Thus we can regulate the hierarchy that will consti­ tute the final construction by defining the type­ function tF of the t-type model.

We can attach conditions to every step of mak­ ing the construction, i.e. the compound expression representing it. The co ection between the parts of the construction is represented by relations. If in every stage of the designing process all require­ ments of the construction are given by the corre­ sponding relations, then, in fact, the necessary "knowledge" is given, i.e. "the world of the design" is defined. The choice of these relations is but the definition of the type function tR. As a result,

we can declare that the most important moment of modelling a constructional designing task by classi­ cal many-sorted t-type structures is fixing the appropriate type t = (s, tR, t~.

Let us go back to describing the world of the designing task. We aim not only at the representa­ tion of all requirements of the technical construc­ tion by mathematical relations, but also to create the given product with a computer system. To achieve this, we need to express the requirements in a spe­ cif ic form which can be used by an automatic mecha­ nism. Since this specific form is nothing else than formulas of logic, the mechanism mentioned should be a certain kind of calculus. PROLOG is a computer system based on first-order logic where the running of a program is controlled by a complete calculus present in the interpreter.

A PROLOG interpreter accepts Horn-clauses, i.e. implications whose conditions are connected by the logical connective "and", and have only one conclusion. tn this paper we do not wish to give a de ­ tailed description of PROLOG. See (10, 11].

Note that PROLOG is based on a one-sorted language. However, it does not make any difference, because the pattern matching mechanism built in the deduction system of PROLOG automatically fulfils the requirements that only the terms of the corre­ sponding sorts should be substituted for each other.

IV APPLICATION OF MANY-SORTED LOGIC

IN MODELLING OF THE DESIGN OF

MANY-STORIED HOUSES

IV.!. The task

The task is to work out a model of the design­ ing process of many-storied apartment houses in PROLOG which will result in a ready-to-run CAD system. Our purpose is to design one or more houses, so the different customer can choose from different ground-plans, and at the same time these buildings will meet certain technical and functional require­ ments.

One program will provide a set of different ground-plans for every customer who can set a prior­ ity order excluding the less good ones. Another program will design the whole building, placing the apartments beside and above one another. We can get several variants of buildings by changing the input data of the building given by the architect and/or by reordering or extending the computerized repre­ sentation of the apartment variants stored in a disc file. The detailed description of the program system can be found in [6].

The programs are run on an IBM 3031 computer of the Hungarian Academy of Sciences; the PROLOG sys­ tem was installed by Peter Koves. The results of our PROLOG program was gra?hically represented on a GDBO graphic display [4) by Laszlo Andor and on a CALCOMP plotter by Judit Takacs.

A three-storied apartment house designed by the program is shown in Figs. 2 and 3.

In order to be able to present the logical mo­ delling of the task, we have to get acquainted with the architectural conception determining our model.

The basic elements of an apartment are the cells with different sizes and functions. According to their size the cells can be classified into two groups: narrow and wide cells. The middle of the apartment is constructed by joining three wide cells, whereas the perimeter is made up by 2-4 narrow cells. An apartment consists of the middle and the outside parts together (Fig. 1).

A narrow or a wide cell is defined by its func­ tion and its variation number. The function of a cell can be the following: living room, bedroom, kitchen, dining-room, entrance, water-block (bath­ room + toilet). The variation numbers of the nar­ row and wide cells define the number and locations of the doors in the cells.

The basic units of a building are the apart­ ments. TWo apartments and a staircase make one sec­ tion.The horizontal linking of one or two sections make one level. The vertical linking of 2-4 leve l s makes one unit. Any number of units linked horizon­ tally make up one building.

IV.2. The logical representation of the task We shall illustrate the functions which con­ struc t the whole building from apartments (Fig.S.).

(f 6 ,(a,a;s))

Two apartments and one staircase together make up one section.

(f 7 ,(s,s;l>>

The horizontal linking of two sections makes up one level.

(f 8 ,(l,u;u))

The vertical linking of a level and a unit makes up a new unit.

(f 9 ,{u,b;b»

By linking a unit and a building, we can get a new building. To construct a one-unit building, we use the "empty building". (Fig. 6.)

IV.4. Relations

As an example, we examine the relations bet­ ween the apartments which determine the condi­ tions of constructing the buildings in a proper way.

The respective part of the type-function tR is the set of pairs:

The se relations not only define connections, but as parts of the PROLOG program they are procedures with contro lling o r construction function. Let us examine them one after another.

Valid if apartment K 12 is the mirror image of apart­ ment X with respect to the y-axis.

Valid if the s taircase can be adjusted between two apartmen t s next to each othe~QK 11 , K 1 ~ 1 so that the entrances will open from the staircase.

Va lid if the geometrical structure of the right segments of the first apartment (K 12 l and that of the l eft segments of the second apartment (K 13 ) are capable t o join each other.

Valid if the left (right) segments of apartment(K 1 ~ (K 14 l on the first level, i.e. on the left (right) side of the unit, correspond to the left (right) type o f the unit.

Valid if the water-block, the entrances and the segment of the staircase of the upper apartment (K 21 l and that of the apartment below it (K 21 l

are on top o f one another.

Valid if there are lower segments under each seg­ ment of the upper apartment (K 21 l.

Valid if the l eft (right) segments of the apart­ ment correspond to the type of the left (right) side o f the unit, and the geometry of the upper and lower apartments match.

Having defined the type of the language, the axioms written in that language constitute the specification of the designing problem. These axioms define t he above functions and relations, and so they determine the class o f possible models. To obtain a PROLOG program from these axioms, it may be necessary to introduce new functions and rela­ tion symbols . Let us use the symbols t~ and t~ for

these "auxiliary" functions and relations. Thus the definition o f the type

wil l be compl e t ed after finishing the specification.

Figure 7. Illustration of the VERTICAL relation of two apartments

+VERTICAL(*Ml;*Fl,*M2;*F2)

• -CENTRETYPE(*Ml,*M2,*X)
• -WATERBLOCK(*X,*Fl,*F2)
• -ENTERING(*Fl,*F2)
• -VERSTAIR(*Fl,*F2).

+CENTRETYPE(*Ql.*N.*Ll, *Q2.*N.*L2,*N).

+WATERBLOCK(46!*V, *Fl,*F2)

-KITCHEN(*Fl,*F2).

+WATERBLOCK(42!*V, *Fl,*F2)

-KITCHEN(* Fl, *F2)

-BATH(*Fl,*F2) .

+KITCHEN(*Fl,*F2)

-THESAME(*Fl,*F2, 45, 25).

+BATH(*Fl,*F2)

-THESAME(*Fl,*F2, 63, 63).

+ENTERING(*Fl,*F2)

-EXISTENTER(*Fl) - EXISTENTER(*F2)

-THESAME(*Fl,*F2, 43, 45).

+ENTERING(*Fl,*F2)

-EXISTENTER (*Fl)

-NOT(EXISTENTER(*F2)).

+ENTERING(*Fl,*F2)

-NOT(EXISTENTER(*Fl)).

+EXISTENTER(*F)

• -MEMBER(*F,*COD!*V)
• -ENTRANCE(*COD!*V).

+VERSTAIR(*Fl,*F2)

-EXISTSTAIR(*Fl) - EXISTSTAIR(*F2)

• -UNDER(*Fl,*F2 , L!L).

+VERSTAIR(*Fl;*F2)

• EXISTSTAIR ( *Fl)
• -NOT(EXISTSTAIR(*F2)).

+VERSTAIR(*Fl,*F2)

-NOT(EXISTSTAIR(*Fl)).

• +EXISTSTAIR (*F1) -MEMBER(*F1,*COD!*V) -CONSTANT(*COD)
• -EQUAL(*COD!*V, L!L).

The relation VERTICAL is needed in the selec­ tion of every apar~ent above the ground floor. It has two arguments,

1. the lower apartment (*M1;*F1) and
2. the upper apartment (*M2;*F2),

and it is true if the following four conditions are fulfilled:

It checks whether the middle wide cells of the two apartments are the same; if they are, it gives

• -CENTRETYPE(*Ml,*M2,*X) their value to the variable *X.

-WATERBLOCK(*X,*Fl,*F2)

The variant *X already contains the value (with or without bathroom) of the middle cell. Depending on this value, the relation checks whether the kitch­ ens or the kitchens plus bathrooms are on top of one another in the two apartments.

-ENTERING(*F1,*F2)

If there is an entrance in each apartment, it checks whether they are on top of one another. (The hall of the middle cell can also be the entrance, in this case there is no entrance in the narrow segments.)

-VERSTAIR{*F1,*F2)

If a staircase belongs to each apartment, it checks whether they are on top of one another.

Note that the definition of the auxiliary rela­ tions THESAME, MEMBER, ENTRANCE, UNDER is withheld here but they are of course defined in the ready­ to-run program.

VI CONCLUSION

A new technique for the solution of CAD prob­ lems is presented and illustrated on an architec­ tural example. The designing knowledge is represen­ ted in the form of axioms described in the lan­ guage of mathematical logic. The calculi of logic which manipulate these axioms can be used to mo­ del designing processes.

In this paper we wish to point out that the decisive step in the above method is the selec­ tion of the adequate type of language. If Horn­ formulas are used, then the description of the technical problem can be considered as a program written in PROLOG.

VII ACKNOWLEDGEMENT

I would like to express my appreciation to Mr. Miklos szots for the helpful and inspiring discussions we had about this subject.