advertisement

advertisement

Information about Continuous Systems To Discrete Event Systems

Continuous Systems To Discrete Event Systems

advertisement

Dr Hongnian Yu

Department of Computing

Outline of the presentation Motivation example Modelling and control of continuous engineering systems Petri nets (PN) PN modelling of manufacturing systems Performance analysis using PN Scheduling using PN and AI search Summary

Motivation example

Modelling and control of continuous engineering systems

Petri nets (PN)

PN modelling of manufacturing systems

Performance analysis using PN

Scheduling using PN and AI search

Summary

Motivation example We can represent numerals in many different ways, e.g. Arabic, Roman, English, Chinese, etc. Which one shall we use? It depends on the tasks. For numerical analysis, we prefer the Arabic representation. E.g. carry out a simple multiplication (twenty five times thirty five =?) To write a check, what will we use? Problem Solving = Representation + Reasoning

We can represent numerals in many different ways,

e.g. Arabic, Roman, English, Chinese, etc.

Which one shall we use? It depends on the tasks.

For numerical analysis, we prefer the Arabic representation. E.g. carry out a simple multiplication

(twenty five times thirty five =?)

To write a check, what will we use?

Differential Equations A powerful representation tool of continuous engineering systems (1) Mechanical system: Mass-spring-damper, m: mass, k: spring constant, b: friction constant, u(t): external force, y(t): displacement. (2) Electrical system: RLC circuit General form (State space representation)

Interesting Issues of Engineering Systems Stability Controllability Observability Optimality disturbance Adaptation Robustness

Stability

Controllability

Observability

Optimality

Adaptation

Robustness

Control Methods Adaptive control Adaptive Control of Robot Manipulators Using a Popov Hyperstability Approach, Journal of Systems and Control Engineering, 1995. Simple adaptive control Simple adaptive control of processes with uncertain time-delay and Affine linear structured uncertainty, Journal of Control Theory and Application, 2001. Robust control Exponentially Stable Robust Control Law For Robot Manipulators, Journal of Control Theory and Applications, 1994. Combined adaptive and robust control Robust Combined Adaptive and Variable Structure Adaptive Control of Robot Manipulators, Journal of Robotica, 1998. Iterative learning control Model Reference Parametric Adaptive Iterative Learning Control, 15th IFAC World Congress on Automatic Control, 2002.

Adaptive control

Adaptive Control of Robot Manipulators Using a Popov Hyperstability Approach, Journal of Systems and Control Engineering, 1995.

Simple adaptive control

Simple adaptive control of processes with uncertain time-delay and Affine linear structured uncertainty, Journal of Control Theory and Application, 2001.

Robust control

Exponentially Stable Robust Control Law For Robot Manipulators, Journal of Control Theory and Applications, 1994.

Combined adaptive and robust control

Robust Combined Adaptive and Variable Structure Adaptive Control of Robot Manipulators, Journal of Robotica, 1998.

Iterative learning control

Model Reference Parametric Adaptive Iterative Learning Control, 15th IFAC World Congress on Automatic Control, 2002.

Representation of discrete event systems Man-made systems Computer networks Communication networks Transportation networks Power networks Water networks Manufacturing systems Supply chains Common features: discrete event systems Representation approaches: various, but not unique Finite state automata MAXPLUS algebra Petri nets No standard representation (model) like differential equations for continuous dynamic systems

Man-made systems

Computer networks

Communication networks

Transportation networks

Power networks

Water networks

Manufacturing systems

Supply chains

Common features: discrete event systems

Representation approaches: various, but not unique

Finite state automata

MAXPLUS algebra

Petri nets

No standard representation (model) like differential equations for continuous dynamic systems

Petri nets A PN is a mathematical formalism and a Graph tool to model and analyze discrete event dynamic systems. It is directed graphs with two types of nodes: places and transitions. Places represent conditions which may be ‘held’ and transitions represent events that may ‘occur’ Enabling rule: A transition t is enabled if and only if all the input places of the transition t have a token. Initial state Final state place: transition: Firing rule: An enabled transition t may fire at marking Mc. Firing a transition t will remove a token from each of its input places and will add a token to each of its output places. t t

A PN is a mathematical formalism and a Graph tool to model and analyze discrete event dynamic systems. It is directed graphs with two types of nodes: places and transitions. Places represent conditions which may be ‘held’ and transitions represent events that may ‘occur’

Enabling rule:

A transition t is enabled if and only if all the input places of the transition t have a token.

Firing rule:

An enabled transition t may fire at marking Mc. Firing a transition t will remove a token from each of its input places and will add a token to each of its output places.

Graphical representation of a Petri net an arc’s weight an arc a place a transition a token 2 4

Petri nets: Mathematics Model A Petri net is 5-tuple, PN=(P,T,I,O,M) where P={p 1 ,p 2 , ···, p mp } is a finite set of system states; T={t 1 ,t 2 ,···, t np } is a finite set of transitions; I: the input (preincidence) function; O: output (postincidence) function; M: the m-component marking vector whose i th component, M(p i ) is the number of tokens in the i th place. M 0 is an initial marking. A Petri net from stage k to stage k+1 can be expressed by the following state equation M k+1 = M k + C T u k (1) where M k is the current marking state vector, u k is the control vector and C=O-I is the incident matrix.

A Petri net is 5-tuple, PN=(P,T,I,O,M) where

P={p 1 ,p 2 , ···, p mp } is a finite set of system states;

T={t 1 ,t 2 ,···, t np } is a finite set of transitions;

I: the input (preincidence) function;

O: output (postincidence) function;

M: the m-component marking vector whose i th component, M(p i ) is the number of tokens in the i th place. M 0 is an initial marking.

A Petri net from stage k to stage k+1 can be expressed by the following state equation

M k+1 = M k + C T u k (1)

where M k is the current marking state vector, u k is the control vector and C=O-I is the incident matrix.

Example P={p 1 , p 2 , p 3 }; T={t 1 , t 2 , t 3 }; I(t 1 )={}, I(t 2 )={p 1 , p 2 }, I(t 3 )={p 3 }; O(t 1 )={p 1 }, O(t 2 )={p 3 }, O(t 3 )={p 2 } Initial marking: M 0 =[1, 1, 0]. Using the firing rule , we have M 1 =M 0 +e t C=[1, 1, 0]+[0, 1, 0]C=[0, 0, 1] where e t is the characteristic vector of t: e t (x):=1 if x=t, else =0. t 1 t 2 t 3 p 1 p 3 p 2

Petri Nets: Time Information The concept of time is not explicitly given in the original definition of PNs. For performance analysis and scheduling problems, it is necessary and useful to introduce time delays associated with transitions or places in their PN models. A timed Petri net TPN=(PN,h): PN is a normal Petri net defined as the before; h: the time delay associated with the relevant state. Timed transition Timed place

The concept of time is not explicitly given in the original definition of PNs. For performance analysis and scheduling problems, it is necessary and useful to introduce time delays associated with transitions or places in their PN models.

A timed Petri net TPN=(PN,h):

PN is a normal Petri net defined as the before;

h: the time delay associated with the relevant state.

Example

Batch Plant Flowchart with 1 Reactor and 1 Blender Synthesising and Analysis of a Batch Processing System Using Petri Nets, 1997. The Petri net model of the batch plant Batch plant = charging + reaction + blending + testing & discharging

The Petri net model of the batch plant

Batch plant = charging + reaction + blending + testing & discharging

PN Modelling of Solvent Charging Illustration of places and transitions. p 1 : Reactor available p 2 : Charging Solvent 1 to the reactor p 3 . Charging Solvent 2 to the reactor p 4 : Charging Solvent 3 to the reactor p 5 : Charging Solvent 4 to the reactor p 6 : Reaction in progress to the reactor S 1 : Solvent 1 S 2 : Solvent 2 S 3 : Solvent 3 S 4 : Solvent 4 t 1 : Start charging solvent 1 t 2 : Stop charging solvent 1 & start charging solvent 2 t 3 : Stop charging solvent 2 & start charging solvent 3 t 4 : Stop charging solvent 3 & start charging solvent 4 t 5 : Stop charging solvent 4 & start reaction

PN Modelling of Solvent Charging This is a marked graph since every place has exactly one input and one output transition. The net is live and reversible since every circuit has at least one token. It is a safe net since no place has more than one token.

This is a marked graph since every place has exactly one input and one output transition.

The net is live and reversible since every circuit has at least one token.

It is a safe net since no place has more than one token.

Modelling of Reactor and Blender Illustration of places and transitions p 7 : Charging solvents p 8 : Reaction in progress to the reactor p 9 : Discharging reactor & charging blender p 10 : Blending&testing&discharging R: Reactor available B: Blender available t 6 : Start charging solvents t 7 : Stop charging solvents & start reaction t 8 : Stop reaction&start charging blender t 9 : Stop charging&discharging & start blending t 10 : Stop discharging blender

Modelling of Quality Test Illustration of places and transitions p 12 : Ready for blending p 13 : Logical place for rejected material p 14 : Blending p 15 : Testing p 16 : Testing fail & require reblending p 17 : Testing success & discharging blender S 5 : Blending resource available O 1 : Operator available for testing O 2 : Operator available for discharging t 12 : Pumping to blender finish t 13 : Start blending t 14 : Stop blending & start testing t 15 : testing finish (fail) t 16 : testing finish (success) & start discharging blender t 17 : Start reblending t 16 : Discharging finish

Reachability Graph

Final Petri net model for the batch plant

Performance Analysis Using Timed Petri Nets Performance evaluation of a production system provides the ability to perceive clearly the production plan of the system. It is used to identify the bottleneck in the production unit, estimate the raw material required for production and decide operating policies. Time to charge each solvent is about 30 min. The total time for charging four solvents into the reactor is about 120 min and this can be reflected as a delay time in place p 7 . The time for reaction is 1080 min which represents the delay time in p 8 . The time for discharging the reactor/charging the blender is 60 min which represents the delay time in p 9 . The time for blending is 360 min. The time for testing and discharging is about 180 min. The delay time in p 10 represents the sum of the blending time and the time for testing and discharging.

Performance evaluation of a production system provides the ability to perceive clearly the production plan of the system. It is used to identify the bottleneck in the production unit, estimate the raw material required for production and decide operating policies.

Time to charge each solvent is about 30 min.

The total time for charging four solvents into the reactor is about 120 min and this can be reflected as a delay time in place p 7 .

The time for reaction is 1080 min which represents the delay time in p 8 .

The time for discharging the reactor/charging the blender is 60 min which represents the delay time in p 9 .

The time for blending is 360 min. The time for testing and discharging is about 180 min. The delay time in p 10 represents the sum of the blending time and the time for testing and discharging.

Performance Analysis When the times are deterministic, we can compute the cycle time of each circuit g: Cg = m(g)/M(g) for g = { 1....q } where q is the number of circuits in the model, m(g) is the sum of place delays in the circuit g, M(g) is the sum of tokens in the circuit g For a marked graph, the minimum cycle time, Cm is Cm = Max { m(g)/M(g) } To compute the result, it is important to list all the circuits produced by this model and show the minimum cycle time of each circuit. There are two elementary circuits in our model. Circuit 1 C1 = 120 + 1080 + 60 =1240 min Circuit 2 C2 = 60 + (360 + 180)=600 min Therefore the minimum cycle time is 1240 minutes. The bottle neck machine is in element circuit 1, i.e., the reactor.

When the times are deterministic, we can compute the cycle time of each circuit g:

Cg = m(g)/M(g) for g = { 1....q }

where q is the number of circuits in the model, m(g) is the sum of place delays in the circuit g, M(g) is the sum of tokens in the circuit g

For a marked graph, the minimum cycle time, Cm is

Cm = Max { m(g)/M(g) }

To compute the result, it is important to list all the circuits produced by this model and show the minimum cycle time of each circuit. There are two elementary circuits in our model.

Circuit 1 C1 = 120 + 1080 + 60 =1240 min

Circuit 2 C2 = 60 + (360 + 180)=600 min

Therefore the minimum cycle time is 1240 minutes. The bottle neck machine is in element circuit 1, i.e., the reactor.

Scheduling Approaches The mixed integer linear programming approach: It is similar to the linear programming approach with linear objective function and constraints but some of its variables are integer and others binary. The critical path scheduling approach (CPA) and the program evaluation and review technique (PERT): Both are network based methods. The artificial intelligence (AI) based approaches: These include depth-first and breadth-first search approaches, Branch and Bound search approach, best-first search approach, climb hill search approach, beam search approach, A* (heuristic) search approach, etc. These are called the systematic approaches. The non-systematic approaches: genetic algorithm based approach, simulation annealing approach, etc. Rule based approaches: Copying the expertise of human schedulers and adopting the tactics that they use. The simulation based approaches: discrete-event simulation.

The mixed integer linear programming approach: It is similar to the linear programming approach with linear objective function and constraints but some of its variables are integer and others binary.

The critical path scheduling approach (CPA) and the program evaluation and review technique (PERT): Both are network based methods.

The artificial intelligence (AI) based approaches: These include depth-first and breadth-first search approaches, Branch and Bound search approach, best-first search approach, climb hill search approach, beam search approach, A* (heuristic) search approach, etc. These are called the systematic approaches.

The non-systematic approaches: genetic algorithm based approach, simulation annealing approach, etc.

Rule based approaches: Copying the expertise of human schedulers and adopting the tactics that they use.

The simulation based approaches: discrete-event simulation.

Petri Net + AI Based Scheduling Methods Scheduling: Based on reachability tree analysis (for simple Petri nets) Uses reduced reachability space for more complex Petri nets Example: A 2 product & 2 processor system is used to illustrate the method. Problem statement: A complete description of the problem discussed is as follows: The objective function to be minimised is the time makespan required to complete all the jobs. The given constraints are: precedence relationships among the jobs; fixed number of resources and prescribed job-resource assignment. The goal is to find a sequential order of jobs that satisfies the above conditions.

Scheduling:

Based on reachability tree analysis (for simple Petri nets)

Uses reduced reachability space for more complex Petri nets

Example: A 2 product & 2 processor system is used to illustrate the method.

Problem statement:

A complete description of the problem discussed is as follows:

The objective function to be minimised is the time makespan required to complete all the jobs.

The given constraints are:

precedence relationships among the jobs;

fixed number of resources and prescribed job-resource assignment.

The goal is to find a sequential order of jobs that satisfies the above conditions.

Gantt Chart Firing sequence: t 1 t 2 t 3 t 4 t 5 t 6 t 7 t 8 leads to c=14 min Firing sequence: t 5 t 6 t 1 t 7 t 2 t 8 t 3 t 4 leads to c=11 min (optimum)

PN Based Intelligent Scheduling Approaches A scheduling approach using Petri net modelling and a Branch & Bound search, Proc. IEEE International Symposium on Assembly and Task Planning, 1995. Planning through Petri Nets, Proc. of the Sixteenth Workshop of the UK Planning and Scheduling Special Interest Group, 1997. Petri Net-Based Closed-Loop Control and On-line Scheduling of the Batch Process Plant, Proc. of CONTROL 98, 1998. Rule-Based Petri Net Modelling and Scheduling of Flexible Manufacturing Systems, Proc. of 14th NCMR Conference, 1998. Generic Net Modelling Framework for Petri Nets, IASTED International Conference on Intelligent Systems and Control, 1999 Integrating Petri Net Modelling and AI Based Heuristic Hybrid Search for Scheduling of FMS, Journal of Computer in Industry, 2002. Advanced Scheduling Methodologies for FMS using Petri Nets and Artificial Intelligence, IEEE Trans on Robotics and Automation, 2002. Petri Nets, Heuristic Search and Natural Evolution: Promising Scheduling Algorithm for Job Shop Systems, Proc. of The Third International ICSC Symposia on INTELLIGENT INDUSTRIAL AUTOMATION, 1999 Petri net Modelling and Witness Simulation of Manufacturing Systems , Proc. of Third World Manufacturing Congress, 2001

A scheduling approach using Petri net modelling and a Branch & Bound search, Proc. IEEE International Symposium on Assembly and Task Planning, 1995.

Planning through Petri Nets, Proc. of the Sixteenth Workshop of the UK Planning and Scheduling Special Interest Group, 1997.

Petri Net-Based Closed-Loop Control and On-line Scheduling of the Batch Process Plant, Proc. of CONTROL 98, 1998.

Rule-Based Petri Net Modelling and Scheduling of Flexible Manufacturing Systems, Proc. of 14th NCMR Conference, 1998.

Generic Net Modelling Framework for Petri Nets, IASTED International Conference on Intelligent Systems and Control, 1999

Integrating Petri Net Modelling and AI Based Heuristic Hybrid Search for Scheduling of FMS, Journal of Computer in Industry, 2002.

Advanced Scheduling Methodologies for FMS using Petri Nets and Artificial Intelligence, IEEE Trans on Robotics and Automation, 2002.

Petri Nets, Heuristic Search and Natural Evolution: Promising Scheduling Algorithm for Job Shop Systems, Proc. of The Third International ICSC Symposia on INTELLIGENT INDUSTRIAL AUTOMATION, 1999

Petri net Modelling and Witness Simulation of Manufacturing Systems , Proc. of Third World Manufacturing Congress, 2001

Petri Nets Applications Performance analysis Optimisation, scheduling, planning Simulation Control synthesis Formal verification and validation

Performance analysis

Optimisation, scheduling, planning

Simulation

Control synthesis

Formal verification and validation

Summary Two types of systems Natural (continuous) engineering systems A powerful representation tool, differential equation, is available Many analysis approaches have been developed Man-made (discrete event) systems Many representation approaches are proposed, but none of them is as powerful as the differential equation Complexity Uncertainty

Two types of systems

Natural (continuous) engineering systems

A powerful representation tool, differential equation, is available

Many analysis approaches have been developed

Man-made (discrete event) systems

Many representation approaches are proposed, but none of them is as powerful as the differential equation

Complexity

Uncertainty

Variable structure control Assumption: The bounds of the unknown parameters are known, i.e. Theorem. For the system (1), if the robust control laws are (t)= n (t)+ l (t), n (t)=W(t) v (t)+W 0 (t), l (t)=-(P ll +P cc -1 P cc )s(t)+P cc E 1 (t) where then for a reasonably small positive constant , all the signals in the system are bounded and E(t) tends to zero with at least an exponential rate that is independent of the excitation. p is the number of the uncertainty parameters, P cc , , P ll R n n are symmetric positive definite gain matrices, P 12 =P cc -1 R n n , P 1 =[P 12 I n n ] R n 2n , Exponentially Stable Robust Control Law For Robot Manipulators, Journal of Control Theory and Applications, 1994. Back Dynamic equation: (1)

Assumption: The bounds of the unknown parameters are known, i.e.

Exponentially Stable Robust Control Law For Robot Manipulators, Journal of Control Theory and Applications, 1994.

Adaptive control Dynamic equation: Define the control law as (t)= n (t)+ l (t) (2) Linear control law: Non-linear adaptive control law: (1) Theorem. The control system (1) with the control law (2) is globally convergent, that is E(t) asymptotically converges to zero and all internal signals are bounded. Adaptive Control of Robot Manipulators, Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems, 1992. Adaptive Control of Robot Manipulators Using a Popov Hyperstability Approach, Journal of Systems and Control Engineering, 1995. Back

Dynamic equation:

Adaptive Control of Robot Manipulators, Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems, 1992.

Adaptive Control of Robot Manipulators Using a Popov Hyperstability Approach, Journal of Systems and Control Engineering, 1995.

Iterative learning control Dynamic equation: (1) Control input: (2) Parameter ILC law: (3) Theorem: For the robot system described by (1), if the control law (2) and the parameter iterative learning law (3) are used, the desired joint trajectories and their up to 2nd order derivatives are bounded, and the initial tracking errors (0)=0 and (0)=0 for j=1,2…, then the following properties hold: i ii iii Parametric Iterative Learning Control of Robot Manipulators, Proc. of the Chinese Automation Conference, 1999. Model Reference Parametric Adaptive Iterative Learning Control, 15th IFAC World Congress on Automatic Control, BARCELONA, Spain, 2002. Back

Dynamic equation: (1)

Parametric Iterative Learning Control of Robot Manipulators, Proc. of the Chinese Automation Conference, 1999.

Model Reference Parametric Adaptive Iterative Learning Control, 15th IFAC World Congress on Automatic Control, BARCELONA, Spain, 2002.

Discrete event simulation produces a system which ... therefore discrete. A continuous simulation of ... continuous simulation, the continuous time ...

Read more

DEVS abbreviating Discrete Event System Specification is a modular and hierarchical formalism for ... and hybrid continuous state and discrete event systems.

Read more

Discrete-Event System Simulation FIFTH EDITION Jerry Banks ... 1.8 Discrete and Continuous Systems 32 1.9 Model of a System 33 1.10 Types of Models 33

Read more

Discrete event simulation of continuous systems. James Nutaro Oak Ridge National Laboratory nutarojj@ornl.gov 1 Introduction Computer simulation of a ...

Read more

Discrete Event Systems ... discrete event system” was introduced in the ... in the description of a DES are both continuous and discrete, ...

Read more

Introduction to Discrete-Event ... • System: Discrete and Continuous ... such systems should be studied by means of

Read more

Control Theory for Discrete Event Systems! The manufacturing system can be formally modelled as a discrete-event system (DES). In contrast to continuous ...

Read more

Introduction to Discrete Event Systems is a comprehensive ... The revised second edition incorporates essential elements of Hybrid System ...

Read more

Description. sysd = c2d(sys,Ts) discretizes the continuous-time dynamic system model sys using zero-order hold on the inputs and a sample time of Ts seconds.

Read more

## Add a comment