Including Qualitative Knowledge in Semiqualitative Dynamical Systems

Including Qualitative Knowledge in Semiqualitative Dynamical Systems J. A. Ortega, R. M. Gasca, M. Taro Universidad de Sevilla Departamento de Lenguajes y Sistemas Informaticos, Facultad de Informatica y Estadistica Avda. Reina Mercedes s/n, Sevilla (Espana) e-mail:{jaortega,gasca,mtoro }@lsi.us.es Abstract. A new method to incorporate qualitative knowledge in semiqualitative systems is presented. In these systems qualitative knowledge may be expressed in their parameters, initial conditions and/or vector fields. The representation of qualitative knowledge is made by means of intervals, continuous qualitative functions and envelope functions. A dynamical system is defined by differential equations with qualitative knowledge. This definition is transformed into a family of dynamical systems. In this paper the semiqualitative analysis is carried out by means of constraint satisfaction problems, using interval consistency techniques. 1 Introduction In engineering and science, knowledge about dynamical systems may be represented in several ways. The models constructed for studying them are normally composed of qualitative as well as quantitative knowledge. Models which only incorporate quantitative knowledge (quantitative models) have been well studied. The techniques developed to analyse and simulate are well known, too. On the other hand, a great variety of techniques have been studied for representation and manipulation of qualitative knowledge, such as algebra of signs, interval arithmetic, fuzzy sets, and order of magnitude reasoning. The knowledge composed of quantitative and qualitative knowledge is known as semiqualitative. Real models contain quantitative, qualitative and semiqualitative knowledge, and all of them need to be considered when they are studied. Therefore, sometimes it is necessary to solve conflicts on the request of accuracy and flexibility. The models of dynamical systems should provide different levels of numerical abstraction for their elements. These levels may be purely qualitative descriptions [7], semiqualitative [1], [5], numerical based on intervals [14], quantitative and mixed of all levels [6). In the sixties, the methodology of system dynamics was proposed. It incorporated qualitative knowledge to models by means of variables and quantitative functions suitably chosen. But, it is not until the eigthies when the interest for studying qualitative knowledge independently of its quantitative representation 330 emerges. This interest appears around qualitative simulation [7], and qualitative analysis [11]. Mathematical concepts of quantitative analysis of dynamical systems have been applied into qualitative simulation and analysis (see [8]). Qualitative methods for studying dynamical systems began at the end of the last century, by the French mathematician Henri Poincare. The subsequent evolution of these works has originated the qualitative theory of dynamical systems. In [10] the techniques to carry out the analysis of the qualitative models were introduced, that is, the study of equilibrium regions, stability and bifurcation points. In this paper, the qualitative knowledge is represented by means of real intervals, continuous qualitative functions and envelope functions. The intervals include all the real values where the qualitative label of such magnitude is found. A continuous qualitative function stands for a family of functions defined by means of landmarks. An envelope function stands for a family of functions included between a real superior function and an inferior one. It is also presented A method to transform semiqualitative models into a constraint network is presented, as well. The interval constraint satisfaction problems are solved applying consistency techniques [3]. 2 Semiqualitative models A semiqualitative model is represented by «P(:i:, x,p), x(to) = xo, «Po (p, xo) (1) being x the state variables of the system, p the parameters, :i: the variation of the state variables with the time, «Po the constraints in the initial conditions, and «P the constraints depending on :i:, x and p. They are expressed by means of the operators defined in the next section. They are composed of variables, constants, arithmetic operators, functions, qualitative functions and/or envelope functions. Therefore the equations (1) stand for a family of dynamical systems depending on p and xo. The integration of qualitative knowledge is made by adding constraints to the network. They are constraints combined with 'and' and 'or' operators. This representation will help us to obtain the behavior of the system if we apply an appropriate algorithm to solve the resulting constraint network (see [3]). 3 Representation of qualitative knowledge We shall focus our attention in dynamical systems where there may be qualitative knowledge in their parameters, initial conditions and/or vector field. They constitute the semiqualitative differential equations of the system. First, we need to take into account that the representation of the qualitative knowledge is carried out by means of operators. They have associated real intervals. This representation provides the following advantages: easy integration of 331 qualitative and quantitative knowledge [2]; and it makes possible the definition of the range of qualitative variables and parameters of the system. This definition is provided by experts, and it allows for techniques developed on intervals analysis and constraint satisfaction problem to be used [4], [13] and [3]. 3.1 Qualitative parameters and initial conditions The qualitative representation of parameters and/or initial conditions of dynamical systems may be carried out by means of the qualitative operators U and B. They represent, respectively, the set of unary and binary qualitative operators. For example, U = {very negative, moderately negative, slightly negative, slightly positive, moderately positive, very positive } and B = {much less than, moderately less than, slightly less than, much greater than, ... }. Each operator op E U or op E B has associated a real interval fop. This real interval denotes a quantity. It stands for those values where the magnitude has the qualitative label. The binary qualitative operators are classified in two classes according to their types: • Operators related to the difference. They can be exactly equal to =, smaller or equal to ~, and larger or equal to 2::. • Operators related to the quotient. They can be much less than «, moderately less than - <, slightly less than ~<, approximately equal to f:::i, slightly greater than >~, moderately greater than > -, and much greater than » 3.2 Envelope functions These functions establish a possible range of values for its image for each given value. They represent the family offunctions included between two defined function, a superior one g : IR --+ IR and another inferior one g : IR --+ JR. Let be y = g(x) an envelope function (see figure l.a). It is represented by means of (£ (X) , g( X) , J) , 't:/x E I: £(x) ~ g(x) (2) where I is the definition domain in the real line of g, and x is a variable. 3.3 Qualitative continuous functions Let be y = h(x) a qualitative continuous function. It represents a functional relationship with x as independent variable, and y as dependent variable. y = h(x), h ={PI, s1, P2, ... sk-I, Pk} with Pi= (di, ei) (3) where each Pi is a point. It stands for an important qualitative landmark of h. Each Pi is represented by means of a pair ( di, ei) where di is the associated qualitative landmark to the variable x and ei to y. Points are separated by the sign Si of the derivative in the interval between a point and the following. The sign Si is + if the function is strictly monotonic increasing in that interval, -if it is strictly monotonic decreasing, and 0 if it is constant. The definition of a function 332 g y a) b) X X -rFig. 1. Qualitative functions is always completed with the landmarks which denote the cut points with the axes, and the points where the sign from the derivative changes (a maximum or a minimum of h). Qualitative interpretation of h (see figure l.b) for each P; is: { x = d;::::} y = e; yh(x) = 0 = { s; : +::::} e; < y < ei+l di < x < di+l ::::} si = - ::::} e;_! y > ei+l si0 => ye, A special case of continuous function is that where the sign of all intervals is the same, that is, s 1 = ... = Bk-l = s. It is a strictly monotononic function. This function can be expressed in a short way by h = M s { P 1, P 2, .•. , Pk} 4 From quantitative and qualitative knowledge to constraint networks The qualitative knowledge is added by means of a set of constraints. They are combined with 'and' and 'or' operators. The constraints obtained from qualitative knowledge are: • Qualitative parameters and initial conditions For each operator, it is obtained a constraint according to its type. Let r be a new variable generated. Iu, h are the intervals associated to the unary and binary operators. Intervals Iu are stablished in accordance with [12], and intervals h with [9]. * Let u be an unary operator u E U. Let e be an arithmetic expression. The resulting constraints are u(e):={e-r=O, rEiu * Let b be a binary operator b E B. Let op the binary operator, and let e1, e2 be two arithmetic expressions. If b is an operator related to the difference ( =, ~, 2:) then the resulting constraints are 333 and if b is an operator related to the quotient, • Envelope functions For each envelope function y = g ( x) the constraint ( 4) is obtained g(x) = O:f!_(x) + (1o:)g(x) o:E[0,1] (4) This constraint stands for a family of functions included between g and g. It is interesting to notice that if o: = 0 :::::? g(x) = g(x) and if o: = 1 =?-g(x) = g(x) and any other value of o: in [0,1] stands for any included value between g(x) -and ~x). - • Qualitative functions For each qualitative function y = h(x) defined as (3) is carried out the followmg: * For each landmark d; or e; appeared in the definition of h, it is added to the set of variables of the model a new variable with a domain ( -oo, +oo ). * The following linear constraints due to the definition of h are added to the constraint network { d1 < d2 < ... < dk, e1 o e2 o ... o ek-1 o ek, y _ h(x) = O = ((x = d1, y = e1); ... ; (x = dk, y = ek); (d1 < x < d2,e1 01 yo1 e2); ... ; (dk-1 <X< dk, e1 Ok-1 y Ok-1 ek)) (5) where (5) is a set of linear constraints combined with and and or operators, respectively denoted by comma (, ) and semicolon (; ) . The operator o is defined as { x > y if s; -1 = s; = + X 0; y = X < y if Si -1 = Si = - X= y if Si-1 = Si = 0; Si-1 =F Si The set of constraints obtained by the inclusion of qualitative knowledge to the model is formuled as an interval constraint satisfaction problem. As we have indicated, a constraint-based reasoning method by means of interval consistency techniques is applied (see [3]). The results obtained are a set ofreal intervals by the variables and constraints order among them. 5 An example Let be two interconnected tanks (see figure 2). The semiqualitative model is Variables: V = {x1,x2,r1,r2,s,p} Landmarks: L = {a, b} Functions: h1 := M+ {(0, 0), a, b} 91 =< 2x, x, [0, oo] > Constraints: r1 = h1(s), r2 = 91(x2), s = x1x2 ~ - ~ -"t" d" ( ) dt - Pr1, dt - r1 -r2, pos1 1ve me mm p 334 Fig. 2. The interconnected tanks system The constraint network obtained applying the proposed techniques is V = {xl,x2,rl,r2,s,p,a,b} 0 <a, 0 < b, ( (s < 0, r1 < 0); (s = 0, r1 = 0); (0 < s <a, 0 < r1 <b); (s=a,r1=b); (s>a,rl>b)), r2 = a(x2) + (1a)2x2, a E [0, 1], fu- ~- E (3 5] s = x1x2, dt - pr1, dt - r1r2, p , (6) The concepts introduced in (10] have been applied in order to carry out the analysis of this model. The constraint network that stands for the equilibrium regions of the model are replacing the expressions dxl/ dt, dx2/ dt by zero in (6). This constraint satisfaction problem has an unique solution, hence there is an equilibrium region where it is satisfied that x1 > x2 (7) being lx 2 a real interval. If it is applied interval arithmetic to ( 6), the intervals obtained for x1 ,x 2 are too wide. The equilibrium region is [O.,oo] X [O.,oo]. In order to narrow this solution it is applied the consistency techniques [3], and then it is obtained for x2 the interval (1.06487, 5.0]. The intervals for x1, s are positives, and using the constraint s = x1 -x2, then results (7) are concluded. Therefore the solution for lx 2 is closed to the real solution [1.5, 5.0]. The results (7) may be interpreted as: the system has an unique equilibrium where the height of the first tank is higher that the second one. The height of second tank is in the real interval [1.5, 5.]. In a similar way, it is obtained the network that stands for the stability of such region. This network is also satisfied, hence it is an stable equilibrium region. The constraint network that define the bifurcations points are not satisfied. Therefore it is concluded that there are no bifurcations. 6 Conclusions This paper provides a method for including qualitative knowledge in semiqualitative dynamical systems. Qualitative knowledge is represented by means of intervals, continuous qualitative functions and envelope functions. This knowledge helps us to make analysis of that kind of systems. 335 We have applied the method proposed to several examples. The obtained results have been satisfactory. The technique presented is appropriate for predictive problems in industrial processes where there is qualitative information of their components. At the moment, we are applying the method to study a real biometall urgic system. References 1. Dvorak D.Monitoring and diagnosis of continuous dynamic systems using semiquantitative simulation Ph.D. Dissertation, University of Texas. Tech. Report AI92-170 (1992) 2. Gasca R.M., Taro M., Ortega J.A., Propagaci6n de restricciones integrando conocimiento cualitativo y cuantitativo Bolet{n de AEPIA num 6 (1996) 23-30 3. Gasca R.M. Razonamiento y Simulaci6n en Sistemas que integran conocimiento cualitativo y cuantitativo Ph.D. Thesis, Universidad de Sevilla (1998) 4. Hyviinen E. Constraint reasoning based on interval arithmetic: the tolerance propagation Artificial Intelligence no. 58 (1992) 71-112 5. Kay H., Kuipers B., Numerical behavior envelopes for qualitative models. Proc. 11th National Conf. on Artificial Intelligence (1993) 606-613 6. Kay H. Refining imprecise models and their behaviors Ph.D. Tesis, University of Texas (1996) 7. Kuipers B.J., Qualitative simulation, Artifical Inteligence 29, (1986) 289-338 8. Lee W.W., Kuipers B.J., A qualitative method to construct phase portraits, Proc. 11th National Conf. on Artificial Intelligence (1993) 614-619 9. Mavrovouniotis M.L., Stephanopoulos G. Formal order-of-magnitude reasoning Process Engineering Computer Chemical Engineering no. 12 (1988) 867-880 10. Ortega J.A., Gasca R.M., Taro M., Automatizaci6n del analisis y simulaci6n de modelos cualitativos mediante restricciones Proc. VII Conf. Asoc. Espanola para Inteligencia Artificial, (1997) 85-94 11. Sacks E., Automatic qualitative analysis of dynamic systems using piecewise linear approximations, Artificial Intelligence 41 (1990) 313-364 12. Trave-Massuyes 1., and Piera N., The order of magnitude models as qualitative algebras Proc. of 11th Int. Joint Conf. on Artificial Intelligence, Detroit MI (1989) 1261-1266 13. VanHentenryck P., McAllester D., Kapur D., Solving polynomial systems using a branch and prune algorithm. Tech. report CS-95-01 University of Providence (1995) 14. Vescovi M., Farquhar A., Iwasaki Y., Numerical interval simulation: combined qualitative and quantitative simulation to bound behaviors of non-monotonic systems, Proc. 14th Int. Joint Conf. on AI (1994) 1806-1812