Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Knowledge based dynamic restructuring of flexible production systems Gu, Jianhua 1994

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata


831-ubc_1994-0438.pdf [ 2.72MB ]
JSON: 831-1.0080854.json
JSON-LD: 831-1.0080854-ld.json
RDF/XML (Pretty): 831-1.0080854-rdf.xml
RDF/JSON: 831-1.0080854-rdf.json
Turtle: 831-1.0080854-turtle.txt
N-Triples: 831-1.0080854-rdf-ntriples.txt
Original Record: 831-1.0080854-source.json
Full Text

Full Text

KNOWLEDGE BASED DYNAMIC RESTRUCTURING OFFLEXIBLE PRODUCTION SYSTEMSByJianhua CuB.A.Sc. (Electrical Engineering) Tsinghua University, China, 1985M.Sc. (Electrical Engineering) Chongqing University, China, 1988A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF APPLIED SCIENCEinTHE FACULTY OF GRADUATE STUDIESDEPARTMENT OF MECHANICAL ENGINEERINGWe accept this thesis as conformingto the required standardTHE UNIVERSITY OF BRITISH COLUMBIASeptember, 1994© Jianhua Cu, 1994In presenting this thesis in partial fulfilment of the requirements for an advanceddegree at the University of British Columbia, I agree that the Library shall make itfreely available for reference and study. I further agree that permission for extensivecopying of this thesis for scholarly purposes may be granted by the head of mydepartment or by his or her representatives. It is understood that copying orpublication of this thesis for financial gain shall not be allowed without my writtenpermission.Department of Mh644The University of British ColumbiaVancouver, CanadaDate cctcbr 7DE-6 (2/88)AbstractThis thesis addresses high level automation in flexible production systems (FPS). Ina flexible production system, for example in a dedicated FPS for fish processing, theprocess components are typically organized as distinct workcells where each workcell isresponsible for a special class of production activity. Changes in production demand,variation in raw material supply, and malfunction or failure of workcell components canchange the workload on some components in the workcell. A technique that is termeddynamic restructuring, which enables an FPS to change its configuration automaticallyto suit new situations, thereby achieving a near-optimal load distribution among systemcomponents is developed in the thesis.Characteristics of the restructuring problem are known to be fuzzy (both restructuring goal and FPS status), complex, and non-analytic. A knowledge-based method isemployed for solving this problem rather than the conventional mathematical methods.Different types of knowledge sources are organized in a three-level hierarchy of decisionmaking:• The first (highest) level determines whether there should be a restructuring operation according to the current FPS status.• The second level determines a restructuring method, in which, due to the fuzzinessof the restructuring goal, general heuristics are used.• The third level selects an optimal action based on the current situation, employingfuzzy logic to handle system uncertainty.11Various approaches of knowledge representation and reasoning are used, as appropriate in different levels of the hierarchy. A blackboard architecture is implementedto coordinate associated knowledge sources, which makes the entire system easily expandable. Heuristics are organized in the order of their priorities, in the planning ofrestructuring actions. Techniques of fuzzy associative memory are developed to evaluatea set of possible restructuring actions from which a decision maker could pick an optimalone. Therefore, the system is intelligent in the sense that the decision maker alwaysselects a proper action based on the current system status.The FPS restructuring system is implemented in Prolog. The approach is appliedto an automated fish processing plant, in computer simulation. Several special casesare studied through simulation experiments, to demonstrate the practical use of theapproach.111Table of ContentsAbstract iiTable of Contents ivList of Figures viiiAcknowledgment x1 Introduction to System Restructuring 11.1 Demand for High-Level Automation . 11.2 Structure of a Hierarchical Automation System . 51.3 Feasibility of FPS Restructuring . 81.4 Characteristics of Dynamic Restructuring 101.5 Implementation of Dynamic Restructuring Using Machine Intelligence . 121.6 Objectives of the Research 151.7 Summary 162 A Theoretical Framework for Restructuring 172.1 Flexible Production Systems . 172.1.1 FPS Configuration and Layout . . . 172.1.2 Workcell Activity Level 192.1.3 Component Capacity . 192.1.4 Component Workload Status . 212.2 Formulation of Restructuring Problem . . . 22iv2.2.1 Performance Index. 222.2.2 Restructuring Requirements for Knowledge Based System . . 232.3 Literature Review on Background Material 242.3.1 Dynamic Restructuring 242.3.2 Knowledge-Based Design of Flexible Systems 252.4 Restructuring as Planning 302.4.1 State Space Method 312.4.2 Action Calculus 332.5 Knowledge-Based Restructuring 352.5.1 Workload Sharing 362.5.2 Component Releasing 392.6 Summary 413 Problem Solving Architecture 433.1 Knowledge Organization 433.1.1 Organization of Knowledge in a Hierarchy 443.1.2 Organization of Different Types of Knowledge Sources 463.2 Blackboard Model 473.2.1 Blackboard System History 473.2.2 Blackboard System Structure 483.2.3 Characteristics of a Blackboard 503.3 Problem Formulation in a Blackboard Architecture 523.3.1 Knowledge Sources 533.3.2 Blackboard 583.3.3 Control Unit 623.4 Functions of Knowledge Sources 64v3.5 Summary4 Heuristics and Actions4.1 Analysis of Restructuring Procedure4.1.1 Planning Using Blackboard4.1.2 Heuristics for Search4.2 Heuristics for Problem Solving4.2.1 Heuristics4.2.2 Usage of Heuristics4.3 Actions4.4 Summary675 Fuzzy Decision Making5.1 Conflict Resolution5.2 A Fuzzy Decision-Making Structure . .5.3 Representation of Situation5.3.1 Fuzzy Representation of Component5.3.2 Compound Propositions5.4 Knowledge Representation and Reasoning5.4.1 Rule Belief5.4.2 Reasoning5.5 Summary84848688889197981011066 Implementation and Case Study6.1 A Fish Processing System6.2 Implementation and Operation of the Restructuring System6.2.1 Rule Bases686868707172788083Status107107109109vi6.2.2 Separation of Knowledge from Reasoning Procedure 1116.2.3 Panorama of Restructuring 1116.3 Restructuring Due to Change of Demand 1126.4 Restructuring Due to Change of Sharing Feasibility 1186.5 Summary 1217 Conclusions and Future Work 1227.1 Conclusions 1227.2 Main Contributions 1237.3 Future Work 124Bibliography 126A Logic Programming 130A.1 Horn Clauses 130A.2 Syntax of Prolog 131A.3 Resolution and Unification 131A.4 Prolog for AT Programming 132A.5 Non-logic Features 133B Intended Interpretation of Prolog Predicates 134viiList of Figures1.1 A Multiple Cell Production System and Its Dynamic Reconfiguration: (a) (b)3451318262732373840455052606566Before Reconfiguration; (b) After Reconfiguration.1.2 The Component Sharing Modes: (a) Run-Time ComponentStatic Sharing1.3 The Hierarchy of an FPS Control System1.4 Semantics and Syntax in Machine IntelligenceA Flexible Production SystemAn Integrated System for Mechanical DesignA Reconfiguration and Scheduling System for an FMCThe State-Space Representation of PlanningThe Rulebase of Component Matching for Load SharingThe Fuzzy Associative Memory2.7 The Rulebase of Component Matching for Component ReleasingThe Hierarchy for Organization of the Restructuring KnowledgeA Model of a Blackboard SystemThe Blackboard Structure of the Restructuring SystemA Sub-Blackboard Representing Component CapacityAn Intelligent Sensing SystemThe Membership Functions for Fuzzy Descriptors of Overload (a)Undercapacity (b) of Componentandviii4.1 The Blackboard-Based Planning . . . 694.2 The Heuristic Search and Optimization . . . . 714.3 The Reasoning Sequence 795.1 Schematic Representation of Fuzzy Decision Making . 865.2 The Membership Functions of Component Status . . 895.3 Computation of the Validity Degree of Actions . . . . 1036.1 A Model of a Flexible Production System (FPS) . . 1086.2 A Case Study: the Simulation of a Demand Change 1146.3 A Case Study: the Simulation of a Change of Sharing Feasibility 120B.1 The Representation of Membership Functions . . . . 138ixAcknowledgmentI would like to take this opportunity to express my deep gratitude to my supervisor Dr.Clarence de Silva for his encouragement, support, and delightful guidance throughoutthe entire course of my M.A.Sc. program.My acknowledgment should also go to my colleagues in the Industrial AutomationLaboratory for their help, discussion and comments on my research project.The financial support by grants to Dr. C.W. de Silva from the Advanced SystemsInstitute of B.C., and from the Natural Sciences and Engineering Research Council ofCanada is highly appreciated.xChapter 1Introduction to System RestructuringThis chapter introduces the work that is described in the thesis. It addresses the conceptof dynamic restructuring of flexible production systems, and the background informationthat is needed to study this concept. The characteristics of system restructuring isdiscussed. Based on this backdrop, machine intelligence is considered for the problemsolving, along with appropriate control techniques, and fuzzy logic is proposed here todeal with complexity, uncertainty and the non-analytic nature of the problem.Section 1.1 starts with a discussion of the demand for high level automation in flexibleproduction systems; Section 1.2 describes a hierarchical structure that is suitable formonitoring and control of an automated system; Section 1.3 studies the feasibility ofdynamic restructuring in flexible production systems (FPS); and Section 1.4 discussessome important characteristics of the restructuring problem in an FPS. According tothese characteristics, an approach is proposed in Section 1.5 for solving the restructuringproblem. Section 1.6 outlines the objectives of the thesis. Finally, Section 1.7 givesconcluding remarks for this chapter, which will include a brief overview of the entirethesis.1.1 Demand for High-Level AutomationDue to the market competition, modern production systems are developed focusing onthe two objectives: flexibility and minimum inventory, especially minimum intermediateinventory [43, 45]. Efficient management and high level control are required for achieving1Chapter 1. Introduction to System Restructuring 2these objectives.Fluctuating supply and demand levels and the popularity of small-batch productioncall for high-level flexibility and adaptability in a production system. Systems with thesecharacteristics can better cope with increasing quality and throughput rate demands ofthe market. To respond to this challenge, highly automated systems have to be developed. Such systems should be intelligent with the ability to adapt quickly to differentproduction operations autonomously and self-organize their structure to make them operate efficiently and cost-effectively [10].In a conventional production system [45, 43, 29], workcells are linked into a fixedarchitecture. Workload of components in a workcell changes correspondingly only inresponse to the processing demand on the workcell, which may fluctuate due to marketfactors. Some components in a particular workcell may work at a fraction of their fullcapacity, while similar components in another workcell are overloaded. In order to achieveefficient and optimal operation of the overall system, the workloads of the same type ofcomponents should be redistributed. This “balanced” operation may be realized bymeans of restructuring the workcell configurations. In order to achieve this, the workcellboundaries should be flexible and the overall system structure variable, resulting in adynamic structure control system [10] (see Figure 1.1).In Figure 1.1, suppose that the production demand for warkcell is increased, whichwould make some components in the workcell overloaded. Meanwhile, suppose that thereexists a surplus in the component capacity in warkcell; for example, components A, Bin warkcell, which are of the same types as the overloaded ones in the workcell1,operatebelow their full capacities. Therefore, component B may be reassigned to warkcell, so asto fill its processing capacity requirement. Note that the original workload of componentB may be transferred to other components of the same type in workcell before assigningB to workcell, which is known as component releasing. Component A shows anotherChapter 1. Introduction to System Restructuring 3(a)Dynamic SharingControlLocal NetworkBCell i Cell]AComponentDynamic SharingControlLocal NetworkBCelli Cell]DynamicSharingFigure 1.1: A Multiple Cell Production System and Its Dynamic Reconfiguration: (a)Before Reconfiguration; (b) After Reconfiguration.Chapter 1. Introduction to System Restructuring 4operation mode. It is shared between the two workcells. In this latter case, the workcellsshould be scheduled cooperatively for sharing the components.It is important to mention how the shared components work. They could be scheduledin different operation modes as illustrated in Figure 1.2. Here, case (a) is considered asComponent Aworking forworkcell Itime(a)Component Aworking forworkcell IComponent A timeworking forworkcellj —(b)Figure 1.2: The Component Sharing Modes: (a) Run-Time Component Sharing (b)Static Sharingthat where A works for both workcell1 and workcell1,which is somewhat analogousto time sharing of a computer CPU for multiple processes, resulting in slow processingspeed, but without extra intermediate inventory. It should be noted that, the processingspeed (fast or slow) or workcell activity level (high or low) are of significance. In case(b), component A works for a workcell for a considerable long time, and then shiftsfor another workcell, and then returns to the first workcell, and so on. In the secondcase, there would be significant extra inventory, provided that the processes of the twoworkcells are related and are constituents of a complete production activity, which is theusual case in production. This extra inventory will degrade the system performance.Consequently, dynamic sharing of a component, which requires switching of components in order for them to work for more than one workcell in runtime, as shown in caseChapter 1. Introduction to System Restructuring 5(a) discussed above, for example, is required in order to achieve system flexibility andzero/minimum inventory.1.2 Structure of a Hierarchical Automation SystemFor better understanding of dynamic restructuring from the point of view of informationexchange and control, the system in Figure 1.1 can be organized into a control hierarchyas schematically illustrated in Figure 1.3.High-LevelKnowledge Feedback Flexible ProductionSystem ControllerWorkcell-LevelInformation tothe FPSI____ __Workcell LevelControllers LevIComponent-LevelSensorySlgnats4’l( I.Figure 1.3: The Hierarchy of an FPS Control SystemProductionDemandsIntelligentSensor Fusion1FPSLevelInformationPreprocessorComponentLevelComponent LevelSensingGroup: 1Component Levelcj j Controllers I.i- Group: 1 EnvironmentI IThe top level FPS controller plays the important role of management of the entireChapter 1. Introduction to System Restructuring 6system. It responds to the changes of task demands and the feedback information; makesdecisions on FPS reconfiguration; and commands the low-level controllers to employproper components in carrying out the required taks. The task demands considered hereare assumed independent and assigned to individual workcells, which may actually bepart of a complete production task. For example, product grading and packaging maybe considered independent for separate workcells, but they may be (usually are) part ofa complete production activity, as an example, fish processing, which may include fishhead cutting, grading, and packaging. Task demand management, which is to decidetask demands for individual workcells according to the overall production requirements,is not included in this system. However, it is important to note that the tasks assigned todifferent workcells are related, and for achieving zero intermediate inventory, the workcellsshould operate at a desired processing speed. The major objective of an FPS controlleris to realize the desired processing rates under the condition of current available facilityresources. In particular, if the workload of the overall system is not properly assignedto its components, say, some are overloaded, while some of same type possess significantcapacity surplus, the system should be restructured so as to achieve uniform or balanceoperation, which will result in increased system performance and reduced operating cost.A workcell controller is the executor of an assigned task. It performs the giventask in a desired rate using designated components under control of the FPS controller,and may include some components in a sharing mode. Components are scheduled andcontrolled according to the task type and processing rate. Task planning is discussedin Vollmann (1992) [45]. In particular, the shared components should be scheduledin coordination with other workcells. In dedicated production systems, a fish processingplant, for example, task planning is standardized, and the component workloads will varyalmost proportionally with the task demand, which may be represented by a processingrate. Of course, for different tasks, component load factors, (workload/unit-task), mayChapter 1. Introduction to System Restructuring 7be different. For example, suppose a vision system is required for fish head cutting, andthe load factor is O.4s/unit-cutting. As a result, for a unit cutting (1 unit-cutting/sec),a standard’ vision system should work O.4s. If the same vision system is used for fishgrading, the load factor may be lower, say, O.25s/unit-grading.Components physically belong to workcells, but are logically grouped by their functions, and assigned to groups. Components in the same group are assumed to be interchangeable and shareable (The feasibility aspect will be considered in the next section).Even human workers could be grouped into one or more groups when they are consideredas part of a workcell in this manner. A component controller responds to commands fromthe workcell level. For example, an image processing system will execute a particular jobas required, for example, to measure the gill position of a fish or to analyze the firmnessof an object such as herring roe.The low-level sensory signals are fed back to component controllers as well as workcellcontrollers for closed loop control. The component signals, together with reports fromthe workcell controllers, are pre-processed by an intelligent sensing system, which willgenerate information for the FPS, and will provide knowledge to the FPS controller in aproper form, as fuzzy sets, for example.The information between the production system and outside world takes two forms:updating of the task demands, and interactions between components and their enviroment, for example in material handling and processing. Both types of information maytrigger the system for restructuring. The change of task demands, which results in thechange of component workloads, is a direct trigger for restructuring. Also an FPS maycall for a restructuring action during processing, when some components are damagedor partially damaged and have a degraded performance. Such a damage may cause areduction of the component capacity, may reduce the speed of communication, and can1This concept is used for component capacity measurement, which will be discussed in Chapter 2.Chapter 1. Introduction to System Restructuring 8bring about other undesireable effects.This thesis will be centered around the restructuring controller of a flexible productionsystem (FPS), which will be designed to make decisions based on task demands and FPSinformation, to assign proper components to a given production activity.1.3 Feasibility of FPS RestructuringThree points are presented here to support the concept of system restructuring. Firstly,well developed low level automation provides the possibility of dynamic restructuring of asystem. Especially, programmability and the availability of sophisticated component levelcontrollers that have the necessary flexibility make some components easily be shiftableto other jobs. Then, it will be possible for a component to shift. from one task to another,or work in a sharing mode.As an example, an image processing system can function differently using differentprogram modules. It may calculate the mean brightness to measure temperature froman infrared image; firmness from an ultrasonic image, and colors from the separate Red-Green-Blue (RGB) channels of a color image. It may also recognize and “measure” theposition and shape of an object. In fish processing industry, such functions are needed inmany different workcells, with different processing time requirements. Therefore, someimage systems, if they operate below full capacity, could be used for more than oneworkcell to save operating costs.Secondly, local network communication should be highly developed, which can effectively support the high-level hierarchical control; provide information feedback; andenable cooperation of shared components. For example, it is well known that automaticguided vehicles (AGV) usually operate in a completely sharing mode.Thirdly, one should take into consideration that some types of components in workingChapter 1. Introduction to System Restructuring 9site are actually mobile. Human beings, when considered as components in workcells,can walk from one site to another. Mobile robots [19] also fall into this category. In thiscase, travelling time of a component may be included as a part of the working time inscheduling. The shifting frequency, therefore, needs to be optimized by considering theratio of working time and travelling time. However, this is not a major topic here. Somerobots (or human beings) can perform work, such as loading and unloading, in a sharingmode. To generalize the feasibility representation in dynamic restructuring, the conceptof feasibility index is introduced. Two situations can be considered:• Load sharing. In this case, a load is shared by more than one component of asame type. The feasibility index of load sharing is determined by the type of loadand attributes of the sharing pair of components. Also, some geographical factors,such as FPS layout, and network communication capacity should be considered aswell. A system expert may recommend a value or an algorithm to calculate thefeasibility index. This feasibility index is taken into account when an overload is tobe shared by another component, the load sharing feasibility should be consideredbetween the pair of components, one of which is overloaded and the other is atbelow capacity.• Component sharing. Here, a component is assigned to more than one load.The component may work for several workcells which carry out different tasks.The feasibility index of component sharing is slightly different from that of loadsharing. The former case happens when a component is to be released from thesystem, its workload should be transferred to another component of the same type.The second component is therefore in a mode of component sharing: it works formore than one job. In this case, the feasibility index of component sharing isprimarily determined by the component itself, rather than a pair of components.Chapter 1. Introduction to System Restructuring 10In both the cases, a basic property of components which is associated with the capability of sharing determines the feasibility index. In this research, it is defined as“component shareability”. The shareability index of a component is considered as thecapability of this component to share loads, the basic factors that affect the index beingthe capability of communication, its mobility, etc, of the component. The index takesa real number in the interval [0, 1], and is usually assigned by a system expert. Thisnumber indicates the degree of shareability of a component; in particular, “1” means thecomponent is completely shareable, and “0” means the component is not shareable at all.This, then, together with geographical layout and task type, will be used for evaluatingcomponent sharing. The feasibility of load sharing, which involves pairs of components,also takes into consideration such factors as geographic layout and repair state of thecomponents.1.4 Characteristics of Dynamic RestructuringTo develop an approach for solving the present problem, it is helpful to understand thecharacteristics of the problem. From the point of view of control, the task and theperformance requirements of an FPS controller are greatly different from that of a low-level control system [21]. It has the common characteristics of a high-level control systemas well as its own specific features.Generally, a high-level control system is different from a low level control system inthe following aspects [7, 8, 11, 40].• Control bandwidth and dynamic response.The control cycle of high-level restructuring is sufficiently long that the system maybe considered to be in a steady state (normal operation) most of the time. Thesteady state, therefore, is the most important consideration. What we optimize isChapter 1. Introduction to System Restructuring 11the FPS operation rather than the dynamic response during the transient stage ofperforming a restructuring operation.• Intelligence and accuracy.In general, required intelligence is high and the associated precision may be lowfor decision making in a high-level system. The restructuring system should bedesigned to make intelligent decisions and to deal with uncertainty of informationand knowledge.What should be particularly stated with regards to a dynamic restructuring controllerare the following features:• The fuzziness of the performance requirement itself (fuzzy goal).This feature makes the goal of the control system fuzzy, resulting in the possibilityof multiple solutions. The general requirement of restructuring is to make an FPSoperate uniformly with respect to the load distribution among components, andalso to make the workcell components work close to their full, design capacity. Anexample is given now to indicate how fuzziness may enter into the decision makingprocess of system restructuring. Suppose two components A and B are identicaland shareable. In one case, component A works at 50% of its full capacity and,component B works at 90% of its full capacity. In another case, component Aworks at 70%, and component B works at 70% as well, in which 20% workload ofB is shared by A. It is difficult to precisely determine which case is better, andfuzziness may enter the decision making process.• The non-analytic nature of the restructuring problem.It is the fuzziness of a restructuring goal that leads to this second feature of theproblem. In the absence of fuzziness, if there exists an analytic cost function, forChapter 1. Introduction to System Restructuring 12instance, a linear programming method could be used for solving the associatedproblem. Such a method, like an optimal control design, is actually driven by arequirement of control performance. Usually, the algorithm can be deduced fromthe cost function and system constraints, such as a mathematical model. In arestructuring problem, both the control performance and the constraints may befuzzy, and the problem is generally non-analytic. Therefore past experience wouldbe very valuable to solving the associated problem. Heuristics are very helpful inthe design of control actions, which may indirectly respond to the restructuringrequirements. The conventional, performance-index-oriented design is no longersuitable here. Instead, a data-driven method incorporating heuristics may apply.The complexity of knowledge sources needed for problem solving.As a consequence of the feature mentioned above, dexterious knowledge wouldbe required to support the decision making in selecting a proper restructuringaction. This feature needs an open structure, in order to cope with different kindsof knowledge sources.1.5 Implementation of Dynamic Restructuring Using Machine IntelligenceFor the characteristics that have been discussed in the previous section, it is clear that, toimplement dynamic restructuring technology in an automated process, human expertiseand past experience would be extremely useful. Specifically, a knowledge-based systemis desirable for problem solving. Therefore, in system design and implementation, onehas to primarily consider formulation of the restructuring problem, represention of theproblem solving knowledge, and the design of reasoning strategies [31].Problem formulation is the first step toward machine intelligence [32]. Here, theproblem should be represented in a form that would enable a computer to “understand”Chapter 1. Introduction to System Restructuring 13it. Human beings can understand a language through semantics, but a computer cannot.Computers recognize syntax. Everything must be represented in a certain form whichis recognizable to a computer. One such form of representation is propositional calculus[2], in particular, the first order predicate calculus. For example, father(tom, david)is a predicate which means that “torn is david’s father”. This is understood throughthe semantics of the word father to a human being. A computer simply recognizes thesymbol father, regardless of the meaning it holds. This is illustrated in Figure 1.4.andFigure 1.4: Semantics and Syntax in Machine IntelligenceSuppose that the factsfather (torn , david)father(david, catherine),InputComputerSematicsUnderstood by Sematicsoutputand a definition:Chapter 1. Introduction to System Restructuring 14grandfather(X, Y) — father(X, Z), father(Z, Y),are given. Then if the query “who is catherine’s grandfather” is made, its logic consequence will begrandfather(tom, catherine).The predicate grandfather could be understood by human beings since it has an accepted meaning, but it is only a symbol to a computer which only recognizes the relationdefinition of grandfather and father.A simple logic programming language dealing with operation of the first order predicates, which is to be used throughout the thesis, is explained in Appendix A.Knowledge representation and reasoning are the core in system design and realization.Due to the complexity of the system, the problem solving knowledge is organized intoa hierarchy. The programmatic knowledge and detailed knowledge are considered indifferent level, so as to implement hierarchical decision making. The agent then couldnot be tangled into unnecessary detail at first.Some important conditions have to be satisfied in system design. They are usuallymet, but are explicitly discussed here to avoid confusion, with respect to subsequentdesign procedures.• Full knowledge of actions that change the FPS is known. This will provide thepossibility of planning the next step restructuring action, since each decision makingshould be made based on the current situation. In this manner, an agent will beable to completely predict the effects of an action.• The agent has complete knowledge about the FPS. All the related and necessaryinformation should be given to the system. This includes the assumable and askableknowledge, which, by indicating as askable, the agent may ask the user to provide.Chapter 1. Introduction to System Restructuring 15Therefore, “negation as failure” could be applied to the restructuring system. Forexample, if there is no information about a component, it is assumed to be nonexistent.1.6 Objectives of the ResearchDynamic restructuring is a new research area, with many aspects to be studied, fromcomponent sensing to final system integration. It is not possible to cover all the topicsin this thesis. The major objectives of the research are as follows:• To study and develop a methodology of dynamic restructuring of a flexible production system;• To formulate and represent the restructuring problem and associated knowledge,and to obtain and abstract restructuring heuristics and rules on the basis of a fuzzymeasure of FPS performance;• To develop an architecture and reasoning strategies for problem solving;• To design a fuzzy decision making procedure for the optimization problem associated with selecting proper actions in restructuring;• To design and implement a simulation system for further research on this area, andto use it for the simulation of a realistic FPS.Although many other related topics are mentioned and briefly discussed in the thesisfor the sake of completeness of the design procedure, and also for providing a somewhatcomplete view of solving the problem, they are not considered major objectives of theresearch.Chapter 1. Introduction to System Restructuring 161.7 SummaryThis chapter introduced the problem of dynamic restructuring of an FPS; and discussedthe role it plays in a high level FPS automation system. The dynamic restructuring technology is actually developed to meet the needs of system flexibility, minimum inventory,and cost-effective operation.Modularity, multitude working modes and mobility of components, together with thehighly developed local-network communication techniques, provide the feasibility of FPSrestructuring in a practical setting.Restructuring problem is generally characterized as fuzzy, complex, non-analytic andheuristic-oriented. These features require the use of knowledge-based techniques andmachine intelligence.The remainder of the thesis is arranged as follows: Chapter 2 gives a theoretic framework for the problem solving method. Chapters 3 develops a blackboard architecturefor the restructuring problem, giving particular attention to the knowledge representation and processing frameworks. Chapter 4 investigates the heuritics associated withthe problem. In Chapter 5, the use of fuzzy logic is treated as a suitable approach intaking into account the incompleteness and non-analytic nature of the knowledge andassociated decision making. Chapter 6 discusses some implementation problems of theapproach and gives simulations of the application of the technique to an automatedfish processing plant. Chapter 7 provides some concluding remarks on the research andproposes possible future work.Chapter 2A Theoretical Framework for RestructuringIn Chapter 1, the dynamic restructuring problem for a flexible production system (FPS)is proposed as a reorganizing system that will enable near-optimal or uniform operation ofthe FPS. This chapter will formulate the associated problem and discuss the methodologyto achieve the goal.Section 2.1 introduces the representation of system configuration; and the attributesof workcells and components. Section 2.2 formulates the restructuring problem. Thena short literature review is given in Section 2.3. Section 2.4 discusses the possibility ofinterpreting the problem of restructuring as conventional planning. Section 2.5 presentsa method of knowledge based restructuring, which includes both load sharing and component releasing. Section 2.6 concludes the chapter.2.1 Flexible Production SystemsFrom the point of view of restructuring (see Figure 1.3), a flexible production system(FPS) can be organized in a hierarchy that includes a system level, a workcell level anda component level. Attributes related to restructuring in each level are discussed andrepresented in this section.2.1.1 FPS Configuration and LayoutConsider the multiple-workcell FPS that is schematically shown in Figure 2.1. The ithworkcell is denoted by W1 and its jth component is denoted by c. For simplicity of17Chapter 2. A Theoretical Framework for Restructuring 18notation the subscript and superscript of this component notation is dropped in thesequel, except when they are explicitly needed.Figure 2.1: A Flexible Production SystemTwo attributes should be noted in the system level of an FPS: workcell configurationand layout. Configuration of workcell W can be expressed byCON = {cw} (2.1)Suppose that the task demand of a particular workcell is Dw. The corresponding work-loads L of the individual components of this workcell may be determined using a standardtask planning procedure, as expressed by the relationship= L(Dw) (2.2)Note that, if a component is shared between two workcells, whose status is denoted byc’T4T, then the component is considered as a component in both workcells W and 14,.PlantLocal AreaNetwork(High Speed)..C(g,Cc,L,Ac)Chapter 2. A Theoretical Framework for Restructuring 19Geographic location of a workcell is also an important factor that affects restructuring. Usually, restructuring system favours in establishing component sharing betweenworkcells that are conveniently located with respect to each other. Two coordinates forthe position of workcell W on the workshop floor are denoted by Xw and Yw.2.1.2 Workcell Activity LevelSuppose that the processing capacity of a workcell component c is C. Also, at a giveninstant, suppose that the production level of a workcell is Pw and the activity level ofcomponent c of this workcell is A. Then the following relations will hold:If LC<C VcEWthen A (2.3)If c W such that L> Cthen AC<LCand Pw <Dw (2.4)Here, W denotes the set of components in a particular workcell.2.1.3 Component CapacityThe processing capacity of the components is the resource of the system that will berearranged in restructuring in the FPS. Since components could be shared for carryingout different tasks, capacities of the components of the same type should be standardizedso as to make the load transfer conveniently comparable. Using this standard componentrepresentation, load planning in equation (2.2) can be represented by referring to thestandard component. As an example, a linear representation for load planning or capacityChapter 2. A Theoretical Framework for Restructuring 20requirement planning is illustrated as below:Consider the calculation of the capacity requirement for image processing in a cuttingworkcell of a fish processing system. The workcell may consist of vision workstations,robots and automated guided vehicles (AGV), in addition to other necessary equipment.Given the cutting demand as x units/sec, in which the unit may be a processed item offish; and the standard capacity requirements for processing a unit task, which are calledplanning factors, as follows:standard vision: v sec/unit,standard robot: r sec/unit,standard AGV: a sec/unit,we can calculate the capacity needed for the cutting process as:standard vision: vx x 100%,standard robot: rx x 100%,standard AGV: ax x 100%.For instance, if the speed of vision processing for a cutting task is 0.3 sec/unit, andthe processing rate demanded for cutting is 2 units/sec, then the vision capacity needed(i.e. the load) is 60% of full capacity of a standard vision facility, say an IBMp0TM basedvision system with a SHARP GPB3TM image processing board. Different vision systemsmay be expressed as a percentage referred to the IBM PCTM system as the baseline unit.A SunSPARCTM station based vision system with Datacube MaxVideo 20TM imageprocessing system (which requires a host computer with VME Bus), could be faster,and may be assigned a capacity factor 2, with respect to the baseline unit (IBMTM pcbased). Then the above vision requirement applied to a SunSPARCTM station basedsystem corresponds to a load of 60%/2, or 30%, a significantly low percentage of itsfull capacity. In other words since the capacity of the more powerful vision system isChapter 2. A Theoretical Framework for Restructuring 21double that of the baseline system, the load is halved for the same task, which should beintuitively clear as well.2.1.4 Component Workload StatusNext consider a group g of “similar” components which are shareable or interchangeablewithin the group. The characteristics of a component c may be represented by the orderedset [g, C, L, At], as shown in Figure 2.1. Here C L A are the capacity, workload andactivity level of component c respectively. Suppose that, at a given instant of workcelloperation, the workcell components are monitored and some are determined to operatebelow capacity (under-capacity) while some others are overloaded. Then, the followingconditions hold:If cegandL<Cthenceg (2.5)If cEgandL>Cthenceg0 (2.6)withg A g = g and g0 A g = g0 (2.7)where gu= subgroup which contains all components that operate below capacity (under-capacity) within the component group g; g0= subgroup which contains all componentsthat are overloaded within g.Note that, in general, g, Vg0 g because for some components within g, it is possiblethat L = C = A. Also, even when L = C for a particular component, it is possiblethat A < C for that component as a result of gross reduction of the production level Fof the workcell that contains the component, due to an overload in some other componentwithin the same workcell [12].Chapter 2. A Theoretical Framework for Restructuring 222.2 Formulation of Restructuring ProblemThe restructuring problem may be formulated as one of parameter optimization. For thispurpose, a performance index has to be defined.2.2.1 Performance IndexThe optimal restructuring problem may be expressed asminimize J = J(,Q,A,J) (2.8)subject to P(A)=D(j) VwEFPS (2.9)where a is a vector of weighting parameters.For example, a quadratic cost function could be used; thusJ = c(C— A)2 (2.10)with nonsymmetric weighting parameters such thatcz=a0ifL>C (2.11)a=czifLC (2.12)= 0 if L = 0 (2.13)It should be noted that no activity (zero activity) is considered a desirable condition.In other words, rather than having, say, two undercapacity components of the same type,it is desirable to transfer the load of one component into the other and completely releasethe first component. This is advantageous for reasons such as reduction in operatingcosts and wear and tear. Furthermore, the component that is released of activity in thisChapter 2. A Theoretical Framework for Restructuring 23manner will be available for absorbing overloads from other similar components in theFPS. It is clear that, zero-activity components do not contribute to the cost functionJ, as expressed by equation (2.10). Accordingly, the optimization strategy inherentlyfavours the existence of zero-activity components.2.2.2 Restructuring Requirements for Knowledge Based SystemDue to the presence of fuzziness, as discussed in Chapter 1, the cost function given inSection 2.2.1 provides only a guideline for restructuring and a rough evaluation of the restructuring performance, but shouldn’t be considered as the entire goal of restructuring.There are still many other factors that should be considered, such as, sharing penalty,sharing feasibility, the geographical possibility of sharing, and so on. As an example,sharing within a workcell is usually considered better than sharing between workcells.Because of these reasons, in view of fuzziness of a restructuring goal, heuristics fromexperienced operators could be considered as well in order to complete the requirementsfor modeling a restructuring problem. This may provide an easy way to design restructuring strategies using past experience. In this context, some requirements that have tobe satisfied by a restructuring procedure may be stated.These requirements are itemized below:1. Overloads are not allowed. The load limitation of a component is its full (design)capacity. A main purpose of a restructuring controller may be considered as theelimination (or reduction) of overloads.2. Reduce the operating cost of an FPS by releasing components which are greatlyunder their full capacity. (For employees, hiring and firing may be considered inthis context). The judgement associated with problem is fuzzy in general. ThereChapter 2. A Theoretical Framework for Restructuring 24might not exist a crisp standard to judge whether a component should be released.Therefore, fuzzy decision making will be needed here.3. Maintain the number of sharings (both load sharing and component sharing) aslow as possible, for the system reliability may weaken with increased activity ofsharing.4. Selection of components for sharing or releasing cannot be done arbitrarily. Someevaluation should be made in choosing an action for sharing or releasing.5. Use any available past knowledge and experience, which may be helpful in improving the knowledge base.Thus, restructuring of components in a multiple-workcell FPS should not be carriedout using purely analytical optimization criteria alone. Certain factors or conditionsmay favour some structures while objecting to some others. The factors that determinethe desirability of a particular structure of component sharing may be based on non-analytical criteria such as what has been mentioned above. Under such conditions, aknowledge-based approach to making the restructuring decisions would be desirable.2.3 Literature Review on Background MaterialIn this section, we will present a literature survey of the background work of the presentresearch.2.3.1 Dynamic RestructuringDynamic restructuring of flexible production system originated in the work of de Silva(1992) [8]. It was proposed as an important concept of soft automation [9]. A frameworkfor the problem solving is presented in de Silva (1993b) [10]. Knowledge based system isChapter 2. A Theoretical Framework for Restructuring 25developed in Cu an de Silva (1994a, b, c) [20, 21, 22] and in de Silva and Cu (1994) [12].The problem solving architecture was established in Gu and de Silva (1994a) [20] andthe heuristics and conflict resolution method are developed in Cu and de Silva (1994b, c)[21, 22]. An analytical framework is presented and a new evaluation method for actions,using priority fuzzy sets, was introduced in de Silva and Gu (1994) [12]. Also, in thatpaper, the concept of restructuring-feasibility index was formalized and utilized for theoptimization of restructuring.2.3.2 Knowledge-Based Design of Flexible SystemsThere are three major areas of research related to this work: 1. Integrated system design;2. Decision support systems; 3. Expert control systems. Pertinent work in these threeareas is outlined in this section.Computer Integrated TechnologyThe main research activities in production automation are concentrated in integratedmechanical design; planning and scheduling of flexible production systems; and decisionsupport systems for plant design.Leong et al. (1991) [30] described an integrated knowledge-based system for mechanical design using a blackboard architecture. In solving a typical mechanical designproblem, they viewed the design process as being composed of a set of tasks that can beprogressively subdivided into a hierarchy of smaller tasks in the form of a tree structure,(see Figure 2.2). These tasks are solved by a team of specialists using a distributedproblem-solving approach.Two kinds of communication were proposed for the hierarchy; specifically, broadcasting using a blackboard, and message passing directly between two members in thesame team. In Figure 2.2, the detail mechanical design is composed of coupling design,Chapter 2. A Theoretical Framework for Restructuring 26Figure 2.2: An Integrated System for Mechanical DesignChapter 2. A Theoretical Framework for Restructuring 27shaft design, gear design, motor selection, bearing selection, etc. There are natural linksbetween these various knowledge sources. Leong et al designed a horizontal communication structure for this system, which may be necessary but makes the entire blackboardsystem not so modular and opportunistic reasoning.The planning and scheduling system for a flexible manufacturing workcell (FMC),described by Kovacs and Mezgar [29] is closer to the problem in the present research.In Kovacs (1991) [29], designed FMC configurations, layouts and schedules are put intomodules of simulation and analysis for testing. System will return to carry out reconfiguration if the design is not satisfactory. The design procedure is illustrated in Figure 2.3,in which several modules have been identified. They are described below.• Configuration moduleFigure 2.3: A Reconfiguration and Scheduling System for an FMCThe cell configuration design has two separate steps, which can be carried out byChapter 2. A Theoretical Framework for Restructuring 28iteration: the first step is to get a pre- or basic configuration which is an “average” ofseveral possible configurations, and the second step is the reconfiguration from thisaverage configuration according to the actual production tasks and manufacturingsituations.Reconfiguration may be necessary in certain situations, for example,— During normal operation, better adaptation to changing workloads can beachieved by rearrangement of system elements, or regrouping of some of them.— In the case of component failures, the operation has to be continued withoutusing the defective element, and with a minimal loss of production.— New elements can be added to the system, and old elements can be disconnected, for the purpose of system maintenance and upgrade.Flexibility in design and operation can be guaranteed under these circumstancesthrough the capability of configuration and reconfiguration.• Layout planning moduleIn this module the relative geographic positions of the manufacturing machineswithin the workcell are specified, while the useful aspects of the material-handlingsystem are taken into consideration.• Scheduling moduleOnce the configuration and the layout of the system are designed, the processingtime needed for each item that is produced will be known. Consequently, a task canbe scheduled. If the schedule is unsatisfactory, then modification to machines andtransportation procedure, layout changes and reconfiguration can be considered toChapter 2. A Theoretical Framework for Restructuring 29improve the situation. The accepted schedule is forwarded to both the simulationand the analysis modules.Another configuration example is described by lizuka and Tsuji (1988) [23]. This isan expert system for the design of a computer system configuration. It focuses on thefollowing two points: 1. Discussions on the effectiveness of Prolog for representationof the interconnections between various pieces of equipment; for representation of thesystem components; and for implementation of the functions of knowledge base retrieval,and 2. System structure which emphasizes on improved maintenance of expert system.The paper gives a good example of using Prolog to represent knowledge, especially thatof interrelationship between components, and also describes the implementation of aninferencing mechanism.Decision support systemDecision making is traditionally supported by operations research techniques. Its basic purpose is to predict future events and choose an optimal one according to someperformance index and constraints.The knowledge to support a decision, based on real-time data, must be able to provideanswers to the following questions [3]:• “What happens?”: Ability to analyse a situation and identify advantageous andproblematic aspects.• “What can happen?”: Ability to reason on the evolution of the system. It mightbe possible to identify the possible descriptive patterns of the situation in futuretimes.Chapter 2. A Theoretical Framework for Restructuring 30• “What should be done?”: Ability to reason on the control actions most convenientfor improving the system operation.Fayyad and Kass (1991) [17] described a part of the PAVE (Plant Assembly Verification Environment). PAVE is intended to support industrial engineers during the designprocess and help manage the complexity of the problems which they encounter.Expert control systemUsually a decision making system is an open loop system. Given a situation and atask, it makes a decision. In a feedback control system, the system situation is updated automatically and a control decision is made periodically. Due to system delays(inertia delay and pure delay), these decisions will interact with each other and causethe system behave as a dynamic system response. Many authors have discussed expertcontrol. Some emphasize on the representation of system situation, such as system error characteristics[48],and fuzzy representation of system error [6]. Some emphasize onsystem structure and parameter knowledge, such as self-tuning expert system [1]. Someothers emphasize on control policy, such as, robust control, wait and see control etc.[34].Information feedback is useful in any type of control system.Although dynamic restructuring is a new technique in automation, its development ismore or less related to the above mentioned areas. Its application domain is associatedwith flexible production systems; and its technology is based on knowledge engineeringwhich incorporates decision making techniques and information feedback.2.4 Restructuring as PlanningA naive method of restructuring is to represent it as a simple planning procedure [18, 38]of restructuring actions. Basically, the central activity of restructuring planning willChapter 2. A Theoretical Framework for Restructuring 31require the following:• An initial world (here the term “world” is used to denote a certain FPS situation)in which overloads may exist;• A restructuring goal (fuzzy) that typically states “There should be no componentoverloads and components should operate near their design capacity,with minimalcost and near the specified production demand“; and• A set of actions which includes establishing or terminating a load sharing processand releasing of an undercapacity component, or moving of a component from oneworkcell to another.The planning problem then is to find a sequence of actions which can transfer an initialworld into one in which the desired goal has been achieved [38]. Every action changes theworld to some extent, and eventually, by completing the entire set of actions, the systemwill reach the final world, in which no component overloads or capacity shortages wouldexist. If such a final world does not exist after all the actions have been tried, then therestructuring planning would have failed.2.4.1 State Space MethodOne popular method of representing planning knowledge is the state space representation.The concept is illustrated in Figure 2.4. In a state space, each node represents a list ofproperties of a world; in short, every node is a certain world. An arc corresponds to anaction which changes the status of a world. Each action provides a complete specificationof how to obtain the new world from the world where this action was originated; forexample,move(robotl, f’rom(canning), to(cutting)) : worldl = world2Chapter 2. A Theoretical Framework for Restructuring 32where, worldl and world2 are expressed as,worldl:world2:holds(robotl, position, canning, worldl);(other properties)holds(robotl, position, cutting, world2);(other properties)Initial worldI.World.1.i • World.1.kFigure 2.4: The State-Space Representation of PlanningThe predicate move(robotl, frorn(canning), to(cutting)) corresponds to an actionwhich moves robot 1 from the canning workcell to the cutting workcell. Assuming thatthe effect of this action is only to change the position of robotl, then the new world denoted by world2 will keep all properties of worldl except for the position of robotl. Theproperties are represented by the predicate hold(O, F, V, World) which has the intendedinterpretation that object 0 holds the property P at value V in world World.Action,1 Action.n•••Chapter 2. A Theoretical Framework for Restructuring 33Reasoning through a state space is simple. A search can be made starting from theinitial world to a final world in which desired goal is true. A plan is just the list of actionson the path that reaches the final world (desired goal).The major problem with the state space representation is that everything about theworld must be explicitly listed, which will require a long list of properties. Even moreserious, in the fact that, every effect of an action must be anticipated and explicitly listed,in this approach.Suppose that we have m groups of components which could be rearranged in an FPS,and that each group has the same number (m) components. Then the total number ofsharing or releasing pairs of components is given by n.C = n.m(m — 1)/2. The numberof graph nodes (ignoring other restructuring actions such as moving a component) isgiven by [m . m(m — 1)/2J” approximately, where d is the number of stages of action in aplan.Consider a small system with n = 3 (e.g., robot, vision unit, AGV), m = 5 (i.e., 5components in each group), and d = 10 (i.e., 10 actions in a plan), the size (in number ofnodes) of the search space for breadth first or A* search is of the order of [n.m(m_1)/2]d =(3x5x4)lo= 6 x iO’. It is therefore almost impossible to explicitly list all the situationsand effects of actions in a graph of this size.2.4.2 Action CalculusNow consider reformulating the problem in order to deal with the complexity of the statespace representation for planning. We represent the world in the form of either mit (theinitial world) or do(A, W’); which means a new world that is derived by applying theaction A on world W’. This is called action calculus.Therefore, the planning problem is to find a world W in which the desired goal issatisfied. A typical goal for the restructuring problem may be represented as,Chapter 2. A Theoretical Framework for Restructuring 347- {holds(visionl, work_load, 100%, W);(for all components),{holds(robot5, work_load, 100%, W);where all the component loads are required to be at 100% of its full capacity.Two kinds of knowledge are required in the reasoning process that achieves the goal:the specifications of the initial world and the effects of all actions on various worlds. Acomplete specification of each action will, in general, require at least one axiom or postulate for each relation of the domain (i.e., each property). There are nm componentsin the FPS, and suppose that each component has the six properties (group, position,work_for, capacity, worlcioad, shareability). Hence the total number of domain relations is 6n•m. The number of actions may be estimated as n.m(m — 1)/2. Accordingly,we will need at least 6nm . nm(m — 1)/2 axioms, because all the relations have to bestated for each action. Clearly, it is a difficult job to specify all these axioms, but it isbetter than the state space method, where it is required to specify everything (state andaction) for every world.Goal regression[38] may be employed as the reasoning procedure for system restructuring. In an actual situation, each action affects only a very small part of the world.Much of the world will remain unchanged, which means most of the axioms will just statethat the properties in the new world are the same as those of the old world [39]. In thisthesis, a blackboard-based planning method will be developed to cope with the practical problems associated with an extensive action space. It avoids the problem of largedimensionality by assuming that if a property is not changed by an action, it remainsunchanged in the new world. In this manner, we will need only to specify the effects ofChapter 2. A Theoretical Framework for Restructuring 35the actions. Heuristics play a very important role in that method.2.5 Knowledge-Based RestructuringOne may observe that the goal represented for planning the restructuring process, asgiven in the last section, is somewhat artificial. The problem is that the actual goalis fuzzy, and it cannot be represented by a crisp description of component loads, forexample, 90% of full capacity. Furthermore, expertise and past experience should beused to decide the search direction rather than employing a non-heuristic search. A morerealistic framework for knowledge-based restructuring is developed in this section.Consider a group g of shareable or interchangeable components which are associatedwith a set of workcells in a flexible production system (FPS). Each workcell in thisset has an associated set of components E g. Then the knowledge-based restructuringprocess may be expressed asg(w*(c*))=R(g)®g(w(c)) Vge FPS (2.14)Here R(g) may be interpreted as a knowledge system which evaluates the present association of components with workcells , within a group g and then modifies theseassociations appropriately so as to reduce component overloading, according to some performance criterion. The resulting new association of components within g, now with aset of modified workcells , is denoted by g(*(ç*)). Note that the flexible productionsystem is said to be restructured when the configuration of the workcells changes dueto such a modified association of components. The decision making process given byequation (2.14) has to be executed for all groups of component within the FPS.Basically, the changes in the association of components constitute two types of actions: A component joining a workcell, or a component leaving a workcell, which will bediscussed in detail in the remainder of this section.Chapter 2. A Theoretical Framework for Restructuring 362.5.1 Workload SharingAgain, consider a group of shareable or interchangeable component g with m overloadedcomponents represented by the subgroup g0 and r undercapacity components representedby the subgroup g.In knowledge based restructuring, each overloaded component (OC) has to be matchedwith an appropriate undercapacity component (UC) for load sharing. This may be accomplished using the rulebase given in Figure 2.5. Note that a rule represented here hasthe format:IF situation THEN action WITH bfThe situation is the current status (or context) of the components, which could berepresented by a fuzzy descriptor. Therefore, the context of situation could be representedin a Cartesian product space with dimensions equal in number to the context levels ofcomponents. The action is a crisp action set, where each composed proposition in thesituation context may lead to one or more actions. Each implication from a situation toan action is assigned a belief value bf, which is a representation of the corresponding tohuman confidence on the particular rule.A rulebase is a mapping from a situation space S to an action space A.(2.15)In particular, R(a) represents a sub-rulebase of R associated to a specific action a.Consider the rule base given in Figure 2.5 for component matching with the objectiveof load sharing. The states that a component may take are given by the set {no activity,undercapacity, balanced, overloaded}. Even though, the condition of “no activity” (na)may be treated as a special case of “highly undercapacity” (hu), it is desirable to definea separate state for this condition, for example, as in the rulebase given in Figure 2.5, forChapter 2. A Theoretical Framework for Restructuring 37reasons that should be clear later, in the context of component releasing. In particular,the state of na is far more desirable than that of hu. A balanced state is said to existin a component when its activity is equal to its capacity (i.e., A = Ce). This is theoptimal state of component operation. The membership functions of the fuzzy resolutionlevels for the two context variables OC and UC should be known in using fuzzy logic torepresent and process [7] the knowledge base given in Figure 2.5.Context LevelsOverloaded Component Undercapacity ComponentOC UCNo activity naHighly overloaded ho Highly undercapacity huModerately overloaded mo Moderately undercapacity muLightly overloaded lo Lightly undercapacity luIf OC is ho and UC is na then sharing(OC, UC) with bf 1.0.If OC is ho and UC is hu then sharing(OC, UC) with bf = 1.0.If OC is ho and UC is mu then sharing(OC, TiC) with bf = 0.8.If OC is ho and UC is lu then sharing(OC, UC) with bf = 0.6.If OC is mo and UC is na then sharing(OC, UC) with bf = 0.8.If OC is mo and UC is hu then sharing(OC, UC) with bf = 0.8.If OC is mo and UC is mu then sharing(OC, UC) with bf = 0.6.If OC is mo and UC is lu then sharing(OC, UC) with bf = 0.6.If OC is lo and UC is na then sharing(OC, UC) with bf = 0.4.If OC is lo and UC is hu then sharing(OC, TiC) with bf = 0.4.If OC is lo and UC is mu then sharing(OC, UC) with bf = 0.6.If OC is to and UC is lu then sharing(OC, UC) with bf = 0.6.Figure 2.5: The Rulebase of Component Matching for Load SharingIn evaluating the load sharing decisions, the factors considered in the rulebase ofChapter 2. A Theoretical Framework for Restructuring 38Figure 2.5 are the level of overload L — A of the overloaded components and the levelof undercapacity C— A of the undercapacity components. This information is “crisp”as obtained from sensory data of the workcell components, and has to be fuzzified usingthe corresponding membership functions.A reasoning procedure [22] using the techniques of fuzzy associative memory (FAM)[27] is designed in prioritizing an action by considering the membership grade valuesof the situations as well as the belief values of the fuzzy logic rules. The procedure isillustrated in Figure 2.6.SituationSpaceFigure 2.6: The Fuzzy Associative MemoryThe priority value of an action is then expressed by:PV(a) = fam(R(a))IOC, UC. (2.16)It follows that, the priority value PV of an action a is a function of a sub-rulebase R(a)associated with action a under the condition of the fuzzy status of OC and UC of twosharable components.Apart from the priority as evaluated from the overload level Loc— Ao and theundercapacity level Cuc — Au along with the rule beliefs, the feasibility of load sharingshould also be considered. The feasibility may be expressed as a matrix; thusF= (2.17)Chapter 2. A Theoretical Framework for Restructuring 39The priority value for a matching pair of components being considered for load sharing, has to be multiplied by the corresponding feasibility index as given by equation(2.17) in order to arrive at a total assessment of the load sharing decision. The feasibilityvalues have to be suitably updated following each decision of load sharing.Finally, the action with the highest assessment value based on the current systemsituation will be selected as the correct decision for restructuring purpose.2.5.2 Component ReleasingAs noted before, an undercapacity component may be released by transferring its loadto another undercapacity component of the same type to save operation cost. But, anundercapacity component need not be released in every load transfer process betweentwo undercapacity components. For example, a lightly undercapacity (lu) componentmight be converted into either a moderately undercapacity (mu) component or a highlyundercapacity (hu) component in this cycle, and would be ready for sharing with anoverloaded component (regardless of whether ho, mo, or lo) in the next planning cycleof restructuring.The rule-based approach to load transfer between two undercapacity componentsis somewhat similar to that between an overloaded component and an undercapacitycomponent. But the rulebase that is used would be quite different from what is given inFigure 2.5. Consider an undercapacity component (UR) that is expected to be releasedof its load and a second undercapacity component (UL) that is expected to receive theload of the first component. An appropriate rulebase for determining the priority ofcomponent releasing actions is given in Figure 2.7.It should be noted that the no-activity components should not be involved here, sinceit will not benefit the system operation. Specifically, an inverse action in a subsequentstep could make the decision system cycle in an endless loop.Chapter 2. A Theoretical Framework for Restructuring 40Context LevelsReleasing LoadingUndercapacity Component Undercapacity ComponentUR ULHighly undercapacity hu Highly undercapacity huModerately undercapacity mu Moderately undercapacity muLightly undercapacity lu Lightly undercapacity luIf UR is hu and UL is hu then releasirig(UR, UL) with bf = 1.0.If UR is hu and UL is mu then releasing(UR, UL) with bf = 0.8.If UR is hu and UL is lu then releasing(UR, UL) with bf 0.6.If UR is mu and UL is hu then releasing(UR, UL) with bf = 0.6.If UR is mu and UL is mu then releasirig(UR, UL) with bf = 0.4.If UR is mu and UL is lu then releasing(UR, UL) with bf = 0.4.If UR is lu and UL is hu then ‘releasing(UR, UL) with bf 0.4.If UR is lu and UL is mu then ‘releasing(UR, UL) with bf = 0.4.If UR is lu and UL is lu then ‘releasimg(UR, UL) with bf = 0.4.Figure 2.7: The Rulebase of Component Matching for Component ReleasingChapter 2. A Theoretical Framework for Restructuring 41Here too, a feasibility matrix of load transfer is used, and the application of thefuzzy-associative memory (FAM) reasoning procedure would be given by a counterpartof equation (2.16), asPV(a)= fam(R(a))IUR, UL (2.18)In the same manner as for load sharing, the decision maker in this case picks an actionwith the highest assessment value.2.6 SummaryThis chapter presented a theoretical framework for restructuring a flexible productionsystem (FPS). Basic properties of an FPS were discussed first. In particular, the statusof a component is determined by the load (or capacity requirement) which is given bythe load planner based on task demands, and the available capacity of the component.Usually, the component status is represented by a fuzzy descriptor, Next the restructuringproblem was formulated. The restructuring performance index, or the goal, was studied.A quadratic cost function could be used for evaluating the restructuring results, butfor knowledge based system design, expertise and past experience would be much morehelpful, in order to cope with the fuzzy performance requirements.A brief literature review was given. Since the dynamic restructuring is a new researcharea, some related work was also presented.The basic idea of restructuring is the planning of actions. Due to the complexityand fuzziness of the system, conventional planning methods do not apply in general.Heuristic-based restructuring was suggested and presented. However, in a practical design, the knowledge required to complete a restructuring process is complex and foundin various forms. Knowledge representation and reasoning will be the main topics thatCh.apter 2. A Theoretical Framework for Restructuring 42will be addressed in the following three chapters.Chapter 3Problem Solving ArchitectureThe concept and a theoretic framework of dynamic restructuring have been discussed inchapters 1 and 2. In this chapter, a problem solving architecture will be introduced andapplied to the dynamic restructuring problem.In Section 3.1, the complexity and variety of knowledge sources required for FPSrestructuring are discussed. A hierarchy is considered to organize knowledge of differentlevels of complexity and resolution. Knowledge sources which may be represented in avariety of forms and in need of different reasoning strategies, will be organized in anopen architecture,using a blackboard model. Section 3.2 presents the architecture ofthe blackboard model. In Section 3.3, the restructuring system is organized into theblackboard structure. Some specific knowledge sources are discussed in Section 3.4.Someconcluding remarks are made in Section 3.5 of the chapter.3.1 Knowledge OrganizationKnowledge associated with restructuring of a flexible production system (FPS) dealswith various aspects and may be treated at different levels. In particular, the followingknowledge sources are needed:• Knowledge about load planning, which determines the component loads corresponding to a given task demand. The component capacity requirements will be determined according to appropriate relations between the task demands and component43Chapter 3. Problem Solving Architecture 44loads.• The operating data about the FPS which is an important source of information fordecision making. Specifically the following information should be updated:— component type and capacity;— component shareability;— information associated with load sharing feasibility, such as the FPS layout;— current component load, and the component associations with workcells.• Knowledge needed for information pre-processing. This knowledge is needed toevaluate the FPS data and determine values for component status and sharingfeasibility index, for the the decision making associated with system restructuring.Component status is evaluated by comparing the required load and the availablecapacity of a component. Also the updating of the index of sharing feasibility isusually a knowledge-based process.• Knowledge about the restructuring decision itself. This will include heuristics indifferent levels of detail and resolution. Detailed selection of sharing pairs of orreleasing pairs of components should not be made before deciding whether a sharingor releasing action is actually needed. The decision as a whole should be made afterthe current FPS situation has been correctly recognized. In general, in view of thecomplexity and variety of knowledge sources and due to the presence of differentlevels of knowledge, a well organized structure would be strongly recommended.3.1.1 Organization of Knowledge in a HierarchyIn the restructuring system, knowledge of different levels is organized in a hierarchy asshown in Figure 3.1.Chapter 3. Problem Solving Architecture 45Should there beLevel 1a restructuringLevel 2 How to restructureSelecting an optimalLevel 3 restructuring actionFigure 3.1: The Hierarchy for Organization of the Restructuring KnowledgeLevel 1 decides whether there should be a restructuring action. The FPS situation,which could be changed by the restructuring actions, should be updated and recognizedbefore a decision is made.Level 2 decides how to restructure the system. Some general heuristics about loadsharing, component releasing, and some other restructuring actions are vital in restructuring planning, since the search space is extensive by large. Without the heuristics,it may not be practical to find a solution. Particularly, in a data driven system, suchas an FPS restructuring system, search space could be narrowed by using heuristics foroptimization.Level 3, which is the lowest level in a restructuring system, deals with more preciseinformation. A more accurate method can be used to decide the optimal restructuringaction under the guidance of level 2. It is still a fuzzy decision procedure, however, sincethe restructuring system as a whole is a high level one in an automation system of thetype shown in Figure 1.3. Level 1 is developed in this chapter. Level 2 and Level 3 willbe discussed in more detail in the next two chapters.Chapter 3. Problem Solving Architecture 463.1.2 Organization of Different Types of Knowledge SourcesSince the level 1 uses different knowledge sources for deciding whether to carry out arestructuring action, it may be organized into a blackboard [16, 25] architecture. Thisarchitecture consists of a global (shared) data region called blackboard (BB), severalknowledge sources (KS) or intelligent modules that interact with this data region, anda control unit. The knowledge sources are not arranged in a hierarchical manner andwill cooperate as equal partners (specialists) in making a knowledge-based decision. Theknowledge sources interact with the shared data region under the supervision of thecontrol unit. When the data in the blackboard changes, which corresponds to a changein context, the knowledge sources would be triggered by that in an opportunistic mannerand an appropriate decision would be made. That could result in further changes to theblackboard data and subsequent triggering of other knowledge sources. Note that thedata may be changed by external means (for example, through a user interface) as wellas due to knowledge-sources actions.The decision making process of the restructuring problem that was presented in theprevious sections is essentially an opportunistic one where an appropriate knowledgesource would be acting at a given time in carrying out the most appropriate action (e.g.,information updating, load planning, restructuring decision making). It follows that ablackboard model would be suitable for the implementation of the associated knowledgebased system. Furthermore, the following charcteristics of this level of decision makingshould be noted:• The knowledge sources may take different forms. They may include rule based decision making; planning procedures; information processing; or even look-up-tableupdating. In a blackboard architecture, the knowledge sources can be implementedas independent modules, so as to employ different reasoning strategies.Chapter 3. Problem Solving Architecture 47• The practical control mechanism of this level can be quite complex. For example,after the system makes a sharing decision, the control may continue with anotherdecision if an overload remains; or may determine component loads if task demandschanged; or may establish the system activity level if some components become disabled. The blackboard architecture provides a mechanism of opportunistic control,which can carry out such steps in the present application.• The FPS information should be accessible by every knowledge source, in whichthe integrated data of the overall operation of the FPS is needed for the reasoningprocess. Such data may be posted on a blackboard which would be visible to allknowledge sources.3.2 Blackboard ModelBlackboard model is known as a powerful achitecture for constructing knowledge basedsystems. As a model, blackboard system is basically modular, and employs opportunistically reasoning. As a result, it provides the dexterity and flexibility to deal with diversekinds of knowledge, and different inferencing mechanisms. Based on this model (or concept), one can establish a customized blackboard framework, although there are somecommon and general consideration. In order to understand the various blackboard structures, it is helpful to trace the intellectual history of blackboard concepts.3.2.1 Blackboard System History“Blackboard” as a technical term used in the AT literature first appeared in Newell (1962)[33]. Newell concerned with the organizational problems of programs that existed at thetime. He tried to organize subroutines independently and in a hierarchical manner.Even though this organization had many advantages, it also had difficulties: First, it wasChapter 3. Problem Solving Architecture 48found difficult to communicate between subroutines; Second, the ordered subroutine callsfostered the need for doing things sequentially; Third, the total program was organizedto do only one thing at a time. For these difficulties, it was noted [33] that they “mightbe alleviated by maintaining the isolation of routines, but allowing all the subroutinesto make use of a common data structure”. This should be the rudimentary idea of ablackboard system.The first real blackboard system is known to be Hearsay project [16] which wasdesigned and implemented for speech understanding. This blackboard structure wasproposed by H. Simon (1977) [41]. Before that, Simon published a paper [16] in whichhe mentioned the term “blackboard” in a slightly different context from Newell. Therehis focus was on the problem-solving method: In the typical organization of a problem-solving program, the solution effort is guided and controlled by goals and subgoals [41].Together with Newell’s common data structure, we can visualize a prototype frameworkfor a blackboard system; which consists of a common data structure and employs hierarchical problem solving.In the design of Hearsay [16], such system characteristics as hierarchically organizeddata levels and opportunistic reasoning, which we now accept as integral parts of ablackboard system, were derived from needs and constraints that were different fromthose of Newell and Simon. (Accordingly, the structure of a blackboard system may bemodified slightly in order to meet different needs and constraints).Presently, BB techniques are widely used for problem solving [25, 35, 36] and will beincreasingly popular in the future because of their attractive characteristics.3.2.2 Blackboard System StructureNow we consider the structure of a blackboard system at the model level. The blackboardmodel is a conceptual, high-level organization of information and knowledge which areChapter 3. Problem Solving Architecture 49needed to solve a problem. It is a general prescription for dynamic control of a system, andfor the use of knowledge for incremental, opportunistic problem solving. Organizationally,the blackboard model consists of three components.The knowledge sources ( KS ). The knowledge needed to solve the problem ispartitioned into knowledge sources, which are kept separate and independent.The blackboard data structure. The data on the system state which are neededfor problem-solving (represented as objects in the solution space) are kept in a globaldata store known as the blackboard. Knowledge sources can activate changes in theblackboard, which will lead incrementally to a solution to the problem. Communicationand interaction among the knowledge sources take place solely through the blackboard.Controller. What knowledge source should be applied, when, and to what part ofthe blackboard, are problems handled by the blackboard controller.The reasoning process associated with a blackboard has the following characteristics:The solution to a problem is progressed one step at a time. At each control cycle anytype of reasoning step (data driven, goal driven, forward chaining, backward chaining,etc.) can be used. The selection and the application of knowledge sources are dynamicand opportunistic rather than fixed and preprogrammed.The data objects on the blackboard are organized into hierarchical levels. Differentdata associated with different concepts can be made distinct and organized. Kowledgesources can be made to span two levels, with the information on one level serving asinput and the information on another level as the output. Such a system is illustrated inFigure 3.2.The control unit also gets information from the knowledge source ( KSs ), becausea KS consists of not only the domain knowledge (for problem-solving), but also theknowledge of using that knowledge.Therefore, a blackboard system is quite suitable for handling restructuring problemsChapter 3. Problem Solving Architecture 50Figure 3.2: A Model of a Blackboard Systemas in the present research, as it has some beneficial characteristics for handling systemsof: 1. large solution spaces; 2. noisy and unreliable data; 3. a variety of input data anda need to integrate diverse information; 4. many independent pieces of knowledge whichshould cooperate in forming a solution; 5. need to use multiple reasoning methods; 6.need of an evolutionary solution. These are considered as characteristics of the dynamicrestructuring system.3.2.3 Characteristics of a Blackboard• Complexity Management. A common technique for dealing with complexityin a system is to divide the system into subsystems and make the relationship between subsystems lessextensive, and implement the interaction between subsystemsthrough a higher level system.Chapter 3. Problem Solving Architecture 51In blackboard systems, a problem is decomposed so as to maximize the independence of the subsystems (KSs). Specificaaly no direct interaction between KSs isallowed, and all interaction should take place through the blackboard. But weshould note that a KS may interact with more than one blackboard. It can getthe problem from a domain blackboard, and communicate theoutput to anotherblackboard.• Easy problem formulation. In a blackboard structure, both the problem andthe knowledge are partitioned, which makes the problem formation relatively easy.Knowledge representation is separated into two parts: domain knowledge, and theknowledge of using the domain knowledge. (how, when, or where it is to be used).We can view a KS as a big rule,with the knowledge of using the knowledge as thecondition part and the domain knowledge as the action part of the rule.• Flexible reasoning strategy. Ill-structured problems are characterized by poorlydefined goals and an absence of a predetermined decision path from the initial stateto a goal. For example, in a dynamic restructuring problem, given a task, we donot have a clear goal that represents the workcell configuration for performing thetask. For example, two components of the same type could be interchanged withoutaffecting the system performance. The opportunistic problem-solving approach ina blackboard system provides the capability to deal with unpredicted or unenumerated events.In next section, the restructuring problem will be formulated in a blackboard architecture for the first level decision making.Chapter 3. Problem Solving Architecture 523.3 Problem Formulation in a Blackboard ArchitectureThe blackboard architecture that is used in the implementation of the FPS restructuring system is illustrated in Figure 3.3. There are seven knowledge sources (KS) whichrepresent the problem solving knowledge and four blackboards representing system information which can be accessed by the knowledge sources. A control unit supervisesthe system and activates a triggered KS according to its priority. There may be datachanges in the blackboard in executing of a KS. Such a change may trigger other KSs,which may lead to more execution of KSs. The procedure will end once the data in theblackboard satisfy the restructuring goal.User KNOWLEDGESOURCESFigure 3.3: The Blackboard Structure of the Restructuring SystemChapter 3. Problem Solving Architecture 533.3.1 Knowledge SourcesKnowledge is organized into seven modules with information encapsulated, except thedata from the blackboard. The modules are independent knowledge sources, each beingresponsible for solving a particular problem. In particular, the KSs are:• a user interface for interaction between man and machine;• a load planning system;• an FPS information updating system;• a component status evaluating system;• an updating procedure for load transfer feasibility;• a restructuring decision maker; and• an output module.The functions of these knowledge sources will be discussed in the next section.The KSs are represented by a frame structure as follows:KS:trigger-status;priority;input-blackboards;function-procedure.Here, “trigger-status” which has values “O and “off”, indicates whether the KScould be activated. The “priority” value resolves conflicts if more than one KS is triggered. The priority value is not given arbitarily, but according to the problem solvingmechanism. For example, if both the KSs of “status evaluation” and “restructuring” areChapter 3. Problem Solving Architecture 54triggered, the priority should be given to “status evaluation” for it should be executedbefore restructuring. This is the case because restructuring module should make decisions based on current status of the components which is evaluated by the KS “statusevaluation”.The “input-blackboards” provide information that could cause the triggering of theKS “status evaluation” through the data change in one or more of these blackboards.Hence, KS triggering could be done automatically when a blackboard is modified. The“function procedure” is actually the action part of the KS. It is designed with encapsulated information so as to avoid parameter passing when it is called.In the KS frame, each entity represents a property of a KS. From the point of viewof object-oriented design, this structure defines a template or “schema” of which a KSis an instance. In logic representation (for Prolog), a predicate is designed for the KSimplementation: ks(K, F, V) which is intended to mean that the KS K has the property(attribute) P at the value of V. The template is then represented byks(KS, trigger_status, T).ks(KS,priority, R).ks(KS, input_blackboard, B1).ks(KS, input_blackboard, Ba).ks(KS, function procedure, F).where, KS is the name of the knowledge source, T is the value of the trigger-status (either“on” or “off”); R is the number of the priority value; and B1, ..., B are the input-blackboards of this KS. (The advantage having separated clauses of input blackboardsshould be clear in the later design of automatic triggering.) F is the functional procedureof the KS to be called when the knowledge source KS is activated.Chapter 3. Problem Solving Architecture 55There are three methods of data operation related to this template: “trigger_KS”,“remove_trigger” and “execute_KS”, which could be designed as member functions in anobject-oriented system. Their Prolog clauses are as follows:triggerKS(KS) —retract(ks(KS, trigger_status, off)),assert(ks(KS, trigger_status, on)).removetrigger(KS) €—retract( ks(KS, trigger_status, on)),assert(ks(KS, trigger_status, off)).executeXS(KS) —ks(KS, function_procedure, F),call(F).where trigger_KS(KS) triggers the knowledge source KS on; remove_trigger(KS) isthe inverse action of trigger_status; and execute_KS(KS) executes the functional partof the knowledge source KS.The particular knowledge sources in Figure 3.3 can be represented using the KStemplate as follows:1. User interfaceks(user, trigger_status, off).ks(user, priority, 6).ks(user, body, user).where the user is the entry of this KS.Chapter 3. Problem Solving Architecture 562. Updating of FPS information.ks(fps, trigger_status, off).ks(fps,priority, 5).ks(fps, body, fps).where fps is the entry predicate.3. Load planner.ks (load.4istributing, input, demand).ks (load_distributing, trigger.status , off).ks(load_distributing, priority, 4).ks(load_distributing, body, load_distributing).where load_distributing is the entry predicate.4. Evaluation of the component status.ks(set_status, input, workload).ks(set_status, input, capacity).ks(set_status, trigger_status, off).ks(set_status, priority, 3.5).ks(set_status, body, update_workstatus).where update_workstatus is the entry predicate.5. Updating of feasibility.Chapter 3. Problem Solving Architecture 57ks(feasibility, input, sharability).ks(feasibility, input,position).ks (feasibility, trigger .status , off).ks(feasibility, priority, 3).ks(feasibility, body, update_feasibility).where update_feasibility is the entry predicate.6. Restructuring.ks(restructuring, input, position).ks(restructuring, input, work_for).ks(restructuring, input, workstatus).ks(restructuring, input, feasibility).ks (restructuring, trigger_status, off).ks(restructuring, priority, 2).ks(restructuring, body, restructuring).where restructuring is the entry predicate.7. Output.ks(output, input, plan).ks(output, trigger_status, off).ks(output, priority, 1).ks(output, body, output).where output is the entry predicate.It is worth noting that this representation simply gives descriptive knowledge abouta KS. The restructuring procedure which will be implemented in the control unit isChapter 3. Problem Solving Architecture 58separated. Without doubt, knowledge sources themselves could also adopt a blackboardstructure.3.3.2 BlackboardCommon data including workcell level information and component level information arelocated in the blackboard (BB), and represented by objects of workcells and componentsusing simple frames. The structure of a component frame is shown below:component:group;position;work-for;workload;capacity;workstatus.shareabilityand a workcell frame has the following structure:workcell:task-type;production-demand;layout.Similar to the representation of knowledge sources, the predicates component(C, F, V)and workcefl( W, F, V) are defined for the representation of information of a componentand a workcell respectively. Here, comporient(C, F, V) means that the component Cholds the property P at the value V, and workceU(W, F, V) has the same interpretationexcept W representing a workcell rather than a component. Consequently, the componenttemplate is given by:Chapter 3. Problem Solving Architecture 59component(C, group, G)component(C, position, W)component(C, work for, WF)component(C, workload, WL)component(C, capacity, Cc)component(C, workstatus, S)component(C, shareability, N)where C denotes a component, C is the name of a component group, say, vision, robot,AGV etc; W indicates the workcell in which the component C is located; WF is a list ofworkcells for which the component C works, and WF has the form [Wi, W2,• , Wn];WL is a list of workloads corresponding to WF, say [30, 20,•• , 40], in which load 30(30% of the full capacity of a standard component of the group C) is assigned to workcellWi, and load 20 is assigned to W2 and so on; Cc is the capacity of the component Cas a percentage with reference to a standard component; S which is a fuzzy variable,represents the load status of component C; and N which is a real number in the interval[0, 1] represents the shareability index of the component. For example,component(robotl, group, robot).component(robotl, position, cutting_cell).cornponent(robotl, work_for, [cutting_cell]).component(robotl, workload, [80]).component(robotl, capacity, 100).component(robotl, work.status, [(mu, 0.4), (lu, 0.6)]).component(robotl, shareability, 0.9).Chapter 3. Problem Solving Architecture 60Note that the same property of all objects is put in a specific sub-blackboard. Forexample, a sub-blackboard of capacity contains the capacity information of every component of the system. (See Figure 3.4). The KSs are sensitive to the properties of objects.Capacity Blackboardcomponent(visionl, opacity, 100%).component(robot2, opacity, 200%).... ... ... ...componert(robot3, cpacity, 100%).component(agv5, cpacity, 50%).Figure 3.4: A Sub-Blackboard Representing Component CapacityActually, they are designed to handle object properties, rather than individual objects.The template of workcell representation is given by:workcell(W, task_type, T).workcell(W, demand, D).workcell(W, layout, (X, Y)).where W is a workcell; T is the task type that workcell W can process; D is the taskdemand; and (X, Y) pair describes its geographic position on the workshop floor. Aninstance is:warkcell(cuttin_cell, task_type, cutting).workcell(cuttin_cell, demand, 2item/s).warkcell(cuttin_cell, layout, (150, 30)).Also, the properties of workcells are divided into separate sub-blackboards.There are two methods associated with the blackboard operations get_property andmodify_ property which could be considered as member functions in an object-orientedChapter 3. Problem Solving Architecture 61design, such as an implementation in C++[24]. The two methods also incorporate someincomplete knowledge treatments and automatic triggering of KSs.get_property(O, F, V) reports the property (F) value V of object 0, and can beimplemented as follow:get property(O, F, V) —holds(0, F, V),!.geLproperty(0, F, V) *—holds(O,-,assumable(0, F, V).get .property(O, F, V) i—holds(0,_,_),ask(0, F, V).holds(0, F, V) — compo’nent(O, F, V).holds(0, P, V) i— warkcell(0, F, V).holds(O, F, V) — ks(0, F, V).If there exists a fact that the object 0 holds the property F at the value V, thenthe get_property returns this fact. Otherwise it uses the assumable default value or asksuser whether the object exists. Here, object 0 can be either a component, a workcell ora knowledge source. Therefore, if our database is incomplete, the system will not, F, NV) modifies the property F of object 0 to a new value NV.If the property does not exist, the new value will be asserted to the database. Animportant side effect is that when a property BB named P is changed, associated KSswith input from the blackboard should be triggered.Chapter 3. Problem Solving Architecture, F, NV) ÷—component(O, F, V),!,retract(component(O, F, V)),assert(component(O, F, NV)),trigger_KS(P), F, V) +—assert(component(O, F, NV)),trigger_KS(P).trigger_KS(P) ÷—findall(KS, ks(KS, input_blackboard, F), KSs),trigger(KSs).where trigger(KSs) triggers a list of knowledge sources KSs.trigger([J).triggerKS([HIT]) ÷—trigger_KS(H),trigger(T).Therefore, the knowledge sources interact with the blackboard through the methodsgiven above. Conversely, The modification of blackboards will trigger certain agentsthrough the methods associated with the template of “ks”, for example, trigger_KS andremove_trigger.3.3.3 Control UnitThe control unit of a blackboard system functions as an inference engine for the descriptive knowledge that is represented by KSs. It monitors the system by looking for the KSsChapter 3. Problem Solving Architecture 63with their trigger_status “on”; and selecting the KS of the highest priority; and finallyexecuting that KS.The whole system is designed to possess opportunistic reasoning and is data driven.A KS will be triggered when any of its input blackboards are modified, and the trigger-status can be removed only after the KS has been executed. Several KSs may be triggeredat the same time, but the KS with the highest priority will be called first. This reasoning strategy actually provides an open architecture when several knowledge sources areworking together, especially when the problem solving process is not very clear or thefinal goal is ill defined.A simple reasoning procedure is given below:control *—collect_triggered_KS(KSs),.select_highest_PR(KSs, KS),execute(KS),control.control i—trigger( [user, fps]),control.Here, the operation collect_triggered_KS(KSs) collects all triggered knowledge sources.It may fail in case none of the knowledge sources are triggered, which will cause thecontroller turn to the second clause, which will then trigger the knowledge sources of “UserInterface” and “Updating of FPS Information “. As an example of system operation,suppose that the blackboard region the “Component Information” has been changed.Then the knowledge sources “Updating of Sharing Feasibility “ and “Restructuring”will be both triggered, and the former which has a higher priority, will be executed first.This execution may change the blackboard (BB) of “Sharing Feasibility”, and can in turnChapter 3. Problem Solving Architecture 64trigger the KS of “Restructuring” again. The execution of the KS of “Restructuring” maycause some other blackboard regions to change. This will trigger some more knowledgesources and consequently change the data in the associated blackboards, and so on. Theprocedure will end when an execution of the knowledge sources does not result in furtherchanges of the BB data, and the trigger status of all the knowledge sources are off. Then,the system will idle.3.4 Functions of Knowledge SourcesIn the architecture shown in Figure 3.3, there are senven knowledge sources (KS) whichdeal with user interface, information updating, load planning, evaluating of componentstatus, updating of sharing feasibility, restructuring, and output. Major functions ofthese knowledge sources are outlined below:KS of user interface. This handles the input of production demands. It alsoprovides a function that enables a user to change the information in the blackboard. Ithas the highest priority without any precondition.KS of updating of information. This KS updates the operating information of theFPS, including the available capacity resources, workcell activity levels, and the systemlayout. It obtains data from the component level through information preprocessors andfrom the workcell level through intelligent preprocessors as well. This KS has the secondpriority.Techniques of sensor fusion [5, 37, 13] could be used for this purpose. A multiple sensorapproach which is similar to the method a human would use to monitor a productionprocess is considered. The approach of a human is characterized by lack of accuratesensors and process models. However, the human considers a number of different sensors(his/her own senses), and processes the information about a variety of process variables.Chapter 3. Problem Solving Architecture 65Similarly, one can consider a system for the monitoring of production processes wherebythe measurement of process variables is performed by several sensing devices which feedtheir signals into a processing model. A knowledge based system can be employed tohandle these possibly inaccurate and incomplete signals, and provide information to thedecision maker of FPS restructuring. (see Figure 3.5)SensorsThis part in itself is a wide topic, and will not be studied in detail in this thesis. Itis assumed that there is such a system (KS) for later use in the simulation.KS of load planning. This KS has a knowledge base for capacity planning [45, 4]methods and associated transformations that determine component loads for a specifieddemand (see equation (2.2)). It assigns the workload to the workcell components according to the processing demand and the capacity planning method, and then sets thecomponent status according to component capacity, load, and the activity level. ThisKS has the third highest priority.KS of evaluation of component status. This KS uses information, such ascapacity C, load L and activity level A of a component, and evaluates the statusFigure 3.5: An Intelligent Sensing SystemChapter 3. Problem Solving Architecture 66of the component using equation (2.5). The degree of component overload or capacitysurplus is measured by fuzzy descriptors OC and UC, whose membership functions areillustrated in Figure 3.6.‘-too1 2(a) Lc/Ac1.tuchu mulu(b)1 Ac/CcFigure 3.6: The Membership Functions for Fuzzy Descriptors of Overload (a) and Undercapacity (b) of ComponentKS of updating of sharing feasibility. This KS obtains information about component shareability and geographic factors, and updates the sharing feasibility index.Since this should be done before restructuring, it has a higher priority than that for KSof restructuring.KS of restructuring. This KS performs a procedure of deciding the most appropriate action against the badness of current system. Knowledge based methods employingfuzzy logic are used in the decision making. Actually, levels 2 and 3 in Figure 3.1 willimplement this knowledge source, and is central to restructuring decision making.KS of output (commanding of lower levels). This sends restructuring commandsto the workcell controllers which are located at a lower level. Some coordination of theChapter 3. Problem Solving Architecture 67shared components should be done here. In addition, the restructuring commands mighthave to be approved by system experts. This KS has the lowest priority.3.5 SummaryBasic considerations about knowledge organization were presented in this chapter. Athree level decision making hierarchy was used for restructuring system.1. The first level will determine whether a restructuring should be called.2. The second level provide some general guidance about how to restructure the system.3. The third level will select an optimal restructuring action among all the possibilities.The first level will make the blackboard model to cooperate with different kinds ofmodules for information updating, data processing, and decision making associated withrestructuring. The characteristics of a blackboard architecture, such as a common dataarea and opportunistic reasoning, make it particularly suitable for organizing a high levelFPS restructuring system.Domain knowledge is represented by objects of workcells and components. Each typeof property of the objects will occupy a sub-blackboard. Data change in the blackboardwill trigger related knowledge sources. A control unit will monitor the entire system andrepeatedly select a triggered KS that has the highest priority for execution.This structure is suitable for bottom-up proof, particularly, when the restructuringgoal is fuzzy.Chapter 4Heuristics and ActionsThe concept and the framework of dynamic restructuring have been presented in chapters1 and 2, and a problem solving architecture has been developed in Chapter 3. Thischapter will study the heuristics for solving the problem. Actions, are also discussedin detail, which change data in the blackboard system that has been described, so asto make the blackboard evolve from the initial world to the final world in which therestructuring goal is true. -Section 4.1 analyzes the blackboard-based restructuring procedure; Section 4.2 develops the heuristics and Section 4.3 specifies the actions of restructuring. Section 4.4 givesa summary.4.1 Analysis of Restructuring ProcedureReferring to the decision making hierarchy given in Figure 3.1, we note that the secondlevel will be called after the first level has decided to have a restructuring action. It isvery helpful to have a clear picture of the restructuring procedure in building the generalrestructuring heuristics.4.1.1 Planning Using BlackboardAs discussed in Section 2.3, general planning methods are not suitable for the restructuring problem which is addressed in this thesis. A practical flexible production system68Chapter 4. Heuristics and Actions 69(FPS) is too complex to be represented in a reasonable size by classical planning methods. As a remedy, in blackboard-based restructuring planning, the use of expertise fromdomain experts and practical operators is exploited. The basic idea of blackboard-basedplanning is as follows: Represent the initial world in a blackboard; and then change theworld by performing some actions until the final world (goal) is achieved, in which thedesired goal is true. This approach is illustrated in Figure 4.1.Initial BB Intermediate BB Final BBWorld 0 World 1 . . . World n(The goal is (The goal is (The goal isnot true) not true) true)Figure 4.1: The Blackboard-Based PlanningNote, however, that we do not specify object properties for every world in the reasoning procedure. The system (workcells, components) situation is still represented in thegeneral property predicate, but without specifying the world:holds(Object, Property, Value),such ascomponent(O, F, V)orworkcell(O, F, V).If we assume that complete knowledge about an FPS exists and is represented inthe blackboard, then we can use “failure as negation”; that is if a particular propertycannot be found, that means the property does not exist. (i.e., not(holds(O, F, V)) istrue if holds(O, F, V) fails). Therefore, it is important that all the object properties areChapter 4. Heuristics and Actions 70placed in the blackboard (or indicated as assumable and askable), and all changes ofproperties are applied on the blackboard. Then an action will amount to changing thecorresponding blackboard (BB).The present change of representation does not mean that we treat an FPS as a staticworld. Instead, we implicitly assume that if an object property is not changed by anaction, then the object will still keep the old property value in the new world. Clearly,we no longer need axioms for all situations of every action. We rather need only thoserules in which an action really changes the world. This significantly reduces the extentof the representation space of a problem during solution.The effects of all actions should be anticipated and specified. The correspondingblackboard should be modified when an action is applied. It is this modification thatmakes the blackboard evolve from an initial world to the final world where the the goalis achieved.4.1.2 Heuristics for SearchThe search space of restructuring planning is potentially large, and heuristics would benecessary for practical solution of the problem. Also, due to the fuzziness of a restructuring goal, multiple solutions may exist. Thus, optimization should be considered as well.A decision for selecting a restructuring action is made on the following basis:1. Trimming the search space by using heuristics;2. Selecting an optimal action in the trimmed space.Note that without the first step, the second step is not usually feasible for it is hardto evaluate all actions in a global search space. This idea is illustrated in Figure 4.2Here, for example, if only the actions pertaining to “component releasing” should beconsidered first according to some heuristics, then only those actions in the sub-spaceChapter 4. Heuristics and Actions 71Figure 4.2: The Heuristic Search and Optimizationindicated by the shaded area (of releasing) are of interest for further consideration. Thisis what is termed second level decision making, in the present problem, the third levelis a optimization procedure that selects an action that has the highest assessment fromthe sub-space. (The third level will be discussed in Chapter 5.) The same procedure asbefore can be applied in all level of planning, as shown in Figure 4.2.The next two sections will develop heuristics for restructuring and specify all possibleactions.4.2 Heuristics for Problem SolvingIn restructuring, some general guidelines should be taken into account before selecting adetailed action. This is very helpful in the search for an optimal action in a particularcase, for example, as shown in Figure 4.2. Human expertise and past experience areassets in developing heuristics. Note that, each heuristic will be developed for only onecase; separate cases use separate heuristics even though the conclusions might be thesame. Union is not allowed. This would be necessary for a ëlear logic expression andaccording to the convention of Prolog.0<Chapter 4. Heuristics and Actions 724.2.1 HeuristicsTermination of a Load Sharing ActionFirstly, if an FPS does not work properly, the existing load sharing states should bechecked. In case a previously-overloaded component is no longer overloaded due tochanges in operating conditions,(say, the associated task demand has been dropped orthe component has been upgraded), the sharing would not be necessary and should beterminated. Consider the following three heuristics:Heuristic 1A: Terminating a load sharing action due to load reduction. Ifthere exists a load sharing state shared(OC, UC, Load), and the OC would no longerbe overloaded without this sharing, then this load sharing action should be terminated.This may be implemented asheuristic(A) f—plan(shared(OC, UC, Load)),component(OC, workload, L),noLoverloaded(OC, L, Load),A = terminating(shared(OC, UC, Load)).Here plan(R) records an action R which is either shared(OC, UC, Load) a record of actionsharing(OC, UC) or released(VC, C, Load) a record of action releasing(UR, C) whereVC is a virtual component reflecting the properties of UR. not_overloaded(OC, L, Load)is true if OC is not overloaded given loads L and Load. If all the subgoals (conditions)are true, a command of sharing termination will be issued.In another case, if the index of sharing feasibility between a sharing pair of componentsreduces below a threshold value, the sharing should be ceased. This may happen, forexample, when the communication system of a sharing component is damaged completelyor partially, or the moving path for a shared component is no longer available.Chapter 4. Heuristics and Actions 73Heuristic 1B: Terminating a load sharing action due to feasibility reduction. If there exists a load sharing state shared(OC, UC, Load), and the sharing feasibility index drops below a threshold value, then this load sharing action should beterminated. This may be implemented asheuristic(A) i—plan(shared(OC, UC, Load)),feasibility((OC, UC), I),I < 0.6,A terminating(shared(OC, UC, Load)).where I is the index of sharing feasibility between the pair OC and UC; and 0.6 is thethreshold value. If the sharing feasibility value is less than 0.6, the sharing should beterminated.Furthermore, as given in the next heuristic, an existing sharing state should be terminated if either component which is being shared becomes overloaded. Then, a new,more appropriate sharing strategy should be sought in place of the current strategy, inorder to remove the overload.Heuristic 1C: Terminating a load sharing action due to a load increase.If there exists a load sharing state shared(OC, UC, Load), and either OC or UC iscurrently overloaded, then shared(OC, UC, Load) should be terminated. This may beimplemented as follows:heuristic(A) —plan(shared(OC, UC, Load)),overload(OC, or, UC),A = terminating(shared(OC, UC, Load)).where overload(OC, F, UC) checks the workload status of OC and UC according to theflag F. If either of the components is overloaded, the sharing should be disabled.Chapter 4. Heuristics and Actions 74Termination of a Component Releasing ActionA component releasing action also should be checked to determine whether a componentis shared with more than one load, due to that action. Similarly, if the shareability indexof the loaded component on a “component releasing” action is below a certain threshold,or if the component has been overloaded, the component releasing action should beterminated.Heuristic 2A: Terminating a component releasing action due to reductionof the component shareability index. If there exists a component releasing state“released(VC,C,Load)”, and the component C is no longersuitable for receiving thereleased load, then this component releasing action should be terminated.Here released(VC, C) is a record of action releasing(UR, C) which released a component UR by transferring its load to component C, ( Note that C would occupy in itsoriginal task as well, and therefore, would be shared for the loads of both components).A virtual component VC records all the properties of VC except capacity. It is expressedby:heuristic(A) ÷—plan(released(VC, C, Load)),component(C, shareability, I),I < 0.6,A = terminating(released( VC, C, Load)).where I denotes the shareability of component C. If I is less than a threshold value ( 0.6in this case ), the component C should not be shared for the both loads. Note that the“releasing” action actually results in a component sharing, in the sense that the recordreleased(VC, C, Load) represents an existence of a component sharing state for C.Heuristic 2B: Terminating a component releasing action due to an increaseChapter 4. Heuristics and Actions 75of load. If there exists a component sharing state “released(VC, C, Load)”, and thecomponent C is currently overloaded, then this component releasing state should beterminated. This may be implemented as follows:heuristic(A) ÷—plan(releasing(VC, C, Load)),component(C, workload, L),component(C, capacity, Cc),sum.up(L, LD),LD>Cc,A = terminating(releasing( VC, C, Load)).Here LD is the sum of all the loads assigned to component C. If LD is greater than itscapacity C, then component C should not be shared, and hence the component releasingstate should be terminated.Component MovingA component may be moved from a workcell to which it is assigned to another workcell.Usually, for proper control and communication within the system, the geographic positionof the component has to be convenient for the workcell for which it now works. Thissituation takes place when a component is released within its original workcell, and isreassigned to another workcell in order to absorb an overload. One thing which shouldbe noted here is that, the moving action should be done preferably prior to the loadreassignment, in the practical situation, although the moving is actually caused by theneed for a reassignment. Consequently, in the restructuring report, a moving action couldbe placed before the reassignment action.Heuristic 3: Moving a component. If component C is located in workcell W,and is working solely for another workcell Wi, then this component could be moved toChapter 4. Heuristics and Actions 76workcell Wi from workcell W. The implementation of this heuristic is given below:heuristic(A) —component(C, position, W),component(C, work.for, {W1{]]),W:.AW1,A = move(C,from(W),to(W1)).Component ReleasingComponent releasing should be considered before component sharing, because the released components may be used later, in sharing. Based on human expertise, sharing ofcomponents within a workcell is better and easier than sharing between workcells. Hence,component releasing within a workcell is considered to be of higher priority than effecting a component releasing action between workcells. Also, the component shareabilityshould be considered in effecting a releasing action.Heuristic 4: Releasing a component within a workcell. If there exists anundercapacity component, and there exists another undercapacity component of thesame type in the same workcell, then one of them could be released by transferring itsload to the other one. This heuristic may be implemented as follows:heuristic(A) *—group(G),groupcomponents (undercapacity, G, UCs),best_action(UCs, A, PD, within).where G is the group name. Here, group_component.s(F, G, UCs) groups all componentsin group C into a list UCs according to the flag F which may take values “overloaded”and “undercapacity”; and best_action(UCs, A, PD, FL) is a decision making procedure,Chapter 4. Heuristics and Actions 77which will be discussed in Chapter 5, for selecting the best action A which has prioritydegree PD, according to flag FL which has values “within” (a workcell) and “between”(workcells). The action A takes the form “releasing(UR, UL)” here.Heuristic 5: Releasing a component between workcells. If there exists anundercapacity component, and there exists another undercapacity component of thesame type in an other workcell, then one of the two components could be released bytransferring its load to the other. This heuristic may be implemented as follows:heuristic(A) i—group(G),groupcomponents (undercapacity, C, UCs),best_action(UCs, A, PD, between).Here, the only difference from the previous one is that the flag “within” (a workcell) ischanged to “between” (workcells). This difference reflects an important consideration ofpriorities of actions within a workcell or between workcells.Load SharingComponent overloads are considered now. For the same reasons as in releasing a component, a load sharing action within a workcell is considered to have a higher priority thanan action of component sharing between workcells.Heuristic 6: Sharing a component within a workcell. If there exists a component overloaded, and if there exists another component of the same type that is operatingat undercapacity in the same workcell, then share the undercapacity component withthe overloaded one. The implementation of this heuristic may be as follows:Chapter 4. Heuristics and Actions 78heuristic(A) —group(G),group.components(overloaded, G, OCs),best_action(OCs, A, PD, within).Note that this heuristic is different from Heuristic 4 only by the flag “overloaded” inplace of “undercapacity”. The decision-making procedure will select a proper action A bychecking the status of the components. The action A takes the form sha’ring(OC, UC)here.Heuristic 7: Sharing a component between workcells. If there exists acomponent that is overloaded within a workcell, and if there exists another componentof the same type in another workcell that is operating at undercapacity, then share theundercapacity component with the overloaded one. This heuristic may be implementedas follows:heuristic(A) *—group(G),group_components(overloaded, C, 0Cs),best_action(OCs, A, PD, between).It is clear in this heuristic that, the flag is “between” instead of “within” in the previousheuristic, so as to call for sharing actions between workcells.4.2.2 Usage of HeuristicsThe heuristics discussed in the previous sections are given different priorities in practice. They are considered in the order of their priorities, in the actual operation ofChapter 4. Heuristics and Actions 79the knowledge-based decision making system. By reviewing the process of restructuringplanning, it should be noted that the heuristics are actually used by a mechanism thatis schematically shown in Figure 4.3.ICheckStatus=overloadsZfRestructuring RestructuringFailed SucceededFigure 4.3: The Reasoning SequenceHere, the heuristics denoted by 1, 2, 3, ... etc. are arranged in the order of thepriority of execution of the associated rules. Note that only when the heuristics withhigher priority have failed to solve the problem, a lower priority one can be fired. Whena heuristic succeeds, which means the blackboards may receive new data by the actionsissued by the heuristic, the first-level decision maker will review the entire problem inthe blackboard all over again. This process will end when none of the knowledge sourcesSs: successf: failureChapter 4. Heuristics and Actions 80are triggered, which actually means no data change has been made in the last step ofthe restructuring process. In another words, no heuristic succeeded and no action wasissued.4.3 ActionsAlthough the heuristics return various actions, they actually fall into two kinds of physicalactions:transfer_load(OC, UC, L)andmove...component(C, Wi, W2)where transferioad(OC, UC, L) removes load L from OC and assigns it to UC; move...component(C, Wi, W2) moves component C from workcell Wi to workcell W2. Thissection will specify the restructuring actions by means of practical physical actions.Load SharingJ CC0 sharing” an undercapacity component shares the load of an overloaded component. Consequently, the load originally assigned to the second component will be sharedby the two components (of the same type). As a result, the originally undercapacitycomponent is now shared between its original load and the new load. This action isrepresented as follows:sharing(OC, UC) ÷—dete’rminioad(s haring(OC, UC), Load),transfer_ioad(OC, UC, Load),record(shared(OC, UC, Load)).Chapter 4. Heuristics and Actions 81where, determin_load(sharing(OC, UC), Load) determines the load “Load” to be transferred from OC to UC; and record(A) records the information of this action for furtherreference in restructuring.Component ReleasingComponent releasing represents a load transfer from an undercapacity component toanother undercapacity component, with the complete load of the first component beingabsorbed by the second one thereby releasing the first component. This action may beimplemented as follows:releasing(UR, UL) €—determin_load(releasing(UR, UL), Load),trarisferioad(UR, UL, Load),make.virtual(UR, VC),record(released(VC, C, Load)).Here, the predicate make_virtual(UR, VC) records the properties of UR, and in casethis component releasing action should be terminated, the virtual component could beused for the intermediate state of load transfer. Note that, a virtual component is a copyof the released component except its capacity is always set to zero. In the componentreleasing process, it is a copy of Ui? in the record, and makes UR free for other use.Terminating a Sharing or Releasing ActionTerminating a load sharing action is the inverse operation of component sharing. It maybe implemented as below:Chapter 4. Heuristics and Actions 82terminating(shared(OC, UC, Load))transferioad(UC, OC, Load),remove(shared(OC, UC, Load)).Note that the termination of a component releasing operation is not as straightforward,because it is not just the inverse operation of component releasing, since the releasedcomponent might already be used for other purposes. In fact, the inverse operation ofcomponent releasing does not always exist. In such a case, a virtual component couldbe used, which has all the properties (recorded when making the releasing action) of theformerly released component UR, but with zero capacity (i.e., does not exist physically).Thus, a virtual component represents a pure shortage of capacity, and it always seeks asolution for its overload. The implementation is and follows:termimating(reieased(VC, C, Load))transfer_ioad(C, VC, Load),remove(reieased(VC, C, Load)).Moving a ComponentMoving a component needs a specific type of action, which is denoted as mavecompoment.Moving a component is specified as:move(C, from(Wi), to(W2))free(C),move.component(C, Wi, W2).That the component C must be a non-activity component is a precondition for actuallymoving a component.The move_cornpoment/3 action changes only the position of a component. Thetransfer_ioad/3 action changes the component workloads, and also the property ofChapter 4. Heuristics and Actions 83work_for. If the load of a component that is dedicated to a workcell, is zero, it isreleased from that workcell, at least in principle.4.4 SummaryRestructuring of a flexible production system (FPS) was analyzed in this chapter. Thecore activity in restructuring was identified as a planning procedure. A plan is a sequenceof actions from the initial world to a goal world. Heuristics play a very important rolein searching for this sequence.Heuristics include: 1. checking whether the existing sharing states are still suitable;2. moving a component; 3. selecting a component-releasing action and; 4. selecting aload-sharing action. They are fired in the order of their priority.The actions in a restructuring process include: terminating a sharing, moving a component, releasing a component and sharing a load. The main physical actions involvedare: transferload and move_component, which modify the status of a component.Chapter 5Fuzzy Decision MakingIn previous chapters, the architecture of the knowledge-based, restructuring system hasbeen established. In particular, the problem solving heuristics have been developedin Chapter 4. Clearly, there may be more than one action that could be available at arestructuring stage when using heuristics for solving the problem. This chapter addressesthe resolution of this situation, which is known as conflict resolution. Fuzzy logic will beused in evaluating the available actions in a stage of decision making.Section 5.1 discusses the conflict resolution problem in a restructuring process, whichrequires a decision on selecting an optimal action. Section 5.2 gives a fuzzy decision-making structure. According to this structure, Section 5.3 presents a method for recognition of the status of a flexible production system (FPS), using fuzzy descriptors. Section5.4 presents a decision-making method with emphasis on techniques of fuzzy associativememory. Section 5.5 gives concluding remarks.5.1 Conflict ResolutionAs indicated in Figure 4.2, heuristics lead the problem solver to a sub-solution space(shaded area), in the restructuring process. The need for conflict resolution arises in thesubsequent steps of problem solving in the sub-solution space. Since the final goal isfuzzy, there may be more than one solution in the trimmed solution space. Optimizationshould be considered for this reason. Note that, for different types of actions, the appropriate conflict resolution method might be different, which is actually determined by the84Chapter 5. Fuzzy Decision Making 85restructuring mechanism, and will be discussed in detail in the sequel.For actions about terminating a sharing mode, the first match method [13, 14] couldbe used. An action of terminating a sharing state will affect only the pair of sharedcomponents (including virtual components), and the other components in the FPS willnot be affected. Thus, component sharings can be released in any order. In addition, theassociated heuristics have the highest priority, which means, only after all unnecessarycomponent sharings have been released, that other actions such as component releasingand load sharing should be considered.For an action of moving a component also, the first match method is suitable. Almostthe same reasons apply here, specifically, 1. moving a component does not affect othermoving actions; and 2. all moving actions will be executed before making further decisionson releasing and sharing of components. Therefore, the sequence of executing the movingactions will not affect the entire decision making process for restructuring.For component releasing and sharing actions, however, the sequence of actions willaffect the decision making process of restructuring. As an example, consider four components of the same type: Cl, C2, C3, and C4. Suppose that, Cl is lightly overloaded,C2 is moderately overloaded, C3 has a high undercapacity, and C4 has a light undercapacity. If Cl is considered first, C3 should be suitable for sharing the overload in Cl. Asa result, C2 will not be able to find a proper partner to share its overload. The propermatch would be C4 for Cl and C3 for C2.Generally, releasing and sharing actions do affect other releasing and sharing decisions.It follows that an optimal match should be used for the associated conflict resolution. Inparticular, the following important factors should be considered:• The load status of the components which will be subjected to a releasing or sharingaction;Chapter 5. Fuzzy Decision Making 86• The belief degree of knowledge of executing such an action between this pair ofcomponents;• Feasibility of load transfer between the pair.In the following sections, a fuzzy decision making system will be developed for selecting the optimal actions.5.2 A Fuzzy Decision-Making StructureTwo steps are considered for the fuzzy decision making process as illustrated in Figure 5.1.SystemInformation System Fuzzy DecisionSituation : DecisionRecognition Making_____________I_____________Zrership Knowledge 1Functions :L.t*Jt3IFrom Real World FromObservations, ExpertiseEstimation, and Theoryand ExperienceFigure 5.1: Schematic Representation of Fuzzy Decision MakingFirstly, the system status should be recognized. The recognized conditions shouldmatch the control knowledge of experts. Particularly, in a knowledge-based restructuringsystem, component workload status is expressed in terms of linguistic descriptors, suchas “highly overloaded” or “lightly undercapacity”. Naturally, it may be useful then, tomeasure and recognize the component status as well in a qualitative manner. Secondly,based on the current status of the system, a set of rules may be fired to make decisions forChapter 5. Fuzzy Decision Making 87selecting proper restructuring actions. A learning mechanism could be used in a feedbackloop to adjust fuzzy membership functions and the knowledge base.Fuzzy logic [46, 28, 26] has been employed to deal with qualitative and non-crispconcepts that are present in decision-making problems of the real world. Applicationsare found in dynamic systems and control [8, 27]. The present practice in fuzzy logiccontrol is to consider the confidence level of the associated fuzzy-logic rules to be 100percent. In this thesis, however, both the situation facts and human knowledge areconsidered to have varying degrees of belief. A fuzzy decision is made by considering allpossibilities of a system status, with different degrees of belief. The corresponding rulesare also assumed to have different degrees of belief.“Fuzzy membership functions” describe a mapping from real-world “physical” measurements to human interpretations of linguistic terms in a fuzzy descriptor. The conceptsare specific to a particular use, but should be valid for a generally recognized measurement range corresponding to a given attribute. The knowledge base of “decision making”consists of rules such as those given in figures 2.5 and 2.7. The fuzzy decision maker firesthose rules whose condition parts match the present FPS state, as observed, and synthesizes the conclusions of those rules with associated belief values, so as to generate arestructuring decision.In the following two sections, the representation of system information and humanknowledge associated with the present problem will be discussed. Then, a fuzzy decisionmaking procedure will be designed and implemented in Prolog, which uses this representation.Chapter 5. Fuzzy Decision Making 885.3 Representation of Situation5.3.1 Fuzzy Representation of Component StatusComponent status is expressed by a fuzzy set [15] rather than using crisp logic, which isbased on the following reasons:• A “crisp” sensing signal of a component indicating its status may not be accurate ata given time, and may not be reliable. A fuzzy representation might take subjectiveand qualitative considerations and past experience into account, and would bebetter.• Some information on components may be directly as fuzzy indicators, such as theload status of a humanbeing, or quality of a piece of processed herring roe, asprovide by “intelligent” sensors.• Human knowledge describing a component status is fuzzy by itself. In order to usehuman knowledge to make decisions, the system conditions should be recognizedin a compatible manner.The component status can be described by a fuzzy descriptor such as {highly overloaded (ho), moderately overloaded (mo), lightly overloaded (lo), just ok (ok), lightlyundercapacity (lu), moderately undercapacity (mu), highly undercapacity (hu), and noactivity (na)}. Each value of the variable in the “universe of discourse” will have amembership grade which represents the degree to which that value belongs to the set.A component status is represented by the membership grades at which it belongs to agroup of fuzzy sets. For example,Soc = {lo(O.8), mo(O.2)}.Chapter 5. Fuzzy Decision Making 89where Soc is a fuzzy variable representing the status of the component OC. It statesthat the membership of this quantity in the fuzzy set lo is 0.8, and in mo is 0.2, and itdoes not belong to any other fuzzy sets. As a result, this component is eligible to use therules for both states lo and ma.Typical membership functions of component status are shown in Figure 5.2. Forexample, a component of status ok means that when it is working within the crisp loadrange 85 100% it operates in an “ok” state, with any possibility of displaying anotherstate, and when it is operating within the non-crisp edge beyond this range, there isa possibility of displaying the characteristics of little lu or lo as well. Note that the“capacity” and “load” are both standardized for the convenience of comparison in laterdecision making.ItStat1iSna hu mu lu ok Ia mo ho/c1rxJK1.0 0.8 0.6 0.4 0.2 0.0 -.2 -.4 -.6 -. .1.0 c-LFigure 5.2: The Membership Functions of Component StatusTo provide an analytical foundation for our developments, some definitions of fuzzyoperators are given next. Using them, a “symbolic language” can be introduced, whichmay facilitate further developments in the area of fuzzy-logic decision making.Definition 1. Fuzzy operators are denoted as follows, with the given order (increase)of precedence:propositionChapter 5. Fuzzy Decision Making 90negation—‘;intersection fl;union U;(5.19)For example, Soc—lo means the component status is “lightly overloaded” (lo). Thisstatement may be interpreted in two ways. First, the statement may be assigned a “validity value” (say, 0.8). Then, under that particular circumstance, the level of validity ofthe statement is 80%. Alternatively, one could think about of a specific “measurement”,say e1 of the variable Soc. This measurement may represent a membership grade of0.8, as read off the membership function of lo. (i.e., 1L10(el) = 0.8). Under the samecircumstances, the statementS00—mo may be assigned another validity value (say 0.2).As before, then, the specific measurement e1 of Soc has a membership grade of 0.2 (or/.Lmo(ei) = 0.2). In summary, a given fuzzy-logic statement may possess a particularvalidity value under a specific circumstance, or alternatively, the membership grade atwhich the measurement belongs to the fuzzy set in that statement also would be equalto the validity value. In this manner, a given circumstance will satisfy different fuzzystates at different validity values, or equivalently, a given measurement will have differentmembership grades in different state sets (the latter being known as “fuzzification” ofa measurement). As an example, a component robotl whose workload is 60% of its fullcapacity can be fuzzified to:S0bt1 = {lu(0.4),mu(0.6)}A general representation for component status S is= {m(u)} (5.20)Chapter 5. Fuzzy Decision Making 91The ith proposition “S is mi” has a membership grade valueiim(Sc) = (5.21)The proposition set is expressed by:= {w—m()} = {p(tj)} (5.22)with(5.23)Note that the notation of calligraphic letters represent proposition sets. Using thisconvention, the status of robot 1 can be expressed asSrobotl = {Wrobotl_’ lu(O .8), Wrobotl4mU(O. 2)}Members in the above set are propositions of the status of the component robot 1 withassociated validity values.5.3.2 Compound PropositionsFor both sharing and releasing of components, at least two components should be considered. For example, component status of robot 1 and robot2 are factors that should beconsidered for load transfer between the two components. The compound proposition“status of robotl and status of robot2” is therefore taken into account, which is expressedbySrobotl flS1002.It may be expressed in a Catesian product space with dimensions of Srobotl and Srobot2The elements in the space represent a status of the FPS by considering only the statusof robot 1 and robot2.Chapter 5. Fuzzy Decision Making 92Generally a fuzzy state is given by an expression of fuzzy variables, which representsystem-status factors. A fuzzy-status expression may have the following four forms:1. Expr : Single fuzzy variable;2. Expr : -‘Expr;3.Expr : ExprflExpr;4. Expr : Expr U .Expr.(5.24)These are elaborated below:Case 1: Here, the expression is a single fuzzy variable X, given by the fuzzy setX = {si(p’:)}i=i,...,r (5.25)Then, the fuzzy status X is expanded as a set of propositions with the validity values,X = (5.26)where, the statementm = X—.s2 (5.27)has a validity value j in a particular situation. Equivalently, if the situation is givenby a “measurement” i, then its membership grades in the various fuzzy state variablesm2 are given by imi() = ; i = 1,2,•• ,r. (j rather than IImj(ffi), is used in laterrepresentations for simplicity. Note that is defined in the interval [0, 1]). Here, r isthe resolution [7] of a fuzzy set representing variable X; s is the ith fuzzy state of thisvariable; and p may be interpreted as either a validity value of m, or the membershipgrade of a measurement within a fuzzy state set as discussed before.Chapter 5. Fuzzy Decision Making 93Case 2: The negation is a unitary operator. It sets every proposition of theoperand to its “complement of 1”, specifically, ifX = (5.28)then,= (5.29)where,m = —‘mi (5.30)with,(5.31)Case 3: The intersection fl is a binary operator. Its result is represented in theCartesian-product space having the dimensions of the two operands. Specifically, ifX = {mi()}ii,...,r (5.32)and,Y = (5.33)then,X fl 32 = {m’j(p’)}i,...,r; _i,...,p (5.34)where,m7=mflm (5.35)with,4 = min{tj, 4} or 4 = . (5.36)depending on whether the mm or the dot interpretation is used.Chapter 5. Fuzzy Decision Making 94Case 4: The union U is also a binary operator. Its result is also represented inthe Cartesian-product space having the dimensions of the two operands as in case 3.Specifically, ifX {m(tj)}j=i,...,r (5.37)and,(5.38)then,X U Y = (5.39)where,m = m U m (5.40)with,= max{,} or = min(1u+ 4, 1) (5.41)depending on whether the max or the “bounded sum” interpretation is used.For example, consider the two standard components robotl, robot2. Suppose thattheir workloads are about 125% and 50% of their full capacity, respectively. They areevaluated to have the following status, according to the membership functions shown inFigure 5.2.Srobotl = {lo(0.75), mo(O.25)};Srobot2 = {lu(0.85), mu(0.85)};Then the proposition sets are:Srobotl = {Sroôoti_-lO(0.75), Sroboj1—mo(0.25)};8robot2 {Srobot2_+lu(0.85), 700t2—mu( .85)};The compound proposition of intersection of the two components is:Chapter 5. Fuzzy Decision Making 95S7060e1 F’ $robot2={ Sro,otilO fl Sro,,ot2—lu(0.75),Srooti—’lO fl Sroot2—mu(0.75),Srobotl—.mo fl Srobot2+lU(0.25),S0bt1—mo fl Srobot2--mu(0.25)}.Here, the elements tell the membership degrees of the composed status. For example,the first element means the validity degree of the statement of “robot 1 is lightly overloaded and robot2 is at light undercapacity”, or the membership grade of the compoundproposition for the specific measurements of S0bt1 and at that particular status,is 0.75. The entire space represents the status of an FPS by considering the factorsS70b0t1 and Elements in this space represent all possibilities of the system status.Any situation can be represented by this base using different degrees, which actually is ahypersurface in an n + 1 dimensional space (n variables and an extra dimension for thevalidity value or membership grade).To develop a procedure for the computation of compound propositions in Prolog, thefollowing operators are defined for use with fuzzy logic operations.op(300,xfy,’—). %attribute of an object.op(35O, xfy,—). %fuzzy proposition.op(400, fy,—‘). %fuzzy negation.op(45O,yfx, n). %fuzzy intersection.op(500,yfx, U). %fuzzy union.op(550, xfx, —*). %fuzzy implication.op(600, xf, with ). %rule belief.Chapter 5. Fuzzy Decision Making 96Here, op(P, R, N) defines an operator N at the level of precedence P and associatedoperand relation R. In R, f stands for the operator, and x and y stand for the operands,where x means it may contain only operators of lower precedence than that of f, and ymay contain operators of the same level of precedence of f. Note that, operator symbolsmay be changed in actual coding. Here only the logic relations are shown.Then, a compound situation of component status may be implemented by the predicate .situatiorz.(E, 8) in which E is a fuzzy expression and $ is the evaluated situationset..situatiori(O X, S) ÷—holds(O,X,FS),expand(O X, FS, S)..situation(-iX, S) —3itUation(X, Si),expand.not(Si, S).situation(X fl Y, S) —.situation(X, Si),.situation(Y, S2),expand..and(Si, S2, S).situation(X U Y, S) —.situation(X, Si),situatio’n(Y, S2),expand.or(Si, S2, S).The predicates: expand, exparid.not, expand.and, expand_or, are implementationsof the four cases discussed in equations (5.26), (5.29), (5.34), and (5.39).Chapter 5. Fuzzy Decision Making 97The usage of this predicate is illustrated by considering the following example: Suppose that, there are two components with workloads given by:component(agvl, workstatus, [(mo, 0.8), (lo, 0.3)]).component(agv2, workstatus, [(hu, 0.5), (mu, 0.7)]).A query is issued for the situation by considering component status of agvl and agv2.?-situatiori(agvl wo’rk.status fl agv2 i-.. wo’rkstatus, 5).The answer would be:S =[(agvl warkstatus—mo fl agv2 warkstatus—hu, 0.5),(agvl workstatus—mo fl agv2 ‘—i warkstatus—mu, 0.7),(agvl workstatus—lo fl agv2 warkstatus—fhu, 0.3),(agvl warkstatus-+lo fl agv2 workstatus—mu, 0.3)]where, S is the expanded space with elements representing all the possibilities of thesituation.5.4 Knowledge Representation and ReasoningAfter recognizing the system status, a reasoning procedure has to be carried out througha set of rules (knowledge) in order to make a decision. A typical fuzzy-logic rule is of theform:IF situation THEN actionA rule base gives a mapping from a situation set to an action set, as denoted by(5.42)Chapter 5. Fuzzy Decision Making 98Then, for a given context (or situation) 5, the corresponding action set is obtained asA=RoS (5.43)where R= rule base; S = system situation represented in a situation space; == =mapping relation; o = composition operator; and A= an action set.An action set for restructuring is a set of crisp logic actions. The basic idea of fuzzydecision making is to evaluate all possible actions in the set and select the optimal one.For example, an action set of “load sharing” may contain:{sharing(visionl, vision2);sharing(visionl, vision4);sharzng(vzsion3, vision4)}.Note that only one action can be chosen at a time. The fuzzy decision maker evaluatesthe priority degree of every action according to the current system situation, and thenchooses the action with the highest assessment value, which comes from the prioritydegree and load transfer feasibility index.5.4.1 Rule BeliefGiven a particular situation, different people may make different decisions. It shouldbe clear that different people have different belief degrees in their decision-making rules.It is the belief degree that provides the possibility of learning, so as to make a betterdecision.In dealing with uncertainty, the membership grades of a fuzzy set and the belieffactors of a rule could be considered similarly. They represent the same concept: everystatement has a degree of belief; a membership grade represents a validity level of aproposition (fact) and a rule belief factor represents a confidence level of a rule. There isChapter 5. Fuzzy Decision Making 99no absolutely exact measure of situations in the world, and as a result, the recognitionof the world is fuzzy. Also, there is no absolute truth; human knowledge evolves throughlearning and modification. When a rule is used for making a decision, its belief degreeshould be considered so as to give a confidence degree to the decision.Consider the fuzzy-logic ruleIF A THEN B (5.44)The decision based on this rule will vary due to several factors [14].1. If the situation of A is different, then the decision will be different even if themembership functions of A and B are unchanged and the rule itself is unchanged.2. If the definition of the fuzzy variable A changes, then the decision will also changeeven if the system data that is measured by A is unchanged and also B and therule itself are unchanged.3. If the definition of the fuzzy variable B changes, then the decision will also changeeven if the other aspects (as in 1 and 2 above) are unchanged.4. If the validity of the rule itself changes, then the decision based on the rule shouldchange even if other aspects (as in 1, 2, and 3 above) remain unchanged.Note that in case 1, it is the “existing fact” (say A) about the situation that haschanged. This is not a case of “learning” however. In case 2, it is our understanding ofthe fuzzy variable A that has changed. This may be modeled by changing the membershipfunction of A (i.e., A(a)). This may result from learning, new knowledge, expert opinion,etc. In case 3, it is our understanding about the fuzzy variable B that has changed. Thismay be modeled by changing the membership function of B (i.e., uB(b)). This too mayresult from learning, etc. Finally, in case 4, it is the “level of belief” of the rule itselfChapter 5. Fuzzy Decision Making 100that has changed. The definitions of A and B and also the measurement of A mayremain unchanged. Here as well, the change may be a result of the learning of new facts,expertise, experience, etc. This may be modeled by assigning a “belief degree” to therule, which may be adjusted on the basis of new knowledge.Situation recognition (A(a)), and action set B (crisp logic) have been discussed for arestructuring system in the previous sections. The rule beliefs will be further addressedby using an illustrative example. Consider again the sharing match example in Section5.1. Suppose we have a rule base of the form:If X is lo and Y is hu then sharing(X,Y).If X is mo and Y is hu then sha’ring(X, Y).If X is lo and Y is lu then sha’ring(X, Y).We should be able to match Cl (lo) with C3 (hu) since we have such a rule inthe rulebase (rule 1). In actual decision making, however, it is better to match Clwith C4 (rule 3), which is at light undercapacity, and C2 should be matched with C3(rule 2). Clearly, the three rules do not have the same weights, and they actually havedifferent degrees of belief. We know that there would be a wastage of capacity if a lightlyoverloaded component is matched with a highly undercapacity component, and hence,this rule (rule 1) should be given a low belief degree. The other two rules will have higherpriority in the decision making process. Consequently, the correct result can be deducedfrom the modified rulebase as shown below:If X is lo and Y is hu then sharimg(X, Y) with belief 0.7.If X is ma and Y is hu then .sharing(X, Y) with belief 0.95.If X is lo and Y is lu then sharing(X, Y) with belief 0.9.To facilitate the use of the concept of “rule belief”, the following definition is given.Definition 2. A fuzzy rule is an implication from a composed fuzzy situation to anaction with a belief factor;Chapter 5. Fuzzy Decision Making 101R : p(EXP) —+ a with bf (5.45)where, with is defined as an operator having a precedence level higher than that ofimplication; p is a compound situation of a fuzzy expression EXF (a value of EXP); ais an action; and bf is the belief degree of the rule.For example, the rule base given above can be expressed asX-lo fl Y-+hu —+ sharing(X, Y) with 0.7.X-mo fl Y—+hu —* sharing(X, Y) with 0.95.X—lo fl Y-du —* .sharing(X, Y) with 0.9.The belief degrees might be changed consequently, as the operators or experts find thatthe rules need to be modified. A learning procedure may be implemented to automaticallychange the belief values based on new knowledge or information. (see Figure 5.1)Next, to elaborate how rule beliefs affect decision making, let us explore the combination of the membership degrees of facts (context) and rule beliefs in the reasoningprocess to make a decision.5.4.2 ReasoningAs discussed before, fuzzy decision making requires a combined consideration of themembership grades of the context variables (which depend on their membership functionsand current measurements) and rule beliefs. The objective is to select an action withhighest validity degree. The key point here is to decide the “validity degrees” of theaction set.In general, each composed proposition in a situation context is associated with oneor more actions (in the rule base). All associations with an action are counted togetherin determining the “validity degree” of this action.Chapter 5. Fuzzy Decision Making 102Definition 3. Fuzzy associative memory: All rules associated with an action arefired simultaneously, and will contribute their beliefs toward the overall validity degreeof the action. This is expressed asVD(a) = FAM(R(a) : BXP—*A) (5.46)where, VD(a) means the “validity degree” of an action a which is a specific value of theaction variable (action set) A; FAM stands for “fuzzy associative memory”, which is afunction that computes the “validity degree” from the rule base according to the currentsituation expressed by EXF (which provides the membership grades of the situation);and R(a) is the instantiation of the rulebase (R: EXF A), for the specific action a.FAM could be designed in two ways: “validity degree” (or “priority degree”) of anaction is either the maximum value or sum of contributions from all situation elementsthrough corresponding rules (See Figure 2.6). If the summation is used for FAM, the“max-mm” operation in equations (5.36) and (5.41) should be replaced by the “plus-dot”operation, for consistency. Figure 5.3 gives a decision making procedure for selecting anoptimal component pair for sharing or releasing.Note that, in Figure 5.3, the long arrows with bfs may be chains of rules obtained by aproof procedure, as well as direct rules. The decision making procedure is implemented bythe predicate deci.sion(E, A) which selects an action A with the highest priority degreefrom all possible actions according to the situation expressed by E and the installeddecision-making knowledge (rules):Chapter 5. Fuzzy Decision Making 103Membership Rule BeliefGrades Context ValuesValidity Degreeof an ActionFigure 5.3: Computation of the Validity Degree of Actionsdecisiom(E,-) 4—situaion(E, S),fam(S, A, VD),assessment(A, VD, V),V>0.5,assert(action(A, V)),fail.% computation of validity level.% set threshold value at 0.5.% store a might-be action.% find all possible actions.decision(., A) —optimaLaction(A),retractall(action(_, )).use the stored actions.where V > 0.5 sets a threshold value for the assessment level of acceptable actions.fam(S, A, VD) is the implementation of equation (5.46); assessment(A, VD, V) evaluates the action A by the assessment value V from its validity level and the feasibilityindex; and the optimal_action(A) selects an action A corresponding to the highest priority degree. These procedures are shown below:Chapter 5. Fuzzy Decision Making 104fam([], -, 0).fam([(EX, G)IT], A, VD) —EX —* A with BF,!, % find a rule.fam(T, A, VDT),VD is max(VDT, C * BF). % “max” may be replaced by plus.fam([1T], A, PDT)fam(T, A, FDT). % no rule, no contribution.Here, if there is a rule that matches a situation proposition, than the rule is fired.Its belief value BF is multiplied by the validity value G of the situation proposition,and contributed to the validity degree VD of action A according to the fuzzy inferencemethod. If there is no rule for the current situation proposition, the VD of the action isretained for further firing rules. The end condition is that the situation space is empty,which corresponds to zero validity value.optimaLactiorz.(A) —findall(X, actiori(X,.), As),best(As, A,.).Now an example is given to illustrate the decision making process. Suppose that wehave a database in the blackboard of FPS component status.Chapter 5. Fuzzy Decision Making 105component(v’isioril, workstatus, [(hu, 0.8), (mu, 0.3)]).component(vision2, wo’rkstatus, [(lu, 0.9), (mu, 0.1)]).component(vision3, work.status, [(mu, 1.0)]).component(vision4, warkstatus, [(hu, 0.8), (mu, 0.3)]).component(robotl, wo’rkstatus, [(hu, 0.6), (mu, 0.4)]).component(robot2, warkstatus, [(lu, 0.9), (mu, 0.1)]).component(robot3, workstatus, [(mu, 1.0)]).component(rabot4, workstatus, [(mu, 1.0)]).component(agvl, workstatus, [(lu, 0.8), (mu, 0.2)]).component(agv2, workstatus, [(hu, 0.7), (mu, 0.3)]).compoment(agv3, workstatus, [(ma, 0.7), (lo, 0.3)]).component(agv4, workstatus, [(ma, 0.7), (lo, 0.3)]).component(agv5, workstatus, [(hu, 0.7), (mu, 0.3)]).component(agv6, workstatus, [(lu, 0.8), (mu, 0.2)]).Here, for example, agv3 is overloaded, and a component is sought for sharing. Theaction set is:{sharimg(agv3, C)}CEAGVwhere AGV is a group name. This can be accomplished by the query:?-decisiom(agv3 warkstatus fl C wo’rkstatus, sharing(agv3 , C)).C = agv5Note that the “plus-dot” operation (of fuzzy logic) is applied in this decision maker.All possible actions can be observed by examining the dynamic database “action/2”. Forexample:Chapter 5. Fuzzy Decision Making 106action(sharing(agv3, agvl), 0.60).action(sharing(agv3, agv2), 0.65).action(sharing(agv3, agv5), 0.65).action(sharing(agv3, agv6), 0.60).The data in the blackboard will be modified once the selected action is executed. Anew decision will be made based on a new database.5.5 SummaryThis chapter presented a decision making method for selecting an optimal action in thethird level of the restructuring system. A structure was discussed in which two stepswere considered: situation recognition and rule synthesis.Fuzzy logic was used for representing the component status. A general method forsituation representation was presented and implemented in Prolog. In decision making,all rules associated with an action were fired simultaneously. The combined considerationof situation validity level and rule belief have been employed in the assessment of anaction. The action with the best assessment value (which is a product of the priorityvalue and the feasibility index) was selected as the final decision.Chapter 6Implementation and Case StudyThus far in the thesis, the methodology of knowledge-based restructuring of a flexibleproduction system has been developed. The present chapter will give some practicalapplications of the developed approach.Section 6.1 will describe a model of an automated fish processing plant, which is introduced here as a case study. Section 6.2 will discuss some implementation problems,and give a panorama of problem solving. In the remainder of the chapter, several restructuring cases will be given, in which the simulation results will be graphically illustrated.Finally, a short summary of the chapter will be given.6.1 A Fish Processing SystemFigure 6.1 shows a model of an automated fish processing plant. There are three workcellsin the system: a fish head cutting workcell, a fish grading workcell, and a packagingworkcell which have three types of interchangeable component: vision stations, robots,and AGVs (Automated Guided Veicles). It is assumed that the processing activity levelof each workcell is determined by the components of these types. In other words, thecapacity of the above mentioned components is a bottleneck for the production activityof the plant. Under normal production conditions, the components are assigned to theworkcells as follows:• Cutting workcell: Visioni, Vision2, Roboti, AGV2, AGV5;107Chapter 6. Implementation and Case Study 108Task demands and component loads:Robot AGV Vision ComponentStaon ShiftIL1/4Component Current Capacity LoadUndercapacity Load Shortage TransterVision lVision 4 Robot lACy 5 AGV 2 CvhngDemandVi&on2 Robot 2 AGV3AGV4 GradingDemandVision 3Robot 3Robot 4 AGV I AGV S PackagingDemandFPS configurations:1’I IC) Cutting (Z)MachineiIf’_ ( \1a__;“3á 4_II Packaging IMachine IflHiIHiI IIIILIL[LiIii1flFigure 6.1: A Model of a Flexible Production System (FPS)Chapter 6. Implementation and Case Study 109• Grading workcell: Vision4, Robot4, AGV1, AGV6;• Packaging workcell: Vision3, Robot2, Robot3, AGV3, AGV4.The normal operating conditions, which may be considered as the initial stage forrestructuring, is illustrated by the chart of Figure 6.1, in which, the dotted and the solidareas indicate the capacity and the load, respectively, of a component. The componentloads are assigned according to the process demand (task demands) by the load planner.The demand levels are assigned to be 100% in this stage of normal operation, as shown inthe figure. Therefore, the loads in the normal production stage are actually representativeof the load planning factors.6.2 Implementation and Operation of the Restructuring System6.2.1 Rule BasesIn the fuzzy decision making level, rulebases of load sharing and component releasingare given in an object level, which means that the rules are designed separately from thedecision making procedure. The rule base of load sharing is represented as:Chapter 6. Implementation and Case Study 110OC—ho fl UC-+na —* .sharing(OC, UC) with 0.9.OC-ho fl UC-hu —* sharing(OC, UC) with 1.0.OC—ho fl UC-mu —, sharimg(OC, UC) with 0.9.OC-ho fl UC-+lu —* sharing(OC, UC) with 0.7.OC-mo fl UC-ina —* sharing(OC, UC) with 0.9.OC-mo fl UC-Jiu —* sharing(OC, UC) with 0.9.OC-mo fl UC—÷mu —* sharing(OC, UC) with 0.7.OC-mo fl UC-lu —* sharing(OC, UC) with 0.7.OC—lo fl UC-+na —, sharing(OC, UC) with 0.6.OC-1o fl UC—+hu — sharing(OC, UC) with 0.6.OC-lo fl UC—mu —+ sliaring(OC, UC) with 0.7.OC-lo fl UC-lu —* sharing(OC, UC) with 0.7.Note that there are two preconditions for the rules: 1. OC UC; 2. OC and UC areof a same type. There are several methods to check the preconditions, one of which is tocheck the two components before calling the rule, another one is to add the preconditionsas bodies of the rules in Prolog. The rulebase for component releasing is shown below:UR-hu fl UL—hu —* releasimg(UR, UL) with 1.0.UR-hu fl UL-mu — releasing(UR, UL) with 0.9.UR-hu fl UL-lu —, releasing(UR, UL) with 0.7.UR-mu fl UL-hu —+ releasing(UR, UL) with 0.7.UR-mu fl UL—mu —* releasimg(UR, UL) with 0.6.UR-mu fl UL-lu — ‘releasing(UR, UL) with 0.6.UR-lu fl UL-hu —* releasing(UR, UL) with 0.6.UR—lu fl UL-+mu —* releasing(UR, UL) with 0.6.UR—lu fl UL-lu —* releasing(UR, UL) with 0.6.Chapter 6. Implementation and Case Study 111The same preconditions apply here. Note that, the component property in the aboverules is implicitly “the component status”.6.2.2 Separation of Knowledge from Reasoning ProcedureAs the rule bases show, the knowledge about dynamic restructuring is represented independently of the use of the knowledge which is implemented by the inference engine, forexample, fuzzy associative memory (fam). The same is true of the knowledge sourcesand the control unit in the first-level decision making; and also the heuristics and thesearch drive restructuring in the second level. This kind of separation has the advantagesthat the system could be expanded easily, and the reasoning procedure could be modifiedfor different requirements. The fact that the knowledge is represented in a descriptivemanner makes the knowledge-based system quite different from conventional programs.6.2.3 Panorama of RestructuringRestructuring begins at the first level (Figure 3.1) by checking the system status anddeciding whether to call for a restructuring action. Basically, the blackboard system isactivated by the changes of data which typically are a change in the task demand or achange in the status of FPS operation. These changes usually trigger the load distributingand system evaluating knowledge sources, so as to update the current component loads,load-transfer feasibility indices and component status. Any of these data changes willdefinitely call for a check to determine the possibility of restructuring.Selecting an action is a procedure of search. Due to complexity of the problem andfuzziness of the final goal, normal search methods are not practical here. Heuristics aredeveloped, which trim the search space, and limit the search space to only one kind ofactions at a restructuring stage. For actions (of the same kind) in a trimmed space, afuzzy decision maker provides the optimal decision.Chapter 6. Implementation and Case Study 112After an action has been selected, the load to be transferred in the action will bedetermined. Then the action is executed, and the corresponding sharing and releasingrelations will be recorded. This execution may make further changes in the blackboard,and in turn trigger some more knowledge sources, and the control will return to theblackboard (the first level).This cycle repeats until the decision maker failed to pick an acceptable action. (Athreshold of assessment value should be set for actions.) In this case, a reporting procedure (KS of “output”) will be called. If there is no component overloaded, the system isdesirable. This may mean to satisfy two conditions: 1. no component is overloaded; undercapacity pair could provide a component release — components work close totheir full capacity. Consequently, the system restructuring succeeds. If there is still anoverload, clearly, the restructuring has failed. To show the practical application of theapproach, some restructuring case studies will be considered in the following sections.6.3 Restructuring Due to Change of DemandAny change to the demands causes the KS of “Load Planning” to trigger. This KSwill be executed in the subsequent control cycle. It will then change the blackboards of“Workcell Information” and “Component Information”, which will trigger the knowledgesources of “Updating of Sharing Feasibility” and “Restructuring”. Due to the presetpriorities, the KS of “Updating of Sharing Feasibility” will be fired first to modify theBB of “Sharing Feasibility”. After all the presettings are made, the FPS will be restructured according to the information in the blackboard. The KS of “Restructuring” maychange the blackboards of “Workcell Information” and “Component Information”, andalso may post restructuring commands on the blackboard. Restructuring feasibility willbe checked. The change in the information about the workcells and components mayChapter 6. Implementation and Case Study 113trigger some knowledge sources to confirm that the load has been properly distributed.The change of restructuring commands will trigger the output KS. Finally, the systemwill become idle again, for steady operation of the FPS.As an example, suppose that the cutting demand drops by 40% due to a reductionin the raw material supply, (say at the end of a fishing season), and the grading demandis increased by 50% in order to reduce an existing backlog. Only the fish of high gradeare packaged, and the low grade fish may be used for canning. Therefore, suppose thataccording to the current market demand, the packaging load is maintained at the previouslevel.The conditions due to these changes in task demand are shown as “Phase II Transition” in Figure 6.2. Clearly, Robot2, AGV3, and AGV4 will be overloaded, resulting ina capacity shortage. Also Visionl, Vision4, AGV2, and AGV5 now operate well belowtheir full capacity. The component status is updated as follows:component(robot4, workstatus, [(lu,1)]).component(visionl, workstatus, [(mu,O.8),(hu,O.6)]).component(vision4, workstatus, [(mu,O.8),(hu,O.6)]).component(robotl, workstatus, [(lu,O.8),(mu,1)]).component(agv2, workstatus, [(mu,O.8),(hu,O.6)]).component(agv5, workstatus, [(mu,O.8),(hu,O.6)]).component(vision3, workstatus, [(ok, 1)]).component(robot3, vorkstatus, [(ok, 1)]).component(agvl, workstatus, [(ok,1)]).component(agv6, workstatus, [(ok,1)]).component(vision2, workstatus, [(ok,1)]).component(robot2, workstatus, [(io,i)]).Chapter 6. Implementation and Case Study 114Phase I:AGV VW CcopcmtSttk. 521*I :i ,‘Con41enl CU.Te Cpfty LoadCapacy Lo Sht2g2 Traf2rV1 Y4 P.Obd I AGVS SV2 Cdli,.Q 0I111.2 fl212 AGVI*GV*rj;::j ijIJjjfl[Csw,3 Mdli! R.2214 CCVI CCCIPkagingM.hina\I i:j::j ,)(lion! R*bol! Mobolli CCVI CCVI Pod.g..gPhase Transition: (cutting -40%, grading +50%, packaging 0%)tiinii1111TLCdo.II,,* RObot ¶ MCVI CMVI Cot,.’. Vii,, 2 RObot I CCV S AGVA ClOut,1o I Grodi.9“‘ ‘.J’ Mot1non ]j iPhase III: (Restructrured)I Pk.gk,gMet[1h1flJfl[LflJfliM.o,,l Roboll AliVe Oh,0 %tootI2 Robot! MCVI nOVA AMY!,Domed D.’o.’,d(.,,b.•g1,2 (i_____(+ +MhiOfl I Robot S Robot A CCVI CCVI P.C..go,gI PekCinFigure 6.2: A Case Study: the Simulation of a Demand ChangeChapter 6. Implementation and Case Study 115component(agv3 workstatus, [(mo,O.75),(lo,O.25)]).component(agv4, workstatus, [(mo,O.75),(lo,O.25)]).This representation uses the predicate component which is declared in Section 3.The value of the workstatus is a fuzzy set. For example, [(mo, 0.75), (lo, 0.25)] incomponent(agv4, workstatus, [(mo, 0.75), (lo, 0.25)]) means agv4 is moderately overloaded(mo) with a belief degree of 0.75, and lightly overloaded (lo) with a belief degree of 0.25.Sharing feasibility is checked for pairs of component in a group of sharable components. Here, factors such as component reliability, geographical position of the components, and operating cost, will be considered. The following feasibility matrix is usedhere:roboti robot2 robot3 robot4roboti 0.00 0.92 0.90 0.81robot2 0.92 0.00 0.95 0.85robot3 0.90 0.95 0.00 0.90robot4 0.81 0.85 0.90 0.00The matrix gives the feasibility values of sharing workloads between pairs of robot.An example is that the feasibility value of sharing a workload between robot 1 and robot2is 0.92 in a scale of [0, 1].Now, the KS of “Restructuring” is triggered. The following are some intermediateresults showing the decision making procedure:(1). Component releasing action.FIND undercapacity components of vision: [visioni ,vision2,vision3,vision4]To find all possible actions for visioni within workcells.action: releasing(visionl ,vision4)Chapter 6. Implementation and Case Study 116priority= 0.538feasibility = 0.9assessment = 0.48To find all possible actions for vision2 within workcells.To find all possible actions for vision3 within workcells.To find all possible actions for vision4 within workcells.action: releasing(vision4,visionl)priority= 0.538feasibility = 0.9assessment = 0.48The best action is releasing(vision4,visionl); assessment = 0.48This action can be executed!Load (transferred) for action releasing(vision4,visionl) is: 36.0*** execute action:releasing(vision4,visionl)Here, the procedure shows how the restructuring planner makes a decision usingthe heuristic of releasing a component within a workcell. A group of undercapacityvision stations is found, and then the possible actions of releasing a vision station areassessed. This is done by mutipling the sharing feasibility value by the priority value,which is obtained by using the technology “fuzzy associative memory”. A thresholdvalue that is appropriate for this type of actions is 0.4. Note that, the threshold valuedepends on the definition of membership function of priority. Finally, an action will beselected for executing, if its assessment value is higher than the treshold. In this case,the releasing(visiom4 , visionl) is chosen. The load of the to-be-released component willbe transferred to the other one.(2). Component sharing action.Chapter 6. Implementation and Case Study 117FIND all overloaded components of robot: [robot2]To find all possible actions for robot2 between workcells.action: sharing(robot2, 1)priority = 0.4feasibility = 0.92assessment = 0.368action: sharing(robot2 ,robot4)priority = 0.4feasibility = 0.855assessment = 0.342The best action is sharing(robot2,robotl); assessment = 0.368This action can be executed!Load (transferred) for action sharing(robot2,robotl) is: 20.0*** execute action: sharing(robot2,robotl)This is similar to the decision making process that was used for component releasing.The differences are: 1. The threshold is set to a much lower value (here, it is 0.2), becauseany overloaded component should be shared; 2. The load to be transferred is determinedby the work status of both components.Similar procedures are used for other actions. At the end, none of the actions will beexecuted since their assessment values would below the threshold value. Then the plannerwill check the blackboard, calculate the cost function, and report the restructuring result:PLANNING RESULTplan: releasing(vision4 ,visionl)plan: releasing(agv5 , agv2)plan: sharing (robot2 ,robot 1)Chapter 6. Implementation and Case Study 118plan:shifting(agv5,from(cutting) ,to(grading))plan: sharing(agv4 , agv5)plan: sharing(agv3 ,agv5)Restructuring succeeds; The cost function is: J0.729.The final result of restructured system is illustrated as Phase III in Figure Restructuring Due to Change of Sharing FeasibilityAn example is given now to show how the feasibility values can affect the restructuringresults. The same three-workcell fish processing system as in the previous case study, andthe same initial (normal) operating conditions are used here. This time, however, supposethat Robot 1 is partly damaged (say, its network-communication system is operating at areduced speed). Consequently, its sharability is assumed to be reduced, as shown in thefeasibility matrix below:roboti robot2 robot3 robot4roboti 0.00 0.28 0.27 0.24robot2 0.28 0.00 0.95 0.85robot3 0.27 0.95 0.00 0.90robot4 0.24 0.85 0.90 0.00The feasibility change is considered when the planner selects a robot for sharing theload of Robot2. The decision making procedure is outlined below:FIND all overloaded components of robot: [robot2]To find all possible actions for robot2 between workcells.action: sharing(robot2 ,robotl)priority = 0.4Chapter 6. Implementation and Case Study 119feasibility = 0.276assessment = 0.11action: sharing(robot2 , robot4)priority = 0.4feasibility = 0.855assessment = 0.342The best action is sharing(robot2,robot4); assessment = 0.342This action can be executed!Load (transferred) for action sharing(robot2,robot4) is: 20.0*** execute action: sharing(robot2 , robot4)The above procedure is quite similar to the previous one, but with a different result,since the sharing feasibility of the pair (robot2, robotl) has been reduced. As a result,the second action, .sharing(robot2, robot4), is chosen instead of sharing(‘robot2, robotl).The final result is shown in Figure 6.3, and the output is given below:PLANNING RESULTplan:releasing(vision4,visionl)plan: releasing (agv5 , agv2)plan: sharing (robot2 , robot4)plan: shifting(agv5 ,from(cutting) ,to (grading))plan: sharing(agv4 , agv5)plan: sharing(agv3 , agv5)Restructuring Succeeds; The cost function is: J0.777.The higher value of the cost function for this second case is justifiable in view of thedegraded performance of a workcell component. Also, note that the final outcome (PhaseIII of Figure 6.3) now is somewhat different from what was realized in the previous caseChapter 6. Implementation and Case Study(‘?_EE +,ts__I I:L_)pit AGV l/talon CponentStation shiftCernponent Current Capacity LoadCapacity Load Shortage TransferthU1V&onleamt* O.bOIIA005 *002 CU*,gPhase II Transition: (cutting -40%, grading +50%, packaging 0%)ttiLIjLjJIj[I[I1014012 Robot? AGO) AGV* 0,0*119 0*0110 Robots 00*014 *001 01002 P1010)11)0andtiiiiil 1111111SOlon Robot loGy, *004 *000 01.0100 VoanO Robots 50*00* *001 *00)tii• iiVeal, 00*001 01405) 01000s___ ___EL +) I— i,) I — I ,120Phase I:tiV00t101D0114 000001*000 0140*? 0400)0.11)1*7pn0p‘rtii[Li1111111Roan? Robot? 0*03*004 01.* 9.000 Robot? 50000* *0010 *00)I Pankagootdaul*oe— 2_____EL +)-- --,Phase Ill: (IRestructrured)1?‘I PachigingMaeStRo-/11Figure 6.3: A Case Study: the Simulation of a Change of Sharing FeasibilityChapter 6. Implementation and Case Study 121(Phase III of Figure 6.2) for the same starting and transition conditions, which is a directresult of the change in feasibility parameters of component sharing.6.5 SummaryA full view of restructuring of a flexible production system was given, which explainedthe mechanism of decision making of dynamic restructuring. Computer simulations weregiven to demonstrate the application of the method to a fish processing system. Whatshould be particularly mentioned is that, since the fuzziness of a goal was introduced, therestructuring system acquired some tolerance to non-desirable situations, so as to avoidtoo frequent restructuring.Chapter 7Conclusions and Future WorkThis chapter will give a summary of the thesis. The main contribution of the research willbe highlighted. It will also indicate some possible work for future study on the presenttopic.7.1 ConclusionsA novel method for use in the high-level automation of production systems— dynamicrestructuring of flexible production systems — has been developed in this thesis. Theproblem has been formulated as one of reassociating components to workcells, in order todeal with changes in system operating conditions. Uniformity and optimality of processoperation is targeted in this manner, through system restructuring. The fuzziness of arestructuring goal, which results in multiple solutions, is particularly emphasized. Thisfeature determines the use of data-driven proofs and the requirement of optimization inproblem solving.A three level decision making system is proposed by considering fuzziness, complexityand non-analytical nature of the problem. The problem solver makes programmaticdecisions and detailed decisions in different levels, thereby making the system direct,reliable, somewhat modular, and capable of utilizing different methods of knowledgerepresentation and reasonings.The first level adopts a blackboard architecture, in which different types of knowledgesources are employed for updating of system information, evaluation of system status122Chapter 7. Conclusions and Future Work 123and decision making for restructuring. The independence of knowledge sources providesa dexterity or flexibility in knowledge representation, and enables the use of variousreasoning methods. Therefore, the system is readily extendable and maintainable. Themechanism of opportunistic reasoning is quite helpful in coping with complexity andvariety of system operating conditions.Heuristics for different cases are developed in the second level in which an inferenceengine directly applies heuristics, according to their order of priority.The third level makes the most detailed decisions on selecting a specific action usingfuzzy sets and associated technologies. Both the system status and the restructuringknowledge (rules) are evaluated with respect to a validity degree or belief value. Thefuzzy decision making is based on the assessment of actions which uses techniques offuzzy associative memory.Knowledge is represented separately from the reasoning procedure which uses thatknowledge. Also, different reasoning strategies are employed for different cases. Blackboard system provides opportunistic reasoning so as to adapt the system to various,unexpectable events. In the second level of decision making for restructuring, an orderedsearch is quite suitable. This method, together with the third-level decision making, givesa practical and somewhat optimal approach in selecting actions for system restructuring.The dynamic restructuring system has been implemented in Prolog. Case studieshave been presented that applies the technique to a flexible fish processing system, incomputer simulation. The results were found to be quite encouraging.7.2 Main ContributionsThe main contribution of the research is in the development of a new technique that willassist in high-level automation of flexible production systems. In particular, a techniqueChapter 7. Conclusions and Future Work 124for dynamic restructuring of flexible production systems has been developed. From themethodology development to detailed implementation, the thesis emphasizes on emulation of human problem solving through the means of advanced technologies in artificialintelligence, control engineering, and fuzzy logic. In particular, the following contributions have been made:1. Formulated and represented the dynamic restructuring problem;2. Developed or identified proper problem solving methods, by considering specialcharacteristics of the problem;3. Developed a problem solving architecture;4. Successfully adopted blackboard techniques to the dynamic restructuring problem;5. Abstracted effective heuristics for the restructuring problem;6. Designed a fuzzy decision making system for the restructuring; and7. Implemented the developed techniques through computer simulation of an industrial process, demonstrating their use in high-level automation.7.3 Future WorkNot addressing the complement research on related knowledge sources (KS), such assensing and capacity planning, the developed approach for dynamic restructuring stillneeds to be improved in several ways.A learning mechanism could be used for training rule belief values for better decisionmaking in selecting a proper action. A basic idea would be to give a full set of rulesin which those practically impossible (to human) rules are initially assigned zero beliefChapter 7. Conclusions and Future Work 125degrees. Therefore, adding rules and retracting rules may be incorporated as changes inbelief values. Fuzzy neural networks could be employed for this purpose.Since fuzzy membership functions are represented as trapezoids (see figure B.1) byspecifying the four corners in the form of a list in Prolog, it is difficult to have a universalrepresentation of arbitrary membership functions in this format. Fuzzy logic operationscould be represented in C code to avoid this limitation of Prolog.System integration is another major project which has to be carried out in any practical implementation of the approach. Component sharings should be scheduled properly,and hand-shaking signals and other communication should be well planned and designed.The transfer of the developed technology to appropriate industries is also an importantaspect of this research, which needs to be carried out.Bibliography[1] Aström, K.J. and B. Wittenmark, (1989), Adaptive Control, Addison-Wesley, Reading, Mass.[2] Bench-Capon, T.J.M., (1990), Knowledge Representation: an Approach to ArtificialIntelligence, Academic Press, San Diego, CA.[3] Campbell, J.A. and J. Cuena, (1989), Perspective in Artificial Intelligence, EllisHowwood Ltd, GB.[4] Chang, T.C., (1990), Expert Process Planning for Manufacturing, Addison-WesleyPublishing Company.[5] Chryssolouris, G., M. Dpmroese, and P. Beaulieu, (1992), Sensor synthesis for control of manufacturing processes, ASME Trans. Engineering for Industry, Vol. 114,ppl58.[6] de Silva, C.W., A.G.J., MacFarlane, (1989), Knowledge-Based Control with Application to Robots, Springer-Verlag.[7] de Silva, C.W., (1991a), Fuzzy information and degree of resolution within thecontext of a control hierarchy, Proc. IEEE IECON’91, Vol.2, pp1590-95[8] de Silva, C.W., (1992), Research laboratory for fish processing automation, International Journal of Robotics and Computer-Integrated Manufacturing, Vol. 9, pp49-60.[9] de Silva, C.W., (1993a), Soft automation of industrial processes, Engineering Applications of Artificial Intelligence, Vol. 6, pp. 87-90.[10] de Silva, C.W., (1993b), Knowledge-based dynamic structuring of process control systems, Proc. Fifth International Fuzzy Systems Association World Congress,Seoul, Korea, Vol.11, pp1137-40[11] de Silva, C.W., (1993c), Hierarchical processing of information in fuzzy logic controlapplications, Proc. 2nd IEEE Conference on Control Applications, Vancouver, BC,Vol.1, pp. 457-461.[12] de Silva, C.W., and J. Gu (1994), An intelligent system for dynamic sharing ofworkcell components in process automation, Engineering Applications of ArtificialIntelligence (In Press).126Bibliography 127[13] de Silva, C.W., (1994a), Intelligent Control: Fuzzy Logic Applications, CRC Press,Boca Raton, FL. (To be published).[14] de Silva, C.W., (1994b), Automation Intelligence, Engineering Applications of Artificial Intelligence, Vol.7, 1994 (In Press).[15] Dubois, D. and H. Prade, (1980), Fuzzy Sets and Systems. Academic Press, Orlando,FL.[16] Engelmore, R.S. and T. Morgan (1988) (eds), Blackboard System, Addison-Wesley,Reading, Mass.[17] Fayyad, K.E. and R. Kass, (1991), Task dependency modeling to support assemblyplan design, Proc. IEEE 7th Conference on Al Application, pp2i2-2i6.[18] Ceorgeff, M.P. (1987), Planning, in J. Allen, J. Hendler and A. Tate (eds), Readingsin Planning, Morgan Kaufmann, San Mateo, CA, 2:359-400.[19] Gruver, W.A., (1994), Intelligent robotics: an applications overview, IEEE Trans.on Industrial Electronics, Feb. 1994.[20] Cu, J. and C.W., de Silva, (1994a), A procedure for dynamic sharing of components in multiple-workcell process plants. Proc. 199 American Control Conference,Baltimore, MD, Vol. 1, pp. 289-93.[21] Cu, J. and C.W. de Silva (1994b), Dynamic restructuring of flexible productionsystems. Proc. IFAC Symp. on Intelligent Components and Instruments for ControlApplications , Budpest, Hungry, pp.71-76.[22] Cu, J. and C.W. de Silva (1994c). Fuzzy decision making in variable-structure controlsystems. Proc. ASME’94 Congress, Chicago, IL. (In press).[23] lizuka, Y. and H. Tsuji, (1988), A computer system configuration design expertsystem: IDEA/C, Proc. International Workshop on Al for Industrial Application,pp442-447.[24] Jaeschke, R., (1993), C++ : An Introduction for Experienced C Programmers, CBMBooks, Horsham, PA.[25] Jagannathan, V., R. Dodhiawala and L.S. Baum (eds) (1989), Blackboard Architecture and Applications, Academic Press, Boston.[26] Janko, W.H., M. Roubens, and H.J. Zimmermann, (eds) (1989), Progress in FuzzySets and Systems, Kiuwer Academic, Boston.Bibliography 128[27] Kosko, B., (1992), Neural Networks and Fuzzy Systems: A Dynamic Systems Approach to Machine Intelligence, Prentice Hall, Inc., NJ.[28] Kosko, B., (1993), Fuzzy Thinking : The New Science of Fuzzy Logic, Hyperion,New York.[29] Kovacs, G. and I. Mezgar, (1991), Expert systems for manufacturing cell simulationand design, Engineering Application of Artificial Intelligence, Vol.4, pp417-24[30] Leong, K.T., S.K. Sim, and Y.W. Chan, (1991), BESMED: a blackboard knowledge-based approach to integrate mechanical design, Engineering Application of ArtificialIntelligence, Vol.4, pp205-20[31] Levesque, H.J., (1986), Knowledge representation and reasoning, in Annual Reviewof Computer Science, 1:255-87.[32] Luger, C.F. and W. A. Stubblefield, (1992), Artificial Intelligence : Structures andStrategies for Complez Problem Solving, Benjamin/Cummings Pub. Co., Redwood,CA.[33] Newell, A., (1962), Some problems of the basic organization in problem-solvingprograms, Proceedings of the Second Conference on Self-Organizing Systems, pp393-423, Spartan Books.[34] Nicholson, H., B.H., Swanick, (eds) (1985), Self-Tuning and Adaptive Control: Theory and Applications, Peter Peregrinus Ltd, New York.[35] Pang, G.K.H, (1989), A blackboard system for the off-line programming of robots,Journal Intelligent Robotic Systems. Vol. 2, pp. 425-44.[36] Pang, G.K.H, (1991), A framework for intelligent control, Journal Intelligent RoboticSystems. Vol. 4, pp. 503-12.[37] Pau, L., (1989), Knowledge representation approaches in sensor fusion, Automatica,Vol. 25, pp. 207-14.[38] Poole, D., A. Mackworth, and R. Goebel, (1993), Computational Intelligence : ALogical Approach, Department of Computer Science, University of British Columbia,(draft).[39] Reiter, R., (1991), The frame problem in the situation calculus: a simple solution(sometimes) and a completeness result for goal regression, in V. Lifschitz (Ed.),Artificial Intelligence and Mathematical Theory of Computation: Papers in Honorof John McCarthy, Academic Press, pp. 359-380.Bibliography 129[40] Saridis, G.N., (1977), Self-Organizing Control of Stochastic Systems, M. Dekker,New York.[41] Simon, H.A., (1977), Scientific discovery and the psychology of problem solving,Models of Discovery, Reidel, Boston, MA.[42] Sterling, L. and E. Shapiro, (1986), The Art of Prolog: Advanced ProgrammingTechniques, The MIT Press.[43] Tempelmeier, H., H., Kuhn, (1993), Flexible Manufacturing Systems : DecisionSupport for Design and Operation, Wiley, New York.[44] Turner, R., (1984), Logics for Artificial Intelligence, Haisted Press, New York.[45] Vollmann, T.E., L.B. William, and D.C. Whybark, (1992), Manufacturing Planningand Control Systems, Business One Irwin, 3rd Edition.[46] Zadeh, L.A. (1965). Fuzzy sets. Information and Control, Vol. 8, pp. 338.[47] Zadeh, L.A. and 3. Kacprzyk, (eds) (1992), Fuzzy Logic for the Management ofUncertainty, Wiley, New York.[48] Zhou, Q.J. (1985). The robustness of an intelligent controller and its performance.Proc. lEE International Control Conference, Vol. 1, pp. 429-33.Appendix ALogic ProgrammingProlog which stands for PROgramming in LOGic is an implementation language of logicrepresentation and reasoning of knowledge using first order predicates. Essentially, Prologallows the writing of programs as sets of “Horn Clauses” [42, 44] (see next section for adefinition), and executes these programs by means of resolution, applied in a top-downmanner, the effect of which is similar to the operation of a goal driven system, using adepth-first search strategy.A.1 Horn ClausesHorn Clauses are a subset of first-order predicate calculus. They are sentences in clausalform but which contain at most one literal on the left hand side (LHS). In particular,the following are all Horn Clauses:Clausel: P +— QflRClause 2: P —Clause 3:Clause 4: 0Horn Clauses are important to logic programming because they are much more computationally tractable than full clausal forms. Consequently, there is a strong incentiveto sacrifice the expressiveness of full clausal forms to achieve these computational gains.130Appendix A. Logic Programming 131A.2 Syntax of Prolog1. Conjunction of predicates is written as a comma‘,‘;2. Disjunction of predicates is written as a semicolon‘;‘;3. All clauses end with a period ‘.‘;4. Constants and predicate names begin with a lower case letter;5. Variables begin with an upper case letter;6. Parameters to predicates are enclosed in brackets and separated by commas;7. Lists of terms are written in square brackets and the terms are separated by commas;8. The symbol 9’ is used to separate the tail of a list.A.3 Resolution and UnificationWhen a query is issued, the system tries to prove the goal (the query) by a process ofsearch and unification. Prolog selects clauses by trying them in the order they appearin the database, and evaluates the clauses in the body of the Horn Clause from left toright.For example, suppose that we have the database:father(tom, david).parent(david, mary).grandfather(X, Y)— father(X, Z),parent(Z, Y).Appendix A. Logic Programming 132If the query is 7-father( Who, david), the first clause will match the query by unifyingWho to torn, so as to give an answer Who = torn. If “who is mary’s grandfather” isthe query, i.e., ?-grandfather( Who,mary), the third clause will be called to achieve thegoal by instantiating Y to mary and unifying X to Who. Note that X and Who arestill free variables, but if either of them is fixed to a constant, the other one should alsobe fixed to the same value. Now the predicates in the body of the third clause will beverified from left to right: father(X, Z) will match father (torn, david) by instantiatingX to torn and Z to david. Thus, all variables will be instantiated. The second predicatein the body of the third clause will be instantiated to parent(david, mary) which willsucceed since it exists as a fact. Finally, the goal will be achieved by Who = torn.In general, unification has the following forms:1. A free variable unifies another free variable;2. A free variable unifies a constant (numeric or symbolic), which is known as instantiating a variable to the constant;3. Two identical constants always unify.A.4 Prolog for AT ProgrammingProlog provides a means to represent knowledge independent of the use of that knowledge.Only the logic relations are represented by a set of Horn clauses, whereas deductivereasoning is implemented by a built-in inference engine. As an example, a member of alist can be described as follow:member(X, [XT]).mernber(X, [HIT]) — X L H,member(X,T).Appendix A. Logic Programming 133The first clause gives an instance that if X is a head of a list, it is a member of thelist; the second clause completes the description: if X is not the head of a list, but is amember of the tail, it is still a member of the entire list.A.5 Non-logic FeaturesAs a practical programming language, Prolog has some non-logic features. Specifically,it provides the following:1. Input and output, which are necessary for user interface;2. Database operations, which assert new knowledge to a database or retract oldknowledge from the database;3. Controls, which may cut (!) a branch in the search path or force a search to fail(fail);4. Negation, which can be implemented as a failure of proof using “cut” and “fail”.not(P) — P,!,fail.not(P).Non-logic features make Prolog powerful in practical programming. However, abuseof these features may weaken the advantages of logic programming.Appendix BIntended Interpretation of Prolog PredicatesSome important Prolog predicates developed in the dynamic restructuring system arelisted below with intended interpretations.X—S1flY-.S2—--+A: This is an objective level rule, which means A is the conclusionunder conditions that component X has status Si and component Y has statusS2.R with B: True if the rule R has the belief degree B.ask(O, P, V): Asks the user the value V of property P of Object 0.assessment(A, VD, V): Provides an assessment value V of action A where VD (validity value) is one factor, and another one being the feasibility index is obtainedfrom the blackboard.assumable(O, P, V): True if object 0 holds the default value V for property P.belief_calculate(X, S, P): True if P is the membership grade of X belonging to a fuzzyset S, which has the shape defined by [A, B, C, D], as explained in the predicatememiunction/, A, PD): True if A is the best (in terms of priority or validity value) in theset As, where PD is the priority value of A.i34Appendix B. Intended Interpretation of Prolog Predicates 135best_action(CL, A, PD, Flag): To find the best action A for all components in a listCL according to the flag Flag, where PD is the priority degree of action A, andFlag takes values “within” a workcell or “between” workcells.centeroid(P, MF, A, M): True if A and M are area and the first moment of a fuzzyquantity P, where MF is the corresponding membership functions of P.collect_triggered..ES(KSs): True if KSs is a list of all triggered knowledge sources.combine(X, L, LN): True if LN is the combined list of X and a list L, where X andthe elements of L and LN take the form (fuzzySetName, membership Grade). IfX already exists in L, use “max” interpretation to merge X into L. Otherwise,append X to L.component(O, P, V): True if V is the value of property P of component 0. (a blackboard)control: Blackboard controller.decision(E, A): To select an action A with the highest assessment value from all possible actions under the situation expressed by E, and using the installed decisionmaking knowledge (rules).defuzzify(PD, FL, PDV): True if PDV is the crisp value obtained through defuzzifying the fuzzy variable PD using membership functions FL.determineioad(A, LD): Determines the load LD which is to be transferred in carrying out the action A.distance((A,B), D): Calculates the distance D between the workcells A and B.evaluate_workstatus: Functional procedure of the KS “evaluating component status”.Appendix B. Intended Interpretation of Prolog Predicates 136executeJ(S(KS): Executes a knowledge source KS.expand(N, V, CT): Fuzzy variable N which has value V is expanded into a set ofpropositions CT.expand...and(A,B,Z): True if Z is the result of the fuzzy conjunction of A, and B.expand_not(A, B): True if B is a set of negative elements of A.expand_or(A,B,Z): True if Z is the result of the fuzzy union of A, and B.fam(S, A, VD): Calculates the validity value VD of the action A under conditions ofS which is a proposition set in which all propositions are treated as parallel.feasibility(P, V): True if V is the feasibility index of load sharing of a pair of components F, which has the form (Cl, C2) where Cl and C2 are components of thesame type. (A blackboard)fps: Functional procedure of the KS “updating of system information”.free(C): True if component C is load free.fuzzify(V, MF, F): F is a fuzzy value obtained through fuzzification of the crisp valueV based on a fuzzy descriptor of which the membership functions are MF.get_property(O, P, V): To report the value V of property P which is associated withobject 0. It may instruct a user to complete the information of an object if theproperty value is required but not given in the True if G is a group of components.Appendix B. Intended Interpretation of Prolog Predicates 137group_components(S, T, CL): True if CL is a list of all the components of type Twhich have the status S, where S is a flag indicating “overloaded” or “undercapacity” conditions.heuristic(A): True if A is an action deduced from heuristics.holds(O, P, V): True if object 0 holds property P at value V.ks(KS, P, V): True if V is a value of property P associated with a knowledge sourceKS.load_distributing: Functional procedure for the KS “workload planning”, which generates the capacity requirements for the overall FPS.make_virtual(RC, VC): Makes a virtual component VC which is a copy of all properties of the component RC, but with zero capacity.mem_function(N, L): True if L is the membership functions of a fuzzy descriptor N.L is in the form of [(fuzzySetName, [A, B, C, Dj)IOthersets] where A, B, C, andD are points which define the shape of the membership function of a fuzzy setnamed fuzzysetname. In particular, A corresponds to the beginning point of thisset, B to the first point where its membership grade value is 1, C to the last pointwhere its membership grade value remains 1, and D to the last point of this set.(see Figure B.1)modify_cell_property(W, P, V): Changes the value of property P to V, which isassociated with the workcell W, and triggers the knowledge sources which haveinputs from this property blackboard.modify_comp_property(O, P, V): Changes the value of property P to V, which isassociated with component 0, and triggers the knowledge sources which have inputsAppendix B. Intended Interpretation of Prolog Predicates 1380Figure B.1: The Representation of Membership Functionsfrom this property blackboard.move(C, from(W), to(W1)): Moves the component C from workcell W to workcellWi.move_component(C, W, Wi): Moves component C from workcell W to workcell Wi.(physical action)not_overloaded(OC, L): True if component OC is not overloaded when the loads L(a list) are assigned to it.op(P, R, N): Defines an operator N at precedence level F, and an associative relationR, where R has the form of xf, fx and xfx with f standing for operator andfor operand. Note that x may be replaced by y which can contain operators of thesame level as F, while x can contain operators of lower precedence only.optimal_action(A): True if A has the highest assessment value in the current database.output: Functional procedure of the KS “output of restructuring plans”.overload(Ci, F, C2): True if Cl and/or C2 are overloaded according to the flag Fwhich takes the values “and” / “or”.plan(P): True if P is an action in the restructuring plan (A blackboard)Appendix B. Intended Interpretation of Prolog Predicates 139possible_actions(C, Flag): Finds and stores in a dynamic database all possible actionswhich can be applied to component C according to flag Flag, which has the values“within” and “between”.record(R): True if R is a recorded, sharing status reached due to a restructuring action.releasing(C1, C2): Releases the component Cl by transferring its load to componentC2.released(VC, C2, Load): True if Load is the load transferred from a released component to C2, where VC is a virtual component, recording properties of the releasedcomponent.remove(R): Removes a record R.remove_KS_trigger(KS): Sets the trigger status of the knowledge source KS to “off”.remove_zero_degree(S1, S2): True if S2 is the remaining part of the fuzzy value 51after its all zero-grade elements are removed.report_cost_function: Calculates the cost function of the restructuring system, andreports the value.report_restructuring_failur(C): True if component C is overloaded.report_restructuring_plan: Reports the designed restructuring plan.restructuring: Functional procedure of the KS “restructuring”.select_highest_PR(KSs, KS): True if KS is the knowledge source with the highestpriority among the knowledge sources KSs.sharing(OC, UC): Shares load from component OC by component UC.Appendix B. Intended Interpretation of Prolog Predicates 140shared(OC, UC, Load): True if Load is the load shared by UC, which is originallyassigned to OC.situation(X, CT): True if CT is the expanded context of the fuzzy status X.sum_up(L, LD): True if LD is the summation of the elements of the list L.terminate(R): Terminates a recorded relation R which has been either a “released/3”or a “shared/3”.transferioad(C1, C2, L): Transfers the load L from component Cl to componentC2. (a physical action)trigger(KSs): Triggers all knowledge sources in the list KSs.trigger_KS(KS): Sets the trigger status of the knowledge source KS to on.trigger_property(P): Triggers the knowledge sources which have an input from theblackboard of property P.update_feasibility: Functional procedure of the KS “updating of sharing feasibility”.user: Functional procedure of the KS “user interface”.workcell(W, P, V): True if V is the value of property P of workcell W (A blackboard).


Citation Scheme:


Citations by CSL (citeproc-js)

Usage Statistics



Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            async >
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


Related Items