WIXLIB

83ZEIGLER et al.: KNOWLEDGE-BASED SIMULATION ENVIRONMENTKNOWLEDGIE-BASESTABLE IINSTANCEVARIABLESOF CLASSESIN DESEclas5InstanceATOMIC-MODELS-- ind-vim(sigma phase)int-transfninference-engine-- objeet-classea-- aoutputfnt-tmin- We-advancefn-rUle-classUsagevariable* inferencenew-ohjeets** make-new-expertknowledgeIbasesknowledge* make-copy* * *basesknowledgeATOMIC-EXPERT-MODELSind-vars (expert-core)make-copy-basesinferencekb-mmp. name of the instance of the knowledge base component- : instance-variableswhich is the same as the DES’snameenginesinferenceit-iepoints to an inference table which stores theinferencine state-enginesinferencelocal--enginesmemory-I: methodFig. 4. Interface of DES to DEVS-scheme.used to access each DES’sset of fact instancesATOMIC-EXPERT-MODELnameThe objects involved in the definitions of a DES areinstances of knowledge-base, inference-engine, rules and factclasses. An inference-engine instance does not directly accessrules and facts. Instead, it refers to an associated knowledgebase which has links to the relevant rules and facts. In thisway, the inferencing methods of the class inference-enginesor its subclasses are generic (i.e., can be used for rules andfacts stemming from a variety of classes).Fig. 1 also shows the instance variables of each class.The roles of instance variables are explained in Table I. Theinstance variable local-memory-name is used when a copy of aDES is made. This copy can access its own list of facts whichis an independent copy of the original DES’s list of facts (thisenables the engine to keep track of the distinct inferencingstates). The instance variable it-ie points to the inferencetable which stores the current inferencing information about aDES including fired rules, goal state, attribute list, etc., wherethe initial value of the attribute lists represents the currentdynamic status of the model components being controlled.These (fired rules, goal state, attribute list, etc.) are thecontents of the information that should be sent between expertsystem elements and model components. It is the it-ie orinference table that establishes the static communication linksbetween expert system elements and model components beingcontrolled. The nature of the communication links are staticsince the model components to be controlled by particularexpert system elements are predefined at system design level.When there are multiple sets of expert system elements in themodel as the fractal architecture model presented in SectionVI, each set of expert system elements can have its own staticcommunication links to corresponding model components.A. InterJacing DESE and DEVS-Scheme:Atomic-Expert-ModelsThe interface of DESE to DEVS-Scheme is accomplishedby creating classes called atomic-expert-models. This class(multiply) inherits methods and variables from the classesknowledge-bases and atomic-models (Fig. 4). Thus, as illus-r DEVS-COMPONENT- EXPERT-CORE II1hINFERENCE-ENG.OWLWDGE-BASESYE:UPILFig. 5. Composition of atomic-expert-model.trated in Fig. 5, an instance of class atomic-expert-modelshas both a1 DES (called as expert-core) and an atomic-model(called as DEVS component). These models can be duplicated by invoking the make-copy method which producesisomorphic copies [32].When a copy of atomic-expert-model is created, the statevariables of expert-core are initialized to the original model’sexpert-cone name which is extended by the duplicated modelname (in order to access different expert system component).The newly created copies of fact instances have names whichare extensions of the name of the original model. Rules arenot copied. Instead, each copy of the model has pointers tothe original rules.Besides the utilities just presented, all the methods andutilities of DEVS-Scheme remain applicable. In this way,inheritance of methods is exploited to extend hierarchical,modular dliscrete-event model construction and simulation toinclude distributed expert system components.B. Interruptibility of Expert System ModelsRecall that an important requirement for embedding expertsystems in a simulation environment is to provide intenupt-

84A: SYSTEMS AND HUMANS, VOL. 26, NO. 1, JANUARY 1996IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBEF3ETICS-PARTABAB 6leyel-oneIIIIABleveLoneAB-dmIAIAB 6level-twoIIA @level-lwoAB @ level-th reeB-SWABOlevel-nIcABFig. 6. System entity structure for recursive pruning.ibility of the DES models. The interrupt capability is neededwhen an urgent or high priority task arrives while the inferenceengine is processing a less urgent one. When processing ofthe current task is interrupted, its state is saved for use wheninferencing is resumed later. The nature of saved states .arethe value of parameters (or facts of rules) just before theinferencing is interrupted. The values of parameters change asthe inferencing process proceeds toward goal states from initialstates through several intermediate states. Since these states arerepresented by different values of parameters, the saved state isthe value of parameters of an intermediate state.To implementthis behavior, there is transfer of control from the expert-coreto the DEVS component after the end of each basic inferencecycle. A check is done to see if a high priority external inputevent has been buffered by the DEVS component since thelast check was made. This is similar to cyclic polling of anoperating system interrupt. In this context however, the basicinference cycle can be defined as the user desires, for example,as the firing of a single rule, firing of a given number of nules,passage of a predefined simulation time, or the attainmelit ofan inferencing subgoal. The cost of interruption lies in twoaspects. The first aspect is in computer computation time.Whenever the interrupt occurs, all the values must be savedso that the resuming inferencing process can start from theinterrupted states. The second aspect is in simulation time,i.e., the actual delay time of the system due to the interruptionof the current process. This delay occurs, however, ma:y becompensated by improved performance, which is the reasonfor providing interrupt capability.IV. RECURSIVEPRUNINGThe system entity structure (SES) directs the synthesis ofmodels from components in a model base [9], [lo]. TheSES is a knowledge representation scheme that combines thedecomposition, taxonomy, and coupling relationships. Thissection presents a design technique for generating recursivesystem entity structures, where substructures may containcopies of themselves. An operation called recursive pruning isapplied to the SES for generating hierarchical model structureswith properties similar to fractals. For example, Fig. 6 showsA 6 level-nC6level-nFig. 7. PES with recursive pruning.an SES which specifies the recursive structure of model AB.AB consists of A and B, where B is specialized into C orAB,the root model itself. If we select C at B-spec node inthe pruning process, the model AB will have A and C as itssubcomponents and no recursive structure is generated.On the other hand, truly recursive pruning is invoked whenAB is selected at E-spec node. As in a context free grammar,recursion can be continued to an arbitrary desired depth.Fig. 7 represents the PES resulting from n layers of recursionterminated by the final selection of C from the B-spec node.The figure also shows how a level-matched name extensionis generated each time the E-spec node is encountered duringpruning process. This enables self-similar models in differentlevels to be distinguished. Fig. 8 illustrates the hierarchicalmodel represented by the PES in Fig. 7.When there are several recursions in pruning process, itgets more complicated. To alleviate such complexity, wecan prune in more easily managed, reusable stages. In delaypruning, decisions can be delayed for later pruning sessions.For example, Fig. 9 shows an intermediate stage in which onlythe number of recursions of AB and the selection at the Aspec node of level one were decided. The remaining A-specnodes were left undecided and delayed for later pruning. Thisintermediate PES was further pruned, eventually to take theform of the PES at the left lower side of the figure. Here allpossible selections have been made and the PES is ready fortransformation to simulatable form.Delay Pruning is useful in constructing several similarmodel architectures where only relatively small differences insubsequent pruning are needed. This will be further illustratedin the flexible manufacturing system example to be discussednext.v.FRACTALARCHITECTUREMODELThis section describes the application of DES models andrecursive pruning to the fractal architecture for flexible manufacturing introduced by Tirpak et al. [13]. The purpose of this

85ZEIGLER et al.: KNOWLEDGE-BASED SIMULATION ENVIRONMENTSES7AB @ level-twoIAB0lwd-o l-nFig. 9. Dehy pruning.bfunext layer bfus.:atomic modelsII:coapledm Fig. 8. Model AB pruned to have a recursive structure.II.example is not to achieve a fully algorithmic development butto provide a framework for showing the utility of the justpresented simulation concepts.The fractal architecture to be considered includes multipleexpert systems in a family of modular, hierarchically constructed DEVS models. Although this example considers onlya limited aspect of the manufacturing process (transporterrouting), it generalizes readily to all phases of the manufacturing process. Since expert system components are treated nodifferently than other DEVS models, once the SES and modelbase have been constructed, it is relatively easy to generatealternative model architectures.41.transportersII " 'Imuting reqw*muting info.mutingrequest.,--A. SES Representation of Fractal ArchitecturesTypically, a flexible manufacturing system (FMS) consistsof a hierarchy of several workcells, each containing one ormore transporters, sub-cells, etc. Managing the flow of information and control across this hierarchy can be quite complex.Tirpak et. a1 [13] argue that, cast in a fractal, i.e., recursiveform, a model of an FMS admits of a natural hierarchicaldecomposition of highly decoupled units with similar structure materiainowinformation flowFig. 10. Basic fractal unit architecture.and control. The objective of such structuring is to manage thestructural icomplexity and coordination of an FMS hierarchy bymaximizing local functionality and minimizing global control.Moreover. the recurring components can be designed withinthe object-oriented paradigm so as to maximize reuse across

86IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS-PARTA SYSTEMS AND HUMANS, VOL. 26, NO. 1, JANUARY 1996factoryInext layer bSusIc'I:I!j :,,'Mu;hopfloor 1\:workstation 1.\\:in;ai ;next laver bfusinext layer bfus:::::::\t;': : : ,: ;3;Iworkstalion 2next layer bfuscFig. 11. Fractal architecture pruned to have five BFU's.levels. Thus the FMS fractal architecture model represents ahierarchical structure built from elements of a single basicdesign called a basic fractal unit (BFU). The design of theBFU incorporates a set of pertinent attributes that can fullyrepresent any level in the hierarchy [13].Fig. 10 depicts a BFU specifically designed to embodythe elements which fully describe the structure of any levelin the model hierarchy. Included within a BFU is a setof lower layer BFU's whose internal detail is hidden. Therouting controller (transporter router) sees these units asstations to which transfer batches should be delivered. It isthe responsibility of transporter routers within the lower layerBFU's to subsequently route the received batches.For illustration, the structure of one of the pruned models constructed for simulation is shown in Fig. 11 (detailedfunction of each model is described in [14]). The top ofthe hierarchy is a factory. The factory is composed of twoshop floors. The first shop floor (shopfloorl) in turn has

87ZEIGLER et al.: KNOWLEDGE-BASED SIMULATION FACTSI.div:s--ImarOUtermiotranspsIcoops Ill:inst.needd.as*:indicated Un U& provided bylnstanawriables:instanx fFig. 12. Classes in the construction of the expert router.two workstations, workstation1 and workstation2. Whereas,the second shop floor has two machines without having anyworkstation. Workstation1 has two machines and workstation2has just one machine.The transporter router is an expert system model whichcontrols routing of transporters in each BFU. It routes transporters among the lower layer BFU’s, output buffer and inputbuffer. There are total of five such DES models (one for eachBFU) whose inferencing is based on their own sets of facts,responding to the different dynamic conditions encountered ateach level (Fig. 11). The router and the rules used by its expertsystem are depicted in Fig. 12 and Appendix A.bfu :basic fractal unltbel : btu and exp. frameni :neat layerpu :processingunHdiv :dividerrouterm : router modelin-but :Input-bufferout-bur : output-buffertransp :bansporteret :experimentalframegenr :generatortransd :transducerFig. 13. System entity structure for bef (basic fractal unit with experimentalframe) architecture.IIIranapOBfacIB. Fractal Architecture ModelingThe recursive SES for the fractal architecture is shownin Fig. 13. The root of the SES, b e ! which represents themodel as being composed of BFU and ef, experimental frameconsisting of genr (generator model) and transd (transducermodel). Generator provides inputs to BFU, and transd collectsthe outputs from BFU for the calculation of output statistics.The BFU is specialized into two models, the nl (next lowerlayer) and ma (machine). The component nl is decomposedinto div (transfer batch job divider), routerm (transporterrouter), io (input/output buffer), transps (transporters) andBFU’s, where transps and BFU’s are broadcast-models, forwhich the number of components can be selected duringpruning. The io is again decomposed into in-io (input buffer)and out-io (output buffer).The fractal SES is pruned to yield a desired model architecture such as shown in Fig. 11. During recursive pruning,recursion stops when a machine ma is selected. Fig. 14 showsthe PES for the architecture in Fig. 11. This architecture isjust one of many possible that can be generated from the SES(Fig. 13). We can decide on an arbitrary number of hierarchical levels in constructing an architecture by terminating therecursion at the desired depth. Actually the depth need not beuniform. For example, the PES in Fig. 14 has three layers ofrecursion for the left side and two layers for the right side.The coupling at the BFU level is depicted in Fig. 15.IIIIrnrnaoestlmal est1Fig. 14. Pruned system entity structure of BFU.The PES in Fig. 14 does not show the experimental framepart of the architecture. There are five BFU’s in this architecture. The root is BFU@fuc (BFU for factory level).The modells at the second level (shop floor level) BFU’sare BFU@lsJD and BFU@sfl. The models BFU@wsO andBFU@wsl are workstation BFU’s within BFU@sfO. Thereare two transporters in BFU @sfl.All other BFU’s have justone transporter. Self-similar models within different BFU’s aredistinguished by the extension attached after the “@” symbol,

IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS-PART88-IbfubfusA SYSTEMS AND HUMANS, VOL. 26, NO. 1, JANUARY 1996IVO PORTS: message contentsINPUT PORTSi l l IIirpair that ccf&ts of a model requesting muting and a jobinfoe.g. (wsl @&info)iM :transperter model name forsignalinme current trnnspn ia donee.g. tmnsplOwslOVTPUT PORTScut: ajob-info0,.0.,i.Job-W : Uob-rype, Job-id, botch-size, scherbrlc)where zhe scherbrle Is Im Of model Mmes:iFig. 16. U 0 ports and corresponding message contents of transporter routermodel.aut-obb in-ibli int-t-obI t AbfU PO*p o n - m : c o m c t i m (message conmu)in-t-ob :input poil from banspoter(leadingrequest)in-ib inputport from bansporter(transfer batches)out-ob :output port lo vanspotem (bansfarbatches)out-t-ob :w ul port lo muter (routing request)h z k I lPat fmm[don;,dmReC q m f cW t i :wiprrt Pat to muter. * : inforroatian&on-:materklfbwRest of the port co eetionso r e f o d by r m h g ohme “phinwlporrsMd the comecrions of io model ( w f i g u r e ) .Fig. 15. DEVS BFU model.e.g., div@fac, div@s@, d i v e s f l , and so on. These extensions,which are generated during the pruning process, reflect thelevel and the module they belong to.VI. DISCUSSIONAND CONCLUSIONThe interruptibility feature developed for the DES environment is well illustrated by the transporter routing expertsystem. The current positions and velocities of all transporterswithin a BFU must be known when the transporter controller(router) makes its routing decisions. This position infomationis used to decide the departure time (in addition to thedestination) of a transporter. By controlling their departuretimes collisions among the transporters can be avoided. Whennecessary, the router model interrupts the inferencing processand sends position and velocity query messages to all thetransporters. After obtaining the needed position informationit resumes the inferencing process. Not all expert systemshells offer this interrupt capability. However, its utility asdemonstrated through simulation should suggest the need toinclude it in real world applications.Alternate structures (reconfigured structures) of the fractalarchitecture model can be generated through the recursivepruning process. The alternate structures can have differenthierarchical levels and different numbers of sub-BFU’s andtransporters within a BFU. After pruning, the details of anarchitecture model can be conveniently initialized prior tosimulation. Such rapid prototyping should greatly enhancethe ability to investigate alternative architectural solutions tomanufacturing problems in a timely manner.All h e component models in the fractal architecture modelbase are reusable. Since these models are modular and standalone components, reusability is achieved by specifying theirdesired coupling in an SES for a given application. To aidthe user in understanding the models for valid reuse, completedocumentation should be provided of the U 0 ports of models,the message structures on on these ports, and the behavioraldescription of models (Figs. 16, 17 and the Appendix illustratesuch documentation.)In conchsion, we have presented an approach to embeddingexpert systems within an object-oriented simulation environment that facilitates the creation of classes of expert systemmodel elements that can be interfaced with other model components. We have shown how interruptible distributed expertsystems can be defined as modular components of simulationsmodels. Their usefulness in fractal architectures for flexiblemanufacturing, as proposed in the literature, was illustrated.Simulation results forthis study are available in [14]. Finally,we showed how such an architecture can be specified using arecursive system entity structure. This recursive generation ofhierarchical structures is especially appropriate for design ofmultilevel flexible factories using fractal architecture concepts.However, the framework given in this paper extends wellbeyond manufacturing to support simulation modeling ofknowledge-based control in many other systems for whichhigh autonomy is the desired DELThe model gets a routing request and sends the routingdecision after inferencing the router rules. This router modelcan control more than one transporters.A. Model BehaviorInitially the model is at passive state. When a inferencingrequest comes from io model at input port in the model goesto inferencing state. If routerm is at inferencing state whena routing request arrives the routing request is placed in thequeue. The inferencing result is sent to a transporter throughoutput port out. The model returns to passive state when

ZEIGLER et al.: KNOWLEDGE-BASED SIMULATION ENVIRONMENTpassivet0IinferenceIFig. 17. State transition diagram of transporter router model.inferencing is done and the queue is empty (if

IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS-PART A SYSTEMS AND HUMANS, VOL.26, NO.1, JANUARY 1996 81 A Knowledge-Based Simulation Environment for Hierarchical Flexible Manufacturing Bernard P. Zeigler, Fellow, ZEEE, Tae H. Cho, and Jer:zy W. Rozenblit, Member, IEEE Abstract