A FRAMEWORK FOR QUALITATIVE AND SEMI-QUANTITATIVE ANALYSIS IN ENGINEERING DESIGN AND EVALUATION by MICHAEL H. GEDIG B.A.Sc. , C iv i l Engineering, University of British Columbia, 1992 A THESIS SUBMITTED I N P A R T I A L F U L F I L L M E N T OF THE REQUIREMENTS FOR T H E D E G R E E OF MASTER OF APPLIED SCD2NCE in THE F A C U L T Y OF G R A D U A T E STUDIES Department of Civi l Engineering We accept this thesis as conforming to the required standard T H E UNIVERSITY OF BRITISH C O L U M B I A September 1995 © Michael H . Gedig, 1995 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be,- granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of The University of British Columbia Vancouver, Canada Date OCT- If, DE-6 (2/88) A B S T R A C T A framework is presented which is used to support engineering decision-making in the presence of incomplete and imprecise information. A number of sound reasoning techniques which utilize this framework are described. These techniques include qualitative reasoning, a branch of study in the field of artificial intelligence, and semi-quantitative reasoning, which draws inferences from partially-specified numeric values. The constraint-satisfaction paradigm plays an important role in the implementation of these reasoning strategies. The notion of the constraint is well-suited to engineering planning and design, where projects are generally formulated in terms of a set of functional specifications. A computer program was developed based on the framework presented here. The program implements several complementary qualitative and semi-quantitative reasoning strategies. The specific techniques used in the program include constraint-satisfaction algorithms for both qualitative and numeric domains, interval arithmetic, and constraint inference methods. It was intended that the computer program developed as a part of this research serve as a practical tool which could provide logical justification for engineering decisions. For this reason, the program was developed on a platform which is both accessible and familiar. As part of the program, a convenient method of systematically specifying constraints was created, which mirrors the way in which engineering problems are normally specified. Examples are given which illustrate the application of the techniques presented here. These examples show that the techniques discussed in this thesis have significant potential for justifying engineering decisions made under conditions of uncertainty. i i C O N T E N T S ABSTRACT i i CONTENTS i i i TABLES v FIGURES v i ACKNOWLEDGMENTS v i i i INTRODUCTION 1 1. QUALITATIVE ANALYSIS 3 1.1 Qualitative Physics . 5 1.2 Qualitative Calculus 7 1.2.1 The Domain of Signs 8 1.2.2 Qualitative Equations 11 1.2.3 Solving Systems of Qualitative Equations 12 1.2.4 Interpretation of Solutions 14 1.3 Qualitative Reasoning Applications 16 1.3.1 Qualitative Process Theory 16 1.3.2 ENVISION. 19 1.3.3 Q S I M 23 1.3.4 Summary 28 2. SEMI-QUANTITATIVE ANALYSIS 29 2.1 Interval analysis 29 2.1.1 Definition of interval 30 2.1.2 Solutions to Interval Equations 32 3. CONSTRAINT-SATISFACTION METHODS 36 3.1 Search by Backtracking 37 3.2 Consistency Algorithms 39 3.3 Numeric Constraint-satisfaction Problems 43 4. T H E QUALITATIVE ENGINEERING SYSTEM QES 51 4.1 Representation 52 4.1.1 Intervals 52 4.1.2 Bounds :. 53 4.1.3 Expressions 54 4.1.4 Relation Links '. 57 4.1.5 Systems of Equations 58 4.2 Qualitative Analysis 58 4.2.1 Example from Structural Analysis 64 4.3 Semi-Quantitative Reasoning 73 4.3.1 Numeric Constraint Satisfaction 73 4.3.2 Interval Rounding 80 4.3.3 Soundness of Interval Methods , 80 4.4 Constraint Inference 81 4.4.1 Relational Arithmetic 83 4.4.2 Constant Elimination Arithmetic 83 4.4.3 Graph Search 84 i i i I Contents 4.5 Implementation 87 4.5.1 Platform 87 4.5.2 Input Format 89 4.5.3 Output Format 93 5. RELATED WORK 95 CONCLUSIONS 98 BIBLIOGRAPHY 101 APPENDIX A : PROPERTIES OF INTERVALS 105 iv T A B L E S TABLE 1.1: T H E DOMAIN OF SIGNS 9 TA B L E 1.2: QUALITATIVE ADDITION \X\ + [Y\ 9 TABLE 1.3: QUALITATIVE MULTIPLICATION [X] x [Y] 10 TABLE 1.4: QUALITATIVE NEGATION -[X] 10 TABLE 1.5: RULES USED TO GENERATE QUALITATIVE EQUATIONS 12 T A B L E 1.6: QUALITATIVE CONSTRAINTS 27 TABLE 3.1: BACKTRACKING SEARCH TREE 38 TABLE 4.1: QUALITATIVE ADDITION WITH ORDINAL RELATIONS 67 TABLE 4.2: CONSTRAINT PROPAGATION TO PARENTS 77 TA B L E 4.3: CONSTRAINT PROPAGATION TO CHILDREN 78 TABLE 4.4: CONSTRAINT PROPAGATION THROUGH ORDINAL RELATIONS 79 TABLE 4.5: RELATIONAL ARITHMETIC AXIOMS 82 TABLE 4.6: CONSTANT ELIMINATION AXIOMS 83 TABLE 4.7: TRANSITIVITY TABLE FOR ORDINAL RELATIONS 85 TABLE 4.8: FORMAT OF VARIABLES AND CONSTANTS 91 v F I G U R E S F I G U R E 1.1: F U N C T I O N A L R E P R E S E N T A T I O N O F A S T R E T C H E D R U B B E R B A N D 18 F I G U R E 2.1: S O L U T I O N S E T F O R S E T O F L I N E A R E Q U A T I O N S W I T H I N T E R V A L C O E F F I C I E N T S . 33 F I G U R E 3.1: C O N S T R A I N T G R A P H F O R E X A M P L E P R O B L E M 39 F I G U R E 3.2: P R O C E D U R E R E V I S E [ M A C K W O R T H 1977] 40 F I G U R E 3.3: S I M P L E A R C C O N S I S T E N C Y A L G O R I T H M A C - 1 [ M A C K W O R T H 1977] 41 F I G U R E 3.4: A R C C O N S I S T E N C Y A L G O R I T H M A C - 3 [ M A C K W O R T H 1977] 42 F I G U R E 3.5: A N I M P L E M E N T A T I O N O F T H E W A L T Z A L G O R I T H M P A V I S , 1987] 45 F I G U R E 3.6: A L G O R I T H M F O R A R C B ( ^ - C O N S I S T E N C Y [ L H O M M E , 1993] 49 F I G U R E 4.1: I N T E R V A L D A T A S T R U C T U R E 52 F I G U R E 4.2: B O U N D D A T A S T R U C T U R E 53 F I G U R E 4.3: E X P R E S S I O N D A T A S T R U C T U R E 54 F I G U R E 4 . 4 : G R A P H I C A L R E P R E S E N T A T I O N O F E X P R E S S I O N S 55 F I G U R E 4.5: R E L A T I O N D A T A S T R U C T U R E 57 F I G U R E 4.6: R E L A T I O N L I N K S T R U C T U R E 57 F I G U R E 4.7. G R A P H I C A L R E P R E S E N T A T I O N O F A N E Q U A T I O N 58 F I G U R E 4.8: E Q U A T I O N S Y S T E M S T R U C T U R E 58 F I G U R E 4.9: I N I T I A L C O N S T R A I N T N E T W O R K 60 F I G U R E 4.10: C O N S T R A I N T N E T W O R K W I T H E X P R E S S I O N L I N K S A D D E D 60 F I G U R E 4.11: C O N S T R A I N T N E T W O R K A F T E R N O D E C O N S I S T E N C Y P R O C E D U R E 61 F I G U R E 4.12: F I N A L C O N S I S T E N C Y N E T W O R K 63 F I G U R E 4.13: P I N - J O I N T E D S T R U C T U R E 64 F I G U R E 4.14. Q E S I N P U T F O R P I N - J O I N T E D S T R U C T U R E 66 F I G U R E 4.15. Q E S O U T P U T F O R P I N - J O I N T E D S T R U C T U R E 67 F I G U R E 4.16: N E T W O R K R E P R E S E N T A T I O N O F A D D I T I O N W I T H O R D I N A L R E L A T I O N S 68 F I G U R E 4.17: Q E S O U T P U T F O R S T R U C T U R A L A N A L Y S I S U S I N G O R D I N A L R E L A T I O N S 69 F I G U R E 4.18: G R A P H I C A L R E P R E S E N T A T I O N O F S O L U T I O N T O P I N - J O I N T E D S T R U C T U R A L P R O B L E M 69 F I G U R E 4 . 1 9 : S T R U C T U R A L F R A M E M O D E L 71 F I G U R E 4.20: C O N S T R A I N T N E T W O R K R E P R E S E N T A T I O N F O R N U M E R I C C O N S T R A I N T P R O B L E M 74 F I G U R E 4.21: Q E S I N P U T F O R N U M E R I C C O N S T R A I N T P R O B L E M 75 F I G U R E 4.22: S O L U T I O N S E Q U E N C E F O R N U M E R I C C O N S T R A I N T P R O B L E M 75 F I G U R E 4.23: Q E S O U T P U T F O R N U M E R I C C O N S T R A I N T P R O B L E M 76 vi Figures FIGURE 4.24: MODES OF CONSTRAINT PROPAGATION 77 FIGURE 4.25: CONSTRAINT NETWORK FOR GRAPH SEARCH EXAMPLE 84 FIGURE 4.26: T H E APPEARANCE OF Q E S 89 FIGURE 4.27: EXAMPLES OF VALID CONSTRAINT SYNTAX 91 FIGURE 4.28: OUTPUT FOR CONSTANT ELIMINATION EXAMPLE 94 vii A C K N O W L E D G M E N T S The financial support of the Natural Sciences and Engineering Research Council of Canada, in the form of a Postgraduate Fellowship and Research Grants awarded to Dr. S. F. Stiemer, is gratefully acknowledged. In addition, the financial assistance of the Science Council of British Columbia, through a Technology B . C . grant to Coast Steel Fabricators, Ltd., helped make this thesis possible. I would like to thank my thesis supervisor, Dr. Siegfried F. Stiemer, for his lucid advice and continual encouragement during the preparation of this thesis. The opportunities afforded to me by those at Coast Steel Fabricators, David J. Halliday, Adjunct Professor, in particular, are sincerely appreciated. v i i i I N T R O D U C T I O N In the planning and design of engineering projects, engineers are very often required to decide upon a course of action irrespective of the completeness and accuracy of available information. Deficiencies in the quality and quantity of information are unavoidable, and come from a number of sources: from natural processes which are inherently random, from incomplete investigation, from honest mistakes and from deliberate misinformation. Most often, however, the engineer is provided with only a set of functional requirements which represent constraints which must not be violated by a particular design. The job of the engineer is to create something from nothing, or more realistically, from something similar. Much of the uncertainty in engineering derives from the trite realization that no two projects are the same. Technical issues are seldom tackled in isolation; in the practical world the design considerations are almost always entangled with economic concerns. As engineering businesses become more competitive, engineers are asked to make decisions more quickly, and by necessity, to make decisions with less information. Although this situation is perhaps an undesirable symptom of the current trends in engineering, it exists nonetheless, and in dealing with the problem some questions arise. Is there a reliable, systematic way of gleaning insight into situations which are characterized by incomplete and inaccurate information? Is there a way of effectively reducing the risk associated with engineering decision-making, particularly at the early stages of a project? It is well known that the earlier a decision is made in the life of a project, the greater its financial repercussions later in the project. It is more cost-effective to arrive at a sound design initially than to try to modify an inherently poor design later on. As the life of the project advances, costs become 'locked in ' , and increasing amounts of money are required to undo mistakes made in the early stages. A further symptom of functioning with less information is that intuition plays a more central role in decision-making. Although intuition is certainly useful, and wi l l always be a part of both business and engineering, it 1 Introduction has drawbacks because intuitive knowledge is difficult to justify and to transfer. It would be desirable to bolster intuition with the results of a logically sound, clear argument which is based on indisputable facts. The motivation for this thesis is the unfortunate necessity of dealing with incomplete and imprecise information in engineering. One of the main goals of this research was to produce a tool which, using sound logical techniques, could be used to wring as many useful conclusions as possible from unclearly-specified problems. It is intended for such a tool to be used by the practicing engineer to support intuitively-guided design decisions. The tool conceived and developed for this purpose is a computer software program. The software has the ability to draw conclusions from qualitative and partial numeric input data. Because of the incompleteness of information, numerical models are of limited value; instead, qualitative reasoning techniques, which have been studied in depth in the field of artificial intelligence, are more useful. Unfortunately, there is little evidence that an attempt has been made to apply such techniques in a systematic way to practical engineering problems. A n objective of this work is to incorporate these techniques within an accessible and simple framework. Qualitative reasoning techniques are augmented with interval analysis methods, which are sound procedures for reasoning with partially-specified numerical information. In addition to qualitative reasoning and interval methods, a number of other reasoning techniques are used. The emphasis of this work has been placed on the ability of the computer to use sound logic to discover answers rather than on its ability to manipulate numbers. This thesis begins with a overview of qualitative analysis techniques, followed by a discussion of research in qualitative reasoning, a topic in the field of artificial intelligence. The subject of semi-quantitative analysis methods, including interval analysis, is covered next. Constraint satisfaction techniques play an important role in both qualitative and semi-quantitative analysis. These techniques are reviewed next, followed by an extensive description of the computer program developed as a part of this thesis. 2 1. Q U A L I T A T I V E A N A L Y S I S Qualitative analysis has been applied in diverse fields of the physical and social sciences, including economics, applied mathematics, ecology and control theory. There are several reasons for using qualitative analysis instead of quantitative analysis. Precise mathematical models may not be available. Even i f mathematical equations are available, it may not be possible to solve them analytically so that direct relationships between various parameters can be inferred. Qualitative techniques can be used in conjunction with more precise mathematical models, in order to efficiently guide the solution of such models, or to determine bounds on the behaviour of models. In some fields, such as in the social and natural sciences, the exact form of the mathematical relations which link various parameters are not known. For example, in ecology, it may be observed that the populations of foxes and rabbits obey a predator-prey relationship. If the population of foxes increases, the population of rabbits in the same area tends to decrease. Using qualitative analysis techniques, it is still possible to reason with such information even though the exact mathematical form of the relationships is not known. Puccia and Levins [1985] have developed a systematic qualitative method, called loop analysis, for solving problems in diverse areas such as applied ecology, population ecology, and social epidemiology. In an early application of qualitative analysis, Samuelson [1983] notes that many parts of economic doctrine concern complex, many-variable systems, and yield results that are inconclusive. He describes a calculus of qualitative relations, which uses a matrix of signs to represent the qualitative changes in the parameters of an economic equilibrium system. Qualitative analysis is also used in applied mathematics to determine the qualitative behaviour of functions, such as whether a function is bounded or unbounded. Qualitative analysis is used in engineering, particularly where the mathematic formulae which describe certain behaviour are difficult to solve. For example, Goldstein [1994] develops qualitative techniques in continuum 3 Qualitative Analysis mechanics, for such topics as seepage theory and fracture mechanics. Oden [1986] uses qualitative methods in the study of nonlinear mechanics, looking at the problem of determining existence of solutions to problems in contact mechanics and elastic buckling. In most cases, the solutions of boundary value problems of mathematical physics cannot be represented in closed form; series expansions or other numerical approximations are generally used. Qualitative methods are especially important in the study of natural objects, such as rocks or cracks in solids, which are irregular and can never be characterized completely. In such cases it is not practical to evaluate the mechanical fields in detail. Qualitative methods are useful in ascertaining the general properties of the behaviour of solutions to mathematical equations, which concern issues such the existence and bounds of solutions. In the study of elasticity, for example, qualitative methods are used to bound the energy and deformation of a body from above and below [Villagio, 1977]. The qualitative behaviour of a solution at infinity may provide useful information in some cases. It is now realized that methods of establishing existence are not purely theoretical, and that they contain many clues to the solution itself [Oden, 1986]. The engineer often has to contend with complicated problems when the amount of information available is limited. In many cases, the engineer only needs to know the maximum or minimum values of a certain dependent quantity or certain behavioural properties and not the complete, exact solution. In these instances it is reasonable to question.the value of a expensive, detailed numerical calculations for such modest requirements. Even if detailed numerical analysis is possible, it may not warranted because of the effort involved or because of the amount of uncertainty within the input data. In the early stages of engineering design, for example, many of the parameters which define a system have not been specified. Although a numerical analysis tool may exist, such tools generally require that the input data is complete and precisely specified. Rough estimates can initially be used for the parameters, but sometimes it is questionable whether the results of the analysis justify the effort expended in obtaining them. In some situations, it may be beneficial to use qualitative analysis in the initial stages of analysis, and to use quantitative analysis later when more 4 Qualitative Analysis detailed information is required. Qualitative analysis can also be used as a guide for selecting input parameters for the numerical analysis, potentially reducing the number of times the detailed analysis must be repeated. Recently, qualitative analysis has been used in a field of artificial intelligence called qualitative reasoning about physical systems, or qualitative physics. Formal representation schemes have been developed which may be used to reason qualitatively about the behaviour of physical systems. Qualitative physics provides a formal, systematic approach to qualitative analysis, and constitutes a key part of the qualitative reasoning application QES, developed as a part of this thesis. This discussion wi l l focus on the topic of qualitative dynamics, which deals with the behaviour of physical systems over time. There are other areas of qualitative reasoning, such as qualitative spatial reasoning, which is of interest in robotics, but this topic involves a more complex range of issues than need be described here. 1.1 QUALITATIVE PHYSICS Qualitative physics is an area of artificial intelligence concerned with reasoning qualitatively about the behaviour of physical systems [Iwasaki, 1989]. Physical systems include any systems, both natural and fabricated, which operate under the laws of physics. Qualitative physics evolved from the study of "commonsense" physical reasoning. Early in the study of artificial intelligence, researchers realize that humans are able to effectively function with seemingly little effort when faced with situations characterized with uncertainty. The field of commonsense physical reasoning, or naive physics [Hayes, 1979], sought to formalize the types of knowledge required reason about everyday situations. Qualitative physics, while embodying the goals of commonsense reasoning, also seeks to predict the behaviour of physical artifacts, and to generate plausible explanations for their behaviour. Qualitative physics deals not only with everyday devices, but also with complex physical systems. Human experts are able to reason with incomplete information in more complex domains. It is common in engineering, for example, for the expert to use complex qualitative reasoning strategies to answer a given 5 Qualitative Analysis question about a domain. Certainly the expert, who generally has knowledge of the underlying physical principles of the domain, can set up equations and attempt to solve them numerically or analytically. Before attempting a detailed solution, however, experts often reason qualitatively in a way that is different from commonsense reasoning. Research in qualitative physics was spurred on by the shortcomings of expert systems, the first commercially-viable applications of artificial intelligence. Experts systems typically rely on domain-specific heuristic knowledge, and tend to fail ungracefully when confronted with problems that fall even slightly outside the domain for which the system is intended. A key fault of most expert systems is their inability to reason using fundamental knowledge of the domain, such as conservation laws. On the other hand, qualitative reasoning uses a detailed domain model, an explicit representation of the first principles of the domain that underlie heuristic knowledge. Expert systems are often characterized by shallow knowledge; domain knowledge that has been encoded in a format that is particularly efficient for a specific application. Qualitative reasoning uses deep knowledge, which refers to fundamental knowledge of the domain. A further problem of expert systems is that much of their knowledge is encoded as implicit rules. Expert systems generally include several different types of knowledge, such as experiential knowledge, rules of thumb, basic principles, and empirical knowledge. No distinction is made between these different types of knowledge, and as a result, expert systems are difficult to transfer to another domain. It is a problem to determine which types of knowledge apply only to a specific domain, and which are applicable over an number of different situations. The need for an explicit domain model makes some domains more suitable than others for applying qualitative reasoning. The domain of physical systems, for example, is appropriate for qualitative reasoning because a set of fundamental laws of physics is available. In other domains, such as medicine and ecology, a comparable set of laws does not exist. In medicine, for example, most of the knowledge used for diagnosis and treating diseases is empirical, not based on a model of the relevant biological and chemical mechanisms. 6 Qualitative Analysis 1.2 QUALITATIVE C A L C U L U S Qualitative reasoning entails reasoning with information that is less precisely specified than numerical data. The signs, relative magnitude and directions of change in quantities are all types of information that can be used to reason qualitatively. A language has been developed in which it is possible to express imprecise knowledge of quantities and the relations between quantities. The terms qualitative variables, qualitative equations, and qualitative inequalities are used to describe concepts which are analogous to concepts in algebra. The value of a usual algebraic variable specifies only one element in the set of possible values. If the set is the real number line, a value represents a specific point. On the other hand, the value of a qualitative variable can represent one element as well as a set of elements. Functional relationships between quantities may also be described qualitatively. For example, take Hooke's law of ideal springs, which is expressed as F = kx where F is the force applied to the spring, k is the spring constant, and x represents a distance from an equilibrium position. This relation can be expressed qualitatively as: "The greater the force on the spring, the larger the displacement from the equilibrium position." Qualitative variables may be constructed from continuous variables. The entire domain of a continuous variable is subdivided into a finite number of nonoverlapping subintervals, and all the values in the same interval are treated as equivalent. The qualitative value of a variable is the name of the interval in which the actual numerical value lies. For example, a qualitative variable which represents the temperature of water might consist of three intervals: (-°°, 0), the temperature in degrees Celsius over which water exists in the solid form; (0, 100), where water is a liquid; and (100, +<»), in which water is a vapour. It is important that the continuous domain is subdivided into subintervals which represent qualitatively distinct regions of behavior. The representation scheme should capture distinction that make an important qualitative difference, ignoring 7 Qualitative Analysis others. As an example, i f the intervals (0, 80) and (80, 100) were used instead of (0, 100) to represent the temperature of water, this would have introduced unnecessary complexity into the model, which may have an adverse effect on the solution process. The boundary values used to subdivide a continuous domain are called landmark values, or distinguished values. For the variable representing water temperature, the landmark values are at 0 degrees and 100 degrees. A variable can have any number of landmark values at which behaviour changes significantly, but qualitative reasoning is most efficient when their number is finite. Using a finite number of landmarks supports case analysis and reasoning by exclusion, two powerful techniques of qualitative reasoning. The most common subdivision of continuous domains is into three subintervals, labeled negative, zero, and positive. These three subintervals represent the negative numbers, zero and the positive numbers. This subdivision wi l l be used to explain some of the general concepts of the qualitative calculus. One significant aspect of the division into negative numbers, zero, and positive numbers is that when a variable represents the rate of change of the value of some quantity, the value of the qualitative variable indicates whether the quantity is decreasing, constant, or increasing. Representations using more landmark values have been developed; some of these wi l l be described later in the context of specific applications of qualitative reasoning. 1.2.1 The Domain of Signs The domain of signs is the set of qualitative values which results when the landmark zero (0) is used, dividing the positive numbers from the negative numbers on the real number line. The domain of signs is expressed as S e { + , 0 , - } . It is also useful to use the set of extended signs, S', written as S' e { +, 0, -, ? }, which allows us to express ignorance of the sign of a quantity. 8 Qualitative Analysis The fundamental definition of the domain of signs is given in Table 1.1 which defines the intervals which are associated with the elements of the set. Interval Sign (0,+oo) + [0,0] 0 (-oo,0) -(-00, +oo) ? Table 1.1: The domain of signs. A number of sign-valued operators are defined, which when applied to real numbers, return signs as values: + i f X>0 [X]0 =sign(X) = iO ifX = 0 - i f X<0 (1.1) More generally, LY]Xo = sign(X-X0), where X0 serves as a reference for the variable X. The operation LY] 0 is often abbreviated by LY]. In addition, assuming that the variable AT is continuous and differentiable everywhere, [X] = [dX/dt] = siga(dX/dt). (1.2) + + 0 - ? + m o ? + + ? . ? + 0 - ? ? - - ? ? ? ? ? Table 1.2: Qualitative addition [X\ + [Y]. 9 Qualitative Analysis Addition over the real numbers is a function that takes two real values and returns a third. It is not possible to define addition over signs because the sum of the qualitative values + and - is ambiguous (it can be either +, 0, or -). Addition can be represented as a function when defined over the extended signs however, as shown in Table 1.2. For convenience, multiplication and the unary negation operator are also defined over the extended signs, as presented in Table 1.3 and Table 1.4. X + m 0 - ? + + 0 - ? m 0 0 0 0 0 - - 0 + ? ? ? 0 ? ? Table 1.3: Qualitative multiplication [X] x [Y]. + -[X] 0 0 - + ? ? Table 1.4: Qualitative negation -[X]. Kuipers [1994] represents addition and multiplication as relations instead of functions. When qualitative addition and multiplication are viewed as functions, uncertainty can propagate through a chain of calculations. 10 Qualitative Analysis For example, if we wish to evaluate the expression [Z] x ([X] + [Y]) when the value of \X\ is + and the value of [Y\ is -, the expression in brackets evaluates to ?, so the result of the multiplication operation, and also, many other expressions that depend on this one, is ?. When addition is viewed as a relation, three signs are evaluated and a value of true (T) or false (F) is returned. Evaluating the expression amounts to asking the question: "is it true or false that adding [X] to [Y] will result in the value + / 0 / - ?" Although viewing addition as a relation gives us no more information than when it is viewed as a function, it helps to prevent the spread of uncertainty. 1.2.2 Qualitative Equations The qualitative addition and multiplication operators and relations act as qualitative constraints on the values of variables. Qualitative equations are derived from models of physical systems in much the same way as the usual quantitative equations. In fact, quantitative equations are often converted into qualitative equations. In general, a quantitative equation can be transformed into a qualitative equation using rules of the form shown in Table 1.5. As an example of a qualitative equation, consider Newton's second law of motion, F= ma, which governs the relationship between the resultant force acting on a body of mass m and the acceleration a of the body. Since the mass is positive and constant, [m] = + and [m] = 0. We can transform this equation into a qualitative equation and draw several useful conclusions: • Force and acceleration are in the same direction: [F\ = [ma] = [m][a] = [a]. • A change in either force or acceleration results in a change to the other in the same direction: [F] = [d(ma) I dt] = [m][d] + [a] [m] = [a]. 11 Qualitative Analysis [e\+e2] => [ei] + [e2] [eve2] => [e,][e2] [0] + [e] => [e] [0] [e] => [0] [+][*] => [e] HW => -W-Table 1.5: Rules used to generate qualitative equations. Qualitative equations may also be derived from qualitative knowledge of how variable values depend on others. For example, we may notice that the viscosity of a liquid decreases as its temperature increases, although we might not know the precise functional relationship between viscosity and temperature. The relation is expressed qualitatively as where v and k represent viscosity and temperature, respectively. A quantitative equation can also be transformed into a qualitative one by linearizing the equation using a Taylor series expansion [de Kleer, 1984]. 1.2.3 Solving Systems of Qualitative Equations Solving systems of qualitative equations means finding qualitative values of variables that satisfy the equations. Unlike systems of equations in real variables, a system of 'independent' qualitative equations in general does not have a unique solution, even when the number of variables is the same as the number of equations. The problem of finding a set of qualitative variables consistent with a given set of qualitative equations is a constraint-satisfaction problem where the equations are the constraints to be satisfied. Techniques for solving constraint-satisfaction problems can be applied to systems of qualitative equations. A technique that is commonly used to find the values of the variables is local constraint propagation. Given the values of all but one of the variables in an equation, the value of the unknown may be determined by [v] = 4*], 12 Qualitative Analysis substituting in the values of the known variables and simplifying the expression. This process may be viewed as propagating values through networks of equations. As an illustration of local propagation, consider the following system of equations: [a] + [b] = [c] (1.3) [d\ = la] (1.4) [e] + [f] = [b] (1.5) Given the values [d\ = 0, [e] = +,[/] = 0, equation (1.5) simplifies to [b] = +. Since [d] is zero, equation (1.4) implies that [a] must be zero also. Substituting these two results into the first equation and simplifying yields M = +. Sets of qualitative equations are generally inherently simultaneous, which means they cannot be solved by substitution alone. The usual algebraic techniques also do not work. For example, consider the following system of equations: x+y =3 2x+y =4 (1.6) There is no sequence of simple propagation which can solve this problem. Such inherent simultaneity can be resolved, say, by subtracting x + y = 3 from 2x + y = 4, yielding x = 1. The analogous strategy fails in the qualitative domain because the addition and multiplication operators defined for qualitative values do not have associated with them the field axioms which are required to perform this type of manipulation. One of the problems is that sign algebra lacks an additive inverse, so that inferences such as M =W => [s] + [u] = [t] + [u], and [s] + [t] = [u] ^ [s] = [t] - [a], in general, are not valid with qualitative variables [Williams, 1991]. Local constraint propagation methods often do not work, and even though they are able to find a solution, they cannot guarantee that they will find all results. In general a set of qualitative equations cannot be solved to 13 Qualitative Analysis obtain a unique solution. One of the reasons for this is that qualitative algebra is inherently ambiguous, as indicated by the table for qualitative addition (Table 1.2). If the qualitative variable [/] from the previous example had been assigned the negative sign, [/] = -, substituting this value and [e] = + into equation (1.5) the value of [b] is undetermined, or [b] = ?. Any of the three signs +, 0 or - is a possible assignment for [b]. Three new cases, corresponding to [b] = +, [b] = -, and [b] = 0, are generated in order to continue the propagation. This ambiguity causes a very large number of possible cases to be generated as the system becomes large. In general, local propagation is possible when the qualitative equations take the following form: X, = c,X2 = / , (X , ) ,X 3 =f2(XuX2),... where c is a constant, and f\, f2, ... represent explicit expressions that can be evaluated. When there are simultaneous equations such as = g\ (X, X2), X2 = g2(X\, X2), then more powerful constraint-satisfaction methods are required. Another approach to constraint satisfaction is to use a generate-and-test approach, where all possible combinations of assignments to variables are made. Each possible set of assignments is checked against the equations in order to determine i f the assignment implies a contradiction. This method is guaranteed to find all possible solutions to the system of equations, however it is inefficient. More efficient means of obtaining all solutions exist. Some of these methods are discussed in Chapter 3, which deals with constraint-satisfaction methods. 1.2.4 Interpretation of Solutions Systems of qualitative equations have multiple solutions because the field axioms of qualitative algebra are weaker than their quantitative counterparts. The ambiguity of qualitative calculus causes the search for a solution to grow very rapidly with the number of variables in the system and the number of possible assumptions. There have been several suggestions for dealing with the problems of ambiguity and search 14 Qualitative Analysis complexity in qualitative calculus. Most involve using additional knowledge, including quantitative knowledge. Search efficiency can be improved by using domain-specific and problem-specific knowledge. For example, i f we are studying the thermodynamics of a kettle on a stove, we may justifiably ignore the loss of heat from the kettle to the air. Allowing qualitative variables a greater number of possible values is another approach to resolving ambiguity in qualitative analysis. The representation developed by Kuipers in Q S I M [Kuipers, 1984], discussed later, illustrates one possibility for using a richer set of qualitative information. Some of the ambiguities may be removed using knowledge about ordinal relations between variables. A n arithmetic reasoning system called Quantity Lattice [Simmons, 1986], is capable of representing and reasoning with information on partial ordering relations amoung variables and expressions. Some of the techniques used in Quantity Lattice were applied in the computer program developed as a part of this thesis. Finally, Dormoy and Raiman [1988] developed a technique for solving qualitative equations in a manner analogous to the Gaussian elimination procedure that is used to solve sets of conventional linear equations. It should be noted that multiple solutions are not just an artifact of qualitative analysis. They are an important part of the theory, since each solution describes a behaviour that can potentially occur in the operation of the system being modeled. Since the qualitative model is an abstraction of the physical device being modeled, it is possible that the model may represent some other realizable device. Thus qualitative analysis can be useful in design applications, because it is capable of finding solutions to systems of constraints which are not obvious, but nonetheless valid. 15 Qualitative Analysis 1.3 QUALITATIVE REASONING APPLICATIONS A number of different approaches to qualitative physics have emerged. They are similar in many ways, but each emphasizes different types of modeling primitives. Three of the most well-known approaches to the qualitative modeling and simulation of physical devices wi l l be described here. The modeling primitives used in these three examples may be termed the component, the process, and the constraint. 1.3.1 Qualitative Process Theory The goal of qualitative process theory (QPT), developed by Forbus at the Massachusetts Institute of Technology, is to understand commonsense reasoning about physical processes [Forbus, 1984]. Qualitative process theory uses general knowledge about physical processes and objects in the world to infer which processes wi l l occur, their effects in given physical situations, and when they wi l l stop. Forbus used as a basic modeling primitive the process. Processes, defined as agents which cause changes in objects over time, are common in physics. For example, objects move, collide, flow, bend, heat up, cool down, compress, stretch and boil. In QPT, physical situations are modeled as collections of objects, their relationships, and processes. Different types of processes are defined in terms of objects which must be present, the preconditions which must be satisfied by the objects for the process to take place, and the qualitative relationships that hold between parameters when it does occur. In Forbus' theory, the properties of objects are represented as quantities. Quantities consist of two parts: an amount, and a derivative. Both amounts and derivatives may be considered variables, and consist of a magnitude part and a sign part. Signs take on one of three possible values, -1, 1, and 0, corresponding to negative numbers, positive numbers, and zero, respectively. 16 Qualitative Analysis Quantity Spaces The quantity space is used to represent the set of possible assignments to variables. The quantity space consists of a finite number of distinguished values and the ordinal relations amoung them, so that the distinguished values form a partial order. Qualitative values of a variable are either a distinguished value or a range of values between two neighbouring distinguished values. For example, i f a variable X is defined on (-00,-foo) with two distinguished values, V0, and Vu such that V0> Vu the quantity space for X may be represented as: Vi). Vu (Vu Vo), V0, (V0, +00) This represents a totally ordered set of qualitative values. If the ordinal relations (<, =, >, etc.) between distinguished values are only partially specified, additional possibilities must be considered in order to generate a set of totally ordered values. For example, i f the variable X contains the additional distinguished value V2, and the relation V0 > V2, the following three cases must be specified: V\>V2: (-00, V2), V2, (V2, Vx), Vu (Vu V0), V0, (V0, +~) V\ = V2: (-00, V2), V2, (V2, V0), Vo, (Vo, +-) V, < V2 : (-co, V,), Vu (Vu V2), V2, (V2, V0), V0, (V0, +~) The quantity space of the qualitative values of X includes all of these possible qualitative values. A quantity space is essentially a qualitative representation of quantities in terms of inequalities. The concept of ordering is important in qualitative process theory because processes generally start and stop when the orderings between quantities change. Every quantity space has the distinguished value zero (0), which serves to connect the sign of a number with inequality statements, for example, X> 0 => s\gn(X) = 1. Qualitative Proportionalities Forbus uses qualitative proportionalities to establish qualitative functional dependencies between parameters of a situation. In qualitative process theory, the notation Q\ <*Q+ Q2 indicates that there exists a function that determines Q\, and is increasing monotonic (strictly increasing) in its dependence on Q2. Qualitative 17 Qualitative Analysis proportionality induces a set of correspondences between points in the quantity spaces it connects. Correspondences map value information from one quantity space to another. As an example of qualitative proportionality and correspondences, consider an elastic band. Since the restoring force exerted by the elastic band is proportional to its length, the qualitative proportionality Force OCQ+. Length may be written. A correspondence can be used to establish the fact that the internal force in the elastic band is zero when the length of the elastic is equal to its rest length. In other words, as shown in Figure 1.1, the correspondence forces the curve to pass through the origin of a graph of force against length, although the exact shape of the curve is unknown. This example illustrates a powerful aspect of qualitative analysis. Qualitative proportionality is an abstraction of the functional relationships normally used in physics, and allows one to use the same method of reasoning for functional relationships which would normally be categorized quite differently. From the viewpoint of qualitative analysis, it is irrelevant whether the function describing the shown in Figure 1.1 is linear or nonlinear. This distinction implies two quite different approaches to solving a similar problem using the usual quantitative techniques. rest length LENGTH Figure 1.1: Functional representation of a stretched rubber band. 18 Qualitative Analysis 1.3.2 ENVISION With the ENVISION project, de Kleer and Brown [1984] sought to be able to infer the behaviour of a physical device from a description of its physical structure. The structure of a device is described in terms of its components and the interconnections between components. Part of the description of a component includes the laws which govern its behaviour. De Kleer and Brown developed a model library, exploiting the general methodology used in systems dynamics for describing a collection of standard physical components [i.e., Karnopp, 1990]. The goal of the ENVISION system is to derive function from structure for an arbitrary device. The program takes as input: 1) a set of components and their allowable interaction paths; 2) input signals applied to the device; and 3) boundary conditions which constrain the behaviour of the device. The output is a description of the behaviour of the device in terms of its allowable states, and the values and directions of change of the system variables. The output may be directly used to generate a directed graph of the states that correspond to the set of all possible sequences of events that can occur from the initial qualitative state. ENVISION also produces complete causal accounts and logical proofs for the system behaviour. As part of their approach, de Kleer and Brown developed formal rules to govern the qualitative modeling process. Such rules are aimed at forcing the modeler to make all assumptions explicit, and to avoid the pitfalls that were experienced with expert systems. One of the concepts used is that of class-wide assumptions. The principle employed is that the laws for the components of a device of a particular class may not make any more assumptions about the behaviour of the particular device than are not made about the class in general. De Kleer and Brown sought a "pure" modeling methodology, where the behaviour of the device is not implicitly encoded in the governing laws of the parts. By using this methodology, a system is able to objectively determine the function of a device which is represented as a collection of interconnected components. A n example of a class-wide assumption used by de Kleer and Brown is the assumption that behaviour of short enough duration can be ignored. This assumption, generally known as the quasistatic assumption, is a term 19 Qualitative Analysis from classical physics which is used in thermodynamics, fluid dynamics and electronics. Other examples of such assumptions are: "all masses are rigid"; "all flows are laminar"; and "there are always enough particles present so that macroscopic behaviour holds." Qualitative Variables Unlike quantitative variables, qualitative variables may take on only one of a small number of predetermined values. Each value corresponds to some interval on the real number line. The set of possible values is determined by the quantity space [Fortius, 1984] associated with the particular variable. Divisions between intervals are best chosen to be at singularities such as at zeros and discontinuities. In simulation, since the most important property of a quantity is whether it is increasing, decreasing or unchanging, de Kleer and Brown use the quantity space consisting of +, - and 0. This is because the terms increasing, decreasing, and unchanging correspond to derivatives that are positive, negative, and zero, respectively. The notion that a variable x is increasing, for example, is formalized as [dx/dr] = +, or more compactly, as 5x = +. Qualitative Calculus De Kleer and Brown developed a qualitative version of the calculus to support qualitative reasoning. It was necessary to develop a calculus because some component laws are described in terms of derivatives. A simple theory of qualitative integration is developed from the qualitative versions of continuity, Rolle's theorem, and the mean value theorem of standard differential calculus. Continuity and the mean value theorem are defined in terms of functions of time. 20 Qualitative Analysis Qualitative Values The qualitative values a variable can take on are A0, Au ... , Az, representing disjoint abutting intervals that cover the entire number line. The value set^ o = -, A\ = 0, A2 = + is an instance of this definition. The ends of the intervals may be either open or closed. A0 must be -<». If the right end of At is open, the left end of AM must be closed. The right end of Az must be +°°. Confluences In the component model, the laws governing the behaviour of a component are expressed in the form of confluence equations. Each model confluence consists of a set of terms which must sum to a constant, i.e. ZJ, = C. A term can be a variable, the negation of a variable, or the product of a constant and a variable. An example of a confluence is 5F + $A - 8Q = 0 which may be used to model the operation of a valve. A set of assignments to variables, where all variables have values, is said to either satisfy or contradict the confluence equation. The set satisfies the confluence if either the qualitative equality strictly holds using sign arithmetic, or the left hand side cannot be evaluated (is ambiguous). A set of assignments contradicts a confluence if every variable has a value and the left side evaluates, and the confluence is not satisfied. For example, using the confluence above, if §P = + and 54 = -, the confluence is satisfied because the expression 8P + 54 has no value (the result is indicated by ? in Table 1.2). The set of values SP = +, SA = +, SQ = - is an example of a contradictory assignment. The term pure confluence is used to describe those confluences involving simple sums of variables, i.e. SP + 5/1 - SQ = 0, while mixed confluences have sums of products, i.e. SP + [P]SA- 8(2 = 0. 21 Qualitative Analysis Qualitative States Often more than one set of confluences is required to describe the behaviour of a model. In the qualitative regime it is often not possible to formulate a single confluence which is valid over the entire operation of the device. For example, in modeling a valve, different sets of confluences govern the behaviour of the open valve than are used for the closed valve. De Kleer and Brown generally presume that models use pure confluences only. It is always possible to construct models using only pure confluences by using additional states. In the example above: 5P + 54 - 5(2 = 0; §P - 5/1 - SQ = 0; and 5P - 5Q = 0, depending on whether [P] is +, - , or 0. It is possible, for pure models, to divide the set of all confluences into those involving solely derivatives and those involving only the variables themselves. In general, a state is a consistent assignment of values to non-derivative variables. Changes within states are due to changes in derivative variables. A change in value of a non-derivative variable indicates a change in state, because each value in a particular quantity space represents a qualitatively distinct behaviour of the device or component. Solving Systems of Confluences The solution to a system of confluences is a number of predictions, called interpretations. The solution is divided into two tasks: finding the behaviour which is compatible with a given state, the intrastate behaviour, and determining which transitions between states are valid, the interstate behaviour. A device changes state when one or more of its variables exceeds some threshold which defines that state. Since each confluence may be viewed as a constraint, the problem of determining the intrastate behaviour is a constraint-satisfaction problem. Sets of confluences are generally inherently simultaneous, which means they cannot be solved by substitution alone. Since local constraint propagation methods do not usually work, ENVISION uses a combination of generate-and-test and constraint propagation to determine the intrastate behaviour. 22 Qualitative Analysis The interstate behaviour is the set of possible transitions between states. The state-transition diagram, used in system dynamics, is a graphical tool which illustrates possible state transitions in a system. Using a set of initial conditions, the initial state of a device is determined. From the starting state, the possible transitions are used to trace the behaviour from one state to another. In determining the possible state transitions, the values of the derivatives of variables are used. A number of rules can be formulated which limit the legal changes in a variable depending on the value of its derivative. In addition, rules may be derived from the qualitative definitions of continuity and the mean value theorem. Using these rules, the state transition diagram for the device can be constructed. The state transition diagram is a complete description of all possible interstate behaviours of the device. Concepts such as oscillation, ringing, energy dissipation and stability are identifiable as particular patterns in the state diagram. Qualitative physics therefore enables one to draw inferences regarding important functional characteristics of physical devices. 1.3.3 QSEVI Kuipers has developed a qualitative reasoning framework, QSIM, that is designed to express states of incomplete knowledge that are common to human knowledge, but are difficult to express using traditional methods [Kuipers, 1994]. The framework includes inference methods that are designed to be essentially deductive, so that assumptions are explicit and guarantees are provided that every step is sound. Kuipers emphasizes his belief that the various representations and inference methods in the area of qualitative reasoning can best be understood in terms of their relationships to differential equations. Kuipers introduced the notion of qualitative differential equations (QDEs) as an analog to the usual quantitative differential equations. Classical physics uses the language of differential equations extensively to describe a system and to draw inferences about it. A differential equation represents the structure of a physical system using certain 23 Qualitative Analysis continuous variables that characterize the state of the system, and mathematical constraints on the values those variables can take on. The strength of differential equations comes from the expressive power to form models which capture salient aspects of the world, and the inferential power to derive predictions from those models. As Kuipers states, "differential equations are the single most powerful mathematical tool of modern science and engineering, because of their expressive and inferential power." While de Kleer and Brown focus on the topological structure of physical systems as a primitive in their qualitative reasoning scheme, their approach has some elements in common with the theory of Kuipers. Conceptually, the confluences introduced by de Kleer and Brown are an alternate representation for QDEs. In qualitative process theory Forbus downplays the importance of constraints and differential equations as a tool for qualitative reasoning. Forbus emphasizes the concepts which are of greater importance to commonsense reasoning, where intuitive explanation of phenomena plays a more significant role. Kuipers provides formal definitions for the elements of his qualitative representation scheme, and shows how they correspond with familiar elements such as the real number line, continuous functions, and algebraic and differential relationships. He shows that the abstraction relation between the usual differential equations and qualitative differential equations can be actually justified, so that the qualitative representation is not merely like a differential equation, it actually is a differential equation. Qualitative Differential Equations Qualitative differential equations consist of four elements: a set of variables; a set of quantity spaces, one for each variable; a set of constraints which apply to the variables; and a set of transitions which are rules defining the boundary of the domain of applicability of the QDE. The focus of this discussion will be the first three elements, which concern the representation of a system in terms of QDEs. Transitions will not be discussed here, as they deal with the issue of qualitative simulation, where QDEs are used to predict the overall behaviour of a system. 24 Qualitative Analysis Qualitative Variables While differential equations model continuous change, qualitative reasoning is based on discrete symbol systems. Although the world changes continuously, it changes qualitatively only at isolated points. Variables in a QDE are represented as time-varying quantities. In order to apply a systematic approach to qualitative reasoning, variables are restricted to correspond to functions of time whose behaviour is reasonable. Reasonable functions are continuously differentiable, and have only finitely many critical points. A variable V is continuously differential if both V(t) and its derivative V\t) are continuous. Further, each qualitative variable is defined as ranging over the extended real number line, 9T, which includes the endpoints -°° and +00. Using the extended real number line allows the invariant that the value of a variable always lies in a closed interval defined by landmark values, and provides a means of describing asymptotic approach to a limit as reaching the limit at r = °°. Formally, the function V: [0,oo] is defined to be continuous at °° exactly if limt_*„F(f) exists. Applying these criteria, both e"' and e' are reasonable functions on [0,«>], but sinr is not. Quantity Spaces The quantity space representation expresses the intuition that, for reasonable functions at least, there are only a few qualitatively important landmark values. A quantity space is defined by Kuipers as a finite, totally ordered set of symbols, the landmark values: h<k<...<k. Each landmark is a symbolic name, representing a particular value in 9T which is unknown. A quantity space normally contains the landmarks 0, and +°°. In qualitative simulation, new landmarks corresponding to the critical points of a function are inserted into quantity spaces representing the ranges of reasonable functions. The critical points of a function /(r), the points at which f'(t) = 0, describe qualitatively important points of functions. 25 Qualitative Analysis Qualitative Values The qualitatively expressible values of a variable Fare the landmark values and the open intervals bounded by landmark values. The qualitative value of /(r), with respect to the quantity space A < / 2 <...</*, is the pair (qmag, qdir), where qmag represents the magnitude of the value and qdir captures information on how the value is changing: h i f f(t) = lj qmag = 1 , and (1.8) l(',>',+ 1) ^ f(t)e(lJtlJ+l) qdir -inc i f f(t) > 0 std i f /'(0 = 0- (1.9) dec i f / ' ( r ) < 0 In the second expression, inc, std and dec indicate that the value is increasing, steady, or decreasing, respectively. For example, suppose the variable X{t) takes its values in the quantity space X: [ - ° o , 0), 0, (0,A),A, (A, B), B, (B, +<~]. If x starts at equilibrium with the landmark value A, and moves to a new equilibrium at B, then a possible sequence of qualitative values could be described as X(f): (A, std) -» {(A, B), inc) -» {B, std) Although the function X(f) changes continuously, its qualitative description only changes at discrete points. The qualitative value of a function is constant over intervals between landmarks. 26 Qualitative Analysis Qualitative Constraints The constraints in a qualitative differential equation include familiar mathematical relations, such as addition, multiplication, and negation, derivatives of variables with respect to time, the constant constraint, and functional constraints. These are presented along with their representation in the syntax of Kuipers' system, in Table 1.6. The last line in the table illustrates the use of a functional constraint. Functional constraints express incomplete quantitative knowledge about a functional relationship. The example given in the table, (M+ X Y ) , specifies a class of functions which are monotonically increasing. The 'arctan' function is just a particular example of this class; there are many others. The syntactic procedure for decomposing an O D E into simultaneous equations generates a unique set of constraints from a given QDE. However, since different monotonic functions maybe mapped to the same M+ constraint, a given Q D E can be an abstraction of multiple ODEs. Constraint QSIM Command X+Y=Z (add X Y Z) XxY=Z (mult X Y Z) -X=Y (minus X Y) dX(t)ldt=Y(t) (d/dt X Y) dX(f)/dt = 0 (constant X) Y= arctan X (M+ X Y) Table 1.6: Qualitative constraints. Corresponding values are tuples of landmark values that the variables involved in a constraint may take on at the same time. They introduce constraints between the landmark values of different quantity spaces. For example, the (add X Y Z) constraint introduces the corresponding value triple (P, Q, R) where P, Q and R are landmarks in their appropriate quantity spaces. The corresponding value places an additional constraint 27 Qualitative Analysis P + Q = R on the real numbers for which the landmarks stand. Corresponding values are conceptually the same as correspondences in theory of Forbus. As correspondences were are used to constrain the value of a function to pass through a particular point, corresponding value pairs may be associated with functional constraints such as the (M+ X Y) constraint. For example the corresponding value pair (0, 0) forces the function to pass through the value (0, 0). In the notation of corresponding values, horizontal and vertical asymptotes are expressed as pairs with one finite and one infinite landmark. 1.3.4 Summary Three approaches to qualitative reasoning were discussed in the preceding sections. These approaches are distinguished by the use of three different representation primitives: the component-connection model of de Kleer and Brown, the process formalization of Forbus, and the qualitative differential equations of Kuipers. These three approaches are similar in many respects. They are distinguished through the different objectives and philosophies of various researchers. Some of the research is directed at providing clear "commonsense" explanations to phenomena and therefore rejects accepted tools of science and engineering because they are often lacking in intuition. Differential equations, for example, do not contain explicit information about causality; the fact that changes in the level of some quantities cause changes in the values of others. The notion of causality is certainly very important in producing systems which can provide sound and intuitive explanations of physical phenomena. Since it is not a goal of this thesis to produce a tool which automatically generates explanations and rationale for decisions, the approach adopted here is to exploit the one of the most powerful tools of science and engineering, the differential equation. In this respect, the approach used for this research is more closely aligned with the work of Kuipers than the other two approaches. Qualitative differential equations conform with the representation of an engineering problem as a set of constraints, which is also used in this research. 28 2. S E M I - Q U A N T I T A T I V E A N A L Y S I S The engineer is rarely confronted with a situation where purely qualitative information is available. Almost invariably there exists some knowledge of certain quantities, even though these may be incomplete or partially-specified. In order to make full use of incomplete information, it is necessary to be able to reason in some way with partial numeric data. Semi-quantitative reasoning is the task of combining incomplete quantitative and qualitative knowledge. Semi-quantitative reasoning is important to model-based reasoning tasks such as design, monitoring and diagnosis. All of these tasks involve incomplete knowledge in both qualitative and quantitative forms. There are a number of different representations available for reasoning with incomplete knowledge of quantities, including bounding intervals, probability distribution functions, fuzzy sets, and order-of-magnitude relations. This thesis focuses on the use of bounding intervals to represent partial knowledge of a real number. The discipline of interval analysis provides a rich array of techniques for working with intervals [Moore, 1966,1979; Alefeld and Herzberger, 1983; Neumaier, 1990]. 2.1 INTERVAL ANALYSIS Interval analysis was originally developed as a means of providing rigorous error bounds on the results of machine computations. Since all computers perform arithmetic using numbers that are represented with finite precision, it is of interest to know how far a computed result would lie from the result calculated using real numbers. An interval arithmetic was developed which employs a special type of rounding that guarantees an interval which contains both ordinary machine arithmetic results and infinite precision arithmetic results. Interval arithmetic is not just used as a means of studying error bounds on machine computations, however. Interval techniques provide important methods with which one can reason on the range of values of variables. 29 Semi-Quantitative Analysis Interval analysis is now a well-developed branch of applied mathematics. Interval computations are used in a wide range of applications where numeric uncertainty is concerned. For example, in performing a cost-benefit analysis of a project, the World Bank measures the project's profitability by computing the rate-of-return of a projected cost-benefit stream [Moore, 1979]. The rate-of-return is a root of a polynomial whose coefficients are the projected cost-benefit stream. Interval methods have been used by the World Bank to find upper and lower bounds on the rates-of-return. Since interval methods provide a method for dealing with uncertainty, interval analysis includes techniques which are useful in engineering. Engineers use mathematical equations to model the behaviour of physical systems. Even if it is possible to solve the mathematical equation exactly, which is not usually the case, the result is still only an approximate description of the behaviour of the real system. Mathematical models used in engineering often contain constants which are determined experimentally by measurements. The numerical values assigned to such constants will therefore have limited precision. Using interval methods one is able to compute bounds on the set of solutions corresponding to intervals of possible values for the measured quantities. 2.1.1 Definition of interval An interval of real numbers can be thought of as a pair of real numbers, representing the endpoints of the interval. When the endpoints are the same, the interval is said to be degenerate. Degenerate intervals represent real numbers, so that interval arithmetic includes real arithmetic as a special case. This distinction is somewhat meaningless, because it is generally impossible to perform real arithmetic. Most arithmetic is performed on computers, which are confined to approximate arithmetic of limited precision. An interval is a closed bounded set of real numbers: [a,b] = {x:a<,x<b } 3 0 Semi-Quantitative Analysis A n interval can also be regarded as a number represented by the ordered pair of its endpoints a and b, just as a rational number alb is represented by an ordered pair of integers and a complex number x + iy by an ordered pair of real numbers. Fundamental axioms and interval operations are given in Appendix A . The interval representation is well-understood, widely-used, and quite powerful. Many researchers in artificial intelligence have developed and applied methods for combined algebraic, ordinal, and interval reasoning. Although simple, there are a number of important benefits to using the interval representation. Its simplicity means that descriptions of incomplete knowledge of quantities in the form of bounding intervals are easy to obtain. Intervals are also flexible enough to represent both an approximate value and a degree of uncertainty. Intervals can be compactly represented, using two real numbers and two booleans (to represent whether the interval is closed, open, or half-open). A l l connected sets of intervals are intervals (and vice versa). The intersection of two intervals is an interval, so the consequence of two interval descriptions of the same quantity is easy to compute by intersecting the intervals. One concern which arises with regard to the interval representation is whether it is reasonable to treat quantitative knowledge as a step function, to simply state that a quantity lies between two values and nothing more. It may seem more intuitive to think in terms of probability distributions, with a likelihood that gradually diminishes on either side of a central value. The alternatives to the interval representation for representing uncertainty are generally more complex pavis , 1987]. Probability functions require more arbitrary assumptions than simple intervals, their semantics are less clear, and i f done properly, require more complex computations. Representing uncertain values by, say, a Gaussian probability curve is no less arbitrary than representing them by fixed bounds, and it can be difficult to define what the probability means and how to combine different curves. In the context of engineering decision-making, decisions are sometimes made on the basis of subjective assessments of probability distributions. Research has shown that biases are prevalent in such assessments, leading to significant errors [Tversky, 1977]. One of the objectives of this thesis is to employ methods which enable one to reason with less information. Probability functions require more information to 31 Semi-Quantitative Analysis describe parameters than the usual numeric techniques, and so are not suited to the type of semi-quantitative reasoning discussed here. 2.1.2 Solutions to Interval Equations The interval representation is a flexible and simple framework which can be used to represent partial knowledge about quantities. Although interval arithmetic has many similarities with the traditional arithmetic involving real numbers, there are a number of complexities which are introduced in dealing with intervals rather than with real numbers. Consider the linear system of algebraic equations Anxl+A12x2 = Bl (2.1) A2lxl+A22x2 = B2, (2.2) where the coefficients An, Al2,A2i,A22, as well as5i and B2, are intervals: v4 u = [2,3] ^12 = [0,1] A2l = [1,2] A22=[2,3] fli = [0, 120] B2 = [60,240]. (2.3) In the first quadrant, where xi >0andx 2>0, (2.4) the members on the left of (2.1) and (2.2) may be written as [2xu 3xi + x2] and [xi + 2x2, 2xi + 3x2], respectively. Since the intersections [2xi, 3xi +x2] n [0, 120], and [xi + 2x2, 2x, + 3x2] n [60, 240] must not be empty, the following inequalities result: 2xi < 120; 3xi + x 2 > 0; xi + 2x2 <, 240; 2x, + 3x2 £ 60. 32 Semi-Quantitative Analysis In this two-dimensional example, the solution may be represented in the first quadrant as a polygon with vertices (30, 0), (60, 0), (60, 90), (0, 120), and (0, 20). If this process is repeated for the remaining three quadrants, we find that the solution is a polygon in the second and fourth quadrants as well, but that no part of the solution lies in the third quadrant. Combining these results, the solution to the equations is an eight-sided polygon (Figure 2.1). Even in this two-dimensional case, the solution set is not particularly easy to represent. In higher-dimensional cases, the difficulty is obviously compounded. x3 (-120,240) " 1 \ \ 200 • 100 (0.120) (60,90) (-12,24)V_ (0,20) (60,0) i i i i i -100 polo)"^ I l w 100 -100 -(90, -60) Figure 2.1: Solution set for set of linear equations with interval coefficients. Disconnected Intervals Another complexity which arises in interval arithmetic is that of disconnected intervals. The set of values consistent with an equation may be disconnected, because one quantity involved is either discontinuous or a multi-valued function of the other quantities. For example, given the equation xy = z, and the assignments y e [-1,1] and z e [4,5], the solution set for x is x e (-oo, -4] u [4,+oo). The reason is that x = zly is a discontinuous 33 Semi-Quantitative Analysis function of y sty = 0. As another example, given the equation x2 = z and the assignment z e [4, 9], the solution set for x is x e [-3, -2] u [2, 3]. Here, the problem is that the function x = -fz is multi-valued. In interval analysis, the technique that is usually adopted is to represent the solution to by the smallest parallelepiped containing the actual solution having sides parallel to the coordinate axes [i.e., Hansen, 1969]. In the example involving the linear system of equations, the parallelepiped is bounded by the planes x\ = -120, Xi = 90, x 2 = -60, x 2 = 240, so that the solution may be conveniently represented using intervals: xi = [-120, 90] x 2 = [-60, 240]. As shown in Figure 2.1, the solution to this two-dimensional problem can be described by a rectangle with vertices at (90, -60), (90, 240), (-120, 240) and (-120, -60). If the solution set is to be described by a bounding parallelepiped, then the solution may contain points which do not satisfy the system of equations. For example, i f X and Y are intervals, and i f X = [1, 1] and Y = [-2, 2], then XIY = [-«>, +°°], even though values in the open interval (-0.5, +0.5) are not possible values for the quotientX/7. In some cases, a system of equations may have no solution. For example, i f X= [1, 1] and Y [0, 0], then XIY = 0, because there is no x e X and no y e Y such that xly is satisfied. Numeric Constraint Satisfaction Systems of interval equations can be formulated as numeric constraint-satisfaction problems. A constraint-satisfaction problem is defined by a set of variables, each with an associated domain of possible values and a set of constraints on the variables. In numeric constraint-satisfaction problems the domains are continuous while the constraints are numeric relations. Since the domains are continuous, it is impossible to enumerate all of the solutions, which is feasible with finite domains. Even i f the domains are finite integer domains, it is generally not possible to find all solutions, because of the large number of combinations which may be formed. 34 Semi-Quantitative Analysis This difficulty may be overcome by associating a dynamic domain with each variable and by propagating this domain through the constraints. Constraint propagation is a technique used in enforcing consistency in networks of constraints [Mackworth, 1977]. Similar consistency techniques have been used to solve numeric constraint-satisfaction problems Pavis , 1987; Lhomme, 1993]. The goal of these numeric consistency techniques is neither to enumerate all solutions not to algebraically solve a system of constraints, but to determine the exact ranges of values of the different variables. A key concept of numeric consistency techniques is that the domains of variables are represented by intervals, and that as constraints are propagated from one variable to another, the bounds of the intervals are updated dynamically. B y using established techniques for dealing with intervals, numeric consistency techniques are able to guarantee that the correct result wi l l be bounded by the domains of each variable. Kuipers [1993, 1994] incorporates semi-quantitative knowledge into the Q S I M formulation using the interval representation. Since landmark values are symbolic names for unknown real variables, then can represent intervals. Given interval bounds on the values of some landmarks, a behaviour description and its Q D E define a constraint-satisfaction problem: its variables are the landmarks and related terms; the domain of each variable is the set of intervals, and the constraints are the implied algebraic equations. Constraint-satisfaction methods for both finite qualitative domains and continuous domains are covered in the next chapter. 35 3. C O N S T R A I N T - S A T I S F A C T I O N M E T H O D S Constraint-based reasoning is a model for formulating knowledge as a set of constraints without specifying the method by which these constraints are to be satisfied. Many problems are more naturally expressed in terms of what is allowed or, conversely, what is not allowed. A large number of the current computational systems, however, insist on a rigid separation between input and output information. Constraint-based reasoning is becoming more prevalent as a means of flexibly representing a range of problems. A variety of techniques have been developed for finding partial or complete solutions for different kinds of constraint expressions. Constraint-satisfaction problems (CSPs) follow a general formulation, which consists of a finite set V of n variables {Vu V2, ... , V„}, each associated with a domain of possible values, D\, D2, ... D„ and a set of constraints { Q , C 2 , ... , C,}. Each of the constraints is expressed as a relation denned on some subset of variables, given that there are subsets of the Cartesian product of the domains of the variables involved. The set of solutions is the largest subset of the Cartesian product of all the given variable domains such that each n-tuple in that set satisfies all the given constraint relations. A n assignment of a unique domain value to each member of some subset of variables is called an instantiation. A n instantiation is said to satisfy a given constraint C, i f the partial assignment specified by the instantiation does not violate C,. A n instantiation is legal or locally consistent i f it satisfies all the constraints in which it is involved. A number of different tasks may be defined in connection with this formulation. Typical objectives are to determine whether a solution exists (the decision problem), to find one or all of the solutions, or to determine whether an instantiation of some subset of the variables is a partial solution. Several restrictions on the general definition of a CSP are possible. The domains may be required to have a finite number of discrete values. It may be required that all relations are unary or binary, that is, that they only constrain individual variables or pairs of variables, respectively. 36 Constraint-Satisfaction Methods The techniques used in solving constraint-satisfaction problems can be classified into three categories [Dechter, 1992]. The first category consists of search techniques which are used to systematically explore the space of all solutions. The most common algorithm in this class is backtracking, which traverses the search space in a depth-first fashion. The second category is consistency algorithms, which are generally used to perform preprocessing in order to improve the efficiency of the backtracking search, but can also be incorporated in the search. The third technique, structure-driven algorithms, can be used to support both the consistency algorithms and the backtrack search. Structure-driven algorithms wi l l not be discussed here. 3.1 S E A R C H BY B A C K T R A C K I N G A technique exists to solve any constraint-satisfaction problem. Assuming finite discrete domains, the assignment spaceD = A x D 2 x • • • x D3 is finite, so one may evaluate each constraint on each element of D. Once a legal instantiation is found the problem is solved. This generate-and-test algorithm is correct but slow. A more intelligent technique, backtracking, may be used to "prune" away significant portions of the assignment space. Backtracking algorithms systematically explore the assignment space D by sequentially instantiating the variables in some order. As soon as any constraint has all its variables instantiated, its truth value is determined. If the constraint is not satisfied, that partial assignment cannot be part of any total valid assignment. Backtracking then falls back to the last variable with unassigned values remaining in its domain (if any). As an example of backtracking search, consider three variables Vu V2, and V3. The only valid assignment to each of these variables is one of the integers 1, 2, or 3, so that the domains of these variables may be specified as A = D2 = D3 = {1, 2, 3 }. The constraints for this problem are 37 Constraint-Satisfaction Methods CX(X): x> 1 C\2(X\,X2): X\>X2 C23(X\,X2): X\ >X2 where C, indicates a unary constraint on the variable Vh and Cy represents a binary constraint on the variables Vt and Vj. The constraints take as arguments domain elements of the appropriate variable, and return a truth value. For example, C i 2(2,l) evaluates to the truth value true (T). The results of the backtracking search are given in the search tree in Table 3.1. V, V,V2 V1V2V3 1 2 2 1 2 1 1 2 1 2 2 1 3 22 2 3 3 3 1 3 1 1 3 1 2 3 1 3 3 2 3 2 1 322 323 3 3 Table 3.1: Backtracking search tree. In discussing constraint-satisfaction problems, it is convenient to view the task specification as a network which consists of a labeled, directed graph. In the graph, variables are represented by nodes, each with an associated set representing the domain of the variable, unary constraints are represented by loops on the nodes and the binary constraints by labeled, directed arcs between nodes. This type of network is called a binary 38 Constraint-Satisfaction Methods constraint network. The constraint graph for the network associated with the backtracking example problem is shown in Figure 3.1. In this graph, the arcs for Cy T = C,, are not shown. Figure 3.1: Constraint graph for example problem. 3.2 CONSISTENCY ALGORITHMS At times, backtracking can be grossly inefficient. A variety of consistency-enforcing algorithms have been developed which may be performed prior to the search in order to improve its efficiency [Montanari, 1974; Mackworth, 1977; Freuder, 1978]. These algorithms transform a given constraint network into an equivalent, yet more explicit network by deducing new constraints to be added on to the network. The most obvious source of inefficiency in backtracking and the easiest to prevent concerns the unary constraints. If the domain £), for a variable Vt includes a value that does not satisfy C,{x) then it wi l l be the cause of repeated instantiation and failure. Algorithms which enforce node consistency remove the cause of this repeated failure by simply discarding all those domain elements which do not satisfy the corresponding unary constraint. The term node consistency is used because unary constraints are represented as loops on nodes in the constraint graph, as shown by constraint Cx in the example problem. The example problem is made node consistent by removing the element 1 from the domain of variable V\. 39 Constraint-Satisfaction Methods Another source of inefficiency in backtracking search is called arc inconsistency. A n arc from node Vt to V, is inconsistent i f there exists a value a in the domain of Vt such that Cy does not hold for any value of Vj when Vt = a. In the example problem, the constraint network is arc inconsistent. For example, when V3 = 2, there exists no value of the variable V2 such that constraint C23 is satisfied. Inconsistency may be removed from an arc by comparing the two nodes joined by the arc, and deleting those elements which cause inconsistency. Removing an element from a node, however, may allow further deletions from the nodes adjacent to the modified node. For this reason a single pass over the network wi l l not guarantee that the network is arc consistent. The process of enforcing arc consistency between two nodes must be repeated until there is no reduction in any domain. The basic procedure for ensuring arc consistency between two nodes is shown in Figure 3.2. Given discrete domains A and A for two variables Vt and V, which are node consistent, i f X e A and there is no X e Dj such that Cy then X can be deleted from A- When this operation has been performed for each X e A then the arc from node /' to node j (but not necessarily from node j to node /') is consistent. This algorithm is expressed in pseudocode in Figure 3.2. procedure REVISE((/' , /)) begin 1. set D E L E T E to false 2. for each x e A do 3. if there is no y e A s u c n that Cy(X, Y) then 4. begin 5. delete x from A 6. set D E L E T E to true 7. end 8. return D E L E T E end R E V I S E Figure 3.2: Procedure R E V I S E [Mackworth 1977] The simplest algorithm to achieve arc consistency, Mackworth's A C - 1 (Figure 3.3), applies the procedure R E V I S E to each arc in the problem. If at least one of the nodes is modified, every arc is again made arc 40 Constraint-Satisfaction Methods consistent. This process repeats until the network is quiescent (no node requires modification). In procedure AC-1, node consistency is first enforced on every node (line 1). Next, every arc is placed in a list (Q). Each arc is taken in turn from the list and made consistent. If a change has been made, the process is performed again, and repeated until no changes are necessary. procedure AC-1 begin 1. for i = 1 to n do make node /' consistent 2. Q <- {(Jj) 107) is an arc, / *./'} 3. repeat 4. begin 5. set CHANGE to false 6. for each (ij) e Q do set CHANGE to (REVI SE((/,/')) or CHANGE 7. end 8. until CHANGE is false end AC-1 Figure 3.3: Simple arc consistency algorithm AC-1 [Mackworth 1977]. An apparent inefficiency in the procedure AC-1 is that even if one node is changed, every arc in the problem is reprocessed. Waltz developed a method of achieving arc consistency in one pass through the nodes by using information about the arcs leading into and out of a node [Waltz, 1975]. Mackworth developed a more elegant version of the Waltz algorithm which, however, does not attempt to make the network consistent on a single pass. If procedure REVISE is applied to arc (k, m), then every directed toward and away from node m (except for arc (m, k)) is placed on a queue to be processed. In this way, if a node is modified, the change propagates along arcs to neighbouring nodes, which may in turn cause more arcs to be placed on the queue. The propagation continues until quiesence. Mackworth's algorithm AC-3 is presented in Figure 3.4. A generalization of arc consistency techniques is to path consistency [Montanari, 1974; Mackworth, 1977]. A further generalization to p-ary relations is the concept of ^-consistency (1 < p, Jc < ri) developed by Freuder. A network is ^ -consistent iff', given any instantiation of any k-l variables satisfying all the direct constraints * if and only if 41 Constraint-Satisfaction Methods amoung those variables, it is possible to find an instantiation of any £th variable such that the k values taken together satisfy all the constraints amoung the k variables. Node, arc and path consistency correspond to it-consistency for k = 1, 2, and 3, respectively. procedure A C - 3 begin 1. for i = 1 to n do make node /' consistent 2. Q <- {('7) I OV) is an arc, / *j} 3. while Q is not empty do 4. begin 5. select and delete any arc Qc,m) from Q 6. if REVISE((fc, m)) then Q <- Q u {(/, k) | is an arc, / *Jc,i* m} 7. end 8. end end A C - 3 Figure 3.4: Arc consistency algorithm A C - 3 [Mackworth 1977]. Freuder uses an alternate form of constraint network, where constraints are represented by nodes instead of arcs. The procedure^for achieving ^ -consistency begins by building a constraint network consisting of all the unary constraints. Next, nodes are added representing the binary constraints. A binary constraint is synthesized from each pair of unary constraints and two arcs are added, from the binary constraint to the two unary constraints from which the binary constraint was synthesized. The next step is to add a node representing a ternary constraint (a constraint involving three variables). Ternary constraints may be synthesized from the binary constraints. Arcs are then added from the ternary constraint to the appropriate binary constraints. In an incremental approach, new constraints are continually synthesized from lower order constraints. After a new constraint has been created and the network augmented, it is propagated along arcs to the neighbouring constraints. Synthesized constraints represent constraint networks on a subset of the variables in the problem. The subset of variables grows as the procedure continues, until it includes the entire set of variables in the problem. At this point the solution to the problem is the last constraint synthesized. 42 Constraint-Satisfaction Methods By successively adding higher level nodes to the network and propagating constraints in the augmented network, it is possible to achieve Ar-consistency for all k. It is not necessary, as with the arc consistency algorithms discussed earlier, to restrict the given constraints to binary relations. The synthesis algorithm reins in combinatorial explosion by progressively ruling out lower order inconsistencies in stages. As mentioned, the algorithm can be used to find explicitly all the solutions to the constraint-satisfaction problem. In practice, it has been found more efficient to run the algorithm for a few steps as a preprocessor to simplify subsequent backtracking search. 3.3 NUMERIC CONSTRAINT-SATISFACTION PROBLEMS Numeric constraint satisfaction can be used to express a large number of problems, particularly when physical models involving inaccurate data or partially-defined parameters are involved. In contrast to constraint-satisfaction problems involving qualitative variables, domains of variables in a numeric constraint-satisfaction problem are represented as intervals on the real number line. Several techniques have been developed for solving numeric constraint-satisfaction problems. [Davis, 1987] uses a consistency technique called label propagation, which can be used for satisfying constraints where the quantities involved are either the extended signs (+, 0, -, ?) or intervals. [Lhomme, 1993] formalizes a consistency technique for numeric constraint-satisfaction problems, called arc B-consistency (bounds consistency), which is equally valid for both continuous and finite interval domains. Both Davis and Lhomme use a modified version of the previously-mentioned Waltz algorithm. While conventional consistency techniques are only used to simplify a CSP before going on to enumerate the solutions, consistency methods for numeric constraint-satisfaction problems may be used to generate the solution. Traditional constraint-satisfaction problems involve variables with finite domains which support the enumeration of all solutions to the problem. When constraint propagation provides no further pruning, one can always resort to exhaustive search using generate-and-test. In contrast, numeric constraint-satisfaction problems are generally highly under-constrained, resulting in a very large number of solutions. In fact, the 43 Constraint-Satisfaction Methods number of solutions is infinitely large in the case of continuous domains. For this reason, exhaustive search is generally infeasible with quantitative domains. Another difference between qualitative and quantitative constraint propagation is that qualitative domains usually possess little or no internal structure which can provide additional information for solving constraints. The values of a qualitative variable generally have little relationship with one another. On the other hand, the real number line has a high degree of internal structure, which can be exploited in constraint-satisfaction problems. Although it is generally impossible to enumerate all the solutions of a numeric constraint-satisfaction problem, it is often possible to describe the set of solutions. The key to avoiding explosive growth in complexity in reasoning with continuous domains is to represent domains as intervals, and to handle domains only by their bounds. The approach is to attribute a dynamic domain to each variable, and to propagate this domain through the constraints. The constraint propagation process is similar to that used to attain consistency in constraint networks involving variables with finite, qualitative domains. A numeric constraint propagation problem (NCSP) is defined in a manner very similar to conventional constraint-satisfaction problems. A n NCSP consists of a set of numeric variables, V= {Vu V2, ... V„}, a set of domains D = {Du D2, ... D„} where A , a set of numerical values, is the domain associated with variable Vu and a set of constraints C = {C\, C2,... , Cm}, where a constraint C, is defined by any numeric relation linking a set of variables. A variation of the Waltz algorithm may be applied to numeric constraint-satisfaction problems. In the Waltz algorithm, the domains of variables are repeatedly updated, and the changes are propagated to all constraints associated with the given variable. The procedure continues until the constraint network reaches quiesence. Figure 3.5 shows an efficient implementation of the Waltz algorithm. The Waltz algorithm may be illustrated with the following example. Suppose the problem involves three variables, Vu V2, and F 3 with starting bounds given by 44 Constraint-Satisfaction Methods vx = [1, 10] v2 = [3, 8] V* = [2, 7] and with constraints C : Vx + V2=Vi C2: V2 < Vx. procedure REVISE(C(X7, ...,Xk) begin 1. Set CHANGED to 0 2. for each argument X , do 3. begin 4. D <- {x, G Dj 13(x, e A, i = l,...,k,i C(x,,x,,x*)} 5. if Z) = 0 then stop 6. else ifD^Athen 7. begin 8. Dt*-D 9. addX, to CHANGED 10. end 11. end 12. return CHANGED end REVISE procedure WALTZ begin 1. Q <- a queue of all constraints 2. while Q * 0 do 3. begin 4. remove constraints C from Q 5. CHANGED <- REVISE(C) 6. for eachX, in CHANGED do 7. for each constraint C * C which hasX, in its domain do 8. a d d C ' t o Q 9. end 10. end WALTZ Figure 3.5: A n implementation of the Waltz algorithm [Davis, 1987]. The constraint queue Q initially contains both constraints, Cx and C2. The algorithm proceeds as follows: 1. Ci is removed from the queue. - Since Vx > 1 and V2 £ 3, C, gives V3 > 4, so reset F3 to [4, 7]. 45 Constraint-Satisfaction Methods - Since V3 < 7 and V2 > 3, d gives Vx < 4, so reset Vx to [1, 4]. 2. Since Vx and V3 have changed, add C2 to the queue. 3. C2 is removed from the queue. - Since Vx <* 4, C2 gives F 2 £ 4, so reset F 2 to [3,4]. - Since V2 > 3, C 2 gives Fi > 3, so reset F, to [3,4]. 4. Since Vx and F 2 have changed, add Cx to the queue. 5. C\ is removed from the queue. - Since Vx > 3, V2 > 3, Cx gives F 3 > 6, so reset V3 to [6, 7]. 6. Since only F 3 has been changed and V3 has no other constraints besides Cx, nothing is added to the queue. 7. Since the queue is empty, stop. One of the problems with the Waltz algorithm is that, even for well-behaved sets of constraints, it may go into an infinite loop. Consider, for example, the simple equations V\ = V2, V\ = 2V2, with the starting ranges Vx = [0, 100], V2 = [0, 100]. The system is consistent, with the unique solution Vx = V2 = 0. Using the second equation we can deduce that V2 = [0, 50]; then, from the first equation, Vx = [0, 50]; then V2 = [0, 25]; then Vx - [0, 25] ; . . . . There are many more such examples where the starting ranges wi l l cause the algorithm to enter such loops. Because of this problem, some criterion other than quiescence must be chosen to terminate constraint propagation. One such criterion is to consider the amount of change in a variable that is considered significant. This is the method used by Lhomme [1993] to achieve arc B-consistency in numeric constraint-satisfaction problems. The abstract concept of numeric value may be used in order to be able to provide techniques for both finite integer domains and continuous domains [Lhomme, 1993]. For a finite numeric domain a numeric value is simply an element of the domain. For continuous domains, one may utilize the fact that a computer handles real numbers through floating-point numbers. In floating-point representation the set of values that can be 46 Constraint-Satisfaction Methods assigned to a numeric variable is the set of floating-point numbers {fo,f\, ... ,f„}. A real number between two consecutive floating-point numbers is usually approximated. In order to avoid approximations and guarantee correct results, a numeric value in a continuous interval is defined as an element of the set {(-°°,fo),fo, (/o,7i), fu (f\,fi),fi fn, (fm +°°)}. A numeric value is either a floating-point number / o r an open interval whose bounds are two consecutive floating-point numbers if, f+) or one of the terms (-°°, fo) or <f„, +00), representing the infinities. The interval (f, f+) represents an infinite set of real numbers, but is considered as a single value. In this notation, if / is a floating point number,/- and f+ are the two floating-point numbers immediately below and above / respectively. Using this system, the domain associated with a variable may be considered as a finite set while preserving the continuity of the domain. Open intervals are also represented by a finite set, and therefore are closed. For example, the half-open interval [2, 3) is treated as the finite set {2, (2, 2+), 2+ 3-(3-, 3)}, so it maybe represented as the closed interval [a, b], with a = 2 and b = (3-, 3). This formulation is compatible with interval arithmetic, which provides many invaluable techniques for handling intervals. Interval methods have traditionally used closed intervals, and also allow the symbolic handling of the infinities. Whereas computations performed using a floating-point representation are a mere estimate of the correct result, interval-based computing methods provide an interval and guarantee bounds for this correct result. Using the concept of numeric values, it is possible to represent both open and half-open intervals as closed intervals, which complies with the traditional approach to interval analysis [Moore, 1966; Alefeld and Herzberger, 1983]. In describing a numeric constraint-satisfaction problem, a number of additional definitions are useful. If A is the domain of a variable Vh we say that A is convex iff all the numeric values between min(A) and max(A) belong to A . If A , A A are convex then E = A x A x ••• x A may be called a box (also called the convex hull, in interval analysis). The term box used here corresponds to the parallelepiped described in relation to solution sets for interval equations, discussed in Chapter 2. For k variables V\, V2, Vk with an 47 Constraint-Satisfaction Methods associated box E = A x D2 x ... x A , the projection over Vt of the constraint C(VU V2,Vk) restricted to the domains A , D 2 , A , denoted by ni(CiVuV2,...,V&E), is the set { Xi 6 A I 3 (Xi, Xj.u Xj+u xk) G A x ... x A i x A+i x ... x A , such that C(xi,xk) is satisfied }. For example, given a constraint Y-X2, with Ar = [-2, 2] and A = [1, 10], then i f E = Ar x A , H r ( { r=X 2 } ,E ) = [-2, -1] u [1, 2] and LT r ( {Y=X2},E) =[1,4]. For an efficient implementation of numeric constraint satisfaction, some limitation on the types of constraints that may be handled is necessary. The method of solution and the efficiency of the solution technique used depends heavily on the type of constraint [Davis, 1987]. A n efficient yet general technique is to restrict the solution procedure to a set of constraints called basic constraints [Lhomme, 1993]. A constraint C(Vx, V2, Vk) is said to be basic iff V /" e 1, 2, k, it is possible to find two functions F,"1™ and FT"™ such that, for any box E = A x A x ... x A , Fr"(E) and FF**(E) are the minimum and maximum values of U,{C(VU V2 Vk), E). Using the properties of interval arithmetic, the set {X= Y,X< Y, Z = X+ Y, Z = Xx Y, Y= -X, Y = smX, Y = cosX, Y = e*, Y = |A^, Z = XY, Z = min(A", Y), Z = max(X, Y) } is a set of basic constraints. This relatively small set of constraints enables a large set of basic constraints to be expressed, using the conjunction of constraints and the addition of intermediate variables. For example, the constraint Z=XxX+Y is basic but it is not in the set; it may be represented by the conjunction of the constraints Z = V\ + Y and V\ = X2. Note however, that the conjunction of basic constraints is not always a basic constraint. When a constraint is not basic it is often possible to transform it into a conjunction of basic constraints. For example, e* = sin(X + Y) may be expressed as the conjunction ofex=Vx,Vx = sinV2, and V2=X+Y. 48 Constraint-Satisfaction Methods A constraint is said to be disjunctive i f it destroys the convexity of its domains. In other words, a disjunctive constraint maybe satisified when one of the variables contains disconnected intervals. The concept of whether a constraint is disjunctive or not depends on the domains of the applicable variables; the same constraint can be disjunctive for certain domains but non-disjunctive for others. For example, the constraint Y = X2 is non-disjunctive for Dx = [-2, 2] and Dr = [0, 4], but is disjunctive for A r = [-2, 2] and Dr = [1, 4]. Disjunctive constraints cause difficulties with conventional consistency techniques. Disconnected intervals propagate through constraints, which quickly leads to combinatorial explosion. This problem may be avoided by handling only convex domains, which may be efficiently represented by just one interval (i.e. two bounds). Arc B-consistency is a form of arc consistency which is restricted to the bounds of the domain. In contrast to conventional partial consistencies, which guarantee conditions over all elements of a domain, arc B -consistency guarantees conditions only over the bounds of the domain, thereby preserving convexity. procedure IP_2 begin 1. Q <- { (C, V,) | C is a constraint, Vt is a variable of C } 2. while Q is not empty do 3. select and delete {C, V,) from Q 4. I P_REVI SE( <C, V,) | W, RESULT) 5. if RESULT is FAIL then exit with failure 6. if RESULT i s CHANGED then 7. Q <r- Q u { (C, VJ) \C'*C, Vi in C , i *j } 8. end while endIP_2 procedure IP_REVISE«C, V,) begin 9. set F1""1 and F"1"* to the maximum and minimum values of Vt for C 10. s e t / n t o i ^ o v e r A . . A , ; s e t . M ' t o F n a x o v e r A . . . A , 11. if tn andA /do not exist then RESULT = FAIL 12. else if SUFFICIENT_CHANGE([m, M], Dh w) then 13. set A to [m, M] 14. set RESULT to CHANGED 15. else set RESULT to NOTHING end IP REVISE Figure 3.6: Algorithm for arc B(w)-consistency [Lhomme, 1993]. 49 Constraint-Satisfaction Methods One algorithm for computing the solution to a numeric constraint satisfaction using bounds consistency is shown in Figure 3.6. This algorithm, named IP_2 , is similar to both Mackworth's A C - 3 (Figure 3.4) and the Waltz algorithm (Figure 3.5). The difference lies in the way disjunctive constraints are processed, which is by bounding the result in a single interval. Using this algorithm, a constraint wi l l not delete an impossible value between possible values. Algorithm IP_2 uses a technique called arc B(w)-consistency, which incorporates a parameter w (width) to specify authorized imprecision at the bounds. As mentioned, the Waltz algorithm has problems terminating for numeric domains. The specified imprecision w is used to terminate the consistency algorithm. In Figure 3.6, the function SUFFICIENT_CHANGE is true i f at least one of the bounds of A r is more than w distant from the corresponding bound of [m, M\. Arc B(w)-consistency is a technique that has been used and validated on both finite and continuous domains. This method of satisfying systems of numeric constraints is used in the program QES, developed as a part of this research. 50 4. T H E Q U A L I T A T I V E E N G I N E E R I N G S Y S T E M Q E S In developing a practical engineering tool for reasoning with partially-specified information, it would be desirable to incorporate both the power of abstraction inherent in qualitative methods, and the elegance of interval analysis. The Qualitative Engineering System (QES), developed as a part of this research, features a coherent framework which integrates both qualitative and semi-quantitative reasoning techniques. The level of uncertainty present in an engineering project is not static. In the early, conceptual stages, there is more uncertainty than in the final stages. A flexible reasoning framework is needed which is capable of using new information as it becomes available, and updating previous conclusions. QES uses the powerful notion of constraints as a means of expressing engineering problems. Much of an engineer's knowledge is best expressed in terms of what is, or conversely, what is not allowed. Functional requirements, material limitations, labour considerations, environmental characteristics and the laws of physics can all be expressed in the language of constraints. Many of the computational tools currently used in engineering demand a rigid dichotomy between input and output. Furthermore, the input format is often inflexible, requiring that input data be completely specified before computation can proceed. In contrast, QES is able to accept as input only the information that is known at a particular time. Information, both qualitative and quantitative, can be added any stage of a project. QES is effectively a quantity database [Davis, 1987], which is implemented as a constraint network. In this system the quantities are called expressions. There are two types of links between expressions: hierarchical links and relational links. Both links provide conduits for various types constraint propagation. Hierarchical links arise from the structure of expressions, and are limited to particular pairs of expressions. On the other hand, relational links are more general in nature and can be found between virtually any two expressions. Relational links are also the entities which link expressions to form equations and inequalities. A number of techniques, both qualitative and quantitative, are used to reason with the quantity database; these include label propagation using both intervals and signs, interval arithmetic, graph search, and constraint inference. 51 The Qualitative Engineering System 4.1 REPRESENTATION This section discusses the main components of the QES representation: intervals, expressions, variables, constants, equations, inequalities and systems of equations. In QES, constraints are represented as equations and inequalities. Both equations and inequalities are composed of expressions, which consist of variables and constants. Expressions evaluate to quantities. The interval representation is used to express quantities to varying degrees of precision. QES was implemented in the programming language C++, an object-oriented language. In the object-oriented approach, data and the procedures which use this data are encapsulated as entities called objects. In the following discussion, the components of QES are formulated as objects. 4.1.1 Intervals Interval methods are well-developed techniques which enable one to reason on the range of values of quantities. Intervals are flexible enough to represent vague qualitative values as well as precise numeric values. For this reason, the interval representation was chosen as to represent quantities in QES. In QES an interval is represented by a data structure which contains two members, the upper and lower bounds (Figure 4.1). The interval structure includes the procedures add, m u l t i p l y , n e g a t e , and r e c i p r o c a l . interval data members name type n e g a t i v e B o u n d bound p o s i t i v e B o u n d bound methods name arguments add interval m u l t i p l y interval n e g a t e r e c i p r o c a l i s L e s s interval i s G r e a t e r interval i s E q u a l interval Figure 4.1: Interval data structure. 52 The Qualitative Engineering System bound data members name type value number, ±°°t NaN inclusion TRUE, FALSE type UPPER, LOWER methods name arguments add bound multiply bound negate reciprocal isLess bound isGreater bound isEqual bound Figure 4.2: Bound data structure. 4.1.2 Bounds A bound is a structure which consists of three fields: the value, which is either a floating-point number or one of the symbolic constants +°°, or NaN (Not a Number); the inclusion field, which is TRUE if the bound includes the value, and FALSE otherwise; and the type member, which indicates whether the bound is at the lower or upper extent of the interval. Using this representation, QES can reason with open, closed, or half-open intervals. As shown in Figure 4.2, the bound structure also encapsulates procedures which define bound operators (add, multiply, negate, reciprocal). Since operators are defined on the bounds, the implementation of the interval operators is simplified. For example, the interval add procedure takes the following convenient form in C++: add(Interval tolnterval) { lowerBound.Add(tolnterval.lowerBound) upperBound.Add(tolnterval.upperBound) } • Additional processing is required for the multiply and reciprocal functions. For these operators the ordinal relations isLess, isGreater, and isEqual are used to order the bounds correctly. 53 The Qualitative Engineering System expression data members name type domain list of intervals constraint interval type UNARY, BINARY operator NEGATE, RECIPROCAL, ADD, MULTIPLY, SUBTRACT, DIVIDE l e f t C h i l d expression r i g h t C h i l d expression parents list of expressions r e l a t i o n s list of relationLinks methods name arguments constrain r e l a t i v e C o n s t r a i n relation, interval, width add expression multiply expression subtract expression divide expression negate r e c i p r o c a l Figure 4.3: Expression data structure. 4.1.3 Expressions Just as algebraic expressions may take on a number of seemingly different forms, so may expressions in QES. Expressions represent a fundamental component of QES, as several other components of the system derive their behaviour from expressions. The expression data structure is shown schematically in Figure 4.3. The definition of the expression is recursive in nature, as the data structure contains a reference to itself. For illustration, consider the simple algebraic expression A + (B x Q. This expression may be represented as a binary tree, as shown in Figure 4.4. The node labeled 'x' has two children, the variables B and C. The node labeled '+' also has two children, the variable^ and the expression BxC. Since variables may be considered simple expressions, variables and expressions are essentially the same in QES. Representing expressions as trees proves to be a convenient construct for many of the techniques which are used to reason with the quantity database. 54 The Qualitative Engineering System Figure 4.4: Graphical representation of expressions Two of the main components of the expression data structure, shown in Figure 4.3, are the c o n s t r a i n t , and the domain . The c o n s t r a i n t is a single interval, while the domain is a set of intervals. By default, the constraint interval holds the value [-<», +<»], which expresses a complete ignorance of the value of the expression. As more information about various quantities and relations is entered into the system, the constraint intervals become narrower. The domain set is interpreted slightly differently for variables than for expressions. In QES the domain of a variable is analogous to the quantity space representation in other qualitative reasoning frameworks, such as Kuipers' QSIM. Recall that in QSIM, Kuipers defined the quantity space as a finite, ordered set of landmark values: h<h<...<U, which can be represented as the set of alternating closed and open intervals: {[-oo, - « , ] , (-oo, /,), [/,, / , ] , (/,, l2), [l2, I2] [lh 4], Qk, +oo), [+oo + « , ] } . In QES the landmarks are replaced by valid assignments to the value field of the bound structure. For example, the simple quantity space {-, 0, +} may be described by the domain set {[-°°, 0), [0, 0], (0, +<»]} in QES. Expressions are also used to represent numeric constants in the quantity database. The numeric constant zero is a default member of the database. The domain of the constant zero contains the single closed interval which identified with the real number zero, {[0, 0]}. One of the useful aspects of the interval representation is 55 The Qualitative Engineering System the hull operator (see Appendix A) , which may be used to find an interval which has the same lower and upper bounds as the domain set. A n expression may have two, one or no children. A binary expression, such as A + B, has two children, while a unary expression such as -JThas only one child. In the expression structure shown in Figure 4.3, the t y p e field indicates whether the expression is unary or binary. The o p e r a t o r member indicates what type of operator is applied to the child expressions. The available unary operators are negate and reciprocal, while the binary operators are add, subtract, multiply and divide. The l e f t c h i l d and r i g h t c h i l d fields point to the child expressions. The r i g h t c h i l d field is unused for unary expressions, while both are unused when the expression represents a variable. The variables are the 'leaves' of the expression tree, while each expression which has no parent is a 'root'. The child data members act as the hierarchical links between expressions. These links are bi-directional, as each child has a corresponding link with their 'parent'. The p a r e n t s data field holds a list of pointers to the parents of the expression. The network of expressions cannot properly be called a tree, since an expression may have multiple parents, for example, A + B x A. Having noted this, the tree analogy is still a convenient descriptive construct which reflects the hierarchical nature of the interconnections between expressions. The expression tree representation is similar to what Forbus terms a 'tree of functional dependencies', which represents the relationship between qualitative proportionalities. In the tree of functional dependencies, quantities are linked by qualitative proportionalities, independent quantities are at the leaves, and the dependent quantity is at the root. When the expression tree is used for qualitative analysis, the relationships between expressions feature a similar dependence, however, for other operations such as interval propagation, the links are essentially bi-directional. 56 The Qualitative Engineering System 4.1.4 Relation Links Along with hierarchical links, relational links represent the means by which constraints may propagate through the quantity database. Relation links (called relationLinks in QES) serve two purposes: they constrain expressions to form equations and inequalities, and they enable search techniques to be used to infer additional information about ordinal relationships. Inequalities are an important means of capturing fundamental qualitative distinctions, without sacrificing the expressive capabilities of algebraic expressions. Relation links represent the ordinal relation between two expressions. The relationLink data structure, shown in Figure 4.6, contains three fields: one for each expression and another for the ordinal relation. relation data members name type value =, <, >, < >, *, ? Figure 4.5: Relation data structure. Ordinal relations are represented by the relation data structure, presented in Figure 4.5. Relations can take on one of seven values: =, <, >, <, >, and the unknown relation, represented by the symbol ?. relationLink data members name type l e f t E x p r e s s i o n expression rightExpression expression ordinalRelation relation Figure 4.6: Relation link structure. As an example of relation links, consider the equation A + (B x C) = 0. This equation is depicted in Figure 4.7, where the relation link is shown as the dotted arc between the number zero and the expression node labeled '+'. 57 The Qualitative Engineering System Figure 4.7. Graphical representation of an equation. 4.1.5 Systems of Equations When there is more than one equation present in the system, a data structure is used to maintain a list of the applicable equations. The main components of the equationSystem structure are shown in Figure 4.8. The equationSystem structure is required in the constraint satisfaction procedure. This procedure is explained in detail in the next section. equationSystem data members name type expressions list of expressions solutions list of interval sets arguments list of variable names Figure 4.8: Equation system structure. 4.2 QUALITATIVE ANALYSIS In QES, the domains of qualitative variables consist of a finite set of intervals. The most common set represents the domain of signs {[-°°, 0), [0, 0], (0, +°°]}, which may be abbreviated by {-, 0, +}. The domain of signs wi l l be used to look at how QES solves constraint equations which are expressed as qualitative 58 The Qualitative Engineering System variables. The tree structure of expressions is exploited in the solution procedure, which uses constraint-satisfaction methods. Each of the nodes of the constraint network maybe considered a constraint. This representation of a constraint network is different that given by Mackworth, described in Section 3.1. In Mackworth's network, the variables in the constraint-satisfaction problem are the nodes. Loops represent unary constraints on a variable and directed arcs indicate binary constraints. In solving constraints consisting of equations, this representation is unsuitable, because equations can consist of more than two variables. The simple example given earlier, A + (B x C) = 0, involves three variables: A, B, and C. For this reason, the alternate representation of Freuder [1978] is used. In this system, nodes represent constraints, while arcs are used to link constraints having common variables. QES uses a constraint synthesis process to build up successively higher levels of consistency in the constraint network. Freuder also uses a constraint synthesis approach, as explained in Section 3.2, however, the links in Freuder's constraint network have a different significance than in QES. The structure of the expression tree provides a convenient framework in which to construct and solve constraints. Constraints are built up from variables in a incremental fashion, following the expression tree from leaf to root. The following simple example wi l l be used to illustrate the constraint satisfaction process: F i + F 2 = 0 (4.1) F i - F 3 = 0. (4.2) The problem is to determine which assignments to the qualitative variables F\, F2 and F 3 satisfy the two constraints (4.1) and (4.2). We begin building the expression tree by entering three nodes into the constraint network; one for each variable. This network is shown in Figure 4.9. Each variable is initially unconstrained, so the constraint interval of each is [-°°, +°°]. The contents of the domain is shown below each expression. 59 The Qualitative Engineering System Figure 4.9: Initial constraint network. If we add the additional constraint F2 > 0, the values - and 0 can be removed from the domain of F2. The expression F\ + F2 wi l l be constructed first. Addition is a constraint which is satisfied i f the values assigned to the arguments are consistent with the result shown in the qualitative addition table, Table 1.2. Similarly, the multiplication, subtraction, division, negation and reciprocal functions are all constraints. To find the variable assignments which satisfy the addition constraint, the Cartesian product of the domains of the child expressions is generated, and the corresponding value of the sum is determined according to Table 1.2. F,+Ft + -+ + 0 + + + - -0 - - + + 0-0 00 - 0 + + + -+ + 0 ? + + Figure 4.10: Constraint network with expression links added. In Figure 4.10, all possible combinations of the domains of F\ and F2 are shown in the table under the node for expression F\ + F2. The sum of the two values is shown in the left column of the table. A similar table is generated for the expression F\ - F3. The left-hand column of each table contains the elements of the domain 60 The Qualitative Engineering System set for the constraint expression, while the right-hand column holds the values of the arguments of the expression. The next step in solving the system of constraints is to enforce the equality constraint, which wi l l constrict the domains of the two expressions F\ + F2 and F\ - F 3 . As discussed earlier, relation links represent ordinal relations between expressions. Two relational links are added to the constraint network, as shown in Figure 4.11, linking the two expressions to the constant expression zero. The constraint interval of a constant expression is always equal to the domain, which is [0, 0] in this case. The interval [0, 0] is intersected with the constraint interval of the expressions F\ + F2 and F\ - F-$. Since the constraint interval of each is initially [-°°, +°°], their new values are [0, 0]. To enforce the constraint at the two expressions, the constraint interval is further intersected with each element of their domains. When intersection results in the empty set, the domain element is deleted. Figure 4.11: Constraint network after node consistency procedure. 61 The Qualitative Engineering System The updated domains are shown in Figure 4.11, which shows that F\ + F2 has one legal instantiation while F\ - F3 has three. At this point, node consistency has been achieved at the two expression nodes Fi + F2 and Fi - F3. Note that a relational link also exists between the variable F2 and the constant zero. For clarity, this link is not shown in Figure 4.11. The two expressions Fx + F2 and Fx + F3 now contain partial solutions to the problem. These partial instantiations must be combined to find the complete solution. The simple approach is to find all combinations of the domains of the two expressions which correspond to consistent assignments of variables. A more efficient method is employed by QES, which uses the concept of arc consistency, discussed in Section 3.2. In QES arc consistency is enforced on pairs of equations. The simple arc consistency A C - 1 [Mackworth, 1977], is used here. QES maintains a list of all equations in the system using the equationSystem data structure (Figure 4.8). Each time an equation is created, it is made consistent with each of the existing equations. If elements in the domain of an expression are deleted when arc consistency enforced between two expressions, the procedure is repeated until no further deletions are necessary. In the example problem, the expression F i + F2 is first added to the equationSystem structure. Since it is the first equation to be added, no deletions are performed. The second expression is then added, and the two equations are made arc consistent. The uppermost box in Figure 4.12 represents the equationSystem structure with its links to each of the equations. Looking at expression Fx - F3, one of the instantiations involves the assignment Fx = 0 and another involves Fx = +. The domains corresponding to these two assignments are deleted, because the only valid assignment for Fx in the expression F\ + F2 is Fx = -. Because deletions have occurred, the two expressions are checked for consistency again. Since no further deletions are possible, the arc consistency procedure is halted. The complete solution to the problem is found by simply merging together the domains of the two binary expressions. This results in the single legal instantiation: Fx = -F2 = + F3 = -. 62 The Qualitative Engineering System Although this problem has one solution, this is not generally the case when systems of qualitative constraints are concerned. If the additional constraint on F2 (F2 > 0) had not been added, there would be three legal instantiations instead of one. • + • Figure 4.12: Final consistency network. A few comments on efficiency are in order. This method of constraint satisfaction has the advantage that domain values are filtered out as soon as the relational constraint is imposed. The number of combinations is significantly reduced by removing inconsistent instantiations as early as possible in the search for a solution. This method fares no more poorly than backtracking, because illegal partial instantiations are pruned at the same time for each method. The arc consistency algorithm used here suffers from the inefficiency that all pairs of equations in the system are checked for consistency when any deletion is recorded. A consistency technique 63 The Qualitative Engineering System which uses propagation, such as the Waltz algorithm, or Mackworth's A C - 3 (Section 3.2), would be more efficient. 4.2.1 Example from Structural Analysis A n example of qualitative analysis from the field of structural mechanics is given in this section. This example illustrates some of the practical implications of qualitative analysis, as well as some refinements that may be made. F Figure 4.13: Pin-jointed structure. The pin-jointed plane structure model shown in Figure 4.13 wi l l be studied using qualitative analysis techniques. In the figure, the boxed numbers are the element labels and the other numbers are the node labels. The parameters of this model are the lengths (Lu L2, Liy LA) and axial stiffnesses (EAU EA2, EA3, EA4) of each of the four members, as well as the nodal displacements at the upper left node ( A ^ , A ^ ) , and the upper right node (AA^ , A R A ) . The horizontal displacements A ^ and Axi are considered positive i f to the right, and the 64 The Qualitative Engineering System vertical displacements A r a and A r a are positive i f upwards. A horizontal force which acts to the right is applied at the upper left node. One of the uses for such a model would be to estimate the deflected shape of the structure. This is the objective of the qualitative analysis. The qualitative equations which relate the nodal displacements to the material properties and geometry of the structure are given as follows: ^ 2 - A X 3 ] - F = 0 (4.3) L2 - 7 - L A r 2 = 0 (4.4) E2A2 r , EAA A X 3 - A X 2 ] + ^ - ^ - [ A X 3 + A r 3 ] = 0 ( 4- 5) E.A, E.A. r , ^ - A r 3 + - ^ - [ A ^ + A r 3 ] = 0 (4.6) These qualitative equations are very similar to the usual quantitative equations. The difference is that positive numeric constants have been omitted. Positive constants may be eliminated from products, because the positive sign value acts as the identity for multiplication in the domain of signs. The input for QES which is used to solve this problem is shown in Figure 4.14. The QES program accepts input in a format that is quite similar in form to the problem specification that has been given here. The variables in the problem are defined as dx2 , dx3, dy2, and dy2, which have their obvious counterparts in the notation used here. The output produced by QES is shown in Figure 4.15. The analysis produces four solutions to the problem, the first of which is the correct solution: Ajre = + Are = 0 A « = + A r a = -. 65 The Qualitative Engineering System | |3 Qualitative Engineering System | c:\qualan\q rapp\apconn.dat] = | Elle -Edit Analyze Options Window .Help //Pinned and Braced Frame //30.08.95 h // Declare variables variable dx2, dy2, dx3, dy3 constant EA1, L1 constant EA2. L2 constant EA3, L3 constant EA4, L4 constant F // Constrain variables constrain F > 0 constrain EA1 > 0 constrain LI > 0 constrain LI < +INF constrain EA2 > 0 constrain L2 > 0 constrain L2 < +INF constrain EA3 > 0 constrain L3 > 0 constrain L3 < +INF constrain EA4 > 0 constrain L4 > 0 constrain L4 < +INF // Form equations and constrain constrain EA2/L2 * (dx2-dx3) - F = 0 constrain EA1/L1 * dy2 = 0 constrain EA2/L2 * |dx3-dx2) + EA4/L4 * jdx3+dy3| = 0 constrain EA3/L3 * dy3 + EA4/L4 * (dx3 + dy3) = 0 • i—IIPIM] II i ^ - i 1—I-I 1 i ' - ' i - i n r . a = » i u » r r r n - r n - M n " i ri—tUxOlAxi • = i l Figure 4.14. QES input for pin-jointed structure. The result of this analysis is a typical result in qualitative analysis: multiple solutions are generated but the 'correct' solution to the problem is always contained in the set of solutions. The other solutions are not, strictly speaking, incorrect, because they are a correct solutions to the qualitative model. A qualitative model is usually a generalization of an associated quantitative model. The process of generalizing a quantitative model allows solutions which do not satisfy the quantitative equations. One of the prime sources of weakness in qualitative predictions derives from the weakness of the qualitative addition function. Looking at equation (4.3), the assignment A A ? = -, A A o = - causes the term (AA? - An) to evaluate to ?. Since the sign ? represents the interval [-oo, +oo], this combination of assignments satisfies equation (4.3), even though such values would not satisfy the corresponding qualitative equation. As mentioned previously, the qualitative addition function introduces uncertainty which tends to propagate through systems of qualitative equations. 66 The Qualitative Engineering System Qualitative Engineering System - (Analysis Output] :=1>FJIe. Options : Window Help i i S ^* A. wA SYSTEM SOLUTION: ARGUMENT NAMES: dy3 dx3 ARGUMENT LISTS: 1: - + Z: + 3: • 4: + dxZ + 0 + dyZ 0 0 0 0 it Number of system solutions: 4 Analysis time: 1.97 sec Total time: 2.14 sec 3* Figure 4.15. QES output for pin-jointed structure. One way of strengthening the conclusions drawn by qualitative analysis is to make some use of ordinal relations between qualitative variables [Forbus, 1984]. Ordinal relations may be used to reduce the uncertainty caused by the qualitative addition operator. Whenever qualitative addition results in the sign ?, three new cases may be generated to reflect different possible ordinal relations between the arguments involved in the addition operation (Table 4.1). + [X] + 0 + [Y] 0 - |X|>|Y| . + 0 |X| = |Y| + |X|<|Y| + 0 - |X|<|Y| 0 |X| = |Y| + |X|>|Y| Table 4.1: Qualitative addition with ordinal relations. Since qualitative analysis is troubled by combinatorial explosion, at first glance it may seem that considering ordinal relations between variables would exacerbate this problem. Without including ordinal relations, the number of combinations of two variables, each having three values, is nine, while there are thirteen possible 67 The Qualitative Engineering System combinations when ordinal relations are used (Figure 4.16). The advantage in using ordinal relations is that the relations provide additional information that may be used to filter inconsistent variable assignments. The ordinal relations are assertions about the relationship between two variables. This assertion may cause a contradiction at some stage of the solution process, which allows us to delete elements from the partial solution. In QES, the user has the option of including ordinal relations in the solution procedure. The structural model shown in Figure 4.13 was analyzed using information about ordinal relations. The result of this new analysis shows that instead of four possible solutions, there is only one valid solution, which corresponds to the expected behaviour for such a structure (Figure 4.17). X+Y XY --- - + IXI>IYI 0 - + 1X1 = IYI + - + IXI<IYI - 0-0 00 + 0 + - + - IXI<IYI 0 + - 1X1 = IYI + + -+ + 0 + + + Figure 4.16: Network representation of addition with ordinal relations. 68 The Qualitative Engineering System Qualitative hngineering System - [Analysis Outputj ° | FJIe Edit AnajyzeigQptlgns Window Help . .5 ^.1-SYSTEM SOLUTION: ARGUMENT NAMES: dy3 dx3 ARGUMENT LISTS: 1: - + dx2 dy2 0 |dx3|>|dy3| |dx2|>|dx3| Number of system solutions: 1 Analysis time: 2.09 sec Total time: 2.31 sec Figure 4.17: QES output for structural analysis using ordinal relations. In addition to information about the values of the variables, a solution obtained using ordinal relations provides insight into the relationship between the magnitudes of variables. The analysis yields the following additional information: l A d > |A r a| I A d > l 4 » | These inferred ordinal relations enable us to generate a fairly concise qualitative graphical representation of the behaviour of the structural model, as shown in Figure 4.18. Figure 4.18: Graphical representation of solution to pin-jointed structural problem. 69 The Qualitative Engineering System In the previous problem, qualitative analysis lead to a fairly clean, informative solution, considering the minimal amount of specific information that was furnished as input. It is important to note that, in general, a qualitative analysis produces more than one solution. Increasing the number of variables in a problem leads to a rapid increase in the number of combinations which must be considered, and also, an increase in the number of solutions. The following problem illustrates this concept. Figure 4.19 shows the graphical representation of a model of a structure. The model contains three members, each member / with associated length Lh axial stiffness EAit and bending stiffness EIt. As in the previous structural analysis example, a lateral force F directed towards the right acts at the upper left joint. The qualitative equations which may be used to derive the deflections from the loading and member properties given here: EXI, lX2 - e , L2 ElA , ^2 72 -1 - L ( A r 2 - A r 3 ) - ^ . - e 2 - e 3 '2 L-^ 2 © 2 -XX2 E2A2 E2I2 E2^2 T"( Ar3-A r 2 )+e 2 +e 3 = o = 0 \AX3-AX2\+—T *X3 = 0 £ 2 7 2 7 - ( A r 3 - A / 2 ) + 0 2 + e 3 L2 -^-(A 7 3-A r 2)+e 2+e 3 E,A, £ 3 / 3 3^ L e 3 -'X3 u3 j = 0, (4.7) (4.8) (4.9) (4.10) (4.H) (4.12) where again the qualitative equations have been obtained from the quantitative equations by deleting constant numeric terms from products. In this problem, the variables are the four translational degrees of freedom A ^ , 70 The Qualitative Engineering System Are, AA3, and A R A , and the two rotational degrees of freedom 8 2 and 9 3, where the numeral 'two' in the subscript denotes the upper left joint and the numeral 'three' the upper right joint. + + 4 A, A A, 2 e, 3 > + m 3 4 Figure 4.19: Structural frame model. A n analysis of the system of equations (4.7) through (4.12) using QES resulted in a total of 189 different solutions. This result shows that increasing the number of qualitative variables in the problem leads to considerably weaker qualitative predictions. In this case, the added complexity of the equations certainly has a detrimental impact on the analysis. In particular, the equations in this example include more complex sums than in the previous example. Even when ordinal relations are considered in the analysis, the number of solutions increases to 266, in contrast with the previous problem where the number decreased. The use of ordinal relations increases the number of combinations which must be considered, but the additional information simply does not cause enough of the assertions to be refuted. Although the 189 solutions resulting from simple qualitative analysis is less than the total number of possible combinations of six variables, each having three values (3 6 = 729), we gain little practical insight into the problem. Even though more 71 The Qualitative Engineering System sophisticated improvements than the use of ordinal relations may be applied to qualitative analysis, it is worthwhile to consider the application of pure qualitative analysis to engineering practice. In the previous two examples from structural analysis, very little information was specified about the various quantities in the problems. In most problems in engineering, partial knowledge about quantities takes the form of partial numerical values. For example, in the two structural analysis problems* the value of Young's Modulus E was only specified as lying in the interval (0, +°°]. In reality, we may know that the structure is to be constructed of timber, so that the value of E ranges, say, from 6000 M P a for sawn timber to 14000 M P a for glued-laminated timber. Even i f we have almost no idea of which material is to be used, a wide interval which includes values of E for timber, concrete and steel wi l l provide some information. In this general case, the value of E would range from about 6000 M P a for timber to 200000 MPa for steel, so that the range of E could be represented as the interval [6000, 200000] MPa. This observation suggests that, for an engineering application at least, it is more beneficial to pursue a formulation involving partial numeric information, rather than to seek refinements to the pure qualitative representation. This was the direction taken with the QES program. The implications of reasoning with partial numeric information is discussed in the next section. 72 4.3 SEMI -QTJANTITATrVE R E A S O N I N G In QES, partial quantitative information is incorporated using the interval representation. Integers are a simple, compact and flexible means of representing uncertainty or partially-specified numeric information. Since intervals may also be used to represent qualitative information, it is possible to develop a unified framework for representing and reasoning with qualitative and semi-quantitative knowledge. This was the approach used in the QES program, which is meant to support engineering decision-making at different stages of a project: from the initial stages, where qualitative information is more prevalent, to the later stages, which are characterized by primarily quantitative information. 4.3.1 Numeric Constraint Satisfaction The QES program is able to accept constraints in a number of forms, both qualitative and quantitative. Systems of numeric constraints are formulated as numeric constraint-satisfaction problems. The bounds consistency techniques developed by Lhomme [1993], were implemented in QES to solve numeric constraint-satisfaction problems. The details of this implementation within the QES framework wil l be discussed here. Consistency techniques are applied to numeric constraint-satisfaction problems by associating a dynamic domain with each variable and by propagating this domain through the constraints. The domains of variables are represented by intervals, so that as constraints are propagated from one variable to another, the bounds of the intervals are updated dynamically. This procedure can be examined more closely using the following example. Consider the system of constraints: Ci:7=X+l C2: Y=2xX Let the initial domains for the variables X and Y be Dx = [-«>, +°°] Dy = [-°°, +°°]. 73 The Qualitative Engineering System In the constraint network representation of QES, the constraints and variables may be described graphically as shown in Figure 4.20. The constraint network contains six expressions: X , Y, 1, 2, X + 1, and 2 x X. In the figure, solid arcs represent hierarchical links, while broken arcs symbolize relational links. Figure 4.20: Constraint network representation for numeric constraint problem. In the constraint network, changes propagate along relational and hierarchical links. The variable X has a hierarchical link to the expressions X + 1 and 2 x X recorded in its parents field, while the numeric constants 1 and 2 have links to X + 1 and 2 x X, respectively. The expressions X + 1 and 2 x X both maintain a relational link to the variable Y. Suppose the domain Dx is updated to [0, 10]. The following sequence of events transpires: • The change in Dx propagates from X to X + 1 through a parent link of X. • The constraint interval o f X + 1 is updated to [1, 11], using the current values of its children. • The change i n X + 1 is propagated through a relation link to Y. • Variable F i s updated to [1, 11]. • The change in Tcauses 2 x X t o be updated to [1,11], because 2 xXshares a relation link with Y. • X is recalculated using the new value of 2 x X and the right child, the numeric constant 2. The constraint interval o f X i s updated to [0.5, 5.5] • The change in X propagates to X + 1 by way of the hierarchical link. 74 The Qualitative Engineering System The domain changes propagate cyclically through the constraint network, and asymptotic convergence toward the solution (X= 1, Y= 2) occurs. !E | Qualitative Engineering System -[c:\qualan\qrapp\ncs1 .dat| = | EHe Edit Analyze Qptlons Window Help j>* 4k // Numeric constraint satisfaction problem f // Declare variables variable X. Y // Constrain variables constrain X >= 0 constrain X <= 10 constrain Y = X + 1 constrain Y = 2 * X // Print output print X. Y l i •in Figure 4.21: QES input for numeric constraint problem. The input for QES for this constraint-satisfaction problem is displayed in Figure 4.21. As shown, interval constraints are represented by inequality constraints, so that the assignment X = [0, 10] is entered as two constraints; X>0 and X< 10. The QES program uses the technique of arc B(w)-consistency to solve numeric constraint-satisfaction problems. The solution progresses according to the sequence discussed above, as shown in Figure 4.22. Numeric constraint s a t i s f a c t i o n : Modify X to [0.5,5.5] Modify (X+l) to [1.5,6.5] Modify Y to [1.5,6.5] Modify 2*X to [1.5,6.5] Modify X to [0.75,3.25] Modify (X+l) to [1.75,4.25] Modify Y to [1.75,4.25] Modify 2*X to [1.75,4.25] Modify X to [0.875,2.125] Modify X to [0.999998,1.000001] Modify (X+l) to [1.999998,2.000001] Modify Y to [1.999998,2.000001] Modify 2*X to [1.999998,2.000001] Normal termination Figure 4.22: Solution sequence for numeric constraint problem. 75 The Qualitative Engineering System The consistency algorithm terminates after about 20 cycles through the network, using a specified imprecision w of l.OxlO" 6. As shown in Figure 4.23, the final values for the intervals of X and Fare: X= [0.999998, 1.000001] y= [1.999998, 2.000001]. E9 Qualitative Engineering System - [Analysis Output] 1 Modify Y to (1.999998,2.000017) M Modify 2*Xto (1.999998.2.000017) Modify X to (0.999998.1.000009) Modify (X+1) to (1.999998.2.000009) Modify Y to (1.999998,2.000009) Modify 2*X to (1.999990.2.000009) Modify X to (0.999998,1.000004) Modify (X+1] to (1.999990,2.000004) Modify Y to (1.999998,2.000004) Modify 2*Xto (1.999998.2.000004) Modify X to (0.999998.1.000002) Modify (X+1) to (1.99999B.2.000002) Modify Y to (1.999998.2.000002) Modify 2*X to (1.999998.2.000002) Modify X to (0.999998.1.000001) Modify (X+1) to (1.999996.2.000001) Modify Y to (1.999998,2.000001) Modify 2*X to (1.999998,2.000001) Normal termination Printing Variable X EXPRESSION X: (0.999998,1.000001) n Printing Variable Y EXPRESSION Y: (1.999998,2.000001) Analysis time: 0.8 sec Total time: 0.71 sec Figure 4.23: QES output for numeric constraint problem. In the QES constraint network, three distinct types of constraint propagation are used: • From an expression to a parent, through a hierarchical relation. • From an expression to a child, also through a hierarchical relation. • From one expression to another, by means of a relation link. These types of propagation are shown graphically in Figure 4.24, and are detailed in the following discussion. 76 The Qualitative Engineering System + [ X , X ] + [ 7 , 7 ] = [ ( X +D> (x + Y)] - [ X , X ] - [ 7 , 7 ] = [ ( X - 7 ) , ( X - 7)] X [X, X ] x [ 7 , 7 ] = [min(X x 7 , X x Y, X x Y, X x Y), max(X x Y, X x Y, X x 7 , X x ?)] / [ X , X ] / [ 7 , 7 ] = (-oo, +00) if (7 < 0) and (7 > 0) = [min(X / 7 , X / F , X / r, X / 7 ) , max(X / 7 , X / 7 , X / 7 , X / 7)] Table 4.2: Constraint propagation to parents Propagation to parents A change in one of the children of an expression requires the expression to be recalculated. Propagation in this sense is straightforward, given the convenient representation in QES of expressions as trees. The details of this type of propagation follow directly from interval arithmetic (Appendix A) . In the following discussion, the 77 The Qualitative Engineering System notation of Moore [1966] is used for interval arithmetic; an interval is denoted by a capital letter, say X , where X= [X, X]. Given the set of basic constraints available in the QES system, Table 4.2 summarizes the details of the arithmetic. Note that Table 4.2 covers only closed intervals. Open and half-open intervals are handled in a similar way. Propagation to children Given a binary expression Z = X o Y, where the symbol V indicates an operator, equality requires that the argumentsXand 7be updated when Z is modified. Note that a distinction must be made between the right and left arguments in a binary expression, since, in general, X ° Y ± Y ° X. Table 4.3 lists the arithmetic which must be performed to update the children of an expression. In Table 4.3, X denotes the left hand operand and Y the right operand. Expression Left Right + Z=X+Y X=Z-Y Y=Z-X - Z=X-Y X=Z+Y Y=X-Z X Z=XxY X=ZIY Y=ZIX / Z=XIY X=ZxY Y=XIZ Table 4.3: Constraint propagation to children. Propagation through ordinal relations The propagation of constraints through relation links is useful for both qualitative and quantitative analysis. This technique becomes even more useful when additional relational constraints may be inferred from existing ones, a procedure called constraint inference. Constraint inference wi l l be described in a following section. Relational constraints, which take the form X rel Y, where X and Y are expressions, are detailed in Table 4.4. The equality constraint is identical with the intersection operation on intervals (Appendix A) . A constraint 78 The Qualitative Engineering System operation that does not meet the condition listed in Table 4.4 results in an assignment of the empty set (0) to each variable involved in the constraint. This result indicates that an inconsistency exists in the constraint network. This information is indicated to the user of the system. Relation Condition Procedure < X < Y X<Y i f X > ? t h c n X = ? i f Y <X then 7 =X > X > Y i f ? > X t hen? = X i f X <Y t h e n X =Y X = Y X < ? and Y < X i f X >Y t h e n X = ? else ? = X ifX <Y t h e n X = 7 else Y=X Table 4.4: Constraint propagation through ordinal relations. A noteworthy property of propagation over relation links is that modifications to interval bounds always results in an interval of decreased width. This means that the quantitative precision of a variable can never decrease. This property has significant impact on the convergence of numeric consistency algorithms, because intervals shrink monotonically as the algorithm progresses. A n additional detail not recorded in Table 4.4 is that a modification to a bound is only performed when such a modification would result in a change of more than a specified amount. This specified amount is the authorized imprecision w, which is used to terminate the propagation algorithm. 79 The Qualitative Engineering System 4.3.2 Interval Rounding Due the finite nature of computer arithmetic, unexpected results occur in interval computations, especially when dealing with degenerate intervals. In some cases, repeated operations on an interval can cause the upper bound to be modified to a value less than the lower bound. This condition would cause an inconsistency of the sort described by a failed condition in Table 4.4. Proper interval rounding avoids this condition, but more importantly, also ensures that the exact solution is always within the interval bounds. The imprecision of machine arithmetic in interval arithmetic is accounted for by incrementing the upper bound and decrementing the lower bound of each new interval by a small amount at each operation. Rounded interval arithmetic is implemented in QES in the following manner, suggested by Moore [1979]. In QES, the computation of the left and right endpoints of intervals is a separate operation. To take error in finite-precision computer arithmetic into account, positive right endpoints of computed results are multiplied by a factor of the form (1 + 2"') for an appropriate integer t, depending on the number s of significant bits s > t carried in the mantissa of numbers for that particular machine representation. Negative left endpoints, similarly, are multiplied by a factor (1 + 2"'). 4.3.3 Soundness of Interval Methods By using established techniques for dealing with intervals, numeric consistency techniques are able to provide the important guarantee that the correct result wi l l be bounded by the domains of each variable. This is a guarantee which other methods such as Monte Carlo simulation and hill-climbing techniques cannot provide. One of the strengths of numeric constraint satisfaction algorithms is they are able to solve interval equations even when a closed-form formula cannot be obtained. A number of numerical simulation techniques may also be applied to solve these types of equations, including Monte Carlo simulation. In Monte Carlo simulation, complex equations are solved by picking at random a value for each variable which lies within the range of 80 The Qualitative Engineering System acceptable values for the particular variable. Each term in the equation is evaluated on these particular values, giving one possible value for each term. By iterating random choices, a range of possible values of the terms is found. In this way complex terms can be evaluated even though the value of the variables are not known with certainty. Another method which may be used to evaluate such expressions is to use hill-climbing techniques, which seek the maximum and minimum values of each quantity. Neither Monte Carlo simulation nor h i l l -climbing is a sound inferential technique [Davis, 1987]. They generally return a subset of the true range, and thus arbitrarily exclude legitimate possibilities. Experience with hill-climbers has found them to be slow and unreliable [McDermott, 1984]. The assurance that the correct result is bounded by the domains of variables comes from a basic property of interval arithmetic [Moore, 1966]. Let>> =flx) define a function where x is within an interval X, and where F(X) is also an interval which has as a lower bound the minimum value of any fix), and upper bound the maximum value of any fix). This property is stated as: VxeX,fix)eF(X). This result is significant in the context of the soundness of interval analysis techniques. While any other floating-point calculation provides simply an estimate of the correct result of a computation, interval methods guarantee bounds for the correct result. 4.4 CONSTRAINT INFERENCE A number of additional techniques, both qualitative and quantitative, are used to QES to complement constraint propagation. Most of these techniques fall under the category of constraint inference methods, which have been used in systems such as Quantity Lattice [Simmons, 1986]. Constraint inference is a way of deriving new constraints from existing ones. Three types of constraint inference used in QES are relational arithmetic, constant elimination arithmetic, and graph search. 81 The Qualitative Engineering System + XrelO => (X+Y)relY YrelO => (X+Y)relX - XrelY => (X-Y)relO X x>o&r>o => (Xrell=>(XxY)relY)& (Yrel 1 => (Xx7)re/X) X>0&7<0 => (Xre/l=>Fre/(Xxy)& (r>e/-l =>(Xx7)re/-X) X<0&7>0 => (Xn?/-1 = > ( I x i ) r e / - l ) & (7re/l =*Xre/(Xx7)) x<o&r<o => fXre/ -1 =>-Yrel(XxY))& (Yrel-l=>-Xrel(XxY)) / x>o&r>o => XrelY =>(XIY)rel\ X>0&7<0 => Xrel -Y=*-lrel(X/Y) X<0&7>0 => Xrel -Y=>(X/Y)rel -1 X<0&7<0 => XrelY^ \rel{XIY) For rel e {<,<>, >, = *} Table 4.5: Relational arithmetic axioms. 4.4.1 Relational Arithmetic Interval arithmetic sometimes leads to results which are weaker than would be expected. One such limitation of interval arithmetic is the selection problem. Given the relation X > Y, and the assignments X = (0, 1], Y = [0,1), we should be able to infer that (X- Y) = (0,1], since X> Y. In general, interval arithmetic does not even allow one to determine that X - X = 0. Using interval arithmetic, if X = [1, 2] then X - X = [-1, 1]. Only by 82 The Qualitative Engineering System knowing that both intervals refer to the same quantity can we infer that the result is [0, 0]. Another limitation of interval arithmetic is that sometimes it cannot increase our knowledge at all. If we are given two quantities X and Y, and all we know is that X = Y + 5 and Y = [-oo, +oo], interval arithmetic leads to the result X = [-oo, +oo]. Although we know tha tX> Y, interval arithmetic is not able to capture this fact. A n arithmetic technique called relational arithmetic may be used to compensate for both these deficiencies. Relational arithmetic maintains constraints on the qualitative relationship of an arithmetic expression to its arguments. The axioms of relational arithmetic are given in Table 4.5. 4.4.2 Constant Elimination Arithmetic Another type of arithmetic which may be used to reason about relationships between two arithmetic expressions is constant elimination arithmetic [Simmons, 1986]. This type of arithmetic provides inference rules for a simple form of algebraic simplification. Constant elimination axioms allow us to infer that i f A = B +X, C = D +X, and B> D, then A > C. Axioms for constant elimination are shown in Table 4.6. + XrelY (X+Z)rel (X + Z) - XrelY (X-Z)rel (Y-Z) XrelY (Z-Y)rel(Z-X) X X>0&XrelY => (XxZ)rel (YxZ) X<0&Xre!Y =* (YxZ)rel(XxZ) / XZO&XrelY (X/Z)rel (YIZ) X<0&XrelY (Y/Z)rel(X/Z) F o r r e / e { <,<>, >,=,#} Table 4.6: Constant elimination axioms. 83 The Qualitative Engineering System 4.4.3 Graph Search In order to invoke the axioms discussed above, information about ordinal relations between expressions is required. In some cases it is possible to infer new ordinal relations from a given set of ordinal relations on expressions using a technique called graph search. Graph search is conveniently implemented in a constraint network. Consider the constraint network shown in Figure 4.25. Given the relations A < D and D = E, it is possible to deduce that A < E. The transitivity table (Table 4.7) enumerates the relationships between two inequalities which share a common expression. Entering the transitivity table at the intersection of the row labeled < and the column labeled =, we find the relation < In a constraint network, a simple breadth-first search [i.e. Knuth, 1968] may be used to find a path between two expressions. In the constraint graph of Figure 4.25, we wish to find the relationship between the expressions A and C, even though they are not directly connected by a relation link. [2:*] Figure 4.25: Constraint network for graph search example. The search starts at the expression A and proceeds until the expression C is reached. As each expression is visited, the relationship of that particular expression with the variable v4 is recorded. In the figure, the notation [n: ret] is used to indicate that the relation rel is written at the expression node at the /ITH step of the algorithm. For example, since the sign '<' was written at node D in step 1, this information along with the relation '=' on 84 The Qualitative Engineering System the arc linking nodes D and E, is used with the transitivity table to determine that '<' must be entered at expression E. In some cases, more than one path may exist between two expressions in a constraint network. If this occurs, the results of each path may be combined to produce a 'tighter' result. In Figure 4.25, two paths lead from expression A to expression C. On the third step of the algorithm, the sign '<' is written at the node E. Traversing the paiaA-B-E we find that A > E. Combining the relations '<' and '>' we may deduce that^4 = E. If the graph search is able to determine a constraining relation between two expressions, the relation may be cached by adding a new relation link between the two expressions. A subsequent query to the constraint network can use this information to quickly determine the relationship between two expressions. < < > > < < < ? ? < ? < < < ? ? < ? > ? ? > > > ? > ? ? > > ? = < < > > = * ? ? ? ? ? Table 4.7: Transitivity table for ordinal relations. Constraint inference furnishes techniques which complement the constraint-satisfaction methods discussed earlier. Systems which rely only on constraint influence have a number of limitations however. One of the problems with constraint inference is that it is difficult to control and it often falls into infinite loops. In the constraint network shown in Figure 4.25, the relation links are depicted as directed arcs between pairs of expressions. Relations between quantities are more accurately described by bi-directional links on the constraint graph. If the links in Figure 4.25 were bi-directional, it would be possible to traverse the links A-B and B-E in the reverse direction, that is, E-B and B-A. In this case the graph search algorithm would enter an 85 The Qualitative Engineering System infinite loop, repeating the cycle A-D-E-B-A The constraint propagation techniques discussed in connection with constraint satisfaction algorithms are easier to control than constraint inference. In addition, as new constraints are inferred, it may be difficult to ensure that they will be useful in answering queries to the network. It is generally inefficient to use graph search to determine the relation between each pair of expressions in the network, and to record all of these relationships in the network. QES exploits the constraint network paradigm to perform both qualitative and quantitative reasoning within an integrated framework. Qualitative reasoning, quantitative interval arithmetic, arithmetic reasoning and graph search are complementary techniques which are used to extract a considerable amount of information from uncertain or incompletely specified input data. Further research is required to ascertain which types of reasoning are best suited various types of engineering problems. One goal in developing the QES system was to provide an accessible and intuitive interface which could be used to pursue such research. 86 4.5 IMPLEMENTATION A l l of the techniques discussed in this chapter have been successfully implemented in the QES system. The examples given previously show that QES accepts input in a natural and intuitive form. This section discusses details of the implementation of QES, and the motivation behind these details. 4.5.1 Platform A prime goal of this research was to make accessible to the engineer a number of useful techniques for manipulating and reasoning with incompletely specified information. QES is implemented in the Microsoft Windows® environment. The justification for this choice of operating platform is based primarily on accessibility. Microsoft Windows is an operating environment that is becoming increasingly popular throughout the world. Many modern software products, including serious numerical analysis tools for engineers, have been introduced in Windows-compatible versions. Most of the qualitative reasoning techniques discussed in this thesis have been previously implemented in software, but almost all have been on mainframe computers. The benefit of QES is that a number of different methods have been incorporated in one software program, and that the program is much more accessible than mainframe implementations. Microsoft Windows runs on the personal computer, a tool whose absence from the modern engineering office is more remarkable than its presence. The benefits of development in Microsoft Windows to program users are not limited to accessibility. Two other advantages are compatibility and consistency. In the past, software programs had to be supplied with a number of different video and printer drivers to ensure compatibility with existing hardware. The issue of hardware compatibility is one which is being increasingly assumed by platforms such as Microsoft Windows. Consistency of applications is a factor which affects the amount of time required by a user to gain familiarity with a program. A l l Windows programs feature a number of common interface items. These items are 87 The Qualitative Engineering System immediately recognizable to anyone who has used a Windows program, and have the effect of immediately establishing familiarity with the user. Another factor which influenced the decision to use Microsoft Windows is the capability of transferring data between different Windows applications. In Windows, a feature called dynamic data exchange (DDE) allows data to be transferred to and from spreadsheets, word processors, numerical analysis programs other applications. Although not currently implemented in QES, it would be possible to access data from spreadsheets and other programs. Another means exists by which QES may interact with other programs. Some programs may access the QES constraint network through function calls to a version of QES which has been compiled as a Windows dynamic link library (DLL). Tools are available under Windows for programming sophisticated user interfaces. Using one of these tools, the program ToolBook* , for example, a variety of domain-specific applications may be built which are able to access the QES system. Other Windows applications are also able to call Windows D L L s . For example, the expert system shell Kappa-PC* can be used to access the QES functions. In this way, an expert system wil l be able to provide some of the deep reasoning which many such systems lack. The QES application consists of a number of text windows, as shown in Figure 4.26. Specifically, there are four different types of windows: one input window and three types of output windows. The input window is used to create a text file or to modify a file that has been created with any other DOS or Windows text editor. QES incorporates a parser which translates text into QES commands. The three types of output window are: 1) the status, or information window; 2) the result window, and; 3) the debug window. The status window displays the progress of the parser and the qualitative and quantitative analysis routines. The result window shows the intermediate and final results of computations performed during the analysis procedures. The debug window is used to display detailed status and result information together. The debug window, not shown in Figure 4.26, is generally used to track errors in the solution process or simply to get a closer view of the a product of Asymetrix, Inc. a product of IntelliCorp, Inc. 88 The Qualitative Engineering System progress of constraint satisfaction and constraint inference algorithms. The contents of each of the output windows may be saved to disk for later reference. Figure 4.26: The appearance of QES. 4.5.2 Input Format The QES system accepts input in a format that is both flexible and natural. The examples which have been used to illustrate the function of QES have shown that the.system is able to accept input in a form similar to that in which engineering problems are ordinarily specified. The language of constraints allows for flexibility of input by requiring the user to specify only that information which is available. A text parser was developed as part of QES in order to achieve the goal of providing a system that would be both accessible and simple to 89 The Qualitative Engineering System use. The parser allows the user to enter constraints as easily as one enters a formula in a spreadsheet-based application. The constraint language used by QES is detailed in the following discussion. Constants and Variables As mentioned, QES is a quantity database, where quantities are represented by objects called expressions. Expressions may be constants, variables, or more complicated entities built up from unary and binary combinations of constants and variables. Constants may be numeric or qualitative in nature. A numeric constant is a real number, say the number 2.1, while a qualitative constant is an interval, for example, [0, +°°). In QES, the names of both variables and constants must be declared before they are used in an expression. For this purpose, the v a r i a b l e and c o n s t a n t keywords are used. The format of these keywords is as follows: v a r i a b l e Vx [, V2, Vm] c o n s t a n t C\ [, C 2 , C„] where Vu V„ and Cx, C„ are alphanumeric strings, with the limitation that the first character is alphabetic and that the remaining characters are alphabetic, numeric, or the underline character (_). The square brackets indicate that one or more variables or constants may be declared using a single statement. The syntax for variables and constants is summarized in Table 4.8. In the table, the integer, real, and infinity constants indicate entities which are not declared using the c o n s t a n t statement. These items may be used in expressions directly. The representation of constants as integers, reals and the infinities reflects the fact that QES uses techniques which reason on the domain of the extended reals, 9t" = { 3i u ±«> }. Interval methods provide for the domain of extended reals, and operations involving the infinities produce expected results. For example, division by one of the infinities produces zero as the result. The infinities are useful in the context of engineering reasoning, because often simplifying assumptions are made in engineering models. For example, in structural engineering, the statements "assume the beam has infinite axial stiffness" or "assume that a beam of infinite length lies on an elastic foundation." Such statements are also common in other domains, such as thermodynamics. 90 The Qualitative Engineering System entity valid characters example variable - name constant - name - integer -real - infinity a...z,A... Z, 0 ... 9, _ a ...z,A ...Z,0 ... 9,_ 0 ... 9 + , - , 0 . . . 9 , E , e +, -, I, N , F, i , n, f t, A1, deflection atnodeJ c, Cl, alpha 4, 2432 17.9, 23.45E6, 1.02e+06 +INF, -INF Table 4.8: Format of variables and constants. Constraints In QES, equations and inequalities are formulated as constraints. The c o n s t r a i n keyword is used to specify a constraint, according to the following syntax: c o n s t r a i n LHExpression re I RHExpression where LHExpression and RHExpression denote the left- and right-hand expressions, and rel is one of the relations {=,<,<,>,>}. Expressions must involve only variables, constants, one of the operators { +, *, -, / }, and brackets { ( , ) } . / / Val id syntax examples constrain Alph > 0 constrain Bet < +INF constrain Alph = Bet + C constrain Alph = -Bet + C constrain Alph = + Bet * C constrain Alph = Bet + 2/C constrain Alph = Bet + -.01234* C constrain H =1.348 E +2 - Alph constrain G = Alph + Bet *C constrain H =Alph + Bet *C - (D2 + Alph)/G constrain ((Alph + Bet) * C-D2)/G = 0 Figure 4.27: Examples of valid constraint syntax. 91 The Qualitative Engineering System Although the number of operators is small, it represents a set of basic constraints which can be combined to create a much larger set of constraints. In QES expressions are evaluated from left to right following the conventional order of precedence (i.e., *,/ higher than +, -). Brackets may be used to change the order of evaluation, and to clarify the structure of expressions. Figure 4.27 gives of examples of valid expression syntax. Although all the relations have the effect of placing a mutual constraint on the left-hand and right-hand expressions, the equality relation has the additional function of assigning the value of an expression to a temporary variable. The assignment function allows one to build up complex expressions from a number of simpler expressions. Assignment is of particular importance in qualitative analysis, where an expression generally evaluates to a list of values, rather than a single value. When assignment is invoked, the domain list of the left-hand expression is replaced by the domain list of the right-hand expression. Assignment occurs automatically in qualitative analysis whenever the left-hand expression is a variable, and the right-hand expression is not a constant. In qualitative analysis, because expressions evaluate to lists of values, the form of the c o n s t r a i n statement is limited to two cases: 1. Either the left-hand or the right-hand expression must be a constant, i.e. c o n s t r a i n A + B / C = 0 c o n s t r a i n 1 = A * B ; or 2. The left-hand expression is a variable, and the right-hand expression is not a constant, indicating assignment: c o n s t r a i n D = A + B / C . It should be noted that these limitations apply only to qualitative analysis, in cases where either the left-hand or the right-hand expression evaluates to a list of intervals, rather than a single interval. Propagation over relations occurs is an otherwise identical manner in qualitative and quantitative analysis. 92 The Qualitative Engineering System 4.5.3 Output Format The final results of most computations, as well as some intermediate results, appear automatically in the result window of QES. The contents of a variable may be explicitly requested using the p r i n t keyword in the input file: p r i n t V\ [, V2 Vm\ where Vu Vm are variable names. The graph search algorithm may be invoked at any time using the q u e r y keyword: q u e r y V\ ? V2 The use of these two keywords is shown in Figure 4.28, in which the input window is the upper left window, the status window at the upper right, and the result window is at the bottom of the display. The example shown here is a simple application of constant elimination arithmetic. Constant elimination axioms are tested as the constraints are entered in system. New constraints that are inferred as a result of constant elimination are added to the constraint network. The results of these new constraints are retrieved by performing a query operation. In Figure 4.28, the status window displays information about the operations that are performed by the system as it interprets the input file and enters the new constraints in the constraint network. The output window shows that the expression C has one variable amoung its arguments, namely X. The expression C has three possible values, depending on whether the value o f X i s -, 0, or +. In QES the user has the option of specifying whether one of the symbols {-, 0, +,?,*} or the conventional interval notation showing the upper and lower bounds is used to represent interval values. The '* ' symbol is used to represent an interval which is not represented by the other symbols in the set. If this symbol appears in the result of an analysis, the conventional interval notation should be used for display. 93 The Qualitative Engineering System Qualitative Engineering System Elle wgdlt Analyze ^Qptlons Syjlndow; Help // Constant elimination axiom 1 constant B,D variable A.CX constrain B > 0 constrain D > 0 constrain B > D constrain A = B + X constrain C = D • X print C query A ? C 6 P I I B Information Checking constant elimination Relational operator = Relational link added Get variable [6] C Get variable |4] D Get variable |7]X Binary operator add New binary expression (D+XJ Checking constant elimination Launching query: D ? 0 Query result: D > 0 Launching query: D ? B Query result: D < B Axiom 20 invoked: (D+X) < (BtX) Relational operator = Relational link added Get variable [5] A Get variable [6] C Relational operator ? Launching query: A ? C Query result: A > C EXPRESSION C: ? | ARGUMENT NAMES (1): X ARGUMENT LISTS |3): 1 ?: 2 +: D 3 +: + Query result: A is greater than C I I I Figure 4.28: Output for constant elimination example. 9 4 5. R E L A T E D W O R K The research undertaken here seeks to address the shortcomings of a number of different computer applications aimed at reasoning with incomplete information in the engineering environment. The trend of the research in this field has been towards rule-based systems, most of which incorporate some capability for qualitative reasoning, and some of which allow for qualitative knowledge, usually represented in the form of procedural information. Although some research in artificial intelligence has been directed at developing a unified framework for qualitative and quantitative reasoning, the products of this research have apparently had little success in practical engineering applications. Early approaches to qualitative computer applications dealt predominantly with experiential and heuristic knowledge of a particular domain. Slater [1986] developed an expert system for structural engineering design. This system was intended as primarily a teaching tool to aid students in sketching deflected shapes and bending moment diagrams for various statically-indeterminate beam structures. A number of general rules and approximations have long been used in the preliminary selection and design of structural members [i.e., Benjamin, 1959]. Another structural engineering application, the expert system HI-RISE [Maher, 1984] was developed for the initial proportioning of plane structural frames subject to lateral and gravity loads. In the earthquake engineering field, a knowledge-based system has been developed to evaluate preliminary structural designs [Ganguly, 1990]. These rule-based systems suffer from the same problems which plague many expert systems; a lack of generality and heavy dependence on a specific domain. As a means of addressing the deficiencies of expert systems, qualitative reasoning techniques were utilized in some engineering applications. Several of these applications have used the Q S I M formulation discussed in Section 1.3.3. [Roddis, 1988; Biswas, 1991; Fruchter, 1991; Fruchter, 1992]. The QSTRUC system [Fruchter, 1991], working in the domain of structural engineering, captures fundamental laws such as equilibrium, as well as experiential knowledge. The QSTRUC application also incorporates the Quantity Lattice system 95 The Qualitative Engineering System [Simmons, 1986], which is used to resolve some of the ambiguities of the qualitative calculus. Fruchter [1992] also developed a number of model-based reasoning strategies for reasoning about the lateral load resisting system of structures, incorporating the techniques used in QSTRUC. The power of matrix analysis as technique for quantitative analysis in engineering suggests an analogous approach for qualitative analysis. Schwartz [1992] describe the application of qualitative matrix analysis to structural engineering. The matrix inversion procedure is described as a combination of numerical, qualitative, and heuristic techniques. Although the qualitative matrix approach is an attractive concept, the weakness of qualitative algebra diminishes its effectiveness considerably in comparison to the gains offered by quantitative matrix analysis. Bozzo [1992] introduces the concept of qualitative parameter vectors as part of the space-centered approach to qualitative evaluation of preliminary structural designs. The space-centered approach incorporates ordinal relations between parameters as well as the constant elimination technique. The qualitative reasoning research described here has produced disappointingly few practical engineering tools. Few solutions to problems of realistic complexity have been offered. The general topic of complexity and combinatorial explosion in qualitative reasoning seems to have been avoided. At the same time, many researchers suggest that a greater amount of quantitative information be incorporated into qualitative reasoning formulations. The application developed as part of the research for this thesis, QES, is able to augment qualitative reasoning with partial numeric information, which addresses this concern. Relational arithmetic, constant elimination arithmetic and graph search were implemented in the Quantity Lattice system [Simmons, 1986]. Simmons was one of the first to integrate qualitative and quantitative reasoning techniques in one system, which has found several useful applications in a number of domains, including geology and semiconductor fabrication. Many of the techniques used in Quantity Lattice are examples of constraint inference. Although constraint inference is difficult to control, it complements both 96 The Qualitative Engineering System numeric consistency algorithms and qualitative constraint satisfaction procedures. One difference between Quantity Lattice and QES is that in Quantity Lattice, interval constraint propagation is not bidirectional. Propagation proceeds in one direction only: to an arithmetic expression from its arguments. To achieve inferences in the other direction, the user must explicitly enter constraints for each argument of the arithmetic expression. For example, given the expression (A + B), one would assert B = (A + B) - A. Simmons claims that this feature was a design decision that was based on efficiency reasons. Recognizing the limitations of reasoning with purely qualitative information, researchers have implemented qualitative reasoning techniques in frameworks that are able to reason at different levels of abstraction [Roddis, 1988; Murthy, 1988]. Heuristic and qualitative knowledge may be used to guide the selection of appropriate procedural knowledge. Such an approach has been used in the domain of fatigue and fracture in steel bridges [Roddis, 1988]. Numeric analysis routines are included, which represent domain knowledge that is largely procedural. Reasoning at different levels of abstraction is of fundamental importance in engineering problem-solving. The effective utilization of heuristic, qualitative, semi-quantitative and quantitative information would almost certainly require that the topic of abstraction be addressed. 97 C O N C L U S I O N S As part of this research, a framework was developed which supports both qualitative and semi-quantitative reasoning techniques. These techniques are complementary; each is able to reason with information which the other cannot utilize. Qualitative techniques derive their strength from the power of abstraction, while semi-quantitative methods are able to make use of incomplete numeric information, which is almost always available in practical circumstances. The level of uncertainty present in an engineering project is seldom static. In the early, conceptual stages, there is more uncertainty than in the final stages. The framework developed here is capable of providing support for engineering decision-making from the conceptual stage, where primarily qualitative information is available, to the latter stages, where more numeric data is known. A computer program was implemented on the basis of the framework described here. A key element of this program is that it relies on the constraint satisfaction paradigm. Constraints are a powerful concept in the domain of engineering problem-solving. Much of an engineer's knowledge is best expressed in terms of what is, or conversely, what is not allowed. Functional requirements, material limitations, labour considerations, environmental characteristics and the laws of physics can all be expressed in the language of constraints. The constraint formulation allows the user of the program to specify only that information which is known at a particular stage of an engineering project. It was shown that the reasoning techniques presented here have advantages over conventional approaches to dealing with uncertainty in engineering practice. There are currently many tools available which are able to perform detailed numerical analysis. Unfortunately, most require that the input be completely specified, and even though it is possible to estimate values for unknown parameters, the cost and the reliability of such an approach is questionable. There also exist many analysis tools which are based on probability methods. Although these techniques are useful when the uncertain quantities are the result of random natural processes which can be measured, they generally require that more information be specified about the quantities 98 Conclusions involved before an analysis can be made. When random natural processes are not involved, arbitrary assumptions about the shape of probability functions must be made. The number of arbitrary assumptions is more than required for the interval representation used in research presented here. In addition, numerical simulation techniques based on probability, such as Monte Carlo methods, are not sound inferential techniques and thus may exclude legitimate solutions. The techniques discussed in this thesis are all logically sound. The interval analysis methods employed are able to guarantee bounds on the correct solution. Expert systems represent another approach to coping with uncertainty in engineering practice. Expert systems have been applied successfully in engineering domains, partly because they are able to reason with valuable experiential and heuristic knowledge. Most expert systems suffer however from an inability to reason using fundamental domain knowledge. On the other hand, qualitative reasoning uses a detailed domain model, an explicit representation of the first principles of the domain that underlie heuristic knowledge. Purely qualitative reasoning methods developed in artificial intelligence research were applied to a practical problem in the domain of structural engineering. It was found that the conclusions that may be drawn from such methods become rapidly weaker as the number of unknowns in the problem is increased. Although a limited number of problems were tested, the findings are not out of line with previous research. A number of attempts have been made by artificial intelligence researchers to resolve the ambiguity of predictions made using qualitative analysis. The approach used in this research was to augment qualitative analysis with partial quantitative information. A functional computer application was developed as part of this research. This program successfully implements a number of the qualitative and semi-quantitative reasoning strategies discussed in this thesis. As intended, the program runs on a platform which is both accessible and familiar. The computer application was also developed in a way which supports further research, since the platform on which it is implemented supports transfer of data between applications. 99 Conclusions Further research is recommended in order to establish the range of application of the computer program developed here. A variety of possible domains, from engineering planning to architectural design show interesting potential for such a program. 100 B I B L I O G R A P H Y Alefeld, G., and Herzberger, J. (1983) Introduction to Interval Computation. Academic Press, New York. Benjamin, J.R. (1959) Statically Indeterminate Structures. Approximate Analysis by Deflected Structures and Lateral Load Analysis. McGraw H i l l , New York. Biswas, G., Krishnamurthy, K . , and Basu, P .K. (1991) Applying qualitative reasoning techniques for analysis and evaluation in structural design. Seventh IEEE Conference on Artificial Intelligence Applications 265-268. Bozzo, L . M . and Fenves, G.L. (1992) Qualitative evaluation of preliminary structural designs. In Goodno, B.J. , and Wright, J.R. (Eds.), ASCE Proc. Eighth Conference, Computing in Civil Engineering and Geographic Information Systems Symposium 89-96. Buchanan, B . G . , and Smith, R .G . (1989) Fundamentals of expert systems. In Barr, A . , Cohen, P.R., and Feigenbaum, E . A . (Eds.), The Handbook of Artificial Intelligence, Vol. IV. Addison-Wesley, Reading, M A . 149-192. Davis, E . (1987) Constraint propagation with interval labels. Artificial Intelligence 32:281-331. Dechter, R. (1992) Constraint networks. In Shapiro, S.C. (Ed.), Encyclopedia of Artificial Intelligence, 2nd Ed. John Wiley, New York. De Kleer, J. and Brown, J. (1984) A qualitative physics based on confluences. Artificial Intelligence 24:7-83. De Kleer, J. (1993) A view on qualitative physics. Artificial Intelligence 59:105-114. Dormoy, J. and Raiman, O. (1988) Assembling a device. Proc, Seventh National Conference on Artificial Intelligence. Morgan Kaufmann, San Mateo, C A . 95-113. Forbus, K . D . (1984) Qualitative process theory. Artificial Intelligence 24:85-168. Forbus, K . D . (1993) Qualitative process theory: twelve years after. Artificial Intelligence 59:115-123. Freuder, E .C . (1978) Synthesizing constraint expressions. Communications of the ACM, 21:958-966. 101 Bibliography Fruchter, R., Law, K . , and Iwasaki, Y . (1991) QSTRUC: A n approach for qualitative structural analysis. In B . H . V . Toppoing (Ed.), Artificial Intelligence and Civil Engineering. Civil-Comp Press, Edinburgh 27-37. Fruchter, R., and Krawinkler, H . (1992) QLRS: A n approach for qualitative interpretation of lateral load resisting systems. In Goodno, B.J . , and Wright, J.R. (Eds.), ASCE Proc. Eighth Conference, Computing in Civil Engineering and Geographic Information Systems Symposium 253-260. Ganguly, I , Kausel, E . , and Sriram, D. (1989) A knowledge based system for deriving qualitative seismic behaviour. In Nelson, J.K. (Ed.), Proc. of the ASCE Structures Congress, Computer Utilization in Structural Engineering 418-427'. Goldstein, R .V . , and Entor, V . M . (1994) Qualitative Methods in Continuum Mechanics. Longman Scientific and Technical, Essex, England. Copublished with John Wiley and Sons, New York. Hansen, E . (1969) On linear algebraic equations with interval coefficients. In Hansen, E . (Ed.), Topics in Interval Analysis. Oxford University Press, London 35-45. Hayes, P.J. (1979) The naive physics manifesto. In Michie, D . (Ed.), Expert Systems in the Microelectronic Age. Edinburgh University Press, Edinburgh. Iwasaki, Y . (1989) Qualitative physics. In Barr, A . , Cohen, P.R., and Feigenbaum, E . A . (Eds.), The Handbook of Artificial Intelligence, Vol IV. Addison-Wesley, Reading, M A . 323-414. Karnopp, D. , Margolis, D . , and Rosenberg, R. (1990) System Dynamics: A Unified Approach, 2nd Ed. John Wiley and Sons. Knuth, D .E . (1968) The Art of Computer Programming. Addison-Wesley, Reading, M A . Kuipers, B.J . (1984) Commonsense reasoning about causality: Deriving behavior from structure. Artificial Intelligence 24:169-204. Kuipers, B.J . and Berleant, D. (1988) Using incomplete quantitative knowledge in qualitative reasoning. In Proc, Seventh National Conference on Artificial Intelligence. Morgan Kaufmann, San Mateo C A . 324-329. Kuipers, B J . (1993) Qualitative simulation: then and now. Artificial Intelligence 59:133-140. Kuipers, B.J . (1994) Qualitative Reasoning: Modeling and Simulation with Incomplete Knowledge. MIT Press, Cambridge, M A . 102 Bibliography Lhomme, O. (1993) Consistency techniques for numeric CSPs. In Proc. Thirteenth Joint Conference on Artificial Intelligence, IJCAII1993, Morgan Kaufmann, San Mateo, C A . 232-238. Mackworth, A . K . (1977) Consistency in networks of relations. Artificial Intelligence 8:99-118. Mackworth, A . K . (1992) Constraint satisfaction. In Shapiro, S.C. (Ed.), Encyclopedia of Artificial Intelligence, 2nd Ed. John Wiley, New York 285-293. Maher, M . L . (1984) HI-RISE: A Knowledge-based Expert System for Preliminary Structural Design of High Rise Buildings. Ph.D. Thesis, Department of Civi l Engineering, Carnegie-Mellon University, Pittsburgh, PA. McDermott, D . V . and Davis, E . (1984) Planning routes through uncertain territory. Artificial Intelligence 22:107-156. Montanari, U . (1974) Networks of constraints: fundamental properties and applications to picture processing. Inform. Sci. 7:95-132. Moore, R .E . (1966) Interval Analysis. Prentice-Hall, Inc., Englewood Cliffs, NJ . Moore, R.E. (1975) Mathematical Elements of Scientific Computing. Holt, Rinehart and Winston, New York. Moore, R.E. (1979) Methods and Applications of Interval Aritihmetic. Studies in Applied Mathematics, S IAM, Philadelphia. Murthy, S.S. (1988) Qualitative reasoning at multiple resolution. Proc, Seventh National Conference on Artificial Intelligence 296-300. Neumaier, A . (1990) Interval methods for systems of equations. Cambridge University Press, Cambridge. Oden, J.T. (1986) Qualitative Methods in Nonlinear Mechanics. Prentice-Hall, Englewood Cliffs, New Jersey. Puccia, C.J., and Levins, R. (1985) Qualitative Modeling of Complex systems. An Introduction to Loop Analysis and Time Averaging. Harvard University Press, Cambridge, M A . Raiffa, H . (1970) Decision Analysis: Introductory Lectures on Choices under Uncertainty. Addison-Wesley, Reading, M A . Raiman, O. (1991) Order of magnitude reasoning. Artificial Intelligence 51:11-38. 103 Bibliography Roddis, K . W . , and Martin, J.L. (1991) Qualitative reasoning about steel bridge fatigue and fracture. In Kuipers, B . (Ed.), Fifth International Workshop on Qualitative Reasoning about Physical Systems 302-317. Samuelson, P .A. (1983) Foundations of Economic Analysis. Enlarged Edition. Harvard University Press, Cambridge, M A . Schwartz, D .L . , and Chen, S.S. (1992) Spatial and temporal aspects of qualitative structural reasoning. In Goodno, B.J . , and Wright, J.R. (Eds.), ASCE Proc. Eighth Conference, Computing in Civil Engineering and Geographic Information Systems Symposium 277-284. Simmons, R. (1986) Commonsense arithmetic reasoning. Proc. Fifth National Conference on Artificial Intelligence 118-124. Slater, J.H. (1986) Qualitative physics and the prediction of structural behaviour. In Kostem, C .N. and Maher, M . L . (Eds.), Proc. of ASCE Symposium on Expert Systems in Civil Engineering 239-248. Tversky, A . , and Khaneman, D . (1977) Judgement under uncertainty: heuristics and biases. In Modern Decision Analysis, Penguin Books, London. Villagio, P. (1977) Qualitative Methods in Elasticity. Noordhoff International Publishing, Leyden, Netherlands. Waltz, D . L . (1975) Understanding line drawings of scenes with shadows. In Winston, P .H. (Ed.), The Psychology of Computer Vision 19-92. Williams, B . C . (1988) M I N I M A : A symbolic approach to qualitative algebraic reasoning. Proc, Seventh National Conference on Artificial Intelligence 264-269. Williams, B . C . (1991) A theory of interactions: Unifying qualitative and quantitative algebraic reasoning. Artificial Intelligence 51:39-94. Williams, B .C . , and De Kleer, J. (1991) Qualitative reasoning about physical systems: a return to roots. Artificial Intelligence 51:1-9. 104 A P P E N D I X A : P R O P E R T I E S OF I N T E R V A L S A n interval is a closed, bounded set of real numbers [a, b] = [x : a < x < b] (Al) Following the notation of Moore [1979], intervals wi l l be denoted capital letters. Further, i f X i s an interval, its endpoints are denoted X and X. Therefore, X= [ X , X] The degenerate interval [a, a] is treated the same as the real number a. If the real number x is in the interval X, this is written as x e X Two intervals are equal i f their endpoints are equal: The intersection of two intervals X and 7 is empty, X n Y = 0 , i f either X > Y, or Y > X. Otherwise, the intersection of X and Y is again an interval: If two intervals have nonempty intersection, their union, X KJ Y = [min(X, Y), m a x ( X , Y)], is also an interval. The transitive order relation < is extended on to the real number line to intervals in the following manner: X=Y i f X = Y a n d X = Y. (A.2) I n 7 = [max(X, Y), m i n ( X , 7)] . (A.3) X < 7 i f and only i f X < 7 . (A.4) 105 Appendix A Another useful transitive order relationship for intervals is set inclusion: l £ 7 i f and only i f Y<X and X <Y. (A.5) The width of an interval X = [X, X ] is defined by w(X) = X -X. INTERVAL ARITHMETIC The intervals X and Y may be treated as numbers, adding them as X + Y = Z, where Z = X + Y, and Z = X + Y. In other words, we can add the inequalities X<x<X and Y<y<Y to obtain X+X<x+y<X + Y. Thus, we can compute the set X+Y={x+y:xeX,yeY}. (A.6) The sum of two intervals is thus also an interval. It is the interval of sums of real numbers, one from the first interval and the other from the second interval. Similarly, the negative of an interval is defined as -X= -[X, X] = [-X, -X] = {-x:x el}. (A.7) The difference of two intervals is formed as follows: Y-X= Y + (-X) = {y-x : x e l j e Y}. (A.8) More briefly, the rules for interval addition and interval subtraction are written: [X, X] + [Y, Y] = [X + Y, X + Y] (A.9) [X,X]-[Y,Y] = [X-Y,X-Y] (A. 10) The reciprocal of an interval is defined as follows: \IX={\lx:xzX}. (A. 11) 106 Appendix A If Xis an interval not containing the number 0, then 1/X = [ 1 / X , 1 /X] . (A. 12) If X contains 0, so that X <, 0 < X, then x e X implies that l/x > \IX or (but not and) l/x < 1 / X . In this case the set (A. 11) is unbounded and cannot be represented as an interval whose endpoints are real numbers. The product of two intervals is defined XY={xy:xeX,yeY}. (A.13) which is again an interval, whose endpoints are calculated as X • Y = rmn(Xr,Xy.X>.XT) X • Y = max(Xr,XY,Xi:,Xr) (A. 14) The quotient of two intervals is defined as follows: X/Y=X(l/Y) = {x/y:xeX,y€Y}. (A.15) The term 1/7 is defined in (A. 11). If 0 is not contained in Y , then X T is an interval whose endpoints can be computed using (A. 12) and (A. 14). If X i s a more complex function, the following functions may be defined: X=inf(X) (A. 16) X = sup(X). * (A. 17) These functions may also be used for sets that are more general than intervals. If S is a nonempty bounded subset of % then we denote by DS = [ in f©, s u p © ] (A. 18) the hull of S, the tightest interval enclosing S. For example, D{a, b} is the interval with endpoints a and b, i.e. {a, b} = [a, b] if a < b, D{a, b} = [b, a] if a > b. 107 Appendix A The elementary operations o e Q = {+, x, 1} are defined on the set of intervals by putting XoY= n{x°y\x€X,yeY} = {x°y\xeX,y€Y} (A.19) for all x, y e such t h a t X ° 7 is defined for all x eX, y e Y. This restricts the definition of the division XIY to the intervals Y with OiY ALGEBRAIC PROPERTIES OF INTERVAL ARITHMETIC The following algebraic properties of interval arithmetic definitions of the interval arithmetic operations (A.19): X+(Y+Z) = (X+Y) + Z X(YZ) = (XY)Z X+Y=Y+X XY=YX for any interval X , 7 and Z. In addition and multiplication, we have 0 + X = X + 0 = X , 0 X = X 0 = 0, and 1 X = X 1 =X. (A.21) for any interval X. Addition and multiplication are both associative and commutative, however, the distributive law does not hold. For example, [1,2]-[1-11 = 0 but [ 1 , 2 ] 1 - [ 1 , 2 ] 1 = [-1, 1 ]*0 . So ,X(7 + Z) = X 7 + X Z is not always true. Interval arithmetic has a property called subdistributivity, however: X(Y+Z)^XY + XZ. (A.22) are immediate consequences of the set theoretic fi (A.20) 108 Appendix A This property is actually a combination of algebraic and set theory relations. In certain cases, distributivity holds. Some useful cases are: x(Y + Z) = xY+xZ for x real; Y, Z, intervals, X(Y+Z)=XY+XZ i f 7 Z > 0 . (A.23) We can thus distribute multiplication by a real number, and we can distribute multiplication by any interval through sums of intervals all of the same sign. The properties (A.22) and (A.23) follow easily from the definitions of interval arithmetic. If real numbers are identified with degenerate intervals, interval arithmetic is an extension of real arithmetic, and reduces to ordinary real arithmetic for intervals of zero width. A n important aspect of interval arithmetic is that X - X = 0 and XIX = 1 only when X is of width zero. Otherwise ,X-X=[X -X,X - X],X/X= [XIX, XIX] for 0 < X, andXIX= [XIX, XIX] for X <0. The cancellation law holds for interval addition: X+Z=Y+Z (A.24) implies that X= Y. 109
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- A framework for qualitative and semi-quantitative analysis...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
A framework for qualitative and semi-quantitative analysis in engineering design and evaluation Gedig, Michael H. 1995
pdf
Page Metadata
Item Metadata
Title | A framework for qualitative and semi-quantitative analysis in engineering design and evaluation |
Creator |
Gedig, Michael H. |
Date Issued | 1995 |
Description | A framework is presented which is used to support engineering decision-making in the presence of incomplete and imprecise information. A number of sound reasoning techniques which utilize this framework are described. These techniques include qualitative reasoning, a branch of study in the field of artificial intelligence, and semi-quantitative reasoning, which draws inferences from partially-specified numeric values. The constraint-satisfaction paradigm plays an important role in the implementation of these reasoning strategies. The notion of the constraint is well-suited to engineering planning and design, where projects are generally formulated in terms of a set of functional specifications. A computer program was developed based on the framework presented here. The program implements several complementary qualitative and semi-quantitative reasoning strategies. The specific techniques used in the program include constraint-satisfaction algorithms for both qualitative and numeric domains, interval arithmetic, and constraint inference methods. It was intended that the computer program developed as a part of this research serve as a practical tool which could provide logical justification for engineering decisions. For this reason, the program was developed on a platform which is both accessible and familiar. As part of the program, a convenient method of systematically specifying constraints was created, which mirrors the way in which engineering problems are normally specified. Examples are given which illustrate the application of the techniques presented here. These examples show that the techniques discussed in this thesis have significant potential for justifying engineering decisions made under conditions of uncertainty. |
Extent | 5003795 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2009-02-03 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0062468 |
URI | http://hdl.handle.net/2429/4114 |
Degree |
Master of Applied Science - MASc |
Program |
Civil Engineering |
Affiliation |
Applied Science, Faculty of Civil Engineering, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 1995-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_1995-0658.pdf [ 4.77MB ]
- Metadata
- JSON: 831-1.0062468.json
- JSON-LD: 831-1.0062468-ld.json
- RDF/XML (Pretty): 831-1.0062468-rdf.xml
- RDF/JSON: 831-1.0062468-rdf.json
- Turtle: 831-1.0062468-turtle.txt
- N-Triples: 831-1.0062468-rdf-ntriples.txt
- Original Record: 831-1.0062468-source.json
- Full Text
- 831-1.0062468-fulltext.txt
- Citation
- 831-1.0062468.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
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"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0062468/manifest