Qualitative modelling and simulations by piecewise linear analysis

Copyright©IFACArtificialIntelligenceinReal-Time Control,Delft,TheNetherlands, 1992 QUALITATIVE MODELLING AND SIMULATION BY PIECEWISE LINEAR ANALYSIS M. Toro, JJ. Arrabal and L.Romero Facultad de Informatica y Estadlstlca, Universidad de Sevilla, 41012 Sevilla, Spain Abstract Since applications of expert systems were typical in domains with no welldefined models, qualitative methods for modelling and reasoning were soon developed. Most current qualitative reasoning programs derive the qualitative behaviour of a system by simulating a. hand-crafted qualitative version of the differential equation that caracterizes the model of ~ system. This paper describes a method to construct a family of piecewise linear dynamical systems from the qualitative information contained in a model. We apply the dynamical system theory to deduce results about the behaviour of the family of dynamical .systems constructed as a consequence of the qualitative model. Keywords Artificial intelligence; qualitative modelling; nonlinear systems. mical systems has received enough attention in different fields at the last decade (Chua 1983and Sacks 1987c), but the same hasn't happened to the family of piecewise linear dynamical systems. To contribute to the study of the latter, it is possible to apply the theory of bifurcation to obtain interesting qualitative results. Let's assume in this paper that a qualitative model has a set of variables, constants and a set of constraints among them. The variables and the constants take their values in a quantity space. Each quantity space is defined by an ordered set of landmark values. We are going to consider the landmarks that determine the quantity space as variables, with a partial order extracted from the specifications. The value of the variables, as wellas the constants, is described qualitatively in terms of their quantity space. Every variable or constant may take a value in a landmark of its quantity space, or between two landmarks. The constraints among variables can be: Arithmetic,where +, -, *, /, represent the arithmetic operators respectively. Functional, where M +, M -, Nm, they are representable by continuous functions, f:R -t Rand so that M+is a monotonic increasing, M-monotonic decreasing and 1 Introduction A lot of work is being published at present with the name of Qualitative Modelling, Qualitative Simulation and Qualitative Reasoning (Kuipers 1986 and Sacks 1987c). They all have one thing in common, which is to obtain conclusions from models ofsystems, where the information is either qualitative or incomplete. The systematic gathering of all qualitative information about a system makes a qualitative model. That qualitative information can be structured as a set of constraints that join together show the evolution of the different system sections. These constraints can have a derived form, an arithmetic form, a functional form, etc. Once a qualitative model has been coqstructed, the question is to get obtain the maximum information from it. A set of theoretic tools and some practical implements have been developed. Qualitative Simulation is one of them. With some differences, the qualitative information contained in the qualitative model that we take into consideration in this paper, is similar to Qualitative Simulation, but the method to obtain conclusions will be very different. At this point weconstruct a family of piecewise linear dynamical systems containing the qualitative information and later we will apply the dynamical system theory to obtain conclusions from the model. The research of constant piecewise linear dyna- 147 2Qualitative Analysis Model and Nm no monotonic. And Derivative with reference to time. This is represented by D. The associated information to the functional constraints can be extended with a list of pairs of points. In the event Nm joined with the values of the points that the function takes, we designate with the signs +, -, 0 if in this point the function is increasing, decreasing or it takes an extreme respectively. The list of Nm would contain the points where the function takes the extremes. Aqualitative model about the evolution of preys, predators and their interactions it is given in the following equations: :i: =x(J(x) -g(y)) (1) iJ =yh(x) where the number of preys are representable by x, the number of predators are representable by y, the rate of births of the preys is representable by I, the rate of mortality of the preys by predators is representable by 9and the rate of births of the predators is representable by h. We assume that: (quantity-spaces (x (0 hO h2 inf) (0 h1 h2» (y (0 int» (t (mint 0 kO k1 int» (h (mint 0 int) ) (g (mint 0 inf» (tnx (mint 0 int» (ix (minf 0 int» (ty (mint 0 int») (constraints «Ma x t) (0 kO +) (hO k1 0) (h2 0-» «H+ y g) (0 0» «H+ xh) (h1 0) «- tg tnx)) «* x tnx tx» «* yh ty» «0 x fx» «0 y iy») Figure 1: Equations of the Model is piecewise linear if Rncan be divided into a finite number ofpolyhedral regions by a finite number of hyperplanes and in each region i, Iis an afin funtion i: that bind the variables in a symmetric way. This is Kuiper's Qualitative Simulation approach (Kuipers 1986). However, we will consider an asymmetric causal order and the constraints as some bonds between a cause and its effect. This allows us to approach the concepts and the methods of the dynamical systems in the Sense it is understood in Mathematics. In this paper, we apply tecniques from the theory of dynamical system to obtain information from aqualitative model. The use of these techniques consists of two stages: first, in the construction and regularization of a family of piecewise linear dynamical systems and then in their analysis. The first stage consists of a sequence of events that holds up the qualitative information of the model. The second one is the application of the methods of qualitative analysis to the dynamical system that has been constructed. Func- Linear Piecewise tions Acontinuous function 3 The consumption of prey by predator is proportional to the number of preys, and it depends on the number of predators by an increasing monotonic function. In the absence of predator this consumption is null ( 9(0) =0). Birth of predators depends on the prey number, by an increasing monotonic function. In the absence ofpreys (x =0) predators die out (h(O) <0, or equiva.- lent h(ht} =0 with b: >0). In the absence of predation,preys grow without limit,for small xand when xis medium the birth rate decreases becoming negative (f takes a maximum in hoand l(h 2)=0 with 0 <ho<h2 The information contained in the qualitative model above is given in a more formal way in the Figure 1. As we can observe, the relevant information has been defined for every variable in the quantity space and for every constraint of the form M +, M-and Nm. So we can see that 9 takes through (0,0), the maximun of Iis in (ho,k1) , and takes through zero in (h 2,0), htakes through zero in (h1,0) with 11 0< 11 2,etc. The problem now is what information we can extract regarding trasitory behaviour, and for longterm, from the system whose qualitative informa.- tion we have specified. One way to study the problem is to consider the qualitative information as a set of constraints 148 where A~ is a constant nXn matrix and b~ is a constant n-vector. At the following the set of regions associated to the piecewise linear function I are representable by 0/. O} is a region of 0/ and t' the afin function associated to Iat region O~. The set 0/ and the set of afin functions Ii have to be given to specify the piecewise linear function I. If Iis continuous the equation: is unknown. The opposite happens if al >0and a2 <0 We can observe the composition offunction, now. If I: R" -4 Rm,g: R ffl -4 R are piecewise linear functions, the composition : where I:R" ---> R, 9:Rm -t R and h=I EEl 9with EEl =+or EEl =- where h:R" XRm -4 R, then the function his also a piecewise linear function. If OJ and 0; are the canonical partitions of R" x Rminduced by OJ and Og respectively. Each region of Oh is formed with the no empty intersection of a region of OJ with another one of 0;: (5) (6) s=1+9 D :: I-g then 9if S ~ 0 and D ;::: 0 prodL == Iif S ~ 0 and D<0 -/ if S<0 and D ~ 0 -g if S<0 and D<0 is a piecewise linear function too. The partition Ogo/ of R" that will be associated to go Iis formed with the no empty intersections of regions of 0/ with the inverse image by Iof a region of Og: and the associated afin function is The selected method assures that the zeros of prod are the same as the prodL. The regions of prodL are obtained following the rule in (6). So to obtain OprodL ,each region of Os :::: OD is divided into subregions where the sign of S=/+9 and the sign of D :::: I-9are preserved. The operator division / will be considered in a forthcoming paper. If prod =I*9is defined with I, 9piecewise linear functions. We want to find a piecewiselinear function that is a piecewise linear approach of the prod. We can define the piecewise linear function (3) (2) must be held for each xin the boundary between the regions O~, ~. We show now the way to associate a piecewise linear function or an operator on piecewise linear functions to each constraint in our qualitative models. In the constraints of monotony M +, M- and Nm,the polihedral regions are being defined by: Ok+ =(hi, hi+l) where ho,h1, .... ,h" are the landmarks of the corresponding function. In each region i,the corresponding afin function has the form ax +bwhere a> 0 if the constraint is M+, a<0 if it is M- and the sign of a depends on the region if the constraint is Nm. To the arithmetic constraints+or -, we associate an operator of piecewise linear function defined in this way. Given the continuous and piecewise linear functions: Oji = O~ xRm,O;i :::: Rnx O~ In the case I,9have identical domain 4 The construction of the family of piecewise linear dynamical systems (4) each non null region of 0h is formed simply by intersection O~ == O~ no~ The piecewise linear function that results in each region is: This introduces ambiguity about the constraints that may support the element of the corresponding A, b. If al >0 and a2 >0 the sign of at -a2 The construction process consists of rules for building a methodical way. As we have established,the constraints are asymmetric, this means that if the system is wellspecified, the set ofconstraints defines implicity a directed acyclic graph that has as the initial node the state variables and the ending nodes in the variables that specify the field. This graph, without loops, specifies a partial order which is the one we follow to construct the result. 149 related to the class of attractor that the system (7) has for P= Po. The stable equilibrium is the most known of these attractors. It is related to a long term where :i: = O. Another attractor is the Limit Cycle. This is related to the periodic oscillations. The bifurcation theory is the study about the change in number and kind of attractors when the parameters change. If the system (7) is a family of piecewise linear dynamical system its qualitative analysis is simplified. So the equilibria (x) must verify: Figure 2: Directed acyclic graph associated to the example The qualitative analysis of (7) is the long term study of its solutions for a fixed value of its parameters p= Po. The long term behaviour is Each node has no more than two inrnediate predecessors. Every node of the graph specifies an allowed constraint. The directed acyclic graph associated to the example above is shown in Figure 2. Therefore, the constructive method consists of: (8) (9) (10) (11) (12) if = -y z=x x=aJx - a~y + bj iJ =Y 6 Applications to the example and its stability is given by the A} matrix. When the parameters change the number and kind of at tractors changes too. The bifurcation theory can help us to find new kind of atractors. For example, the Hopf bifurcation (a couple of eigenvalues of Jacobian matrix cross the imaginary axis) can be used to find limit cycles. If xER2 the characteristic polynomial of the Jacobian Matrix evaluated in the equilibrium x(p) is ,\2 +al(p),\ + a2(p) =0 AHopf bifurcation appears if al(p) crosses the zero and a2(p) >0when parameters change (Guckenheiner 1982). The application of the above method to example give the following conclusions (see the appendix for intermediate steps). The differentiable field !x,!y is null in three points: • El: (0,0) in the region OJI/: n O}y • E2: (h 2,O) in the region 0jl/: n01y • E3: - (hI, (ajh1+bJ)/a}) in the region Oil/: n nJy, if ho<hI - (h 1,(a}h 1 +b})/a}) in the region n}1/: n nJy, if hI <ho. El: In the region Ojl/: n O}y the field is eigenvalues: '\1 =1>0,'\2 = -1 > O. So (0,0) is an unstable equilibrium. E2: In the region nj~ n n,y the field is: (7) of z= !(z,p) Qualitative Analysis Dynamical Systems 5 First, for each node to obtain the piecewise linear function or operator on piecewise linear function that is associated to constraint as the rules of the previous paragraph. Second, to reduce this graph by suecesive application of one step that consists to replace a function node and their inmediates predecessors nodes by another one whose associated function is the composition of associated functions to them. After we have applied the succesive constraints in the determined order we will obtain a family of the piecewise linear functions and a set of constraints for their parameters. This family, after to regularize it in the boundary of each regions is the field of the dynamical system that we wanted to construct. The application of the qualitative analysis of the dynamical system and the bifurcations theory to the resultant family of dynamical systems provide us the relevant information from the qualitative point of view. Given the family of dynamical systems: 150 and the eigenvalues : ~l = ai <0, ~2 =1>0. So (h2,0) is an unstable equilibrium. E3: In the region O'IIJ n O~y, if ho<hI, the field is: Ii = a~ z - a;v + b~ (13) iJ ::: a~x + b~ (14) If ho<hI the system has an equilibrium (h ll (aJh 1+ b~)/a~) ,with characteristic polynomial: ~2 _ aJ~ + a~a; =0(15) Both eigenvalues have a negative real part. So this point is an attractor. If 0<hI <ho, the field, in region O}IIJ nOJy, is: Ii: ::: a}z-a;V+b} (16) V= a~z+b~ (17) The equilibrium E3 changes. It is the point (h ll (a}hl+b})/a;) ,with characteristic polynomial: ~2 _ a}~ + aka; =°(18) Now it is a repulsor. When parameter h, changes from ho<hI to hI <ho the characteristic polynomial of equilibrium E3 changes from (15) to (18). Since a~a; >0, -aJ >0, -a} <°then a Hopf bifurcation appears. If hI <hoaLimit Cycle exists. We can conclude from the qualitative model in Figure 1 that the system will evolve only to the attractor. This attractor is a stable equilibrium if ho<hI and a Limit Cycle if hI <ho. 7 Conclusions This paper has described atechnique for deriving the properties of nonlinear dynamic systems from their qualitative description. These dynamic systems are interesting because they pose unsolved problems in the representation of knowledge, and because they appear fundamental to commonsense knowledge of causality. The example presented above demonstrate a representation for qualitative reasoning about causality in ecological mechanisms, and it is possible to be applicationed to others problems. The technique developped can be used to deduce results from the qualitative information about a system. It uses the theory of dynamical systems to avoid the ambiguity that appears in other methodologies. 8 References Javier Aracil and Miguel Toro (1991). Qualitative methodsfor system dynamic models. In Revue Internacional of Systemique. 151 Leon Chua and Robin Ying (1983). Canonical Piecewise-Linear Analysis. IEEE Transactions on circuits and Systems, Vol.Cas-30, NO 3. pp, 125-140. J. Guckenheimer and P. Holmes (1982). Nonlinear Oscillations, dynamical systems and bifurcations of vector fields. Springer Verlag. Benjamin Kuipers. Qualitative Simulation. In Artificial Intelligence 29, pages 289-338. Elisha P. Sacks (1985). Qualitative mathematical reasoning. In Proceedings of the Ninth International Conference on Artificial Intelligence, pages 137-139. Elisha P. Sacks (1987a). Hierarchical reasoning about inequalities. In Proceedings of the National Conference on Artificial Intelligence, American Association for Artificial Intelligence. Elisha P. Sacks (1987b). Qualitative sketching of parameterized functions. In Proceedings of the Second International Conference on Applications of Artificial Intelligence in Engineering, August 1987. Elisha P. Sacks (1987c). Piecewise Linear Reasoning. In Proceedings AAAI-87, 655-659. Miguel Toro and Javier Aracil (1988a). Qualitative Analysis of System Dynamic Ecological Models. In System Dynamics Review, Vol. 4, Num. 1-2, 56-60. Miguel Toro and Javier Aracil (1988b). Oscillations and Chaos in Ecological Populations. In Proceedings of the Internacional Conference of the System Dynamics Society, 391- 403. 9 Appendix General Constrainsts °<ha<b: <h2< 00 0< ka<kl< 00 Regions O~ ={zlz ~ O,x:5 ha} OJ ={xix ~ ha} Afin Functions f=P:=a}:t+b}, P :=aJx+bJ Parameter Constrainsts a{ >0, a}ha+ b} ::: kl bi::: ka a~ <° a~ha + b~ ::: k 1aJh 2+ bJ ::: ° The constraints of the fx and the coefficient of tnx and h involve the next definition of fx and fy, and the product rule (6): 9= h= tn21 = fz = Regions 0; ={yly;::: O} Afin Functions gl == a~y Parameter Constrainsts a1>0 9 Regions O~ = {xIx;::: O} Afin Functions h1 == alx + bl Parameter Constrainsts ah >0 alh 1+ b~ =° Regions O}n~ = n~ x 0t n1n~ =n/ x Og Afin Functions tnx 1 == al 21 -a1y+ b1 tnx 2 == aJx - ah + b} Regions n}~ ={(x,y) E nrn.,lx + tnx 1;::: 0, xtnx 1 ~ O} OJ., ={(x, y) E 0in." x+ tnx 1;::: 0, xtnx 1< O} 07:1: ={(x, y) E 0rn." z+ tnz 1<0, xtnx 1 ~ O} 152 fy = 0J~ ={(x, y) E O~n." x+ tnx 2 ~ 0, x -tnx 2;::: O} 0j:l: ={(x,y) E 0~n."x+tnx2 ~ 0, Z - tnx 2<oj 0':1: ={(z,y) E 01n." z+ tnx 2<0, xtnx 2;::: O} Afin Functions fx l == tnz 1 fz2 == x fx 3 ==-x fx 4 == tnx 2 fx 5 == x fx 6 ==-x Regions O}v = {(x,y) E 0~,y+h1 <0, Y-h1;::: O} 0Jv={(x,y) Enk,y+h 1 ;:::0 , y-h1 ~ O} n,v ={(x,y) E nk,Y+ h1;:::0, y-h1< O} n}v ={(x ,y) E n~,y+h1;::: 0, y-h1< O} Afin Functions ly1 ==-y fy2 == h1 fy3 == Y fy4 == _h 1