Concepts for knowledge-based system design environments

Proceedings of the 1985 Winter Simulation D. Can&, C. Elais, S. Solomon (eds.)

Conference

CONCEPTS

Dept.

of

FOR KNOWLEDGE-BASED

SYSTEM

Jerzy W. Rozenblit Computer Science and Engineering Oakland University Rochester, Hichigan 48063

Dept.

sets up a conceptua I The paper framework for constructing knowledge-based, computer-aided environments for system design. The framework is based on the formal structures underlying the expert system design methodology being developed by Zeigler [18], name 1 y that of the system entity and structure frame. experimental The system entity formalism is to the emp I oyed structure family of design configurations. The rules for design model synthesis are generated by pruning the design entity structure with respect to generic experimental frames [I33 that represent the design objectives. This leads to a methodology for design of system design envirohments which recognizes three primary relationships of the domain that application must be modelled: the decomposition the system being hierarchy (of des i gned) , the taxonomi c structure (determining the design alternatives), and the coup l i ng constraints (restricting the combinations in which components can be synthesized into the target system).

SYSTEM ---

DESIGN

AND IIODELLING

ENTERPRISE

d.)

1 SYNERGIES

c.)

Bernard Electrical University Tucson,

P. and

Zeigler Computer Engineering of Arizona Arizona 85721

offered by the representation schemes The and multifacetted methodology are well structured have formalized operations that can exploit such structures. This significantly reduces the effort expert environments for a given of designing problem domain.

The generic experimental frame is a structure that represents a set of design objectives in the form of standard variable types. Such standard variable types performance, express measures of input/output utilization of resources, reliability assessments etc. In outline, the following these two structures play role in our design framework:

Our primary goal in this paper is to embed system design within the multifacetted modelling framework [1,8,16,171 and thus provide a systematic design methodology supper ted forma I adequate by structures. We shall argue that such an approach is amenable to computerization and direct application of expert systems and Al techniques. As i I lustrated in Figure 1, system design is into brought the multifacetted framework, with the design process being supported by the modelling and simulation techniques, in the following contexts:

b.)

of

mind, we shal I present i SSUeS in With the above constructing knowledge-based design concepts for objects in our environments. The two key forma I entity structure and the approach are the system structure aeneric experimental frame. The entity is based on a tree-like graph encompassing the system boundaries and decompositions that have been conceived in for the system. As we shall describe it in detail formal ism is a entity structure Section 3 the that facilitates knowledge representation scheme expressing the decomposition hierarchy, the taxonomy it represents, the coup1 i ng of the objects and the ways constraints on in which system components hierarchy identified the decompos i t i on can be in coupled together.

is a transformation The process of design of a designer’s expertise ideas and into a concrete implementation. This process is driven by the design requirements provided by the client and the available technology. The growing complexity of sys terns being designed has strongly influenced research efforts in constructing computerized support environments for assistance in the design process [4,5,11,12,15].

a.)

ENVIRONMENTS

measurements and methods including the trade-off of multi-level, multi-component, evaluation framework specified models, our hierarchically al lows the designer to describe the attributes of comparative This I eads designs in measures. eventually to the choice of the best design with performance measures under respect to consideration.

ABSTRACT

I.

DESIGN

,t the system entity organizing a family of system being designed. -5 the project frames.

objectives i nduce

structure possible

and requirements appropriate generic

Model 1 ing is a creative act of individuals using basic problem-solving techniques, building conceptual mode I s based on knowledge and perception of reality, requirements and objectives of the modelling project. Thus, considering models as design “blueprints” we establish a direct relationship with the modelling enterprise.

zr the design entity to the generic frames. design configurations objectives.

By providing mechanisms for model decomposition, hierarchical specification and aggregation of partial models. the multifacetted modelling fully responds to the needs of the design of large scale Systems.

* resulting models are experimental frames and the chosen on the basis of such

By providing

We shall approach in

a spectrum

of

performance

223

provide a the ensuing

of

means of of the

the design experimental

structure is pruned with respect This results in a family of that conform to the design

a* the pruned substructures generating rules for synthesis

evaluation

is a basic configurations

sewe of

as design

skeletons models.

for

evaluated in respective best design models are evaluations.

detailed sections.

exposition However,

of let

this us

+z - ii I -Jerzy W. Rozenblit

Entity Base -3

Design

tives

Construction

1

via

Simulation

A ‘detailed the facets of the design I ook into al I process verifies the tools to need for high-level support design activities at and the al 1 levels phases. The architectures for such have tools been 1 i terature presented studied are in the [3,6,7]. However, the proposed solutions lack an underlying theoretical framework that permits a uniform treatment of design at levels by different providing structure and behavior, and concepts 1 ike allows for individuality of detail at each level.

Evaluation System Design in the Multifacetted Modelling Framework

first briefly characterize design process as we this paper.

2.

each Ides i gn level we associate a set of horizontal activities requ i rements such as: specificatioh, system functional specifications, modal I i ng, evaluation and choice of design alternatives v i a simulation studies. The design the above sholjld proceed along both axes of characterization. The designer should be able to derive complete specifications at and design models at each he should be able to validate and verify level, the resulting system and alternatives with its the simulation hel p of analytical and/or tools. Transitions between the design levels must be possible and easy to perform.

Experimentation

Model

L

Fig.

wi 111

Exp . Frame Base

Str.

objet

anli IBernard P. Zeigler

CHARACTERIZATION _-_---

the perceive

major it in

OF THE DESIGN

steps of the context

the of

The above orthogonal characterization of the to has been successfully applied process hardware design support systems 112,153. While attempt to further refine not the definition nor describe all its phases in detail, design, shall show how the modelling techniques and its objects can support the expert design environments.

PROCESS

framework in OUT The term system design will denote simulation techniques to modelling and use of the is evaluate the proposed operation of the system that As opposed to system analysis where being designed. object or the model is derived from an existing real in system design the model comes first as phenomenon, will be from which the system a set of “blueprints” [2,19,20]. The implemented or deployed bui Id, could be forms. They blueprints might take several a set of equations or a complex simple descriptions, in computer program. The task of system design viewed and study models of create is to perspecl: ive this designs before they are physically implemented.

ENTITY 3. HIERARCHIES

piii+y[

Fig.

2

Representation in

the

System

of Entity

Taxonomic

OF DESIGN

knowledge, we mean a representation for BY taxonomic the kinds OF variants that are possible for an object, i.e., how they can categorized and sub-classified. For example the structure know could that transmissions are automatic or manual, and that the latter can be of the four-speed or five-speed variety. Our pr imarv objective is to construct models of the system being designed in order to evaluate them with the help of simulation studies and select the best design alternative. construct a To model, the components of a decomposition must be coupled together. Thus, the third kind of knowledge that our structure .Eor representing the design architectures should have is that of couplinq relationships.

drum

disc

mechanical

REPRESENTATION

TO appropl-iately represent the family of design structures we need a structure that embodies knowledge about the following three relationships: decomposition, taxonomy, and coup1 ing. By knowing about decomposition we mean that the structure has schemes for representing the manner in which an object is decomposed into components, and can operate on, and can communicate about such schemes.

:;::;:E:;.,,

pneumatic

hydraulic

-FOR

In this section we present the formal concepts for representing and integrating the possible design alternatives that may be conceived for a given project. We argue that the system entity structure should be an underlying object used in the construction of the expert system design environments.

the To character:ze the design process we adopt studies [12] which we previous our results of the design procedure is a series summarize as follows: types of two comprising rsf i nements of successive concerns the The first activities. design type The levels. transitions between the so-called design a set design actions associated type deFines second levels are level. The design design with a given the decomposition of the refinements of successive thus the The first, and system under consideration. is defined by the behavioral level, abstract most next the Subsequently, system. the description ot the system into decompos i ng def i ned by levels are such decompositions to the modules, and applying not further are subsystems unti I the modu 1es decomposable. Thus, the atomic system comp;;znts are destgn level of the lowest represented at hierarchy;

,

STRUCTURING

design define we do of we formal

The methodology for constructing an expert system design environments will base itself on codifying appropriate decompositions, taxonom i c and coup1 i ng relations. In other words we seek to model the expert’s knowledge about the design domain by finding pertinent decompos i t ions of the domain, the possible

Relations

Structure

2241

Concepts

for Knowledge-Based

System Design Environments A specialization may existence just as entities do. occur in more than one location: whenever it occurs it carries with all its attributes it and substructures. Of course it may not be meaningful to attach a particular specialization to a particular entity.

variants that can fit within these decompositions, and components of the constraints on how the the This will decompositions can be coupled together. know1 edge constitute the so-called declarative we should provide the procedural base. Beyond this, rules which knowledge base in the form of production can be used to manipulate the elements in the design domain.

Hierarchical decomposition is in many ways analogous to specialization hierarchy just discussed. The the alternation of alternation property now requires entities and is a mode aspects. An aspect of decombosition for an entitv iust as a soecialization is a mode of classification for it. There may be several ways of decomposing an object just as there classifying it. may be several ways of Formally, aspects and specializations are quite alike their in behavior (but not in their interpretation): they each alternate with entities, but cannot be hung from each other. A special of decomposition called a type multiple decomposition facilitates flexible representation of multiple entities whose number in a system may vary. Specializations of a” entity can be mapped into corresponding aspects of its multiple entity. Such transformations are discussed extensively in [17,183.

The rationale behind such an approach is two fold. In the decomposition, the first place, we identify knowledge representation as taxonomic, and coupling which enables the structure to communicate about its objects. that the But more that that, we propose rules themselves can be much better designed once good have been representations above relations for the identified. There are several reasons for advancing this proposition. We shall show that large segments of rules can be generated almost automatically from the in absence of such know1 edge structures: the structures these rules would have to be generated oneby-one in an often ad hoc manner. To the extent that most of the rules can be generated automatically, we attention 0” can then the focus our shou 1d then exceptions. Ultimately, rule development reduce to creative effort required to deal with the the irreducible idiosyncracies of the problem domain. The formal stipulated definition

object above follows.

Definition

(Be\ogus

is

that the

[I],

Zeigler

[18]). with V is that i tern of:

alternation

entity/aspect entity/specialization strict hierarchy inheritance: birth, life multiple entity

and

allows

for

the

following

<

Our approach to expressing the coupling constraints is follows: we apply mappi “g to remove the as the specializations to obtain a” entity structure containing only entities and aspects. Now we imagine that we are synthesizing models by working our way down the entity structure selecting a single aspect for each ent i ty and zero or more entities for each aspect. Such a process is called pruning of the entity structure. We shall describe it in detail in the next section. The coupling constraints we wish to express must then be associated with aspects since they represent the decompositions from which we shall associate a choose when pruning. MOreOVer. we must scopes al 1 the which aspect with an constraint constraint. What entities that are involved in that aspect should be minimal in the sense this is more, below it in that there is no other aspect that I ies scopes al 1 the also which structure entity the entities involved in the constraint.

requirements meets the system entity structure whose

A system entity is a labeled tree structure attached variable types. When a variable type attached to an item occurrence I, this signifies to describe the 1-v may be used a variable occurrence I. The structure satisfies the axioms * ,: * * +

I

operations: 4. w

* naming scheme A generation of distribution /aggregation relations 4: transformations to taxonomy free form fi pruning * attachment of constraints to aspects

PRUNING -

FOR GENERATION -

to discuss We are now ready concepts in our proposed design generic the concerns concept the system entity structure.

E

DESIGN

the two most essential first The framework. frame-based pruning of

crucial and As we have already pointed out the first in the design process is to determine the set of step system being the configurations of possible all structure is the basic system entity The designed. The entities such a fami ly. organizing means of while aspects allow the components represent system alternatives for various form designer to the system entity Thus, decompositions of components. is a set of substructures from which design structure select such constructed. To can be models meaningfully prune the entity substructures we mu5 t structure.

the For a more detailed formal treatment of system entity structure we refer the reader to [17]. Here we shall indicate how the know1 edge discussed representation scheme is realized by the structure. We begin by characterizing the taxonomi representation scheme. An entity may have severa specializations; each specialization may have several entities. The original entity is called a genera relative to the entities belonging to type specialization, which are called special types. Since each such entity may have several specializations, hierarchical structure results, which is called taxonomy.

ENTITY STRUCTURE STRUCTURES

c I I a a a

Recall that our design framework requires that the design models (or more precisely, the structures that the design accommodate them) are used to construct and requirements. The generic experimental objectives shortly, serves frame which we shall define formally Thus, by of expressing such objectives. as a means respect to pruning the system entity structure with generic frames we derive the following benefits:

Figure 2. depicts the entity structure in which the ent i ty BRAKES has been given two specializations, control-type and construction-type. A salient feature is requires the alternation property which that entities and specializations alternate along any path from,root to leaves. Specializations have independent 225

Jerzy W. Rozenblit 1.)

In a.)

b.)

c.)

2.1

terms

of

the

a generic substructures objectives. alternatives applicable problem.

contribution frame which Thus, may or not

the

design

bcehavioral

process

a.)

the

aspects

b.)

the

depl:h

c.)

the

descriptive

Having presented frame concep’: and define the structure. -Generic

that of

are

the

selected

pruning

for

each

frame based algorithm: Procedure

of

for

entity

components

enough to generic

IG and

denotes the OG is the set

set of

restrict the observation

input output

to the pruning observation frame substructures that

Ai

entity

be defined

--the

design

by

the

following

VGOF) :

:=

frame

variable

do

CVGOF

-

do ) where

bk

type).

and

Ek

by in the Ek with

subtracting the entity substructure} all its variables

TE : and

attach

the

CVGoF

store

to

TE,

the

{ TE;

(Ek, is

such

set

of

types

level

that

at

Ek has

226

the

of root

which

aspects

of

the

frame

do

then

a copy of the current model entities the last level serve as a basis for pruning A;+,) ; the

current

model

structure

structure {this copy in the next TE,.

appiar that last level with

TE,

by

last level entities { the eitities off the this next aspect may now be attached to tree] ; end: end: {of Prune] We have not .entity structure the modeller boundaries.

of

CVGoF , VGoF) ; empty

eliminate all the entities level marked as the the variable type occurrence; end ; Update the current model structure

procedure and generates all accommodate

frame

a child

constraint the

a the

al ready

as

denotes

(is

in

o; the model structure 1 entity at the current level in is present type which in model this level the

as the last are present 6 Ai

present

current

coupling

substru:ture least one a variable then mark

v k f VGoF

is

entity

A;

{update

vk

variables present Attach

begin create without wi I I aspect

variable variable

c Ej

Ek s Ai

begin CVGOF

Prune

By defining the generic observation frame in the above manner we 1 imi t its role to representing the behavioral ,aspects of design objectives and requirements. If we were to construct models of designs based on the structures pruned in the generic observation frames we could only implement the behavioral specifications of designs. There are also object i ves that concern the structural aspects of the project under consideration. Therefore, as we shall see in the next section, it will be necessary to augment the design model construction with a process that we terln synthes i s rule generation in order to realize the structural constraints. Let us however return define how a generic the system entity

aspect

each

“GOF structure var i ables end; for each E,

OGI of generic generic

can

(Ej , CVGOF,

current If at contains

if where types, types.

Prune

ascect

The concept of the generic experimental frame has been originally developed for the purpose of generating the experimental = BODY-WEIGHT + MAXIfiUM.LOAD (for a 6 passenger c= MAXlHUM.VOLUME >=

associated

must either from

CYLINDERS-NUMBER the the

* CYLINDERS.NUMBER

associated of the entitv follows:

constraints the form:

5.)

4.)

= CYLINDER.VOLUHE

BODY .VOLUHE ENGINE.POWER BODY.VOLUME car)

The general car design problem is now reduced to the synthesis of a passenger car with a 4 - cycle internal formulate structural combustion engine. Let us constraints and cower t them into a production rule scheme. formulation of a car.

Crankshaft

- compression ratio

-compression ratio Fig.

Cylinders -number III Cylinder

I

be coupled in line each other f

constraints canonical

with

the

in

pairs across

or

Eng i ne synthes

is

12.81 to scheme

production given by

rules we Figure 3. As

Jerzy W. Rozenblit

arld Bernard

P. Zeigler

CAR

II PASSENGER CAR

r-3

Body Brakes

Engine

Fuel

Sys.

Elec. sys.

Cool. sys.

Heat. sys.

II Internal

Combustion II

Fig.

A

I

Cylinders

Pistons

I

Valves

Cylinder

Piston

Fig.

TV Pruned Design

Crankshaft

Valve

then

Entity Structure Problem

for

the

Car

ENGINE.POWER >= BDDY.WElCHT + MAXlMUM.LOAD >= ENGINE.VOLUME+ BODY.VOLUME PASSENCERS.VOLUME Print

“Car

if

then

RC2

if

then

BODY.VOLUWE BOOY.VOLUME expand update

2.

“The Use of Structured Elzas M.S., Improve Realism in Methodology to Economic Planning”, in nodel Adequacy Wedde) , Pergamon Press, London, 1982.

3.

Fasang P.P., Ulrich P.. Whelan M., “n of Methodologies on the Levels -the &.tem Desi qn, Proc. of Conference on Computer Design

Q MAXIMUM.VOLUtiE < ENCINE.VOLUBE

- 1 UNIT + PASSENCERS.VOLUNE

BODY.VOLlJME by 1 UNIT

5.

add this pair of CYLINOERS update ENGINE.VOLUME

to

the

6.

ENGINE

“Needs Gonauser, M., Sauer, A., Desiqn Tools”, Proc. of Conference on Computer Design

Perspective a Diqital 1983 IEEE

Production Rule Model Car Synthesis Problem

_for the

Hiqh-Level

1983

IEEE

“A Wenderoth W., Kober R., Conauser , M, &:hodoloqy for Design g Diqital Systems and Aided SVStem Requirements for a Computer G;iqn Environment”, IFIP WG 10.0, Sept. 1983

Javor,

A. , Simulation and Related

“Proposa

on .the in:Discrete (ed. Javor,

Structure of Simulation A.), North-

Kober R., Wenderoth W., “Problems -experience in High-Level Design”, ,983 IEEE Conference on Computer

and practical Proc. of the Design

Holland,

Systems”, Fields Amsterdamig82.

Is

for 7.

satisfies al I the After a candidat.e structure that constraints has, been found a design model of the car frame should the observation be constructed and to an “Gasol i ne should be refined Consumpt ion” Then, can be experimental frame the model Cl31. shown in evaluated via simulation experiments as Figure 8.

8.

Design National (ed. H.

Completed”

BODY.WEIGHT

7 t.he

Model I inq and “Mu1 tifacetted EngineerG Software A Diss., Wei2mann Doct. Science, Rehovot, Israel. 1985

Belogus D., Simulation: i&jlionion”. Institute of

a pair of CYLINDERS is available ENGINE.POWER < BODY.WEIGHT + MAXIMUH.LOAD

Fig.

for

1.

4. RCl

Study Evaluation

REFERENCES

the in approach rule RC is global the general constraint Rules Rtl and RC2 are implemented checker. 1 and as local constraint satisfiers for constraints 2. Note, that the resource constraints 3 and 5 have been formulated as pretests for applicability of the rules. The production rule scheme is presented below: if

Simulation

in al I its Implementation of such a package, above. specific However, may be a long way off. generality, have already been implemented [lo,211 and parts of it, efforts are under way to further advance the theory of knowledge-based system design t12,18l.

111

Ill

Ill

RC

8

Design

4 - cycle

8.

Oren,

T.I., Simulation

82, 9.

SUMMARY

Reddy

Zeigler

B.P. Systems”,

“Concepts Simulation,

for Advanced 32,3 pp. 6g-

1979

Y.V., Fox M.S., Husain Analysis of Simulations the SCS Multiconference,

N.,

“Automat in KBS”, in San Diego,

i nq the Proc. of January

1985. We have attelnpted to outline a foundation on which the organization of the design process can be based. We envision a computer-aided expert design environment which internally represents the entity structures and generic for observation frames, and has a means dynamically manipulating these structures. The means on are based the procedures discussed

IO.

230

Rozenb I i t J.W.. “EXP A Software Tool for -berimental FrazpeTifTcation j+ Discrete Model I i nq & Simulation”, I” Proc. of --Event the 1984 Summer Simulation Computer Conference, pp. 967-971, Boston 1984.

Concepts 11.

12.

13.

for Knowledge-Eased

Rczenblit J.W., “A Conceptual Basis for ” Inteqrated. Simulation Based System Dzqn”, Doct. Diss. Computer Sci., Wayne Dept. of State University, Detroit, Michigan, 1985 Rozenblit J.W., “Structures for System Design Environment”,echnicaI Siemens AG, West Germany (internal distribution) Rozenbl it Experimental to appear Simulation al.,

a

Hodel-Based Report, I 984 Munich,

J-W., “Generating Meaninqful Modules for Simulation Desiqn”, inKnowledqe-Based fiodellinq and Methodologies, ed. M.S. flzas et.

North

Holland,

Amsterdam,

1986

14. Shannon

R.E., Mayer R., Adelsberger H.H.. Systems and Simulation”, Simulation number 6xune 1985.

1.5.

16.

Siewiorek “Proposal Methodoloqy University,

vol.

“Expert 44,

D.P., Giuse D., Birmingham W-P., for Research on OEMETER. A Desiqn ---b and Environment”, CarnegTe-Mellon Pittsburgh, PA, Jan. 1983

Zeigler B.P. Simulation Model-3ased Springer-Verlag,

for “Structures Mode I in: Simulation Systems”, Methodoloqy: & lnteqrative New York, 1984

17.

Zeigler B.P. Discrete Event London,1984

18.

Zeigler B.P., Framework”,

(in

“Multifacetted Simulation”,

Wymore. W.A., Des i qn”, Arizona,

20.

Wymore W., “Systems lnterdiscipl inary York, 1976

“A Mathematical Technical Tucson, 1980

Zeigler B.P., interactive Proc. of Cybernetics Press 1980

Based and G

Model Iing and Academic Press,

“Expert Systems: preparation)

19.

21.

System Design Environments

n

Model

1 inq

Theory of Systems Report, University of

Engineering Teams”,

fiethodoloqy John Wiley,

for New assistant JERZY W. ROZENBLIT is currently a visiting computer science at Oakland University, professor of in his HSc degree Rochester, Michigan. He received University of from The Technical computer science State 1981 he joined Wayne Wroclaw, Poland. In University in Detroit to pursue the PhO degree under His Bernard Zeig\er. Professor the direction of are in the area of modelling and research interests simulation, system design and software engineering.

Belogus 0.. Bolshoi A., “E An Tool for System StructurTnqy European the-80 Meeting on Systems Research, Hemisphere and

Jerzy W. Rozenblit Dept. of Computer Oakland University Rochester, Michigan

(313)

Science

and

Engineering

48063

370-2200

BERNARD P. ZEIGLER is a professor of computer science and engineering at University of Arizona. He is author Rode1 I ing and Discrete fvent of “Multifacetted and “Theory of Simulation”, Academic Press, 1984, Modelling and Simulation”, Wiley, 1976. His interests for include distributed simulation and expert systems simulation methodology. Bernard P. Zeigler Dept. of Electrical and University of Arizona Tucson, Arizona 85721 (602) 621-2434

231

Computer

Engineering