Class Note for ECE 575 at UA
Popular in Course
Popular in Department
This 23 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Arizona taught by a professor in Fall. Since its upload, it has received 22 views.
Reviews for Class Note for ECE 575 at UA
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
DIFFERENTIAL EQUATION MODELS IN DEVSJAVA Recall that in discrete time modeling there is a state transition function which computes the state at the next time instant given the current state and input In the classical modeling approach of differential equations the state transition relation is quite different For differential equation models we do not specify a next state directly but instead use a derivative function to specify the rate of change of the state variables At any particular time instant on the time axis given a state and an input value we only know the rate of change of the state The state at any point in the future must computed from this information Basic Model The Integrator To see how this form of modeling works let us consider the most elementary continuous system 7 the simple integrator Figure l The integrator has one input variable x and one output variable y One can imagine it as a reservoir with infinite capacity Whatever is put into the reservoir is accumulated 7 with a negative input value meaning outflow The state of the reservoir is its current contents When we want to express this in equation form we need a variable to represent the current contents This is our state variable q The current input x represents the rate of current change of the contents which we express by equation d qt dt xt and the output y is equal to the current state yt qt X oorteris I irthdt quot0 y M I x10 t Figure 1 Basic Integrator Concept Usually continuous systems are expressed by using several state variables Derivatives are then functions of some or all the state variables Let q1 q2 L1 be the state variables and x1 x2 xm be the input variables then a continuous model is form ed by a set of firstorder differential equations dQ1tdtf1 htl 22 I In 395 I X1 I X2 Xmt dQ2tdtf2lhtl Q2 1 gm X1 X2t XMUZH dQntdtfnQ1tl Q2 1 21115 X1 X2t XMUZH Figure 2 The Integrator Note that the derivatives of the state variables q are computed respectively by functions f which have the state and input vectors as arguments Representing the integrator in diagrammatic form as in Figure 2 we can represent a set of first order differential equations in the coupled model form of Figure 3 The state and input vector are input to the rate of change functions f Those provide as output the derivatives dqdl of the state variables L which are forwarded to integrator blocks The outputs of the integrator blocks are the state variables L1 dqzdt I qz x q dqndt J39 qn x l i F Figure 3 Structure of differential equation speci ed systems Continuous system simulation The diagram above reveals the fundamental problem that occurs when a continuous system is simulated on a digital computer In the diagram we see that given a state vector q and an input vector x for a particular time instant I we only obtain the derivatives dqdl But how do we obtain the dynamic behavior of the system over time In other words how do we obtain the state values after this time This problem is depicted in Figure 4 In digital simulation there is necessarily a next computation instant 1H1 and a nonzero interval 1 1H1 The model is supposed to be operating in continuous time over this interval and the input state and output variables change continuously during this period The computer program has available only the values at I and from those it must estimate the values at 1H1 without knowledge of what is happening in the gaps between t and tm This means it must do the calculation without having computed the input state and output trajectories associated with the interval 1 1H1 Figure 4 Continuous system simulation problem Schemes for solving this problem are generally known as numerical integration methods A Whole literature deals with design and analysis of such methods Press et a1 92 Burden Faires 89 The basic idea of numerical integration is easily stated 7 an integration method employs estimated past andor future values of states inputs and derivatives in an effort to better estimate a value for the present time 0 Thus to compute a state value ql for a present time instance 1 may involve computed values of states inputs and derivatives at prior computation times 14 14 andor predicted values for the current time I and subsequent time instants I 1H2 Notice that the values of the states and the derivatives are mutually interdependent 7 the integrator itself causes a dependence of the states on the derivatives and through the derivative functions f the derivatives are dependent on the states This situation sets up an inherent difficulty which must be faced by every approximation method 7 the propagation of errors x A m Ar A F 1 112 111 1 Ix1 Ixz Figure 5 Computing state values at time t based on estimated values at time instants prior and past time t We consider the simplest integration method generally known as the Euler or rectangular method The idea underlying the Euler method is that for a perfect integrator 61W hm 10 h 10 dt h7gt0 h thus for small enough h we should be able to use the approximation m qth qth dt Now the input to an integrator as in Figure 2 is the derivative xl dqdt so we have NW1 11 hx With h fixed we can iterate to compute successive states at time instants 0h2h3h given the initial state at time 0 and the input values x0 xh Although straightforward to apply Euler integration has some drawbacks On one hand to obtain accurate results the step size h has to be sufficiently small But the smaller the step size the more iterations are needed and hence the greater the computation time for a given length of run Traffic Example Consider modeling traffic The basic element is a one way roadway such as a highway or street lane between intersections We divide the roadway into segments as illustrated in Figure 6 The speed of a vehicle in such as segment is to be determined by the number of vehicles in its segment as well as the number in the segment ahead Roughly the more congested the road ahead the slower a driver must go We can represent the roadway as a onedimensional cellular space where the cells represent segments Each cell keeps track of the positions and speeds of the vehicles within it When a vehicle reaches the end of a segment it is added to the following segment Thus one output port of a cell signals the occurrence of a vehicle at the far boundary of the associated segment The other output port will transmit the number of the vehicles in the segment to the rear segment out vehicle in vehi le 4 a 4 a number number ahead 1 Figure 6 Partitioning a Roadway The time line of a vehicle can be depicted as in Figure 7 Because the number of vehicles in a segment changes discretely the speed v of a vehicle changes in a steplike piecewise constant fashion The distance along the segment s therefore increases in line segments as illustrated When the vehicle reaches the end of the segment it is transferred to the next segment This is represented by the output 0 which is zero until the segment boundary is crossed at which point it becomes 1 The number of vehicles in the segment is also computed and transmitted to the predecessor cell at this time as well Seg lengm Figure 7 VehicleTime Segments The Euler approach can be used to update the vehicle positions along the way sth st vth where vt is speed of the vehicle at time t as computed from the number of vehicles in this segment and the one ahead Since there may be a number of vehicles within a segment at any one time we need a container to hold them To make this possible we defined a derived class of entity class Vehicle extends entity public double position speed public Vehicledouble Position double SpeedH position Position speed Speed Following the approach to DEVS implementation of cellular automata Chapter 9 we define a subclass of cell to update the vehicles in the segment it represents public class VehicleStep extends celll protected set Vehiclescrossed protected double time7stepsegLength protected numberAhead public VehicleStep H superquotvehicleStep quotF phasesadd quotactivequot inports add numbe rAhead outportsadd number initialize l public Void initialize passivate Vehicles new set crossed new set segLength lOO timeistep l numberAhead 0 superinitialize public Void deltextdouble emessage X Continuee for int 10 llt Xget7lengthl if messageioniport X quotnumberAheadquot i entity ent Xget7valion7port quotnumberAheadquoti intEnt d intEnten numberAhead dgetv l l for int 10 llt Xget7lengthl if messageioniportxquotinquotl comes with posn amp speed vehiclesaddxget7valion7port quotinquot i add all Vehicles before updating update new old Vehicles for next time step nextCrosseddetermine next crossings for output holdiinquotactive timeistep l public Void update H for entity p vehiclesget7headp l nullp pget7right entity ent pget7ent Vehicle V vehicleent double newSpeed computeSpeedvehiclesgetilength numberAhead vposition vposition newSpeedtime7step Vspeed wSpeed l l public Void nextCrossed if SpeedAhead lt 00lreturn for entity p vehiclesget7head p l nullp pget7right entity ent pget7ent Vehicle V vehicleent if Vposition segLengthH Vposition Vposition segLength Vehicles remove ent crossedaddent l l public Void deltcondouble emessage XH same as deltext crossed new set r39empty after outputting l public Void deltint i if lvehiclesempty update 0 crossed new set r39empty after outputting nextCrossed holdiinquotactivequot timeistep l else passivate 0 l public message out i message m new message if phaseiisquotactivequot m addmake7contentiaddress quotnumberquot new intEnt vehicles getilength new addrclass myilocationiel myilocation j myilocationk for entity p crossedget7head plnullppget7right m add makeicontentiaddress quotoutquot pget7ent new addrclassmyilocationil myilocation j myilocationk l return m l l Note that we predict what the state and output will be at the next time step When that the time of the step elapses we the output is emitted and the next state and output are recomputed CampuIeSpeed is function that embodies our hypotheses about how a traffic cloud around a driver inluences hisher speed There is obviously an approximation here in that most of experience driving decisions in terms of the more detailed behavior of the cars immediately surrounding us on the highway We embed a row of such cells into a block model with a traffic generator public class roadSeg extends block public roadSeg String nm i supernm cell g new trafficGenrquotgquotlOnew addrclass 000 addg for int i l i lt 4i addnew VehicleStepquotVquotinew addrclassi0 O addicoupling quotoutquot quotinquot addicoupling quotmyNumberquot quotnumberAhe adquot initialize Efficient DEVS Representation of Discrete Time and Differential Equation Models Once we make the assumption as in the traffic model above that the input and output of a component are piecewise constant a much more efficient implementation of the internal dynamics becomes possible Compare Figure xx with Figure xx above Instead of the piecewise constant speed input we have discrete event inputs that provide the new values when the speed changes Indeed any piecewise constant time segment can be represented in this manner When a vehicle first enters the segment its position is zero and the time it will take to reach the far end is easily predicted Tcmss segLengthv where v is the speed at the time of entry Now we can schedule an internal event to occur at that time 7 this would enable a cell to produce the same output at the same time as computed in the discrete time approach 7 provided no additional inputs arrive What do we do when such an external event occurs In the external transition function we update the position to where it would be had we been updating it at every discrete time step Then from this new current position we recompute the time to reach the far end In other words at time tm when the il input arrives we have Sg1 s v e Tmssm segLength sm v1 Notice that we use the old speed v to update the position to its current value but we use the new speed viil and new position to predict the next crossing time The following is a DEVSJAVA implementation of a vehicle travelling in one direction and crossing successive segment boundaries public class Veh extends atomicl public double position speed protected double timeistepsegLengthnextBoundary public VehString name double Position double SpeedH supername position Position speed Speed phasesaddquotactivequot initialize39 public Void initialize segLength 100 nextBoundary segLength if speed passivate39 else holdiinquotactivequot segLengthspeed superinitialize public Void deltextdouble emessage x i position position speed e for int 10 llt xget7length Fl if messageionipor xquotspeedquoti entity ent xget7valioniport quotspeedquot i doubleEnt d doubleEntent39 speed dgetv39 l I if speed passivate39 else holdiinquotactivequot nextBoundary positionspeed39 l public Void deltint l position nextBoundary nextBoundary nextBoundary segLength holdiin quotactivequot segLengthspeed l public Void deltcondouble emessage x position nextBoundary nextBoundary nextBoundary segLength for int 10 llt xget7length Fl if messageioniport x quotspeedquot i entity ent xget7valioniport quotspeedquot i doubleEnt d doubleEntent speed dgetv if speed passivate else holdiinquotactivequot segLengthspeed public message out l message m new message if phaseiisquotactivequot H maddmake7content quotoutquot new intEnt l l return m l l Note that every time a boundary is crossed the position and next boundary are updated accordingly Such crossings occur when either the internal or the con uent transition functions are invoked Why In between such events any inputs received are properly handled Notice that the con uent function is a combination of the external and internal transition functions It updates the position and next boundary as in deltint However it can also accept a new speed as input and reschedule its time advance accordingly A Cloud Model of Driver s Speed Recall that our model assumed that the driver s speed is a function of the number of vehicles in the current segment and in the one ahead It s as if the driver reacts to a cloud of vehicles in front and behind As a specific example this function can be formulated as follows Let the nominal speed of a segment be a function of the number of vehicles currently within it As illustrated in Figure 8 let the speed profile along the segment be computed as a linear combination depending of distance of the nominal speeds in the current segment and in the next Then as shown we can compute the travel time within the segment and given an elapsed time the position at that time A DEVSJAVA model of a vehicle which employs these relations is shown below 10 V0 ltix V012dD VDX VD x0 x0 D VD V0V0eVD39V0 D 1 tcross D1nV0 VDV0 VD Figure 8 Estimating Vehicle Speed public class VehSmooth extends atomic protected double position speedspeedAhead protected double timeistepsegLengthneXtBoundary public VehSmoothString name double Position double Speed double SpeedAheadH supername39 position Position speed Speed speedAhead SpeedAhead phasesaddquotactivequot initialize39 public Void initialize segLength 100 neXtBoundary segLength holdiinquotactivequot timeAdvance segLength super initialize 0 public Void updatedouble e double A speed double B speedAhead if A position position eA else double segLeft nextBoundary position double travelled 0 if segLeft gt 0 travelled segLeft A B a A Mathexp BiA esegLeft position pOSition travelled 1 11 double relPos travelledsegLength speed l 7 relPosspeed relPosspeedAhead l protected double timeAdvancedouble segLeftH if speed O HspeedAhead 0 return INFINITY if speed speedAhead return segLeftspeed else return segLeftMathlogspeed MathlogspeedAhead speed speedAhead l public Void deltextdouble emessage X updatee for int 10 llt Xget7length Fl if messageioniport X quotspeedquot i entity ent Xget7valion7port quotspeedquot i doubleEnt d doubleEntent speed dgetv if messageioniportbiquotspeedAheadquoti entity ent Xget7valion7portquotspeedAheadquoti doubleEnt d doubleEntent speedAhead dgetv l l holdiinquotactivequot timeAdvance nextBoundary position l public Void deltint position nextBoundary nextBoundary nextBoundary segLength speed speedAhead holdiin quotactivequot timeAdvance segLength l public Void deltcondouble emessage XH position nextBoundary nextBoundary nextBoundary segLength speed speedAhead for int 10 llt Xget7length Fl if messageioniportbiquotspeedquoti entity ent Xget7valion7port quotspeedquot i doubleEnt d doubleEntent speed dgetv l l holdiin quotactivequot timeAdvance segLength public message out message m new message if phaseiisquotactivequot H maddmake7content quotmequotnew intEnt l l return m l 12 Hierarchical Modular Traffic Construction Putting everything that we have learned together now we ll build up a model of city traffic in a hierarchical modular manner As in Figure 9 a city may be decomposed into various road networks that meet at junctions where traffic can move from one to the other Each road network may consist of several segments where each segment has a traffic light and is itself decomposed into several segments between traffic lights With a road segment we also associate a traffic generator to provide a local source of traffic to a road segment and a scheduler to control the generator for normal vs rush hour conditions and the traffic light The corresponding system entity structure illustrates the different nodes in the structure a multiple entity three parallel lines showing decomposition into one or more subentities b aspect branching node showing decomposition into a finite number of different entities and c specialization paired lines showing alternative choices for the entity eg we can use the time stepped or eventbased models of vehicles owing within a segment In DEVSJAVA a multiple entity is most naturally implemented as a block model with its components which can themselves be block models as we have seen indexed by threedimensional addresses to augment the basic portbased coupling city city roadNet roadssg roadNet A ii road traf c quot9 traf c sched Sam M Light 3 G L seg step event roadNet roadSeg sag Sag sag Sag sag Sag sag Figure 9 Hierarchical Model of Road System 13 DEVSJAVA Simulation of Continuous Systems The approach exemplified in the traffic example above generalizes to enable efficient DEVS simulation of many differential equation models Figure 10 shows the general approach F F d dt DEV Figure 10 Mapping Differential Equation Systems to DEVS Simulators DEVS Repesentation 0f Quantized Integrator The DEVS realization of the quantized integrator has the simple definition M a Y 5 5exb 5exl 5172b Ii la where X Y R and S R XRXI and 39 5extqxxnexx qxexxi n 39 61mm x n n Dsz39gnx x n signx 39 5am qlxxn x9 n t DSignx x 71 3187166 I it qx n signxD Iaqxn lnID qx l if x gt 0 and nID q gt 0 lqnDxlifxlt0andif lqnDl gt 0 lDxl if x 0 and none of the above oo otherwise ie x 0 Here we keep track of the boundary below or at the current state q ie the integer floorqD Recall that even if we start on a boundary the state may eventually be inside a block hence not a multiple of D as a 14 result of an external transition If as in Figure lla we are on a boundary the time advance computation merely divides D by the current input x which is the derivative or slope after all If we reach the upper boundary n1 or lower boundary n fl we output and update the state accordingly Note that so long as the input remains the same the time to cross successive boundaries will be the same Figure llb shows that when a new input is received we update the state using the old input and the elapsed time From this new state q the new time to reach either the upper or lower boundary is computed The Quantized DEVS integrator greatly reduces the number of transitions and output messages needed to simulate an integrator It also reduces the message size from double to integer Actually since the only possible transitions are to the upper or lower boundaries only one bit to represent the binary valued set ll need be sent taq n1DqX tanD lDxl Xgt0 e taq lqnDxl Figure 11 DEVS simulator of a Quantized Integrator DEVSJAVA Implementation of the Quantized Integrator public class DEVSGenInt extends atomic protected double inpquantumpositioninitialPosition protected int lowerBound neXtLowerBound inputineXtLowerBound public DEVSGenIntString namedouble Quantum double PositionH supername inports add quotinquot quotdoubleEntquot inports add quotsetQuantumquot quotdoubleEntquot inports add quotresetquot quotdoubleEntquot outportsaddquotresetPosquot quotdoubleEntquot outports addquotothuantumquot quotdoubleEntquot phase5add quotdoResetquot quantum Quantum initialPosition Position initialize 15 l public Void initialize inp 0 position initialPosition superinitialize lowerBound intMathfloorpositionquantum neXtLowerBound lowerBound holdiinquotdoResetquot O l public int signOfdouble XH if X return 0 else if X gt 0 return 1 else return 1 public Void timeAdvancedouble diffH sigma Mathabsdiffinp l public Void updatedouble e position position e inp if inp gt O ampamp position gt neXtLowerBounquuantum inp lt O ampamp position lt neXtLowerBoundquantum position neXtLowerBoundquantum public Void computeIntNeXtPosition lowerBound neXtLowerBound neXtLowerBound lowerBound signOfinp timeAdvance signOf inp quantum l public Void computeEXtNeXtPosition if in O sigma INFINITY else if inp lt on if neXtLowerBound gt lowerBound neXtLowerBound lowerBound l if neXtLowerBound lt lowerBound neXtLowerBound lowerBoundil l else if inp gt 0 if neXtLowerBound gt lowerBound neXtLowerBound lowerBoundlF l if neXtLowerBound lt lowerBound neXtLowerBound lowerBound l timeAdvance neXtLowerBoundquantum position l l public Void deltcondouble emessage X deltint 0 16 delteXt OX l public Void delteXtdouble emessage X i Continue e y39 for int 10 llt Xget7lengthl if messageioniport X quotinquoti entity ent Xget7valioniportquotinquoti doubleEnt f doubleEntent39 inp fgetv updatee39 computeEXtNeXtPosition for int 10 llt Xget7lengthl if messageioniport X quotsetQuantumquot i entity ent Xget7valion7portquotsetQuantumquoti quantum doubleEnt ent getv39 updatee39 computeEXtNeXtPosition l for int 10 llt Xget7lengthl if messageioniport X quotresetquot i entity ent Xget7valion7portquotresetquoti position doubleEnt ent getv39 lowerBound intMathfloorpositionquantum if inp lt O neXtLowerBound lowerBound holdiinquotdoResetquot O l public Void deltint i if phaseiisquotdoResetquot computeEXtNeXtPosition else position neXtLowerBoundquantum computeIntNeXtPosition l l public message out i int NiQuantum neXtLowerBound lowerBound message m new message if phaseiisquotdoResetquot maddmakeicontentquotoutResetquotnew doubleEnt position m add makeicontent quotoutquot new doubleEnt neXtLowe rBoundquantum return m l DEVSJAVA implementation of Instantaneous Functions public class instantFn eXtends atomic protected double inputl protected double input2 public instantFnString name supername39 inportsaddquotinlquot quotdoubleEntquot 17 inportsaddquotin2quot quotdoubleEntquot initialize l public instantFn superquotinstantFnquot inportsaddquotinlquot quotdoubleEntquot inportsaddquotin2quot quotdoubleEntquot addTestPortValuequotinlquotnew doubleEnt l addTestPortValuequotin2quotnew doubleEnt 2 initialize l public Void initialize inputl 0 input2 0 superinitialize l public Void deltextdouble emessage X Continue e y39 for int 10 llt Xget7lengthl if messageioniport X quotinlquot i entity ent Xget7valion7portquotinlquoti doubleEnt f doubleEntent inputl fgetv sigma 0 l else if messageioniportx quotin2quoti entity ent Xget7valion7portquotin2quoti doubleEnt f doubleEntent input2 fgetv sigma 0 l else if messageioniportbi quotresetlquoti entity ent Xget7valion7portquotresetlquoti doubleEnt f doubleEntent inputl fgetv sigma 0 l else if messageioniportbi quotreset2quoti entity ent Xget7valion7portquotreset2quoti doubleEnt f doubleEntent input2 fgetv sigma 7 0 l l public Void deltint sigma INFINITY l public double fn Virtual l public message out message m new message m addmake7content quotoutquot new doubleEnt fn return m l 18 Example of Differential Equation System in DEVSJAVA A Figure 12 Harmonic Oscillator Figure 13 Undamped Second Order Linear Oscillator a time trajetories b phase space public class plusInstE n extends mstantrm protected double coef1coer2 19 public pluslnstFnString name double Coefldouble Coef2 supername coefl Coefl coef2 Coef2 public double fn return coeflinputl coef2input2 public class oscillator extends digraph public oscillator superquotoscillatorquot39 inportsaddquotresetquot atomic minus new plusInstFnquotminusquotlt05 atomic integl new DEVSGenIntquotinteglquotllOO atomic plus new plusInstFnquotplusquot 05 atomic integZ new DEVSGenIntquotinteg2quotl0 addminus39 addintegl39 addplus39 addinteg239 addTestPortValue quotresetlquotnew doubleEntlOO 39 addTestPortValue quotreset2quotnew doubleEntO 39 Addicouplingthis quotresetlquot integl quotresetquot Addicouplingthis quotresetZquot integZ quotresetquot Addicoupling minus quotoutquot integl quotinquot Addicouplinguntegl quotoutquotplus quotin2quot Addicoupling integl quotoutResetquot plus quotreset2quot Addicouplingplus quotoutquot integZ quotinquot Addicoupling integZ quotoutquotminus quotin2quot Addicoupling integZ quotoutResetquot minus quotresetZ quot initialize 0 20 Appendix Examples of Differential Equation Models 22 2 l8 is u r2 m 275 257 2257 r757 57 r257 U757 nar n 25 39 n 2 6 s a lulZNlSlBZUZeu n 2 6 s a in i2 r 15 m 2mm n 2 5 a l lZlbiSlEZ ZsH 25 2257 2 r757 r5 r257 U757 mar U257 u n 2 6 s a lulZNlSlEZUZeu Figure 14 Exponential growth and decay As illustrated in Figure 14 when we apply an input to an exponential decay we have the socalled exponential delay of first order This type of continuous system plays an important role in many real world phenomenon In abstract terms this is the right type of model to use for system with a driving force and a linear damping The input to the system represents the driving force and the feedback through negative factor e models the damping These two are added de ning the derivative for the state variable The characteristic of the system is that the system reaches an equilibrium state when the damping through the feedback wq equals the driving input 0 shows this for a constant input force x1 and different damping factors e The greater the damping factor the smaller the equilibrium state There are many real world phenomenon which can be modeled by an exponential delay of rst order Examples range from heating systems where the input is the heat supply and the damping represents the heat losses to the environment to mechanical systems where the input is the force supplied and the damping represents the friction which should be counteracted to input of pollution into a natural system and their reduction through an absorption process 21 c m H out 1W H4 my l2557 al 2zi gure 15 Exponential delay of rst order The examples above are systems with one state Variable with a direct feedback loop to imelf Let us now consider a system in two Variables The linear or I Mzrmoru39c oscillator of second order is the most well known example where the effect offeedback can easily be studied 22 b Figure 16 Damped Linear oscillator of second order a n 25 5 75 m 25 5 75 2 225 25 Zeub m u uz r m use 7 at DZ 7 m V no r u5 r 15 M at it u 1 as us m nu 13 Figure 17 Damped linear oscillator a position and velocity trajectories b phase space wae remove damping a1togetherwe get a pure oscillator as shown in Figure 15 and Figure 17 23
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'