SIMULATION & MODELING (IT-702 (C)) - Unit 4 Short Notes

UNIT 4: SIMULATION & MODELING

I. Fundamentals of Simulation

Simulation is the process of developing and experimenting with a model of a real or proposed system to understand its behavior and evaluate alternative strategies.

Purpose:

• Analyze complex systems where analytical solutions are infeasible.

• Test "what-if" scenarios without disrupting the real system.

• Train personnel in a risk-free environment.

• Predict system performance and bottlenecks.

Steps in Simulation Process:

1. Problem Definition: Identify the issue and objectives.

2. Model Design: Develop a conceptual/logical model.

3. Data Collection: Gather input data for the model.

4. Model Implementation: Code the model using a simulation language/tool.

5. Verification & Validation (V&V): Ensure model correctness and accuracy.

6. Experimentation: Run simulations with different inputs/scenarios.

7. Analysis & Interpretation: Analyze output data, draw conclusions.

8. Documentation & Reporting: Present findings and recommendations.

[!TIP] Exam Focus: The 7-mark question on simulation steps requires a clear flow diagram. Be prepared to sketch and explain each step.

Types of Systems:

Limitations of Simulation:

• Cost & Time: Model building and experimentation can be expensive and lengthy.

• Complexity: Building an accurate model for very complex systems is difficult.

• Output Interpretation: Results are estimates; statistical analysis is required to draw conclusions.

• "Black Box" Nature: May not provide deep analytical insight into system relationships.

• Randomness: Requires handling of stochastic elements, needing many replications for confidence.

II. Probability and Statistics in Simulation

Random Variables (RVs):

• Discrete RV: Takes countable values (e.g., number of customers arriving).

• Continuous RV: Takes any value in an interval (e.g., service time).

Key Probability Distributions:

1. Binomial Distribution (n, p):

   • Models number of successes in n independent Bernoulli trials.

   • PMF: $$\displaystyle P(X=k) = \binom{n}{k} p^k (1-p)^{n-k} $$, for $$\displaystyle k=0,1,...,n $$

   • Mean: $$\displaystyle \mu = np $$, Variance: $$\displaystyle \sigma^2 = np(1-p) $$

2. Poisson Distribution (λ):

   • Models number of events occurring in a fixed interval.

   • PMF: $$\displaystyle P(X=k) = \frac{e^{-\lambda} \lambda^k}{k!} $$, for $$\displaystyle k=0,1,2,... $$

   • Mean & Variance: $$\displaystyle \mu = \sigma^2 = \lambda $$

   • Condition for approximating Binomial: When n is large ($n \geq 20$), p is small ($p \leq 0.05$), and $$\displaystyle \lambda = np \leq 5 $$.

3. Normal Distribution (μ, σ²):

   • PDF: $$\displaystyle f(x) = \frac{1}{\sigma\sqrt{2\pi}} e^{-\frac{1}{2}\left(\frac{x-\mu}{\sigma}\right)^2} $$, for $$\displaystyle -\infty < x < \infty $$

   • Mean & Variance: $\mu$, $$\displaystyle \sigma^2 $$

   • Used for sums/averages of many independent random variables (Central Limit Theorem).

Probability Density Function (PDF) vs. Cumulative Distribution Function (CDF):

• PDF (f(x)): For continuous RVs, gives the density at point x. Area under curve = 1.

• CDF (F(x)): $$\displaystyle F(x) = P(X \leq x) = \int_{-\infty}^{x} f(t) dt $$. Probability that RV ≤ x.

• Example: For Exponential(λ) distribution:

  • PDF: $$\displaystyle f(x) = \lambda e^{-\lambda x} $$ for $x \geq 0$

  • CDF: $$\displaystyle F(x) = 1 - e^{-\lambda x} $$

Stochastic Variables & Processes:

• Stochastic Variable: A RV whose value is subject to randomness.

• Stochastic Process: A collection of stochastic variables indexed by time (e.g., arrival process over a day).

Arrival Patterns:

• Often modeled as a Poisson Process:

  • Assumptions: Independence of inter-arrival times, stationary arrival rate (λ), no simultaneous arrivals.

  • Inter-arrival times follow Exponential(λ) distribution: $$\displaystyle f(t) = \lambda e^{-\lambda t} $$.

  • Key property: Number of arrivals in interval (t, t+τ) ~ Poisson(λτ).

[!TIP] Exam Focus: Be ready to state the conditions for Binomial → Poisson approximation and derive/state PDF/CDF for at least one distribution (Exponential, Uniform).

III. Queuing Theory and Simulation

General Queuing System Components ( Kendall's Notation: A/S/c/K/N/Z ):

Queuing System Representation:

[Arrival Source] --> [Queue] --> [Server(s)] --> [Departure]

Performance Measures:

• Server Utilization (ρ): $$\displaystyle \rho = \frac{\lambda}{\mu} $$ (for 1 server, λ = arrival rate, μ = service rate).

• Average Queue Length (Lq): Expected number waiting.

• Average Number in System (L): L = Lq + (number of busy servers).

• Average Waiting Time in Queue (Wq): Expected time spent waiting.

• Average Time in System (W): W = Wq + (average service time).

• Probability of n customers in system (Pn).

Applications:

• Telecommunications (call centers).

• Manufacturing (job shop scheduling).

• Healthcare (patient flow in ER).

• Transportation (traffic light modeling, airport gates).

• Computing (CPU scheduling, web server design).

Simulation of a Queuing System (Steps):

1. Initialize: Set simulation clock = 0, create first arrival event.

2. Event Scheduling: Maintain a future event list (FEL) sorted by time.

3. Event Processing: Remove next event from FEL, advance clock.

   • Arrival Event: Check server status. If free, begin service, schedule next arrival & departure. If busy, increment queue.

   • Departure Event: If queue not empty, remove next customer, schedule new departure. Else, mark server idle.

4. Statistics Collection: Accumulate data (queue length, wait times, server busy time).

5. Termination: Stop after predefined time or number of customers.

6. Analysis: Compute performance measures from collected statistics.

[!TIP] Exam Focus: You may be asked to simulate a simple M/M/1 queue manually for a few events. Know how to calculate ρ and basic performance measures for M/M/1: $$\displaystyle L = \frac{\rho}{1-\rho} $$, $$\displaystyle W = \frac{1}{\mu - \lambda} $$.

IV. Model Verification and Validation (V&V)

Key V&V Techniques:

• Verification: Static/dynamic code analysis, unit testing, trace files.

• Validation:

  • Face Validity: Have domain experts review model logic/output.

  • Sensitivity Analysis: Check if output changes plausibly with input changes.

  • Historical Validation: Compare model output with past system data.

  • Calibration: Adjust model parameters to match real system behavior.

[!TIP] Common Pitfall: Students often confuse the two. Remember: Verification = Code Correctness, Validation = Realism.

V. Simulation Techniques and Languages

Analog vs. Digital Simulation:

Classification of Simulation Languages:

1. Discrete-Event Simulation Languages: GPSS, SIMSCRIPT, Arena, Simio. Designed for event-based systems (queues, logistics).

2. Continuous Simulation Languages: DYNAMO, ACSL, MATLAB/Simulink. Solve differential equations for continuous systems (physics, chemistry).

3. Combined Discrete-Continuous Languages: GASP IV, SIMAN. Can handle both event-driven and continuous dynamics.

AI Techniques in Simulation:

• Neural Networks: Used for system identification (learning the model from data) or as surrogate models for fast approximation.

• Fuzzy Logic: Handles imprecise inputs and human-like reasoning in decision rules (e.g., "if queue is long, add more servers").

• Expert Systems: Embed human expertise into simulation for decision-making (e.g., routing rules in a manufacturing simulation).

• Simulation of Classification Systems: Using AI classifiers (e.g., decision trees) to categorize simulation outputs or to model agent behaviors based on learned rules.

Pure Pursuit Problem:

• Problem: A pursuer (e.g., robot, missile) follows a moving target by always pointing its velocity vector directly at the target's current position.

• Simulation Approach:

  1. Model kinematics: $$\displaystyle \vec{v}_p = v_p \cdot \hat{d} $$, where $\hat{d}$ is unit vector from pursuer to target.

  2. Update positions: $$\displaystyle \vec{x}_p(t+\Delta t) = \vec{x}_p(t) + \vec{v}_p \Delta t $$, similarly for target.

  3. Simulate over time steps until capture (distance < threshold) or timeout.

• Applications: Robotics path tracking, missile guidance, animal predation modeling.

VI. Applications of Simulation

Autopilot Simulation:

• Purpose: Design, test, and certify flight control systems without risk.

• Components:

  1. Aircraft Dynamics Model: Nonlinear differential equations of motion (6-DOF: 3 translational, 3 rotational).

  2. Environment Model: Atmosphere (wind, turbulence), gravity.

  3. Sensor Models: IMU, GPS, air data (with noise/delay).

  4. Autopilot Controller Model: The logic/algorithm (e.g., PID, LQR) being tested.

  5. Actuator Models: Ailerons, elevators, rudder, throttle (with dynamics/limits).

• Simulation Flow: Controller receives (noisy) state estimates → computes control commands → commands sent to actuators → aircraft dynamics respond → new state sensed → loop continues.

• Example: Simulating a pitch hold mode. Controller compares current pitch angle to setpoint, adjusts elevator to minimize error.

Other Application Domains:

• Healthcare: Emergency department patient flow, epidemic spread, hospital resource planning.

• Transportation: Traffic signal optimization, airport operations, supply chain logistics.

• Defense: Battlefield scenarios, weapon system effectiveness, training simulators.

• Manufacturing: Production line balancing, inventory management, maintenance scheduling.

• Finance: Portfolio risk analysis, market micro-structure.

VII. Mathematical Foundations

Role of Differential Equations in Continuous System Simulation:

• Continuous systems (e.g., mechanical, electrical, thermal) are governed by ordinary differential equations (ODEs) or partial differential equations (PDEs).

• Simulation Approach:

  1. Formulate state equations: $$\displaystyle \frac{d\vec{x}}{dt} = \vec{f}(\vec{x}, \vec{u}, t) $$.

  2. Choose numerical integration method (Euler, Runge-Kutta).

  3. Iterate: $$\displaystyle \vec{x}(t+\Delta t) = \vec{x}(t) + \vec{f}(\vec{x}(t), \vec{u}(t), t) \cdot \Delta t $$ (for Euler).

• Example: Mass-spring-damper: $$\displaystyle m\ddot{x} + c\dot{x} + kx = F(t) $$. Convert to two first-order ODEs for state variables (position, velocity).

Stochastic Modeling in Simulation:

• Incorporates randomness to model uncertainty in real systems.

• Key Elements:

  • Input Modeling: Identify probability distributions for uncertain inputs (arrival times, service times, failure times) using historical data and statistical tests (Chi-square, KS).

  • Random Number Generation: Use pseudo-random number generators (PRNGs) to produce uniform (0,1) variates.

  • Random Variate Generation: Transform uniform variates to desired distribution (Inverse Transform, Acceptance-Rejection).

  • Output Analysis: Use statistical techniques (confidence intervals, t-tests) to compare system designs, accounting for inherent randomness. Requires multiple replications (independent runs) to reduce variance.

[!TIP] Exam Focus: Be prepared to write a simple ODE system for a physical system (e.g., predator-prey) and explain the Euler integration step. For stochastic modeling, know the steps from input data analysis to output analysis.