United States Patent [191
`Simoudis
`
`llllllllllllllIII||||lllllllllllllllllllllllllllllllllllllllllllllllllllll
`
`005283857A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,283,857
`Feb. 1, 1994
`
`[54] EXPERT SYSTEM INCLUDING
`ARRANGEMENT FOR ACQUIRING
`REDESIGN KNOWLEDGE
`[75] Inventor: Evangelos Simoudis, Marlboro, Mass.
`[73] Assignee: Digital Equipment Corporation,
`Maynard, Mass.
`[21] Appl. No.: 1,911
`[22] Filed:
`Jan. 8, 1993
`
`[60]
`
`Related US. Application Data
`Continuation of Ser. No. 735,320, Jul. 24, 1991, aban
`cloned, which is a division of Ser. No. 270,893, Nov. 14,
`1988, abandoned.
`
`[51] Int. Cl.5 ......................................... .. G06F 15/18
`[52] US. Cl. .................................... .. 395/77; 364/578;
`395/919
`[58] Field of Search ..................... .. 395/50, 51, 53, 64,
`395/77; 364/578
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`ometries”, Engineering with Computers, 2, 1987, pp.
`l-10.
`Liew, C. W., “Feedback Directed Modi?cation of De
`signs,” IEEE lntl. Joint Conf. Neural Networks, 1990,
`pp. 237-243.
`Kolodner, J., “Extending Problem Solver Capabilities
`Through Case-Based Inference”, Proc. 4th Annual
`Int’l. Mach. Leaming Workshop, 1987, 21-30.
`Hinkle, D., “Clavier: A Case Based Autoclave Loading
`Advisor”, Lockheed Arti?cial Intelligence Center,
`Mar. 1990.
`Maher, M. L., “Process Models for Design Synthesis”,
`AI Magazine, Winter 1990, 49-58.
`Mostow et al., “Automated reuse of design plans”, Arti
`?cial Intelligence in Engineering, 1989, 181-196.
`Steinberg et
`al., “The Redesign System: A
`Knowledge-Based Approach to VLSI CAD”, IEEE
`Design & Test, Feb. 1985, 45-54.
`Kowalski et al., “The VLSI Design Automation Assis
`tant: from Algorithms to Silicon”, IEEE Design & Test,
`Aug. 1985, 33-43.
`(List continued on next page.)
`
`
`
`
`
`4,591,983 5/1986 Bennett et a1. 4,648,044 3/19s7 Hardy ............ .. 4,791,578 12/1939 Fazio
`
`4,837,735 6/1989 Allen
`4,847,784 7/1989 Clancey
`4,860,204 8/1989 Geivdron .
`
`..... .. 364/480
`
`.
`
`364/513
`..... .. 364/513
`
`Primary Examiner-Michael R. Fleming
`Assistant Examiner-Robert W. Downs
`Attorney, Agent, or Firm-Albert P. Cefalo; Ronald C.
`Hudgens; James F. Thompson
`
`4,866,635 9/1989 Kahn . . . . . . . . . . . .
`
`. . . . . .. 364/513
`
`..... .. 364/489
`4,922,432 5/1990 Kobayashi
`..... .. 364/489
`4,967,367 10/1990 Piednoir ..... ..
`4,967,386 11/1990 Maeda ........................... .. 364/578
`5,016,204 5/1991 Simoudis et al.
`. 364/578
`5,019,992 5/ 1991 Brown .... ..
`5,208,768 5/ 1993 Simoudis ..
`5,218,557 6/ 1993 Simoudis ........................... .. 364/ 578
`
`OTHER PUBLICATIONS
`Dixen, J. R., “Arti?cial Intelligence and Design: A
`Mechanical Engineering View”, 5th Intl. Conf. on A1,
`1986, pp. 872-877.
`Bond et al., “Integrating Prolog and CADAM to Pro
`duce an Intelligent CAD System” IEEE Westex-87,
`Conference on Expert Systems, 1987, pp. 152-160.
`Dixon et al., “Expert Systems for Mechanical Design:
`Examples of Symbolic Representations of Design Ge
`
`Ex
`
`ABSTRACT
`[57]
`A new expert system performs a redesign in connection
`with an original design. The expert system comprises a
`discrepancy determination component that identi?es a
`discrepancy between operation of the original design
`and a desired operation. A redesign component includ
`ing at least one redesign module associated with a dis
`crepancy generates a redesign in response to the origi
`nal design and the identi?ed discrepancy. Finally, a
`redesign generation component generates a redesign
`module in response to a previously-identi?ed discrep
`ancy and design, the redesign module thereafter being
`used by the redesign component.
`
`10 Claims, 9 Drawing Sheets
`
`manner-emu. 9°‘
`ammonium:
`ulna-man mu!
`
`serum: at‘:
`mu IIDULE
`
`'05
`
`Page 1 of 17
`
`FORD 1108
`
`

`
`5,283,857
`Page 2
`
`OTHER PUBLICATIONS
`Rosenbloom et a1., “RI-Soar: An Experiment in
`Knowledge-Intensive Programming in a Prob
`lern-Solving Architecture”, IEEE Trans. on Pattern
`Analysis and Machine Intelligence, Sep. 1985, 561-569.
`Brown et al., “Knowledge and Control for a Mechani
`cal Design Expert System”, IEEE Computer, Jul. 1986,
`92-100.
`Sharp, 11., “KDA-A Tool for Automatic Design
`
`Evaluation and Re?nement Using the Blackboard
`Model of Control”, 10th Int]. Conf. on Software Engi
`neering, Apr. 1988, 407-416.
`Minton, 5., “Quantitative Results Concerning the Util
`ity of Explanation-Based Learning”, AAAI 88 Pro
`ceedings, vol. 2, Aug. 1988, 564-569.
`' Huhns et al., “Argo: A System for Design by Analogy,”
`Proc 4th Conf. on Arti?cial Intelligence Applications,
`Mar. 1988, 146-151.
`
`Page 2 of 17
`
`FORD 1108
`
`

`
`U.S. Patent
`
`Feb. 1, 1994
`
`Sheet 1 of 9
`
`5,283,857
`
`zo:.<.52.m
`
`._.zuzon=zoo
`
`N.
`
`mun
`
`am:
`
`O.86
`
`zoawoum
`
`pzmzoazoo
`
`¢_
`
`_.0_n_
`
`ufimozoso
`
`Emzoazoo
`
`n.
`
`aux
`
`muomm‘m<:o410mun
`
`zo_mmo
`
`m._.z_<m._.mzO0
`
`I410munE0
`
`O.
`
`mofimmao
`
`Page 3 of 17
`
`FORD 1108
`
`Page 3 of 17
`
`FORD 1108
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Feb.1, 1994
`
`Sheet 2 of 9
`
`5,283,857
`
`_Innnnnnnnnnnnnnnnnn1+uuuuuuuuuuuuuuuu'l
`
`
`
`¢_wzuzoazoozoauoum
`
`m..z.<EmzooZammo
`
`zo_.5._om
`
`zo..5u._um
`
`
`
`meow...sozx
`
`9.48xofim
`
`L
`
`¢u._._oE.zoozQmuomm
`
`.53
`
`zoEm=..oo<ZO_._._m=..U<
`
`
`M85302!moou.=>ozx20.wwomm
`
`..Eu:_%.__
`zO_...¢On.202.100¢zmzmuowm
`_:53ozaaouxommmo»<mu.__o
`
`csnnE.._m.o...u
`ezsaomzom
`
`zoauoum
`
`mu.sm
`
`_._
`
`__
`
`_.
`
`mo<hEm.pz.
`mopémaoo.
`
`Page 4 of 17
`
`FORD 1108
`
`Page 4 of 17
`
`FORD 1108
`
`
`
`
`
`

`
`US. Patent
`
`Feb. 1, 1994
`
`Sheet 3 of 9
`
`5,283,857
`
`90
`‘NO
`IS TASK TO GENERATE
`NEW REDESIGN MODULE ?
`
`lY ES
`
`9' ascoao DESIGN CONSTRAINTS,
`msc 10 AND DISC CAUSE ID
`
`92 use PROCEDURE lN-FIGS.5A_- as
`T0 GENERATE NEW
`REDESIGN MODULE
`l
`_——+
`~o 93 IS TASK TO 6 ENERATE RULES
`' FOR SOLUTION ssuacnorq
`KNOWLEDGE PORTION?
`
`ins
`
`94 RECORD DESIGN CONSTRAINTS,
`DISC CAUSE m, DISC ID
`AND ELIGIBLE MODULES
`+
`95 use paocaouns m FIG.4
`T0 GENERATE RULES
`
`96 sin’
`
`FIG. 3
`
`Page 5 of 17
`
`FORD 1108
`
`

`
`US. Patent
`
`Feb. 1, 1994
`
`Sheet 4 of 9
`
`5,283,857
`
`META KNOWLEDGE ACQUISITION
`
`INPUTS
`
`DESIGN
`(ORIG DES ID, IREO sEOn ’...)]
`
`DISC IO
`-
`DISC cAusE IO
`REDESIGN OPERATORS AND MOOuLEs
`
`OUTPUTS:
`
`NEW OEs
`(ORIG OEs IO. IREO sEOn? MI]
`SPECIFIC META RuLEs
`'
`AesTRAcT META RULES
`
`ALGORITHM:
`
`KD SELECT A REDE SIGN OPERATOR MODULE
`ASSOCIATED WITH DISC IDAND
`DISC cAusE IO AND APPLY TO
`ORIGINAL DESIGN TO FORM
`REDESIGN
`
`l
`IOI
`FROM
`NO DOES REDESIGN
`ELIMINATE DISCREPENCY? ' @ F IGAB
`YES
`
`'02 GENERA'IE META ME AND
`ABSTRACTED META RULE
`
`I03
`
`EXIT
`
`I04 DOES THE NUMBEROF REDESIGN ITERATIO NS
`EXCEEDA PREDETERMINED
`NO .@ FIG.
`THRESHOLD?
`4B
`
`lY'Es
`
`I06 ARE THERE ANY OTHER REDESIGN
`OPERATOR MOOuLEs WHICH MAY
`BE usEOTO ELIMINATE DISCREPANCY?
`NO
`
`YES
`
`FIG.4A
`
`me an
`I
`6) FIG. 4a
`
`Page 6 of 17
`
`FORD 1108
`
`

`
`US. Patent
`
`Feb. 1,1994
`
`Sheet 5 of 9
`
`5,283,857
`
`I
`
`I0? SELECT ANOTHER REDESIGN
`OPERATOR AND APPLY TO
`INITIAL DESIGN TO FORM
`REDESIGN AND SET NUMBER
`OF REDESIGN ITERATIONS
`TO ZERO
`(5 FIG. 4A
`?
`
`I08 ARETHEREANY UNUSED
`YES
`REDESIGN OPERATOR MODULES
`WHICH ARE ASSOCIATED WITH _
`DISC ID AND DISC CAUSE ID?
`
`1N0
`
`IIO EXIT
`
`I
`m SELECTAN uuusso REDESIGN
`OPERATOR MODULE ANDAPPLY
`TO REDESIGN TO FORM NEW
`REDESIGN AND INCREMENT
`NUMBER OF ITERATIONS
`
`(é) FIG.4A
`
`FIG. 4B
`
`Page 7 of 17
`
`FORD 1108
`
`

`
`US. Patent
`
`Feb. 1, 1994
`
`Sheet 6 ‘of 9
`
`5,283,857
`
`REDES IGN KNOWLEDGE ACQUISITION
`
`I20
`
`I2I
`
`CREATEA REDESIGN
`SEQUENCE IN CONNECTION
`WITH A SPECIFIC DESIGN
`AND SET OF REDESIGN
`GOALS (FIG.5BI
`
`I
`
`ADD REDESIGN SEQUENCE
`TO OTHERS PREVIOUSLY
`CREATED IN CONNECTION
`WITH SAME REDESIGN
`GOALS
`
`I22
`
`CREATE NEW REDESIGN
`OPERATOR MODULE FROM
`SEQUENCES CREATED
`IN CONNECTION WITH
`REDESIGN GOALS
`IFIG.5CI
`
`FIG. 5A
`
`Page 8 of 17
`
`FORD 1108
`
`

`
`US. Patent
`
`Feb. 1, 1994
`
`Sheet 7 of 9
`
`5,283,857
`
`REDESIGN MODULE ACQUISITION
`
`I. CREATION
`
`I30
`
`I32
`
`OPERATOR IDENTIFIES
`REDESIGN GOALS AND
`SELECTS REDESIGN OPERATORS.
`WHICH MAY BE USED TO
`ACHIEVE REDESIGN GOALS
`
`I
`
`OPERATOR IDENTIFIES SEQUENCE
`OF APPLICATION OF REDESI 6N
`OPERATORS FOR PARTICULAR
`REDESIG N OPERATION TO
`ACHIEVE REDESIGN GOALS
`
`I
`
`SEQUENCE IS SAVED IN ,
`ASSOCIATION WITH DISC ID,
`DISC CAUSE ID AND
`REDESIGN MODULE NAME
`
`FIG. 5B
`
`Page 9 of 17
`
`FORD 1108
`
`

`
`US. Patent
`
`Feb. 1, 1994
`
`Sheet 8 of 9
`
`5,283,857
`
`2. REDESIGN MODULE CREATION
`
`I40
`
`I42
`
`I43
`
`RETRIEVE REDESIGN SEQUENCES
`ASSOCIATED WITH SELBZTED
`DISC ID, DISC CAUSE IDAND
`REDESIGN MODULE NAM E
`
`GENERALIZE REDESIGN
`OPERATOR IN RETRI'EVED
`REDESIGN SEQUENCES
`
`I
`l
`
`GENERATE RE DE SIGN
`OPERATORS PORTION
`FROM UNION OF GENERALIZATED
`REDESIGN OPERATORS, INSERT
`INTO REDESIGN MODULE
`
`I
`
`GEN ERATE ELIGIBILITY RULES
`USING DISC ID AND DISC CAUSE ID
`AS CONDITIONS, REDESIGN
`MODULE NAMEJN ACTION LIST,
`INSERT INTO REDESIGN MODULE
`
`I44
`
`GENERATE REDESIGN SCHEDULING
`RULES DEFINED BY RETRIEVED
`SEQ UENCES, INSERT INTO .
`REDESIGN MODULE
`
`FIG. 5C
`
`Page 10 of 17
`
`FORD 1108
`
`

`
`US. Patent
`
`Feb..1, 1994
`
`Sheet 9 of 9
`
`5,283,857
`
`GOO \
`
`DO DISCREPANCIES EXIST
`BETWEEN THE STORED
`OPERATION OF THE SYSTEM
`AND THE DESIRED OPERATION
`OFTHE SYSTEM?
`
`asossuew THE ORIGINAL
`DESIGN OF THE SYSTEM
`USING REDESIGN MODULES
`
`603
`
`G ENERATE A NEW
`REDESIG N MCDULE
`
`605
`
`FIG. 6
`
`Page 11 of 17
`
`FORD 1108
`
`

`
`1
`
`EXPERT SYSTEM INCLUDING ARRANGEMENT
`FOR ACQUIRING REDESIGN KNOWLEDGE
`
`This application is a continuation of application Ser.
`No. 07/735,320, ?led Jul. 24, 1991, now abandoned,
`which is a division of application Ser. No. 07/270,893,
`?led Nov. 14, 1988, now abandoned.
`
`5,283,857
`2
`solution. The rules comprising the redesign operator
`control knowledge of a redesign solution, on the other
`hand, determines the order in which the redesign opera
`tors are to be applied.
`The redesign operators, which are operators that
`indicate the various primitive redesign operations that
`may be provided in the system, form part of the “knowl
`edge” in the system. The redesign operator control
`knowledge provides a level of control knowledge as to
`the sequencing of application of the redesign operators
`to achieve a particular redesign goal. The solution se
`lection knowledge provides a level of “meta-knowl
`edge”, that is, knowledge about the control knowledge
`provided by the redesign operator control knowledge
`in the expert system.
`
`10
`
`INCORPORATION BY REFERENCE
`U.S. patent application Ser. No. 07/106,840, ?led
`Oct. 8, 1987, in the name of Evangelos Simoudis, for
`System Design Tool For Assisting In The Design Of A
`Complex System, and assigned to the assignee of the
`present application (hereinafter referred to as “the
`Simoudis application”), incorporated herein by refer
`ence.
`E. Simoudis, Learning Redesign Knowledge, (at
`tached hereto as an appendix), incorporated herein by
`reference.
`
`15
`
`20
`
`BACKGROUND OF THE INVENTION
`The invention relates generally to the ?eld of digital
`computer systems, and more speci?cally to expert sys
`tems for use in connection with digital computer sys
`tems.
`The aforementioned Simoudis application describes
`an expert system that assists in the redesign of complex
`systems, such as electrical circuits. In using the expert
`system, an operator supplies an initial design for the
`complex system, and a set of operational constraints.
`The expert system simulates the design and determines
`whether the operation of the design, as indicated by the
`simulation, conforms to the operational constraints. If
`not, a redesign element assists'in the redesign of the
`complex system to more closely conform to the opera
`tional constraints. The expert system then simulates the
`redesigned complex system. This procedure may be
`repeated several times until the operation of the com
`plex system conforms to the operational constraints
`speci?ed by the operator.
`To accomplish the redesign, the expert system in the
`aforementioned Simoudis application includes redesign
`operators, each of which operates to modify one of
`various aspects of the design, based on knowledge, in
`the form of rules, organized in a multi-level hierarchy.
`In response to the representation of the design, as pro
`vided by the operator or in response to a redesign, de
`sign constraints and the cause of a discrepancy between
`the operational constraints and the simulated operation
`of the design, a solution selection knowledge module
`selects one of many redesign solutions which are capa
`ble of eliminating the discrepancies by modifying the
`design. Each redesign solution, in turn, includes the
`various redesign operators, and redesign operator con
`trol knowledge indicating the order in which the rede
`sign operators are to be applied to accomplish the rede
`sign.
`The solution selection knowledge and the redesign
`operator control knowledge in the expert system are
`both in the form of rules. The rules in the solution selec
`tion knowledge module ?re in response to the informa
`tion concerning the various solutions which are capable
`of eliminating the discrepancies, the design constraints
`and the causes of the discrepancies between the simu
`lated operation and the desired operation of the com
`plex system. Firing of a rule in the solution selection
`knowledge module initiates operation of a redesign
`
`25
`
`30
`
`35
`
`40
`
`55
`
`65
`
`SUMMARY OF THE INVENTION
`The invention provides a new and improved expert
`system which includes the capability of learning knowl
`edge and meta-knowledge during operation.
`In brief summary, the new expert system performs a
`redesign in connection with an original design. The
`expert system comprises a discrepancy determination
`component that identi?es a discrepancy between opera
`tion of the original design and a desired operation. A
`redesign component including at least one redesign
`module associated with a discrepancy generates a rede
`sign in response to the original design and the identi?ed
`discrepancy. Finally, a redesign generation component
`generates a redesign module in response to a previously
`identi?ed discrepancy and design, the redesign module
`thereafter being used by the redesign component.
`BRIEF DESCRIPTION OF THE DRAWINGS
`This invention is pointed out with particularity in the
`appended claims. The above and further advantages of
`this invention may be better understood by referring to
`the following description taken in conjunction with the
`accompanying drawings, in which:
`FIGS. 1 and 2 are functional block diagrams of an
`expert system constructed in accordance with the in
`vention;
`FIGS. 3 through 5C are ?ow diagrams useful in un
`derstanding the operation of the expert system depicted
`in FIGS. 1 and 2.
`FIG. 6 illustrates a flow diagram of the preferred
`implementation and the method used to perform a rede
`sign operation.
`DETAILED DESCRIPTION OF AN
`ILLUSTRATIVE EMBODIMENT
`The invention will be described in connection with an
`expert system, which may be in the form of a computer
`program processed by a digital data processing system,
`for redesigning a complex system as described in the
`aforementioned Simoudis application. By way of back
`ground FIG. 1, which is generally taken from that ap
`plication, depicts a general functional block diagram of
`a system design tool which includes the invention. With
`reference to FIG. 1, the system design tool receives
`from an operator, which may be the designer of the
`complex system for whose design the system design tool
`will be used, through an operator interface 10, CPR
`DES CHAR operator input design characteristics, from
`which a design representation 11 is generated. After the
`operator has ?nished providing the design representa
`tion 11, it is coupled, as a DES REP design representa
`tion, to a simulation component 12. The simulation
`
`Page 12 of 17
`
`FORD 1108
`
`

`
`10
`
`5,283,857
`3
`4
`identi?ed by reference numeral 25) all of which have
`component 12 performs a simulation of the design of the
`complex system as represented by the design represen
`access to a blackboard 30 in which the redesign modules
`tation 11. The simulation component 12 provides SIM
`25 and other components described below store infor
`OPL CHAR simulated operational characteristics
`mation. The redesign modules 25, under control of a
`redesign controller 31, effectively perform different
`which illustrate the operation of the complex system as
`represented by the design representation 11.
`types of redesign operations in connection with the
`design representation 11. A redesign module 25 includes
`The SIM OPL CHAR simulated operational charac
`teristics provided by the simulation component 12 are
`a redesign operators module 27 which includes one or
`more redesign operators. Each redesign operator per
`coupled to a diagnostic component 13. The diagnostic
`forms a primitive redesign operation in connection with
`component 13 also receives from the operator interface
`10 DES OPL CHAR desired operational characteris
`a design de?ned by the DES REP design representa
`tion. Each redesign module 25 also includes a redesign
`tics which describe the desired operation of the com
`plex system represented by design representation 11.
`scheduling rules module 34 which de?nes sequences of
`The diagnostic component 13 identi?es discrepancies
`redesign operators in the redesign operators module 27
`between the SIM OPI. CHAR simulated operational
`to enable a redesign operation to occur.
`Each redesign module 25 also includes an eligibility
`characteristics and the DES OPL CHAR desired oper
`rules module 32 and an eligibility scheduling rules mod
`ational characteristics and also determines in response
`thereto DISC ID discrepancy identi?cations, which
`ule 33. The eligibility rules module 32 in-a redesign
`identify the discrepancies between the SIM OPL
`vmodule 33 includes eligibility rules, which are described
`below, which identify the discrepancies and discrep~
`CHAR simulated operational characteristics and the
`20
`DES OPL CHAR desired operational characteristics,
`ancy causes which the redesign module 25 may be used
`and the DISC CAUSE ID discrepancy cause identi?ca
`to obviate or correct. The eligibility scheduling rules
`tions (step 601) which identify causes of the identi?ed
`module 33 includes eligibility scheduling rules which
`DIS IDs discrepancy identi?cations.
`identify the number of eligibility rules which may be
`applied during a given redesign operation.
`The DISC ID discrepancy identi?cations and DISC
`25
`During a particular redesign operation, after the diag
`CAUSE ID discrepancy cause identi?cations identi?ed
`by the diagnostic component 13 are coupled to a rede
`nostic component 13 has generated a DISC ID discrep
`sign component 14. The redesign component also re
`ancy identi?cation and a DISC CAUSE ID discrep
`ceives a set of DESIGN CONSTRAINTS from the
`ancy cause identi?cation and posted them on the black
`board 30, the redesign controller 31 processes the eligi
`operator interface 10 and the DES REP design repre
`sentation from the design representation 11. The DE
`bility rules in all of the redesign modules 25 by compar
`ing the eligibility rules in the eligibility rules module 32
`SIGN CONSTRAINTS identify constraints on, for
`example, the physical design of the design 11. In re
`of all of the redesign modules 25 to the DISC ID dis
`sponse to all of these inputs, the redesign component 14
`crepancy identi?cation and DISC CAUSE ID discrep
`generates REDES REP redesigned design representa
`ancy cause identi?cation. If an eligibility rule ?res, the
`tion, which represents a design representation as modi
`redesign controller stores, on the blackboard 30, the
`?ed to reduce or eliminate the operational discrepancies
`identi?cation of the redesign module 25 which includes
`represented by the DI SC ID discrepancy identi?cations
`the eligibility rule. In some cases, the redesign control
`ler 31 may determine that multiple eligibility rules ?re
`and DISC CAUSE ID discrepancy cause identi?ca
`during the comparison operation.
`tions identi?ed by the diagnostic component 13, within
`the DESIGN CONSTRAINTS de?ned by the opera
`The redesign component 14 also includes a solution
`tor through operator interface 10, if the DESIGN
`selection knowledge module 24. The solution selection
`knowledge module 24 includes solution selection rules
`CONSTRAINTS can be satis?ed (step 603).
`The REDES REP redesigned design representation
`which are used to select among multiple redesign mod
`generated by the redesign component forms a new de
`ules 25 whose identi?cations may have been stored on
`sign representation 11. The new design representation
`the blackboard 30 during the eligibility rule comparison
`operation. Following processing of the eligibility rules
`11 is coupled as the DES REP design representation to
`the simulation component 12, which again performs a
`32, the redesign controller 31 processes the solution
`simulation on the redesigned design representation. The
`selection rules by comparing the solution selection rules
`procedure described above is repeated to enable the
`to the contents of the blackboard 30, including the DE
`50
`diagnostic component 13 to identify new DISC
`SIGN CONSTRAINTS, the DISC ID discrepancy
`identi?cation and the DISC CAUSE ID discrepancy
`CAUSE ID discrepancy cause identi?cations and rede
`sign component 14 to generate a new REDES REP
`cause identi?cation. If a solution selection rule ?res, the
`redesigned design representation. The process is itera
`redesign controller 31 stores the identi?cation of the
`tively repeated until the diagnostic component 13 deter
`redesign module 25 contained in the ?red solution selec
`mines that the SIM OPL CHAR simulated operational
`tion rule in the blackboard 30.
`characteristics correspond to the DES OPL CHAR
`The redesign controller 31 thereafter uses the rede
`design operational characteristics provided by the oper
`sign module 25 to perform the redesign operation. In
`particular, the redesign controller 31 initiates a redesign
`ator. At that point, the design of the complex system, as
`represented by the design representation 11, corre
`sequence de?ned by the redesign scheduling rules 34
`60
`sponds to the design required to provide the DES OPL
`and redesign operators 27 to perform the redesign oper
`CHAR design operational characteristics.
`ation on the design identi?ed by the DES REP design
`The simulation component 12 and diagnostic compo
`representation on the blackboard. The redesigned DES
`REP design representation is then available for simula
`nent 13 in the system design tool may be conventional
`tion and diagnosis to determine if its operational charac
`components. FIG. 2 contains a functional block dia
`gram of the redesign component 14. With reference to
`teristics correspond to the DES OPL CHAR desired
`FIG. 2, the redesign component 14 includes a plurality
`operational characteristics de?ned by the operator at
`of redesign modules 25A through 25(M) (generally
`the operator interface 10.
`
`35
`
`55
`
`Page 13 of 17
`
`FORD 1108
`
`

`
`5,283,857
`5
`6 .
`As noted above, the redesign operators in redesign
`module 41 and the meta knowledge acquisition module
`42 operate by observation of redesign operations speci
`operator module 27, eligibility rules in eligibility rules
`?ed by the operator interface 10 during a learning phase
`module 32, the various scheduling rules and the solution
`selection rules in solution selection knowledge module
`as described below in connection with the ?ow dia
`grams in FIGS. 4 through 5C.
`24 are all in the form of production rules. Each produc
`The general procedures performed by the learning
`tion rule has a left hand side, which identities one or
`component 40 are depicted in FIG. 3. With reference to
`more conditions, and a right hand side, which has an
`FIG. 3, the learning component 40, and particularly
`action list. In a production rule in a solution selection
`knowledge module 24, for example, the left hand side
`learning control module 43, ?rst determines whether it
`is to generate a new redesign module 25 (step 90), as
`may identify a DESIGN CONSTRAINT, a DISC
`determined by the operator through operator interface
`CAUSE ID discrepancy cause identi?cation, and a
`DISC ID discrepancy identi?cation. In addition, a pro
`10. If so, it sequences to step 91, in which it records the
`DESIGN CONSTRAINTS, DISC ID discrepancy
`duction rule in a solution selection knowledge module
`identi?cation(s) and DISC CAUSE ID discrepancy
`24 may indicate when one or more of its associated
`redesign modules 25 may be used in the redesign opera
`cause identi?cation(s), and then uses the procedures
`described below in connection with FIGS. 5A through
`tion. The action list in the right hand side of such a
`production rule speci?es which redesign module 25 will
`50 to produce a new redesign module 25 (step 92).
`If the learning control module 43 determines that the
`be used in connection with a redesign operation.
`Similarly, the left hand side of a redesign operator 27
`learning module 40 is not to generate a new redesign
`module 25, it determines whether it is to-generate addi
`identi?es modules of a design on which the operator can
`operate. That is, if the redesign operator 27 is intended
`tional rules for the solution selection knowledge module
`24 (step 93). If so, it records the DESIGN CON
`to remove or add a speci?c type of element of the de
`sign, under speci?c conditions in the placement or inter
`STRAINTS, DISC CAUSE ID discrepancy cause
`identi?cation(s), DISC ID discrepancy identi?cation(s)
`connection of the element in relation to other elements
`of the design, the conditions in the left hand side iden
`and redesign modules 25 which may be used in connec
`tion with a redesign operation (step 94) and performs
`tify those placement and interconnection conditions.
`The action list comprising the right hand side of such a
`the procedure identi?ed in FIG. 4 to generate the re
`quired rules (step 95).
`production rule operate to actually perform the rede
`Following either generation of a new redesign mod
`sign, that is, to remove the element from, or add the
`element to, the design representation. Each redesign
`ule 25 in step 92, or generation of additional rules for the
`operator 27 effectively de?nes a primitive redesign
`solution selection knowledge module 24, or if it deter
`operation, and multiple redesign operators may be used
`mines that it is to do neither, the learning control mod
`ule 43 exits to wait for further. instructions from the
`in sequence to generate a redesign to obviate a discrep
`operator interface 10.
`ancy identi?ed by a DISC CAUSE ID discrepancy
`The operations performed by the meta knowledge
`cause identi?cation 23.
`An eligibility rule in the eligibility rules module 32 in
`acquisition module 42 are depicted in FIGS. 4A and 4B,
`a redesign module 25 indicates whether the redesign
`and the operations performed by the redesign module '
`knowledge acquisition module are depicted in FIGS.
`module 25 may be used to perform a redesign operation.
`In each eligibility rule, the conditions in its left hand
`5A through 5C (FIG. 6, step 605). With reference to
`side identify discrepancies and discrepancy causes, and
`FIGS. 4A and 4B, the meta knowledge acquisition
`40
`the action list in the right hand side identify the redesign
`module 42, in conjunction with the operator interface
`module 25.
`10, operates in one or more sequences of iterations to
`generate eligibility rules, redesign sequence scheduling
`In addition, the redesign module 25 includes two
`types of scheduling rules, including eligibility schedul
`rules 33 and rules for the solution selection knowledge
`ing rules comprising an eligibility scheduling rules mod
`module 24. During each sequence of iterations, the meta
`knowledge acquisition module 42 iteratively determines
`ule 33 and redesign scheduling rules comprising rede
`sign scheduling rules module 34. The eligibility schedul
`whether a redesign operator module 25 eliminates an
`ing rules identify how many eligibility rules will be
`operational discrepancy, as identi?ed by the DISC ID
`applied during each redesign operation. The redesign
`discrepancy identi?cation and DISC CAUSE ID dis
`scheduling rules in the redesign scheduling rules mod
`crepancy cause identi?cation as determined by the diag
`50
`nostic component 13. If so, the redesign operator mod
`ule 34 in a redesign module 25 identi?es one or more
`sequences in which redesign operators 27 are to be
`ule 25 is determined to be a candidate to be used in
`connection with eliminating the discrepancy, and the
`applied to achieve a redesign operation.
`meta knowledge acquisition module 42 performs an
`Returning to FIG. 2, in accordance with the inven
`other iteration in which it selects another redesign oper
`tion, the expert system further includes a learning com
`ponent 40 including a redesign module knowledge ac
`ator module 25 to apply to the redesign to try to elimi
`quisition module 41, a meta knowledge acquisition mod
`nate the discrepancy. If the discrepancy is not elimi
`ule 42 and a learning control module 43 which, under
`nated during an iteration sequence after a predeter
`control of the operator through operator interface 10,
`mined number of iterations, the meta knowledge acqui
`controls the redesign module knowledge acquisition
`sition module 42 returns to the initial design, and tries
`module 41 and meta knowledge acquisition module 42.
`another sequence of iterations beginning with another
`The redesign module knowledge acquisition module 41
`redesign operator module 25 associated with the DISC
`ID discrepancy identi?cation and DISC CAUSE ID
`serves to generate redesign operators for module 27 and
`eligibility rules for module 32 and redesign scheduling
`discrepancy cause identi?cation.
`When the meta knowledge acquisition module 42
`rules for module 34 in a redesign module 25. The meta
`reaches a design whose operation corresponds to the
`knowledge acquisition module 41 serves to generate
`rules de?ning the solution selection knowledge modules
`operation de?ned by the DES OPL CHAR desired
`24. Both the redesign module knowledge acquisition
`operational characteristics, as provided by the operator
`
`30
`
`55
`
`60
`
`25
`
`35
`
`Page 14 of 17
`
`FORD 1108
`
`

`
`20
`
`5,283,857
`8
`7
`interface 10, the meta knowledge acquisition module 42
`12, between the simulated operational characteristics
`and the desired operational characteristics of the design,
`generates meta rules and abstracted meta rules for use in
`the eligibility rules 32, redesign sequence scheduling
`the cause, as determined by the diagnostic component
`rules 33 and solution selection knowledge module 24.
`13, of the discrepancy, and the available redesign se
`quences provided by the various redesign modules 25
`Each meta rule includes a left hand side whose condi
`tions generally identify the DISC CAUSE ID discrep~
`which are indicated as being useful in connection with
`ancy cause identi?cation and the component of the
`the identi?ed discrepancy cause identification, and
`design giving rise to the operational discrepancy, any
`displays them for the operator interface 10. The opera
`DESIGN CONSTRAINTS imposed by the operator,
`tor interface 10 may then select one of the display rede
`and the identi?cation of redesign modules 25 which
`sign sequences. If the operator interface 10 determines
`may be used to perform a redesign operation to obviate
`that no redesign sequence is appropriate, it may initiate
`or correct the discrepancy. The right hand side of the
`operation of the redesign module knowledge acquisition
`meta rule identi?es one of the redesign modules 25,
`module 41, as described below in connection with
`which is the preferred redesign module 25 to perform
`FIGS. 5A through SC, to de?ne a redesign sequence for
`the redesign operation.
`a new redesign module 25, which will then be used by
`The abstracted meta rule generated by the meta
`the meta knowledge acquisition module 42. The meta
`knowledge acquisition module 42 is similar to the gener
`knowledge acquisition module 42 then applies the se
`ated meta rule, with the exception that it does not in
`lected or created redesign sequence to the design to
`clude the redesign constraints. It will be appreciated,
`form an
`redesign (step 100).
`therefore, that the abstracted meta rule is of more gen
`redesign, the meta
`After the creation of the
`eral applicability than the meta rule, since it has fewer
`knowledge acquisition module initiates a simulation by
`conditions, notably the redesign constraints, that must
`the simulation component 12 to determine whether the
`be met in order for the rule to ?re. In applying the meta
`initial re