Applications of Perturbation Analysis in Stochastic Hybrid Systems

Applications of Perturbation Analysis in Stochastic Hybrid Systems

/in /by

Applications of Perturbation Analysis in Stochastic Hybrid Systems
Christos Cassandras and J.L. Fleck

Control and optimization of Stochastic Hybrid Systems (SHS) constitute increasingly active fields of research. Perturbation Analysis (PA) techniques have proven to be particularly useful for SHS, since the size and complexity of such systems frequently render the use of exhaustive verification techniques prohibitive. This book focuses on applying PA to two different problems: Traffic Light Control (TLC) and control of cancer progression, both of which are viewed as dynamic optimization problems in a SHS environment. The TLC problem for a single intersection is modeled as a SHS, for which a quasi-dynamic control policy is proposed based on partial state information defined by detecting whether vehicle backlogs are above or below certain controllable threshold values. The problem of controlling cancer progression is formulated within a Stochastic Hybrid Automaton framework, and an integrative closed-loop framework is proposed for describing the progressive development of cancer and determining optimal personalized therapies. The insights provided by this book should be useful to researchers in the field of SHS and more generally to those interested in cutting-edge optimization solutions.

Energy-Latency Trade-Offs in Real-Time Wireless Sensor Networks

/in /by

Energy-Latency Trade-Offs in Real-Time Wireless Sensor Networks
Lei Mia and Christos G. Cassandras

We study the optimal control of a class of resource allocation problems characterized by energy-latency trade-offs in Wireless Sensor Networks (WSN) using the framework of Discrete Event Systems. Our work is based on the observation that energy of wireless nodes can be greatly saved by introducing some delay of task completion time. Specifically, we consider a family of problems motivated by WSN such as Dynamic Transmission Control and Dynamic Voltage Scaling, where the objective is to minimize energy consumption while satisfying real-time operating constraints. Using advanced techniques, such as sample path analysis and Receding Horizon Control, we address both off-line and on-line scenarios and have found better and more efficient solutions than the existing ones in the literature. Our results do not rely on the exact form of the cost function and can be readily applied to other settings as long as the cost function satisfies certain conditions. This work is beneficial to students, scholars, and engineers who are interested in utilizing advanced control and optimization techniques to solve resource allocation problems in wireless networks.

Introduction to Discrete Event Systems 2

Introduction to Discrete Event Systems 2nd Edition

/in /by

Introduction to Discrete Event SystemsIntroduction to Discrete Event Systems 2Introduction to Discrete Event Systems, 1st and 2nd Editions
Christos G. Cassandras and Stephane Lafortune

The rapid evolution of computing, communication, and sensor technologies has brought about the proliferation of new dynamic systems, mostly technological and often highly complex. Examples are all around us: computer and communication networks; automated manufacturing systems; air traffic control systems; and distributed software systems. The “activity” in these systems is governed by operational rules designed by humans; their dynamics are therefore characterized by asynchronous occurrences of discrete events. These features lend themselves to the term discrete event system for this class of dynamic systems.
A substantial portion of this book is a revised version of Discrete Event Systems: Modeling and Performance Analysis (1993), written by the first author, which received the 1999 HAROLD CHESTNUT PRIZE awarded by the International Federation of Automatic Control for best control engineering textbook. This new expanded book is intended to be a comprehensive introduction to the field of discrete event systems, emphasizing breadth of coverage and accessibility of the material to readers with possibly different backgrounds. Its key feature is the emphasis placed on a unified modeling framework that transcends specific application areas and allows linking of the following topics in a coherent manner: language and automata theory, supervisory control, Petri net theory, (max,+) algebra, Markov chains and queuEing theory, discrete-event simulation, perturbation analysis, and concurrent estimation techniques. Until now, these topics had been treated in separate books or in research literature only.
Introduction to Discrete Event Systems is written as a textbook for courses at the senior undergraduate level or the first-year graduate level. It will be of interest to students in a variety of disciplines where the study of discrete event systems is relevant: control, communications, computer engineering, computer science, manufacturing engineering, operations research, and industrial engineering.

Table of Contents

Preface

1. Systems and Models

Introduction
System and Control Basics
Discrete Event Systems
Summary of System Classifications
The Goals of System Theory
Summary & Problems
Selected References

2. Languages and Automata

Introduction
The Concepts of Languages and Automata
Operations on Automata
Finite-State Automata
Analysis of Discrete-Event Systems
Summary & Problems
Selected References

3. Supervisory Control

Introduction
Feedback Control with Supervisors
Specifications on Controlled System
Dealing with Uncontrollability
Dealing with Blocking
Modular Control
Dealing with Unobservability
Decentralized Control
Summary & Problems
Selected Reference

4. Petri Nets

Introduction
Petri Net Basics
Comparison of Petri Nets and Automata
Analysis of Petri Nets
Summary & Problems
Selected References

5. Timed Models

Introduction
Timed Automata
Timed Petri Nets
Dioid Algebras
Concluding Comments
Summary & Problems
Selected References

6. Stochastic Timed Automata

Introduction
Stochastic Process Basics
Stochastic Clock Structures
Stochastic Timed Automata
The Generalized Semi-Markov Process
The Poisson Counting Process
Properties of the Poisson Process
Automata with Poisson Clock Structure
Extensions of the GSMP
Summary & Problems
Selected References

7. Markov Chains

Introduction
Discrete-Time Markov Chains
Continuous-Time Markov Chains
Birth-Death Chains
Uniformization of Markov Chains
Summary & Problems
Selected References

8. Introduction to Queueing Theory

Introduction
Specification of Queueing Models
Performance of a Queueing System
Queueing System Dynamics
Little’s Law
Simple Markovian Queueing Systems
Markovian Queueing Networks
Non-Markovian Queueing Systems
Summary & Problems
Selected References

9. Controlled Markov Chains

Introduction
Applying “Control” in Markov Chains
Markov Decision Processes
Solving Markov Decision Problems
Control of Queuing Systems
Summary & Problems
Selected References

10.Introduction to Discrete-Event Simulation

Introduction
The Event Scheduling Scheme
The Process-Oriented Simulation Scheme
Discrete-Event Simulation Languages
Random Number Generation
Random Variate Generation
Output Analysis
Summary & Problems
Selected References

11. Sensitivity Analysis & Concurrent Estimation

Introduction
Sample Functions and Their Derivatives
Perturbation Analysis: Some Key Ideas
PA of GI/G/ 1 Queuing Systems
IPA for Stochastic Timed Automata
Sensitivity Estimation Revisited
Extensions of IPA
Smoothed Perturbation Analysis (SPA)
PA for Finite Parameter Changes
Concurrent Estimation
Summary & Problems
Selected References

Appendices

I. Review of Probability Theory
II. IPA Estimator

Index

ERRATA
PDF file of Errata in the book: errata.pdf

If you find a typographical error or have any questions regarding any part of the book, please contact either author:
Christos G. Cassandras, cgc AT bu.edu
Stephane Lafortune, stephane AT eecs.umich.edu

INSTRUCTOR’S AIDS
– Solutions to all problems are available directly from the authors.
– Additional software, interactive web sites, animated presentations on special topics related to Discrete Event Systems are listed in Related Web Sites.

FEEDBACK TO AUTHORS
The authors would appreciate to hear your comments on the book, suggestions, specific questions, or any issue related to Discrete Event Systems.

Stochastic Hybrid Systems

Stochastic Hybrid Systems

/in /by

Stochastic Hybrid SystemsStochastic Hybrid Systems
Christos G. Cassandras and John Lygeros

Because they incorporate both time- and event-driven dynamics, stochastic hybrid systems (SHS) have become ubiquitous in a variety of fields, from mathematical finance to biological processes to communication networks to engineering. Comprehensively integrating numerous cutting-edge studies, Stochastic Hybrid Systems presents a captivating treatment of some of the most ambitious types of dynamic systems.

Cohesively edited by leading experts in the field, the book introduces the theoretical basics, computational methods, and applications of SHS. It first discusses the underlying principles behind SHS and the main design limitations of SHS. Building on these fundamentals, the authoritative contributors present methods for computer calculations that apply SHS analysis and synthesis techniques in practice. The book concludes with examples of systems encountered in a wide range of application areas, including molecular biology, communication networks, and air traffic management. It also explains how to resolve practical problems associated with these systems.

Stochastic Hybrid Systems achieves an ideal balance between a theoretical treatment of SHS and practical considerations. The book skillfully explores the interaction of physical processes with computerized equipment in an uncertain environment, enabling a better understanding of sophisticated as well as everyday devices and processes.

Discrete Event Systems: Modeling and Performance Analysis

Discrete Event Systems: Modeling and Performance Analysis

/in /by

Discrete Event Systems: Modeling and Performance AnalysisDiscrete Event Systems: Modeling and Performance Analysis
Christos G. Cassandras

Discrete Event Systems: Modeling and Performance Analysis is the first instructional text to be published in an area that emerged in the early 1980s and that spans such disciplines as systems and control theory, operations research, and computer science. Developments in this area are impacting the design and analysis of complex computer-based engineering systems. Designed for seniors and first-year graduate students, the book shows where Discrete Event Systems (DES) appear in modern technological environments, such as computer networks, automated manufacturing processes, and airport and highway traffic systems. The text provides a unified framework for modeling, design, analysis, and control of these “man made” dynamic systems.

Objectives of the Text

Explain the characteristics of DES and show how they differ from classical systems.
Describe the differences between various modeling approaches, from simple to more complex untimed to timed, and deterministic to stochastic.
Develop two general directions in analyzing DES models:
– The classical probabilistic approach, using stochastic process theory.
– Computer simulation and sample path analysis.
Show how to simulate DES using commercially available software or from first principles.
Provide the basis for further study in such areas as advanced queuing theory, dynamic control of DES perturbation analysis, and sample path constructability techniques.

Features of the Text

Focus on the timed aspects of DES. The fundamentals of untimed models and analysis are presented in Chapter 2 to give the student an overview of the entire field.
Introduction to queuing theory (Chapter 6) as a method of analysis and performance evaluation.
Introduction to the dynamic control of queuing systems and problems such as admission control, routing, and scheduling (Chapter 7).
Discussion of sensitivity analysis and techniques of sample path constructability for DES to introduce readers to recent research in the field (Chapter 9).
Explicit instructions for building discrete event simulation models.
Computer codes illustrating perturbation analysis algorithms.

Prerequisites

basic course on probability theory and some knowledge of stochastic processes.
Familiarity with concepts from signals and systems.
Elementary differential equations and linear algebra.

Supplements

An Instructors Manual, containing solutions to the problems

How to Order This Book

A new version of this book, co-auhored by Stephane Lafortune, was published in 1999. A Second Edition was published in 2006. Click here for the publisher.

Table of Contents

Preface

Chapter 1 Systems and Models
1.1 Introduction 1.2 System and Control Basics 1.2.1 The Concept of System 1.2.2 The Input-Output Modeling Process Static and Dynamic Systems Time-varying and Time-invariant Dynamic Systems 1.2.3 The Concept of State 1.2.4 The State Space Modeling Process Linear and Nonlinear Systems 1.2.5 Sample Paths of Dynamic Systems 1.2.6 State Spaces Continuous-State and Discrete-State Systems Deterministic and Stochastic Systems 1.2.7 The Concept of Control 1.2.8 The Concept of Feedback Open-loop and Closed-loop Systems 1.2.9 Discrete-Time Systems 1.3 Discrete-Event Systems 1.3.1 The Concept of Event Time-driven and Event-driven Systems 1.3.2 Characteristic Properties of Discrete-Event Systems Untimed and Timed Models for Discrete-Event Systems 1.3.3 Examples of Discrete-Event Systems Queuing Systems Computer Systems Communication Systems Manufacturing Systems Traffic Systems 1.4 Summary of System Classifications 1.5 The Goals of System Theory

Chapter 2 Untimed Models of Discrete-Event Systems
2.1 Introduction 2.2 Languages and Automata Theory 2.2.1 Language Notation and Definitions 2.2.2 Finite-State Automata State Transition Diagrams Automata as Language Recognizers Nondeterministic Finite State Automata Equivalence of Finite-State Automata and Regular Expressions 2.2.3 State Aggregation in Automation 2.2.4 Discrete-Event Systems as State Automata 2.2.5 State Automata Models for Queuing Systems 2.2.6 State Automata with Output 2.2.7 Supervisory Control of Discrete-Event Systems 2.3 Petri Nets 2.3.1 Petri Net Notation and Definitions 2.3.2 Petri Net Markings and State Spaces 2.3.3 Petri Net Dynamics 2.3.4 Petri Net Models for Queueing Systems 2.3.5 Comparison of Petri Net and State Automata Models 2.4 Analysis of Untimed Models of Discrete-Event Systems 2.4.1 Problem Classification Boundedness Conservation Liveness and Deadlocks State Reachability State Coverability Persistence Language Recognition 2.4.2 The Coverability Tree 2.4.3 Applications of the Coverability Tree Boundedness Problems Conseration Problems Coverability Problems Coverability Tree Limitations

Chapter 3 Time Models of Discrete-Event Systems
3.1 Introduction 3.2 Timed State Automata 3.2.1 The Clock Structure 3.2.2 Event Timing Dynamics 3.2.3 A State Space Model 3.2.4 Queueing Systems as Timed State Automata 3.2.5 The Event Scheduling Scheme 3.3 Timed Petri Nets 3.3.1 Time Petri Net Dynamics 3.3.2 Queueing Systems as Timed Petri Nets 3.4 Dioid Algebras 3.4.1 Basic Properties of the (max, +) Algebra 3.4.2 Modeling Queueing Systems in the (max, +) Algebra

Chapter 4 Stochastic Timed Models for Discrete-Event Systems
4.1 Introduction 4.2 Definitions, Notations, and Classifications of Stochastic Processes 4.2.1 Continuous-state and Discrete-state Stochastic Processes 4.2.2 Continuous-time and Discrete-time Stochastic Processes 4.2.3 Some Important Classes of Stochastic Processes Stationary Processes Independent Processes Markov Processes Semi-Markov Processes Renewal Processes 4.3 Stochastic Clock Structures 4.4 Stochastic Timed State Automata 4.5 The Generalized Semi-Markov Process (GSMP) 4.5.1 Queueing Systems as Generalized Semi-Markov Processes 4.5.2 GSMP Analysis 4.6 The Poisson Counting Process 4.7 Properties of The Poisson Process 4.7.1 Exponentially Distributed Interevent Times 4.7.2 The Memoryless Property 4.7.3 Superposition of Poisson Processes 4.7.4 The Residual Lifetime Paradox 4.8 The GSMP With a Poisson Clock Structure 4.8.1 Distribution of Interevent Times 4.8.2 Distribution of Events 4.8.3 Markov Chains 4.9 Extensions of The Generalized Semi-Markov Process

Chapter 5 Markov Chains
5.1 Introduction 5.2 Discrete-Time Markov Chains 5.2.1 Model Specification 5.2.2 Transition Probabilities and the Chapman-Kolmogorov Equations 5.2.3 Homogeneous Markov Chains 5.2.4 The Transition Probability Matrix 5.2.5 State Holding Times 5.2.6 State Probabilities 5.2.7 Transient Analysis 5.2.8 Classification of State Null and Positive Recurrent States Periodic and Aperiodic States Summary of State Classifications 5.2.9 Steady State Analysis 5.2.10 Irreducible Markov Chains 5.2.11 Reducible Markov Chains 5.3 Continuous-time Markov Chains 5.3.1 Model Specifications 5.3.2 Transition Function 5.3.3 The Transition Rate Matrix 5.3.4 Homogeneous Markov Chains 5.3.5 State Holding Times 5.3.6 Physical Interpretation and Properties of the Transition Rate Matrix 5.3.7 Transition Probabilities 5.3.8 State Probabilities 5.3.9 Transient Analysis 5.3.10 Steady State Analysis 5.4 Birth-Death Chains 5.4.1 The Pure Birth Chain 5.4.2 The Poisson Process Revisited 5.4.3 Steady State Analysis of Birth-Death Chains 5.5 Uniformzation of Continuous-Time Markov Chains

Chapter 6 Introduction to Queueing Theory
6.1 Introduction 6.2 Specification of Queueing Models 6.2.1 Stochastic Models for Arrival and Service Processes 6.2.2 Structural Parameters 6.2.3 Operating Policies 6.2.4 The A/B/m /K Notation 6.2.5 Open and Closed Queueing Systems 6.3 Performance of a Queuing System 6.4 Queueing System Dynamics 6.5 Little’s Law 6.6 Analysis of Simple Markovian Queueing Systems 6.6.1 The M/M/1 Queueing System 6.6.2 The M/M/m Queueing System 6.6.3 The M/M/ Queueing System 6.6.4 The M/M/1/K Queueing System 6.6.5 The M/M/m/m Queueing System 6.6.6 The M/M/1//N Queueing System 6.6.7 The M/M/m/K/N Queueing System 6.7 Markovian Queueing Networks 6.7.1 The Departure Process of the M/M/1 Queueing System 6.7.2 Open Queueing Networks 6.7.3 Closed Queueing Networks Computation of the Normalization Constant C(N) Mean Value Analysis 6.7.4 Product Form Networks 6.8 Non-Markovian Queueing Systems 6.8.1 The Method of Stages 6.8.2 Mean Value Analysis of the M/G/1 Queueing System 6.8.3 Software Tools for the Analysis of General Queueing Networks

Chapter 7 Controlled Markov Chains
7.1 Introduction 7.2 The Nature of “Control” in Markov Chains 7.3 Markov Decision Processes 7.3.1 Cost Criteria 7.3.2 Uniformization 7.3.3 The Basic Markov Decision Problem 7.4 Solving Markov Decision Problems 7.4.1 The Basic Idea of Dynamic Programming 7.4.2 Dynamic Programming and the Optimality Equation Convergence of the Dynamic Programming Algorithm The Optimality Equation 7.4.3 Extensions to Unbounded and Undiscounted Costs 7.4.4 Optimization of the Average Cost Criterion 7.5 Control of Queueing Systems 7.5.1 The Admission Problem 7.5.2 The Routing Problem 7.5.3 The Scheduling Problem

Chapter 8 Introduction to Discrete-Event Stimulation
8.1 Introduction 8.2 The Event Scheduling Simulation Scheme 8.2.1 Simulation of a Simple Queueing System 8.3 The Process-Oriented Simulation Scheme 8.4 Discrete-Event Simulation Languages 8.5 Discrete-Event Simulation Using the Siman Language 8.5.1 The MODEL File – Some Basic Block Functions 8.5.2 The MODEL File – Some Data Collection Block Functions 8.5.3 The EXPERIMENT File 8.5.4 More Elaborate Models 8.5.5 Common Mistakes 8.6 Random Number Generation 8.6.1 The Linear Congruential Technique 8.7 Random Variate Generation 8.7.1 The Inverse Transform Technique 8.7.2 The Convolution Technique 8.7.3 The Composition Technique 8.7.4 The Acceptance – Rejection Technique 8.8 Output Analysis 8.8.1 Simulation Characterizations 8.8.2 Parameter Estimation Point Estimation Interval Estimation 8.8.3 Output Analysis of Terminating Simulations 8.8.4 Output Analysis of Non-Terminating Simulations Replications with Deletions Batch Means Regenerative Simulation

Chapter 9 Sensitivity Analysis and Sample Path Constructability
9.1 Introduction 9.2 Sample Functions and Their Derivatives 9.2.1 Performance Sensitivities 9.2.2 The Uses of Sensitivity Information 9.3 Perturbation Analysis: Some Key Ideas 9.4 Perturbation Analysis of GI/G/1 Queueing Systems 9.4.1 Perturbation Generation Derivatives of Random Variated Scale and Location Parameters Parameters of Discrete Distributions 9.4.2 Perturbation Propagation Infinitesimal and Finite Perturbaton Analysis 9.4.3 Infinitesimal Perturbation Analysis (IPA) 9.4.4 Implementation of IPA for the GI/G/1 System 9.5 IPA for Stochastic Time Automata 9.5.1 Event Time Derivatives 9.5.2 Sample Function Derivatives 9.5.3 Performance Measure Derivatives The Commuting Condition Continuity of Sample Functions Unbiasedness of IPA Estimators 9.5.4 IPA Applications Sensitivity Analysis of Queueing Networks Performance Optimization 9.6 The Sensitivity Estimation Problem Revisited 9.7 Extensions of IPA 9.7.1 Discontinuities due to Multiple Customer Classes 9.7.2 Discontinuities due to Touting Decisions 9.7. Discontinuities due to Blocking: IPA with Event Rescheduling 9.8 Smoothed Perturbation Analysis (SPA) 9.8.1 Systems with Real-Time Constraints 9.8.2 Marking and Phantomizing Techniques 9.9 Perturbation Analysis for Finite Parameter Changes 9.10 Sample Path Constructability Techniques

Appendix 1: A Review of Probability Theory
Appendix 2: Discrete-Event Simulation Using the SIMAN Language
Appendix 3: Infinitesimal Perturbation Analysis (IPA) Estimators