CPS_lec.pdf

Lecture 1: Course Introduction and Logistics Amr Alanwar Technical University of Munich Credits and reference The content is based on extending/modifying the lecture material from UC Berkeley EECS 149 (Lee & Seshia) Slides from the Duckietown Team: Andrea Censi, Jacopo Tani, Liam Paull, Matt Walter Introduction to Embedded Systems — A Cyber-Physical Systems Approach 2 Instructors Amr Alanwar Ahmad Hafez Yiğit İlk Dias Altay [email protected] [email protected] [email protected] [email protected] 3 Cyber-Physical Systems (CPS): Transportation (Air traffic Integration of computation with physical processes, control at defined by their intersection Avionics SFO) Building Systems Telecommunications Automotive Instrumentation E-Corner, Siemens (Soleil Synchrotron) Factory automation Power Cyber generation and Physical distribution Daimler-Chrysler Military systems: Courtesy of Courtesy of Doug Schmidt General Electric Courtesy of Kuka Robotics Corp. Definition A cyber-physical system (CPS) is an integration of computation with physical processes whose behavior is defined by both cyber and physical parts of the system. 5 E Pluribus Unum: Out of Many, One Smarter Machine to Internet of Planet Machine Everything (M2M) Internet of Things The Fog (IoT) TSensors Industry 4.0 (Trillion The Industrial Sensors) Internet Cyber-Physical Systems Lee, Berkeley An Analogy x The challenges of working Small Computer in a multidisciplinary area x Connected Industrial System Network Big Complex System Advanced Manufacturing Robot Automotive CPS: Representative of Big Societal Challenges Smart Cities / Transportation Energy Efficiency Climate Change Human-Robot Collaboration A View of the Automotive Industry Trend ? [Jyo Deshmukh, Toyota] What this course is about A principled, scientific approach to designing and implementing embedded systems Not just hacking!! Hacking can be fun, but it can also be very painful when things go wrong… Focus on model-based system design, and on embedded software Modeling, Design, Analysis Modeling is the process of gaining a deeper understanding of a system through imitation. Models imitate the system and reflect properties of the system. Models express what a system does or should do Design is the structured creation of artifacts. It specifies how a system does what it does Analysis is the process of gaining a deeper understanding of a system through dissection. It specifies why a system does what it does (or fails to do what a model says it should do) Report: McKinsey Global Institute Disruptive technologies: Advances that will transform life, business, and the global economy … with major CPS components Tesla Gigafactory From: https://www.tesla.com/gigafactory Apple iCar https://www.youtube.com/watch?v=OHsDaxkfyVw However Apple Car" project has been canceled. Rumors speculated that it will be a fully- featured self-driving electric vehicle that will compete with Tesla and other EVs, but the margins weren't viable. Staff working on the project pivoted to artificial intelligence divisions. https://appleinsider.com/inside/apple-car 16 The Emerging IT Scene Infrastructural core The Cloud! Sensory swarm Mobile access Courtesy: J. Rabaey 17 Bell’s Law: A new computer class every decade “Roughly every decade a new, lower priced computer class forms based on a new programming platform, network, and interface resulting in new usage and the establishment of a new industry.” - Gordon Bell [1972,2008] 18 18 Number of computers/person grows over time Mainframe [Bell et al. Computer, 1 per Enterprise 1972, ACM, 2008] log (people per computer) Workstation 1 per Engineer Laptop 1 per Professional Smart Sensors Mini Ubiquitous Computer 1 per Company Personal Computer 100 – 1000’s per 1 per Family 1 per person person Smartphone 19 Computer volume shrinks by 100x every decade Mainframe 1 per Enterprise 100x smaller Workstation every decade 1 per Engineer [Nakagawa08] Laptop 1 per Professional Smart Sensors Mini Ubiquitous Computer 1 per Company Personal Computer 100 – 1000’s per 1 per Family 1 per person person Smartphone 20 Price falls dramatically, enabling new applications Mainframe Workstation Number Crunching Data Storage Laptop productivity interactive Mini Computer streaming Smart information Personal Sensors to/from the Computer physical Smartphone world 21 Motivating Example of a Cyber-Physical System (see Chapter 1 in book) Modeling: Flight dynamics (ch2) Modes of operation (ch3) Transitions between modes (ch4) Composition of behaviors (ch5) Multi-vehicle interaction (ch6) Design: Sensors and Actuators (ch7) Processors (ch8) Memory system (ch9) Sensor interfacing (ch10) Concurrent software (ch11) Real-time scheduling (ch12) Analysis STARMAC quadrotor aircraft (Tomlin, et al.) Specifying safe behavior (ch13) Achieving safe behavior (ch14) Verifying safe behavior (ch15) Guaranteeing timeliness (ch16) Security and privacy (ch17) STARMAC http://www.youtube.com/watch?v=rJ9r2orcaYo 23 STARMAC Aerobatics http://www.youtube.com/watch?v=iD3QgGpzzIM 24 STARMAC Design Block Diagram LIDAR RS232 URG-04LX 115 kbps 10 Hz ranges PC/104 WiFi USB 2 Pentium M 802.11g Stereo Cam Firewire 1GB RAM, 1.8GHz 480 Mbps + ≤ 54 Mbps Videre STOC 480 Mbps RS232 Est. & control 30 fps 320x240 GPS UART Superstar II 19.2 kbps Stargate 1.0 10 Hz CF WiFi Intel PXA255 802.11b UART 64MB RAM, 400MHz 100 Mbps ≤ 5 Mbps IMU 115 Kbps UART UART Supervisor, GPS 3DMG-X1 76 or 100 Hz 115 kbps Robostix Atmega128 Low level control Ranger I2 C PPM SRF08 400 kbps 100 Hz 13 Hz Altitude Analog Ranger Beacon Mini-AE ESC & Motors Timing/ Tracker/DTS Phoenix-25, Axi 2208/26 10-50 Hz Altitude 1 Hz Analog A Theme in This Course: Think Critically Any course that purports to teach you how to design embedded systems is misleading you. The technology will change! Our goal is to teach you how things are done today, and why that is not good enough. So you will not be surprised by the changes that are coming. Full of Contradictory Requirements in CPS It’s not just information technology anymore: Biomedical Cyber + Physical Computation + Dynamics Energy Security + Safety Contradictions: Adaptability vs. Repeatability Automotive Avionics High connectivity vs. Security and Privacy High performance vs. Low Energy Military Asynchrony vs. Coordination/Cooperation Scalability vs. Reliability and Predictability Laws and Regulations vs. Technical Possibilities Economies of scale (cloud) vs. Locality (fog) Open vs. Proprietary Buildings Algorithms vs. Dynamics Innovation: Cyber-physical systems require new engineering Manufacturing methods and models to address these contradictions. Lee, Berkeley Your textbook strives to identify and introduce the durable intellectual ideas of embedded systems as a technology and as a subject of study. The emphasis is on modeling, design, and analysis of cyber- physical systems, which integrate computing, networking, and physical processes. http://LeeSeshia.org/ Book Map The three threads are designed to be read concurrently and fit nicely within a 14-week semester. Weekly Schedule Exercises Distribution: Every Tuesday at 16:00, a sheet with exercises will be handed out on Moodle/selected problems from the reference Submission Deadline: Solutions to the exercises can be submitted on Moodle by the following Tuesday at 16:00 Tutorials: Tutorials are scheduled for Wednesdays from 12:15 to 13:45 Upcoming Tutorial: The first tutorial will be held on the third week of lectures Plagiarism Policy: Plagiarism is strictly prohibited and might result in expulsion from the course 30 Grades 40% final exam 40% project 20% assignments 31 Course Project A VERY important component of the course Project teams are self-organized. Project topics are self-selected Be careful, many proposals are HARD to achieve in the time allotted. Requires good project management 5-6 students per group Berkeley Previous Projects Biomimemics Face Tracking Autonomous Flight Distributed Music Robot Train Robot Swarm Example Project: May 16, 2008 One of the five project teams in 2008 developed a balancing robot inspired by the Segway. They used a Nintendo Wiimote as a controller communicating with a PC running LabVIEW, communicating with a Lego Mindstorm NXT, which they programmed in C. Project Guidelines You may use resources you find online You must give full attribution to your sources You must go beyond what you find online You must use concepts from the course Modeling Design Analysis A hack that works is not enough! Start forming your teams now!! Some available hardware Rplidar with a jet racer Less than 2 inches LCD Controller Adeept car 36 37 3 8 The first edition at MIT 3 9 History Duckietown today 4 2 AI Driving Olympics Competition It is series of embodied intelligence competitions in the field of autonomous vehicles 4 3 4 4 Platform: Duckiebots 4 5 Platform: Duckietowns 4 6 Simulator Self-driving car simulator environments https://github.com/duckietown/gym-duckietown Duckiebook Online book ("The Duckiebook”): https://docs.duckietown.org/daffy/ 4 9 The Five Levels of Autonomy Level 0: the human driver does everything Level 1: an automated system on the vehicle can sometimes assist the human driver conduct some parts of the driving task Level 2: an automated system on the vehicle can conduct some parts of the driving task, while the human continues to monitor the driving environment and performs the rest of the driving task Level 3: an automated system can both actually conduct some parts of the driving task and monitor the driving environment in some instances, but the human driver must be ready to take back control when the automated system requests Level 4: an automated system can conduct the driving task and monitor the driving environment, and the human need not take back control, but the automated system can operate only in certain environments and under certain conditions Level 5: the automated system can perform all driving tasks, under all conditions that a human driver could perform them 5 0 Level 2 51 What Level of Automation is Tesla Autopilot? 52 Why level 4 AVs? Two Paths to Level 4+ Courtesy Emilio Frazzoli 54 Hasn’t Deep Learning Solved all of this? 55 https://arxiv.org/abs/1604.07316 Hasn’t Deep Reinforcement Learning Solved all of this? https://arxiv.org/abs/1807.00412 56 Deep Learning is Great But… It is very unlikely (read: not going to happen) that it is going to be able to solve the entire driving task end-to-end The part of the problem that has been solved so far end-to-end is actually very easy - it was solved 25 years ago. 57 Data Collection - Corner Cases 58 The Role of Simulation 59 60 Continuous Dynamics Amr Alanwar Technical University of Munich Credits and reference The content is based on extending/modifying the lecture material from UC Berkeley EECS 149 (Lee & Seshia) Chapter 2 - Introduction to Embedded Systems — A Cyber-Physical Systems Approach 2 Choose Your Group https://www.moodle.tum.de 3 Modeling, Design, Analysis: An Iterative Process Modeling is the process of gaining a deeper understanding of a system through imitation. Models imitate the system and reflect properties of the system. Models express what a system does or should do. Design is the structured creation of artifacts. It specifies how a system does what it does. Analysis is the process of gaining a deeper understanding of a system through dissection. It specifies why a system does what it does (or fails to do what a model says it should do). Models vs. Reality Solomon Golomb: Mathematical models – Uses and limitations. Aeronautical Journal 1968 You will never strike oil by drilling through the map! Solomon Wolf Golomb (1932) mathematician and engineer and a professor of electrical engineering at the University of Southern California. Best known to the general public and fans of mathematical games as the inventor of polyominoes, the inspiration for the computer game Tetris. He has specialized in problems of combinatorial analysis, number theory, coding theory and communications. But this does not, in any way, diminish the value of a map! Our Approach in this Course Mathematical Models are Central to the Design Process Create models and use them judiciously! But there is no unique approach to Model-Based Design (at least today). Some Industrial Model-Based Design Tools Matlab/Simulink National Instruments LabVIEW StateCharts (offered by multiple vendors) … Several Academic Tools: Berkeley’s Ptolemy II Modeling Techniques in this Course Models that are abstractions of system dynamics (how system behavior changes over time) Examples: Modeling physical phenomena – differential equations Feedback control systems – time-domain modeling Modeling modal behavior – FSMs, hybrid automata, … Modeling sensors and actuators – models that help with calibration, noise elimination, … Modeling hardware and software – capture concurrency, timing, power, … Modeling networks – latencies, error rates, packet loss, … Today’s Lecture: Modeling of Continuous Dynamics Ordinary differential equations, Laplace transforms, feedback control models, … An Example: Modeling Helicopter Dynamics Modeling Physical Motion Six degrees of freedom: Position: x, y, z Orientation: Pitch: rotation around the z axis Yaw: rotation around the y axis Roll: rotation around the x axis Notation Position is given by three functions: 𝑥: ℝ → ℝ 𝑦: ℝ → ℝ 𝑧: ℝ → ℝ where the domain ℝ represents time and the co-domain (range) ℝ represents position along the axis. Collecting into a vector: x: ℝ → ℝ3 Position at time 𝑡 ∈ ℝ is 𝐱(𝑡) ∈ ℝ3 Notation Velocity xǗ : ℝ → ℝ3 is the derivative, ∀𝑡 ∈ ℝ, 𝑑 Ǘ 𝐱(𝑡) = 𝐱(𝑡) 𝑑𝑡 Acceleration xǃ : ℝ → ℝ3 is the second derivative, 𝑑2 𝐱ǃ = 2 𝐱 𝑑𝑡 Force on an object is 𝐅: ℝ → ℝ3 Newton’s Second Law Newton’s Second Law: F: force vector M: mass of the object Velocity is the integral of acceleration Using Newton’s Second Law Position is the integral of velocity 15 Orientation Orientation: 𝜃: ℝ → ℝ3 Ǘ ℝ → ℝ3 Angular velocity: 𝜃: ǃ ℝ → ℝ3 Angular acceleration: 𝜃: Torque: 𝐓: ℝ → ℝ3 Rotational Version of Newton’s Second Law 𝑑 Ǘ 𝐓(𝑡) = (𝐼(𝑡)𝜃(𝑡)) 𝑑𝑡 where 𝐼(𝑡) is a 3 × 3 matrix called the moment of inertia tensor 𝑇𝑥 (𝑡) 𝐼𝑥𝑥 (𝑡) 𝐼𝑥𝑦 (𝑡) 𝐼𝑥𝑧 (𝑡) 𝜃Ǘ𝑥 (𝑡) 𝑑 𝑇𝑦 (𝑡) = 𝐼𝑦𝑥 (𝑡) 𝐼𝑦𝑦 (𝑡) 𝐼𝑦𝑧 (𝑡) 𝜃Ǘ𝑦 (𝑡) 𝑑𝑡 𝑇𝑧 (𝑡) 𝐼𝑧𝑥 (𝑡) 𝐼𝑧𝑦 (𝑡) 𝐼𝑧𝑧 (𝑡) 𝜃Ǘ𝑧 (𝑡) Here, 𝑇𝑦 (𝑡) is the net torque around the 𝑦 axis (which would cause changes in yaw), 𝐼𝑦𝑥 (𝑡) is the inertia that determines how acceleration around the 𝑥 axis is related to torque around the 𝑦 axis Intuitively, the moment of inertia tensor represents the reluctance that an object has to spin around any axis as a function of its orientation along the three axes Rotational Version of Newton’s Second Law If we have constant moment of inertia tensor. More specifically, If the object is spherical, for example, this reluctance is the same around all axes, so the moment of inertia tensor reduces to a constant scalar 𝐼 (or equivalently, to a diagonal matrix I with equal diagonal elements 𝐼) ǃ 𝐓(𝑡) = 𝐼 𝜃(𝑡) 𝑡 Rotational velocity is the integral of acceleration 𝜃(𝑡) Ǘ Ǘ = 𝜃(0) ǃ + ∫0 𝜃(𝜏)𝑑𝜏 1 𝑡 If we have constant moment of inertia tensor 𝜃(𝑡) = 𝜃(0) + ∫0 𝐓(𝜏)𝑑𝜏 Ǘ Ǘ 𝐼 Orientation is the integral of rotational velocity 𝑡 𝜃(𝑡) = 𝜃(0) + Ǘ ∫0 𝜃(𝜏)𝑑𝜏 1 𝑡 𝜏 Ǘ = 𝜃(0) + 𝑡𝜃(0) + ∫0 ∫0 𝐓(𝛼)𝑑𝛼𝑑𝜏 𝐼 18 Feedback Control Problem A helicopter without a tail rotor, like the one below, will spin uncontrollably due to the torque induced by friction in the rotor shaft Control system problem: Apply torque using the tail rotor to counterbalance the torque of the top rotor Simplified Model A model of a physical system is found by a differential or an integral equation that relates input signals (force or torque) to output signals (position, orientation, velocity, or rotational velocity) Fix coordinate system to the helicopter Assume it stays vertical (no pitch/roll) Yaw dynamics: 𝑇𝑦 (𝑡) = 𝐼𝑦𝑦 𝜃ǃ𝑦 (𝑡) To account for initial angular velocity, write as 1 𝑡 𝜃Ǘ𝑦 (𝑡) = 𝜃Ǘ𝑦 (0) + න 𝑇𝑦 (𝜏)𝑑𝜏 𝐼𝑦𝑦 0 Simplified model of a helicopter These assumptions are not as unrealistic as they may seem since we can define the coordinate system to be fixed to the helicopter. Actor Models A continuous-time system (one that operates on continuous-time signals) may be modeled by a box with an input port and an output port as follows: where the input signal x and the output signal y are functions of the form Here the domain represents the time, and the codomain represents the value of the signal at a particular time 21 Actor Models (cont.) The model of the system is a function of the form The function S may depend on parameters of the system, in which case the parameters may be optionally shown in the box, and may be optionally included in the function notation A box like that bellow, where the inputs are functions and the outputs are functions, is called an actor 22 Actor Model of the Helicopter Input is the net torque of the tail rotor and the top rotor Output is the angular velocity around the y axis Parameters of the model are shown in the box. The input and output relation is given by the equation to the right Cascade Composition Actor models are composable. Given two actors S1 and S2, we can form a cascade composition as follows 24 Question Can you represent the Helicopter actor in a cascade composition? 25 Composition of Actor Model The actor model for the helicopter can be represented as a cascade composition of two actors as follows 26 Actor Models with Multiple Inputs We can have actors that have multiple input signals and/or multiple output signals A particularly useful building block with this form is a signal adder Properties of Systems We consider several properties that actors and the systems they compose may have, including Causality Memorylessness Linearity time invariance, and Stability 28 Causal Systems A system is causal if its output depends only on current and past inputs but not future inputs 29 Memoryless Systems A memoryless system does not have memory to store any input values because it just operates on the current input A system has memory if the output depends not only on the current inputs, but also on past inputs (or future inputs, if the system is not causal) Consider a continuous time system 𝑆: 𝑋 → 𝑌 where 𝑋 = 𝐴ℝ (equivalent to X=ℝ → 𝐴 )and 𝑌 = 𝐵ℝ (equivalent to Y=ℝ → 𝐵 ) for some sets 𝐴 and 𝐵 A system is memoryless if there exists a function 𝑓: 𝐴 → 𝐵 such that for all 𝑥 ∈ 𝑋, (𝑆(𝑥))(𝑡) = 𝑓(𝑥(𝑡)) for all 𝑡 ∈ ℝ That is, the output (𝑆(𝑥))(𝑡) at time 𝑡 depends only on the input 𝑥(𝑡) at time 𝑡 30 Questions Is The Integrator considered before memoryless? Is the adder considered memoryless? The Integrator is not memoryless, but the adder is 31 Linear Systems A system , where X and Y are sets of signals, is linear if it satisfies the superposition property: 32 Question Is the helicopter system linear? The helicopter system is linear if and only if the initial angular velocity 33 Question Is the cascade of any two linear actors linear? Yes 34 Time Invariance A time-invariant system is one whose behavior (its response to inputs) does not change with time We first define a specialized continuous-time actor called a delay Let , where X and Y are sets of continuous-time signals, be defined by where is a parameter of the delay actor A system is time invariant if 35 https://www.youtube.com/watch?app=desktop&v=LezLNMznZm4 36 https://www.youtube.com/watch?app=desktop&v=LezLNMznZm4 37 Is the helicopter system time invariant? the helicopter system is not time invariant. A minor change, however, makes it time invariant: 38 Stability A system is said to be bounded-input bounded-output stable (BIBO stable or just stable) if the output signal is bounded for all input signals that are bounded Is the helicopter system stable? The helicopter system is unstable because if we apply a unit step (bounded input) starting from t=0, the output grows without bound In practice, a helicopter uses a feedback system to determine how much torque to apply at the tail rotor to keep the body of the helicopter straight We study how to do that next 39 “Plant” and Controller Plant Control Input State Controller Proportional controller desired error net angular signal torque velocity We make measurements of an error, which is a discrepancy between desired behavior and actual behavior, and use that measurement to correct the behavior Behavior of the controller Desired angular velocity: Simplifies differential equation to: Which can be solved as follows (see textbook): 43 Discrete Dynamics Amr Alanwar Technical University of Munich Credits and reference The content is based on extending/modifying the lecture material from UC Berkeley EECS 149 (Lee & Seshia) Chapter 3 - Introduction to Embedded Systems — A Cyber-Physical Systems Approach 2 Choose and start working on your project! 3 Discrete Systems Discrete = “individually separate / distinct” A discrete system is one that operates in a sequence of discrete steps or has signals taking discrete values It is said to have discrete dynamics Concepts covered in Today’s Lecture Illustrative Example of Discrete Dynamics Actor Models of Discrete Systems: Types and Interfaces States, Transitions, Guards Determinism and Receptiveness Discrete Systems: Example Design Problem Count the number of cars that are present in a parking garage by sensing cars entering and leaving the garage. Show this count on a display Discrete Systems Example: count the number of cars in a parking garage by sensing those that enter and leave The ArrivalDetector actor produces an event when a car arrives The DepartureDetector actor produces an event when a car departs The Counter actor keeps a running count, starting from an initial value i. Each time the count changes, it produces an output event that updates a display Discrete Systems Example: count the number of cars that enter and leave a parking garage Pure signal: up ∶ ℝ → { absent,present } This means that at any time t, the input up is either absent, meaning that there is no event at that time, or present, meaning that there is A signal of this form is known as a pure signal. It carries no value, but instead provides all its information by being either present or absent at any given time Discrete Systems Example: count the number of cars that enter and leave a parking garage: Signal count: ℝ → {absent } ∪ ℤ ℤ is the integers Is count a pure signal? This signal is not pure, but like up and down, it is either absent or present. Unlike up and down, when it is present, it has a value (an integer) When an event is present at the up input port, it increments its count and produces on the output the new value of the count. When an event is present at the down input, it decrements its count and produces on the output the new value of the count. At all other times (when both inputs are absent), it produces no output (the count output is absent) Integrator A function is written 𝑓: 𝐴 → 𝐵 and the set A is called its domain and the set B its codomain The set of all functions 𝑓: 𝐴 → 𝐵 is written (𝐴 → 𝐵) or 𝐵 𝐴 The input of an Integrator is a function of the form 𝑥: ℝ → ℝ or 𝑥: ℝ+ → ℝ a continuous-time signal The Integrator actor can be modeled by a function of the form 𝐼𝑖 : ℝℝ+ → ℝℝ+ which can also be written 𝐼𝑖 : ℝ+ → ℝ → ℝ+ → ℝ 10 Notation A cartesian product of sets A and B is a set written 𝐴 × 𝐵 and defined as follows 𝐴 × 𝐵 = {(𝑎, 𝑏): 𝑎 ∈ 𝐴, 𝑏 ∈ 𝐵} A member of this set 𝑎, 𝑏 is called a tuple We define the following sets 𝔹 = {0,1}, the set of binary digits ℕ = {0,1,2, ⋯ }, the set of natural numbers ℤ = {⋯ , −1,0,1,2, ⋯ }, the set of integers ℝ, the set of real numbers ℝ+ , the set of non-negative real numbers The powerset 2𝐴 of a set A is defined to be the set of all subsets 11 Discrete Systems If the signal is present at all rational numbers t, then we do not call this signal discrete Reaction / Transition Reactions: The dynamics of a discrete system can be described as a sequence of steps that we call reactions, each of which we assume to be instantaneous State: condition of the system at a particular point in time. It Encodes everything about the past that influences the system’s reaction to current input State Space A practical parking garage has a finite number 𝑀 of spaces, so the state space for the counter is States = {0,1,2, ⋯ , 𝑀} What are the scenarios in which the given parking garage (interface) design does not handle well? Counter saturates at M: cannot tell if there are more cars inside looking for spots. State machine A state machine is a model of a system with discrete dynamics that at each reaction maps valuations of the inputs to valuations of the outputs, where the map may depend on its current state A finite-state machine (FSM) is a state machine where the set States of possible states is finite Transitions between states govern the discrete dynamics of the state machine and the mapping of input valuations to output valuations A transition may also start and end at the same state. In this case, the transition is called a self transition 15 FSM Notation The guard determines whether the transition may be taken on a reaction A guard is a predicate (a boolean-valued expression) that evaluates to true when the transition should be taken, changing the state from that at the beginning of the transition to that at the end. When a guard evaluates to true we say that the transition is enabled The action specifies what outputs are state produced on each reaction initial state An action is an assignment of values (or transition absent) to the output ports. Any output port not mentioned in a transition that is taken is implicitly absent. If no action at all is given, then all outputs are implicitly absent self loop Garage Counter Finite State Machine (FSM) in Pictures The transition from state 0 to 1 has a guard written as up ∧ ¬ down. This is a predicate that evaluates to true when up is present and down is absent. The output port count is not explicitly named because there is only one output port, and hence there is no ambiguity Examples of Guards for Pure Signals If 𝑝1 and 𝑝2 are pure inputs to a discrete system, then the following are examples of valid guards: These are standard logical operators where present is taken as a synonym for true and absent as a synonym for false. The symbol represents logical negation. The operator ^ is logical conjunction (logical AND), and is logical disjunction (logical OR) Third input port Suppose that in addition the discrete system has a third input port 𝑝3 with type. Then the following are examples of valid guards Then the following are examples of valid guards: 19 Thermostat 20 Multiple outputs If 𝑞1 and 𝑞2 are pure outputs and 𝑞3 has type , then the following are examples of valid actions Any output port that is not mentioned in a transition that is taken is implicitly absent When assigning a value to an output port, we use the notation name := value to distinguish the assignment from a predicate, which would be written name = value 21 When does a reaction occur? Suppose all inputs are discrete and a reaction occurs when any input is present. Then the above transition will be taken whenever the current state is s1 and x is present. This is an event-triggered model When does a reaction occur? Suppose x and y are discrete and pure signals. When does the transition occur? When the environment triggers a reaction and x is absent When does a reaction occur? Suppose all inputs are discrete and a reaction occurs on the tick of an external clock. This is a time-triggered model. Some Definitions Stuttering transition: (possibly implicit) default transition that is enabled when inputs are absent, that does not change state, and that produces absent outputs. No progress is made and nothing changes. If the input is absent and no guard on any transition out of the current state evaluates to true, then the machine will stutter Receptiveness: A state machine is said to be receptive if, for each state, there is at least one transition possible on each input symbol. For any input values, some transition is enabled. This structure together with the implicit default transition ensures that our FSMs are receptive. In other words, receptiveness ensures that a state machine is always ready to react to any input, and does not “get stuck” in any state Determinism: In every state, for all input values, exactly one (possibly implicit) transition is enabled Stuttering If on any reaction both inputs are absent, then the machine will stutter If we are in state 0 and the input down is present, then the guard on the only outgoing transition is false, and the machine remains in the same state. Do you consider this Stuttering? We do not call this a stuttering reaction because the inputs are not all absent. 26 More Notation: Default Transitions A default transition is enabled if no non-default transition is enabled and it either has no guard or the guard evaluates to true. When is the above default transition enabled? The default transition is enabled if (up ∧ ¬ down) evaluates to false. When the default transition is taken, the output is absent Example where default transitions need not to be shown Example: Traffic Light Controller Only show default transitions if they are guarded or produce outputs (or go to other states) 30 Discrete Dynamics (Cont.) Amr Alanwar Technical University of Munich Credits and reference The content is based on extending/modifying the lecture material from UC Berkeley EECS 149 (Lee & Seshia) Introduction to Embedded Systems — A Cyber-Physical Systems Approach 2 Bonus Questions There will be questions with bonus grades during the lecture 3 Finite-state Machine Notation A finite-state machine is a five-tuple (States; Inputs; Outputs; update; initialState) States is a finite set of states Inputs is a set of input valuations Outputs is a set of output valuations update : States × Inputs → States × Outputs is an update function, mapping a state and an input valuation to a next state and an output valuation initialState is the initial state 4 Finite-State Machine Notation The FSM reacts in a sequence of reactions The dynamics of the state machine are given by the following equation (𝑠(𝑛 + 1), 𝑦(𝑛)) = update(𝑠(𝑛), 𝑥(𝑛)) State 𝑠: ℕ → States be a function that gives the state of an FSM at reaction 𝑛 ∈ ℕ. Initially, 𝑠(0) = initialState 𝑥: ℕ → Inputs, input valuations at each reaction 𝑦: ℕ → Outputs, output valuations at each reaction The update function encodes all the transitions, guards, and output specifications in an FSM. The term transition function is often used in place of update function 5 Inputs The input and output valuations also have a natural mathematical form. Suppose an FSM has input ports 𝑃 = 𝑝1 , ⋯ , 𝑝𝑁 , where each 𝑝 ∈ 𝑃 has a corresponding type 𝑉𝑝 Inputs is a set of functions of the form 𝑖: 𝑃 → 𝑉𝑝1 ∪ ⋯ ∪ 𝑉𝑝𝑁 ∪ { absent }, where for each 𝑝 ∈ 𝑃, 𝑖(𝑝) ∈ 𝑉𝑝 ∪ {𝑎𝑏𝑠𝑒𝑛𝑡} gives the value of port 𝑝. Thus, a function 𝑖 ∈ Inputs is a valuation of the input ports 6 Garage Counter The FSM can be mathematically represented as 7 Mealy and Moore machines Mealy machines are characterized by producing outputs when a transition is taken The state machines we describe in this chapter are known as Mealy machines Moore machine produces outputs when the machine is in a state, rather than when a transition is taken. That is, the output is defined by the current state rather than by the current transition 8 Bonus Question 1: What is the Moore machine for Car Garage? Bonus question 2: Is it equivalent to the Mealy machine? This machine is not equivalent to the Mealy machine 9 Extended State Machine The notation for FSMs becomes awkward when the number of states gets large An extended state machine solves this problem by augmenting the FSM model with variables that may be read and written as part of taking a transition between states A variable is not an input or an output M is a parameter 10 Extended State Machine Notations 11 Extended State Machine vs FSM Variable declarations are shown explicitly to make it easy to determine whether an identifier in a guard or action refers to a variable or to an input or an output Upon initialization, variables that have been declared may be initialized The initial value will be shown on the transition that indicates the initial state Transition annotations now have the form The guard and output action are the same as for standard FSMs, except they may now refer to variables set actions specify assignments to variables that are made when the transition is taken. These assignments are made after the guard has been evaluated and the outputs have been produced 12 Assignments order Bonus question 3: Is the output available first, or is the counter incremented first? If the guard or output actions reference a variable, the value of the variable (c+1) is out before the assignment in the set action (c=c+1) If there is more than one set action, then the assignments are made in sequence 13 Traffic Light Controller This is a time triggered machine that assumes it will react once per second. It starts in the red state and counts 60 seconds with the help of the variable count 14 State Space Size Bonus question 4: If there are n discrete states (bubbles) and m variables each of which can have one of p possible values, then the size of the state space of the state machine is 15 Nondeterminism If for any state of a state machine, there are two distinct transitions with guards that can evaluate to true in the same reaction, then the state machine is nondeterministic It is also possible to define state machines where there is more than one initial state. Such a state machine is also nondeterministic Nondeterministic model of pedestrians that arrive at a crosswalk 16 Formal Model of the Nondeterministic FSM A nondeterministic FSM is represented as a five-tuple, similar to a deterministic FSM 17 Formal Model of the Nondeterministic FSM (cont.) The codomain of a function is the set of its possible outputs The form of the function possibleUpdates indicates there can be more than one next state and/or output valuation given a current state and input valuation. The codomain is the powerset of States × Outputs What is the powerset? The powerset 2𝐴 of a set A is defined to be the set of all subsets We refer to the possibleUpdates function as an update relation, to emphasize this difference. The term transition relation is also often used in place of update relation To support the fact that there can be more than one initial state for a nondeterministic FSM, initialStates is a set rather than a single element of States 18 FSM example States = { none , waiting , crossing } Inputs = ({sig 𝐺, sig 𝑌, sig 𝑅} → { present , absent }) Outputs = ({ pedestrian } → { present , absent }) initialStates = { crossing } The update relation none , absent if 𝑠 = crossing ∧ 𝑖( sigG ) = present none, absent , waiting, present if 𝑠 = none possibleUpdates (𝑠, 𝑖) = crossing, absent if 𝑠 = waiting ∧ 𝑖( sigR ) = present {(𝑠, absent )} otherwise for all 𝑠 ∈ States and 𝑖 ∈ Inputs. Note that an output valuation 𝑜 ∈ Outputs is a function of the form 𝑜: { pedestrian } → { present,absent }. The second alternative gives two possible outcomes, reflecting the nondeterminism of the machine. Remember 𝑠 𝑛 + 1 , 𝑦 𝑛 = possibleUpdate(𝑠(𝑛), 𝑥(𝑛)) 19 Uses of Nondeterminism 1. Modeling unknown aspects of the environment or system Such as: how the environment changes a robot’s orientation 2. Hiding detail in a specification of the system Behaviors and Traces Consider a port p of a state machine with type 𝑉𝑝. This port will have a sequence of values from the set 𝑉𝑝 ∪ {𝑎𝑏𝑠𝑒𝑛𝑡} We can represent this sequence as a function of the form 𝑠𝑝 : ℕ → 𝑉𝑝 ∪ {𝑎𝑏𝑠𝑒𝑛𝑡} A behavior of a state machine is an assignment of such a signal to each port such that the signal on any output port is the output sequence produced for the given input signals 21 Example The garage counter has input port set 𝑃 = {𝑢𝑝, down}, with types 𝑉𝑢𝑝 = 𝑉down = { present}, and output port set 𝑄 = {count} with type 𝑉count = {0, ⋯ , 𝑀}. An example of input sequences is 𝑠up = ( present, absent, present, absent, present , ⋯ ) 𝑠down = ( present , absent , absent , present, absent, , ⋯ ) The corresponding output sequence is 𝑠count = ( absent , absent , 1,0,1, ⋯ ). These three signals 𝑠𝑢𝑝 , 𝑠𝑑𝑜𝑤𝑛 , and 𝑠count together are a behavior of the state machine. If we let ′ 𝑠count = (1,2,3,4,5, ⋯ ), ′ ′ then 𝑠up , 𝑠down , and 𝑠count together are not a behavior of the state machine. The signal 𝑠count is not produced by reactions to those inputs 22 Language and Traces The set of all behaviors of a state machine M is called its language, written L(M) Let 𝑥i represent the valuation of the input ports and 𝑦i the valuation of the output ports at reaction 𝑖 Then an observable trace is a sequence 𝑥0 , 𝑦0 , 𝑥1 , 𝑦1 , 𝑥2 , 𝑦2 , ⋯ An execution trace includes the state trajectory 𝑥0 , 𝑠0 , 𝑦0 , 𝑥1 , 𝑠1 , 𝑦1 , 𝑥2 , 𝑠2 , 𝑦2 , ⋯ Where 𝑠0 = initialState This can be represented a bit more graphically as follows 23 Example Can you give an example to execution trace for the garage counter? : means that up is present, down is absent, and count has value 1 24 Computation tree A computation tree is a graphical representation of all possible traces FSMs are suitable for formal analysis. For example, safety analysis might show that some unsafe state is not reachable Non-deterministic Behavior: Computations Tree Nodes in the tree are states and edges are labeled by the input and output valuations For a fixed input sequence: A deterministic system exhibits a single behavior A non-deterministic system exhibits a set of behaviors visualized as a computation tree Deterministic... FSM behavior:... Non- deterministic... FSM behavior:...... Can you state the computation tree? Nondeterministic FSM specifying order of signal lights, but not their timing. Notice that it ignores the pedestrian input. 27 Answer Nodes in the tree are states and edges are labeled by the input and output valuations. The notation true means any input valuation A computation tree 28 Non-deterministic  Probabilistic (Stochastic) In a probabilistic FSM, each transition has an associated probability with which it is taken In a non-deterministic FSM, no such probability is known. We just know that any of the enabled transitions from a state can be taken 30 Chapter 4: Hybrid Systems Amr Alanwar Technical University of Munich Credits and reference The content is based on extending/modifying the lecture material from UC Berkeley EECS 149 (Lee & Seshia) Chapter 4 - Introduction to Embedded Systems — A Cyber-Physical Systems Approach 2 Recap Finite state machine: It consists of some states and transitions to model a discrete behavior Differential equations: It can be used to model a continuous behavior Button pressed Light on Light off Button pressed 3 Recall FSM Notation state initial state transition self loop Garage Counter Example Recall this example, which counts cars in a parking garage: Extended State Machines Extended state machines augment the FSM model with variables that may be read or written. E.g.: General Notation for Extended State Machines We make explicit declarations of variables, inputs, and outputs to help distinguish the three Extended state machine model of a traffic light controller at a pedestrian crossing: This model assumes one reaction per second (a time-triggered model) Hybrid Systems Hybrid systems are systems with mixed discrete and continuous behaviors Heating on Heating off Source: gricad-media Source: istockphoto 9 Source: inc.com How to model hybrid systems? Heating on Heating off 10 Continuous Behavior What about adding continuous behavior to the state machine? Each mode has a discrete variable and a differential equation of a continuous state Heating on Heating off 11 Guard Conditions The condition that triggers the transition is called the guard condition Heating on Heating off 12 Hybrid Automaton It is a formal model that combines a discrete finite state automaton with continuously evolving variables It has: Discrete variable and continuous state continuous flow Discrete transitions, according to the guards 13 Bonus Question: Draw a sample Trajectory? Target obstacle robot position obstacle position 14 Obstacle Avoidance Target obstacle robot position obstacle position 15 Obstacle Avoidance - Demo robot position obstacle position 16 Livelock It occurs when the system switches infinitely between discrete states and no time passes in between discrete transitions Solution: add /Heating off / Heating on 17 Where do Hybrid Systems arise? Digital controller of physical “plant” thermostat intelligent cruise/powertrain control in cars aircraft auto pilot Phased operation of natural phenomena bouncing ball biological cell growth Multi-agent systems ground and air transportation systems interacting robots Modal Model In a hybrid system, the current state of the state machine has a state refinement that gives the dynamic behavior of the output as a function of the input A hybrid system is sometimes called a modal model because it has a finite number of modes, one for each state of the FSM, and when it is in a mode, it has dynamics specified by the state refinement The states of the FSM may be referred to as modes rather than states 19 Timed Automata (Wiki) A timed automaton is a finite automaton extended with a finite set of real- valued clocks During a run of a timed automaton, clock values increase all with the same speed. Along the transitions of the automaton, clock values can be compared to integers 20 Timed Automata (cont.) They are modal models where the time-based refinements have very simple dynamics; all they do is measure the passage of time A clock is modeled by a first-order differential equation ∀𝑡 ∈ 𝑇𝑚 , 𝑠Ǘ 𝑡 = 𝑎 Where s(t) is the value of the clock at time t 𝑇𝑚 ⊂ ℝ is the subset of time during which the hybrid system is in mode m a is a constant rate of the clock while the system is in this mode 21 An alternative to FSMs that is explicit about the passage of time: Timed automata, a special case of hybrid systems Thermostat - Timed Automaton The input is a continuous-time signal 𝜏: ℝ → ℝ where 𝜏(𝑡) represents the temperature at time 𝑡 Each state refinement has a clock, which is a continuous time signal s with dynamics given by 𝑠(𝑡) Ǘ =1 The value s(t) increases linearly with t The other two transitions each have set actions that reset the clock s to zero The portion of the guard that specifies 𝑠(𝑡) ≥ 𝑇ℎ ensures that the heater will always be on for at least time 𝑇ℎ and similarly for cooling 23 Bonus Question Can you plot 𝜏 𝑡 , s(𝑡), and h 𝑡 as an example? 24 Thermostat - Timed Automaton (cont.) We call s a continuous state variable, whereas heating and cooling are discrete states. Draw the response given the input temperature 25 Thermostat - Timed Automaton (cont.) Bonus question: What is the state of the system in this example? The state of the system at any time t is not only the mode, heating or cooling, but also the current value s(t) of the clock We call s a continuous state variable, whereas heating and cooling are discrete states When there is any possibility of confusion, we explicitly refer to the states of the FSM as modes 26 27 Chapter 4: Hybrid Systems (cont.) Amr Alanwar Technical University of Munich Credits and reference The content is based on extending/modifying the lecture material from UC Berkeley EECS 149 (Lee & Seshia) Chapter 4 - Introduction to Embedded Systems — A Cyber-Physical Systems Approach 2 Timer ticks The timed automaton in the figure produces a pure output that will be present every 𝑇 time units, starting at the time when the system begins executing Notice that the guard on the transition, 𝑠(𝑡) ≥ 𝑇, is followed by an output action, 𝑡𝑖𝑐𝑘, and a set action, 𝑠(𝑡): = 0 3 Remember the traffic light Extended State Machine Bonus questions: Show a timed automaton with same behavior? 4 A Timed Automaton Variant of the Traffic Light Controller 5 Momentum https://youtu.be/IrcN3yxzuhI?si=abFD2erRsjHer8c7 6 Round Masses with Springs The springs are compressed or extended and then released. If they collide, they stick together and oscillate together. After some time, the stickiness decays, and the masses pull apart again. The masses oscillate on a frictionless table Let 𝑝1 and 𝑝2 denote the neutral positions of the two masses, i.e., when the springs are neither extended nor compressed, so the force is zero Using Newton’s second law: 𝑦ǃ1 (𝑡) = 𝑘1 𝑝1 − 𝑦1 (𝑡) /𝑚1 𝑦ǃ 2 (𝑡) = 𝑘2 𝑝2 − 𝑦2 (𝑡) /𝑚2 𝑘1 and 𝑘2 are spring constants 7 Displacement plot Both springs begin compressed, so the masses begin moving towards one another They almost immediately collide and then oscillate together for a brief period until they pull apart In this plot, they collide two more times and almost collide a third time 8 Round Masses with Springs (cont.) With the masses stuck together, they behave as a single object with mass 𝑚1 + 𝑚2 and y(t) = 𝑦1 (t) = 𝑦2 (t) The dynamics are given by 𝑘1 𝑝1 + 𝑘2 𝑝2 − 𝑘1 + 𝑘2 𝑦(𝑡) 𝑦(𝑡) ǃ = 𝑚1 + 𝑚2 9 Round Masses with Springs (cont.) The transition is labeled with a set action that sets the initial positions of the two masses to 𝑖1 and 𝑖2 and the initial velocities to zero The transition from apart to together has the guard 𝑦1 (t) = 𝑦2 (t) s represents the stickiness of the two masses 10 Round Masses with Springs (cont.) The momentum of the left mass is 𝑦Ǘ1 𝑡 𝑚1 The momentum of the right mass is 𝑦Ǘ 2 (𝑡)𝑚2 The momentum of the combined masses is 𝑦(𝑡) Ǘ 𝑚1 + 𝑚2 To make these equal, it sets 𝑦Ǘ1 (𝑡)𝑚1 + 𝑦Ǘ 2 (𝑡)𝑚2 𝑦(𝑡) Ǘ = 𝑚1 + 𝑚2 11 Bonus Question Can you explain the following relation? 𝑘1 − 𝑘2 𝑦(𝑡) + 𝑘2 𝑝2 − 𝑘1 𝑝1 > 𝑠 12 Round Masses with Springs (cont.) The transition from together to apart has the more complicated guard 𝑘1 − 𝑘2 𝑦(𝑡) + 𝑘2 𝑝2 − 𝑘1 𝑝1 > 𝑠 Which is satisfied when the right-pulling force on the right mass exceeds the right-pulling force on the left mass by more than the stickiness s The right-pulling force on the right mass is 𝑓2 (𝑡) = 𝑘2 𝑝2 − 𝑦(𝑡) and the right-pulling force on the left mass is 𝑓1 (𝑡) = 𝑘1 𝑝1 − 𝑦(𝑡) Thus, the difference is 𝑓2 (𝑡) − 𝑓1 (𝑡) = 𝑘1 − 𝑘2 𝑦(𝑡) + 𝑘2 𝑝2 − 𝑘1 𝑝1 Which if exceeds the stickiness s, then the masses pull apart 13 Hybrid Automaton for Bouncing Ball y – vertical distance from ground (position) a – coefficient of restitution, 0< a < 1 A bump event is produced when the ball hits the ground Hybrid Automaton for Bouncing Ball (Cont.) Consider a bouncing ball. At time 𝑡 = 0, the ball is dropped from a height 𝑦(0) = ℎ0 where ℎ0 is the initial height in meters. It falls freely. At some later time 𝑡1 it hits the ground with a velocity 𝑦ሶ 𝑡1 < 0 m/s (meters per second) The collision is inelastic (meaning that kinetic energy is lost), and the ball bounces back up with velocity −𝑎𝑦ሶ 𝑡1 , where 𝑎 is constant with 0 < 𝑎 < 1. The ball will then rise to a certain height and fall back to the ground repeatedly When it is not in contact with the ground, the ball follows the second-order differential equation 𝑦(𝑡) ǃ = −𝑔 15 Bonus Question If you plot y(t), what would it look like? 16 Hybrid Automaton for Bouncing Ball (Cont.) The ball follows the second-order differential equation 𝑦ǃ 𝑡 = −𝑔 where 𝑔 = 9.81 m/sec 2 is the acceleration imposed by gravity If we integrate the previous relation, we get, for all 𝑡 ∈ 0, 𝑡1 , 𝑦(𝑡) Ǘ = −𝑔𝑡, 𝑡 1 𝑦(𝑡) = 𝑦(0) + න 𝑦(𝜏)𝑑𝜏 Ǘ = ℎ0 − 𝑔𝑡 2 0 2 Bonus question can you determine 𝑡1 ? 𝑡1 > 0 is determined by 𝑦 𝑡1 = 0. It is the solution to the equation 1 2 ℎ0 − 𝑔𝑡 = 0 2 Thus, 𝑡1 = 2ℎ0 /𝑔 17 Supervisory Control A control system involves four components Plant: the physical process that is to be controlled Environment in which the plant operates Sensors that measure some variables of the plant and the environment Controller that determines the mode transition structure and selects the time-based inputs to the plant The controller has two levels Supervisory control that determines the mode transition structure Low-level control that determines the time-based inputs to the plant The supervisory controller determines which of several strategies should be followed, and the low-level controller implements the selected strategy Hybrid systems are ideal for modeling such two-level controllers 18 Automated Guided Vehicle (AVG) AVG moves along a closed track painted on a warehouse or factory floor. We will design a controller so that the vehicle closely follows the track The vehicle has two degrees of freedom At any time t, it can move forward along its body axis with speed u(t) with the restriction that 0 ≤ u(t) ≤ 10 mph (miles per hour) It can also rotate about its center of gravity with an angular speed w(t) restricted to -π ≤ w(t) ≤ π radians/second 19 Automated Guided Vehicle (AVG) (cont.) The motion of the vehicle is given by 𝑥(𝑡) Ǘ = 𝑢(𝑡)cos 𝜃(𝑡), 𝑦(𝑡) Ǘ = 𝑢(𝑡)sin 𝜃(𝑡), Ǘ 𝜃(𝑡) = 𝜔(𝑡) We design the supervisory control governing transitions between modes in such a way that the vehicle closely follows the track, using a sensor that determines how far the vehicle is to the left or right of the track The sensor estimates the displacement e(t) of the center of the AGV from the track ∀𝑡, 𝑒(𝑡) = 𝑓(𝑥(𝑡), 𝑦(𝑡)) 20 Automated Guided Vehicle (AVG) (cont.) Initially, the vehicle is within distance of the track, so it moves straight At some point, the vehicle goes too far to the left, so there is a mode switch to the right as the following guard is satisfied After some time, the vehicle will again be close enough to the track, so the mode will be straight, and the following guard is stratified 21 Automated Guided Vehicle (AVG) (cont.) The plant is described by the differential equations The environment is the closed track The supervisory controller comprises the four modes and the guards that determine when to switch between modes The low-level controller specifies how the time-based inputs to the plant are selected in each mode 22 23 Chapter 5: Composition of State Machines Amr Alanwar Technical University of Munich Credits and Reference The content is based on extending/modifying the lecture material from UC Berkeley EECS 149 (Lee & Seshia) Chapter 5 - Introduction to Embedded Systems — A Cyber-Physical Systems Approach 2 Remember Actor Model for Extended State Machines 3 Synchronous Composition The term synchronous means occurring or existing at the same time or moving or operating at the same rate In circuit design, the word synchronous refers to a style of design where a clock that is distributed throughout a circuit drives latches that record their inputs on edges of the clock In power systems engineering, synchronous means that electrical waveforms have the same frequency and phase 4 Side-By-Side Composition A time-honored principle in engineering is that complicated systems should be described as compositions of simpler systems State machines being composed do not communicate The inputs and outputs of the two actors are disjoint, i.e., the state machines do not communicate Side-by-side composition of two actors 5 Example A has a single pure output a, and B has a single pure output b. The side-by-side composition C has two pure outputs, a and b If the composition is synchronous, then On the first reaction, a will be absent, and b will be present On the second reaction, it will be the reverse. On subsequent reactions, a and b will continue to alternate being present 6 Side-By-Side Composition (cont.) Such compositions are modular in the sense that the composition itself becomes a component that can be further composed as if it were itself an atomic component If the two-state machines A and B are deterministic, then the synchronous side- by-side composition is also deterministic We say that a property is compositional if a property held by the components is also a property of the composition. For synchronous side-by-side composition, determinism is a compositional property 7 Side-By-Side Composition (cont.) The rules of notation of a model are called its syntax, and the meaning of the notation is called its semantics Suppose that state machines A and B are given by the five tuples Then the synchronous side-by-side composition C is given by 8 Side-By-Side Composition (cont.) Update function is defined by where Recall that InputsA and InputsB are sets of valuations What we mean by is that a valuation of the inputs of C must include both valuations for the inputs of A and the inputs of B 9 Bonus question: Can You Give a Single State Machine Giving the Semantics of Synchronous Side-by-Side Composition of the State Machines Synchronous composition 10 The outputs a and b alternate being present. Notice further that (s1; s4) and (s2; s3) are not reachable states. Side-by-Side Asynchronous Composition In an asynchronous composition of state machines, the component machines react independently The key to each semantics is how to define a reaction of the composition C. Two possibilities are: Semantics 1. A reaction of C is a reaction of one of A or B, where the choice is nondeterministic. It is called interleaving semantics, meaning that A or B never react simultaneously. Their reactions are interleaved in some order Semantics 2. A reaction of C is a reaction of A, B, or both A and B, where the choice is nondeterministic. A variant of this possibility might allow neither to react 11 Asynchronous Composition Asynchronous composition using interleaving semantics Bonus Question: State Machine Giving the Semantics of Asynchronous Side-by-Side Composition - Semantics 1 Note that now all states are reachable. C Asynchronous composition using interleaving semantics Bonus Question: What are the Changes to Satisfy Semantic 2? A & B react simultaneously It would be possible to move to for (s1,s3) to (s2, s4) 14 Syntax vs. Semantics Can a and b be simultaneously present? Answer: it depends! Depends on our model of computation Synchronous: No Asynchronous Interleaving Semantics: No When composition reacts, Take one machine (non- deterministically) and let it react, then take one machine (non-deterministically) and let it react; Since only one machine reacts, both a and b cannot both be present Side-by-Side Asynchronous Composition For asynchronous composition under semantics 1, the symbolic definition of C has the same definitions of StatesC, InputsC, OutputsC, and initialStateC as for synchronous composition But the update function differs, becoming 16 Shared Variables An extended state machine has local variables that can be read and written as part of taking a transition Sometimes it is useful when composing state machines to allow these variables to be shared among a group of machines 17 Two Servers Example Consider two servers that can receive requests from a network Each request requires an unknown amount of time to service, so the servers share a queue of requests If one server is busy, the other server can respond to a request, even if the request arrives at the network interface of the first server A shared variable pending counts the number of pending job requests When a request arrives at the composite machine C, one of the two servers is nondeterministically chosen to react, assuming asynchronous composition under semantics 1 18 Two Servers Example 19 Cascade Composition The output of machine A feeds the input of B. This style of composition is called cascade composition or serial composition In synchronous composition of the cascade structure, a reaction of C consists of a reaction of both A and B, where A reacts first, produces its output (if any), and then B reacts. Logically, we view this as occurring in zero time, so the two reactions are in a sense simultaneous and instantaneous. But they are causally related in that the outputs of A can affect the behavior of B 20 Cascade Composition A B Output port(s) of A connected to input port(s) of B Bonus Question Can you give the semantics of the cascade composition assuming synchronous composition? 22 It is clear that the reactions of the two machines are simultaneous and instantaneous. When moving from the initial Example of a cascade composition of two FSMs state (s1, s3) to (s2, s4) (which occurs when the input a is absent), the composition machine C does not pass through (s2, s3)! In fact, (s2, s3) is not a reachable state! In this way, a single reaction of C encompasses a reaction of both A and B Semantics of the cascade composition example, 23 assuming synchronous composition Example: Time-Triggered Pedestrian Light This light stays green for 55 seconds, then goes red. Upon receiving a sigR input, it repeats the cycle. The output sigR of the traffic light can provide the input sigR of the pedestrian light Example: Time-Triggered Car Light Pedestrian Light with Car Light sigY sigG sigR sigR pedG pedR Synchronous cascade composition unsafe states are unreachable State = (CarLight, PedLight) Synchronous composition with unreachable states removed General Composition Side-by-side and cascade composition provide the basic building blocks for building more complex compositions of machines 𝐴1 and 𝐴3 are a side-by-side composition that together define a machine B. B and 𝐴2 are a cascade composition, with B feeding events to 𝐴2. However, B and 𝐴2 are also a cascade composition in the opposite order, with 𝐴2 feeding events to B Cycles like are called feedback 29 Hierarchical State Machines The key idea in hierarchical state machines is state refinement State B has a refinement that is another FSM with two states, C and D. What it means for the machine to be in state B is that it is in one of states C or D OR state (being B means being in C or D) 30 Semantics of the Hierarchical FSM Semantics of the hierarchical FSM Hierarchical FSM 31 What happens if both guards g1 and g4 evaluate to true? Different variants of Statecharts may make different choices at this point One variant of the reaction of a hierarchical FSM is defined in a depth-first fashion. The deepest refinement of the current state reacts 1. First, the refinement of the current state (if any) reacts. 2. Then the top-level machine reacts 32 Preemptive Transition A preemptive transition is shown with a (red) circle at the originating end of the transition The guards of a preemptive transition are evaluated before the refinement reacts, and if any guard evaluates to true, the refinement does not react As a consequence, if the machine is in state B and g1 is true, then neither action a3 nor a4 is performed Bonus question: Show the semantics Semantics with a preemptive transition 33 Reset Transition The transition from A to B is called a reset transition because the destination refinement is reset to its initial state, regardless of where it had previously been Whenever the machine enters B, it always enters C, never D, even if it was previously in D when leaving B A reset transition is indicated in our notation with a hollow arrowhead at the destination end of a transition 34 History Transition The transition from A to B is a history transition, an alternative to a reset transition When a history transition is taken, the destination refinement resumes in whatever state it was last in (or its initial state on the first entry) In our notation, a solid arrowhead denotes a history transition. It may also be marked with an “H” for emphasis. 35 Bonus Question: Show the Semantics of the History Transition The initial state is labeled (A, C) to indicate that the machine is in state A, and if and when it next enters B it will go to C. The first time it goes to B, it will be in the state labeled (B, C) to indicate that it is in state B and, more specifically, C. If it then transitions to (B, D), and then back to A, it will end up in the state labeled (A, D), which means it is in state A, but if and when it next enters B it will go to D. That is, it remembers its history, specifically where it was when it left B 36 37 Chapter 7: Sensors and Actuators Amr Alanwar Technical University of Munich Credits and Reference The content is based on extending/modifying the lecture material from UC Berkeley EECS 149 (Lee & Seshia) Chapter 7 - Introduction to Embedded Systems — A Cyber-Physical Systems Approach 2 What is a sensor? An actuator? A sensor is a device that measures a physical quantity → Input / “Read from physical world” An actuator is a device that modifies a physical quantity → Output / “Write to physical world” Sensors and Actuators – The Bridge between the Cyber and the Physical Sensors: Actuators:  Cameras  Motor controllers  Accelerometers  Solenoids  Gyroscopes  LEDs, lasers  Strain gauges  LCD and plasma displays  Microphones  Loudspeakers  Magnetometers  Switches  Radar/Lidar  Valves  Chemical sensors  Pressure sensors Modeling Issues:  Switches  Physical dynamics  Noise  Bias  Sampling  Interactions  Faults Sensor-Rich Cars Source: Analog Devices Sensor-Rich Cars Source: Wired Magazine How Does LiDAR Remote Sensing Work? https://youtu.be/EYbhNSUnIdU?si=bAz2eYh0WMbRVDjG 7 Radar vs. Ultrasonic https://youtu.be/QterBt_Ht6k?si=ZBzB4Lh4sfAHUQ6M 8 Self-Driving Cars Berkeley PATH Project Demo, 1999, San Diego. Kingvale Blower Berkeley PATH Project, March 2005 Kingvale Blower: Technology Overview Berkeley PATH Project, March, 2003 Google Self-Driving Car 2.0 12 https://www.youtube.com/watch?v=uHbMt6WDhQ8 Models of Sensors and Actuators Linear Model where is a function the models the sensor the physical quantity reported by the sensor proportionality constant Affine Model where is the bias Every linear function is an affine function (with ), but not vice versa 13 Sensor Range No sensor or actuator truly realizes an affine function The range of a sensor, the set of values of a physical quantity that it can measure, is always limited For example, a thermometer designed for weather monitoring may have a range of -20 to 50 Celsius. Physical quantities outside this range will typically saturate, meaning that they yield a maximum or a minimum reading outside their range An affine function model of a sensor may be augmented to take this into account piecewise affine where L and H are the low and high end of the sensor range, respectively 14 Sensor Precision & Range Digital sensors are unable to distinguish between two closely spaced values of the physical quantity Bonus question: What is the sensor precision? The precision p of a sensor is the smallest absolute difference between two values of a physical quantity whose sensor readings are distinguishable The dynamic range D of a digital sensor is the ratio 𝐻−𝐿 𝐷= 𝑝 where 𝐻 and 𝐿 are the limits of the range 15 Quantization A digital sensor represents a physical quantity using an n-bit number, where n is a small integer There are only 2𝑛 distinct such numbers, so such a sensor can produce only 2𝑛 distinct measurements The actual physical quantity may be represented by a real number x(t), but for each such x(t), the sensor must pick one of the 2𝑛 numbers to represent it. This process is called quantization 16 Example Consider a 3-bit digital sensor that can measure a voltage between zero and one volt It can be modeled by the function where is the voltage Bonus value: What is the precision value? The precision is p=1/8 17 Sampling A digital sensor will sample the physical quantity at particular points in time to create a discrete signal In uniform sampling, there is a fixed time interval T between samples; T is called the sampling interval The resulting signal may be modeled as a function 𝑠: ℤ → ℝ defined as ∀𝑛 ∈ ℤ, 𝑠(𝑛) = 𝑓(𝑥(𝑛𝑇)) where ℤ is the set of integers The sampling rate is 1/T, which has units of samples per second, often given as Hertz (written Hz, meaning cycles per second) 18 Accelerometers An accelerometer is a sensor that measures proper acceleration Uses:  Navigation  Orientation  Drop detection  Image stabilization  Airbag systems Accelerometers (cont.) The most common design measures the distance between a plate fixed to the platform and one attached by a spring and damper. The measurement is typically done by measuring capacitance When the frame accelerates in the direction of the double arrow in the figure, the acceleration results in displacement of the movable mass, and hence this acceleration can be measured Spring-Mass-Damper Accelerometer By Newton’s second law, F=ma. If the assembly is instead aligned vertically, then gravitational force will compress the spring and displace the mass Accelerometer Modeling 22 https://youtu.be/Z_kRE1JjHMs?si=lyP6WUScsqgAog4n Spring-Mass-Damper System x Measuring Position and Velocity In theory, given a measurement 𝑥 of acceleration over time, it is possible to determine the velocity and location of an object Consider an object moving in a one-dimensional space. Let the position of the object over time be 𝑝, with initial position 𝑝(0). Let the velocity of the object be 𝑣, with initial velocity 𝑣(0). And let the acceleration be 𝑥. Then 𝑡 𝑝(𝑡) = 𝑝(0) + ∫0 𝑣(𝜏)𝑑𝜏 𝑡 𝑣(𝑡) = 𝑣(0) + ∫0 𝑥(𝜏)𝑑𝜏 Difficulties in Measuring Position and Velocity If there is a non-zero bias in the measurement of acceleration, then 𝑝(t) will have an error that grows proportionally to 𝑡 2 Such an error is called drift, and it makes using an accelerometer alone to determine position not very useful However, if the position can be periodically reset to a known-good value, using for example GPS, then an accelerometer becomes useful to approximate the position between such settings 𝑡 𝑝(𝑡) = 𝑝(0) + ∫0 𝑣(𝜏)𝑑𝜏 𝑡 𝑣(𝑡) = 𝑣(0) + ∫0 𝑥(𝜏)𝑑𝜏 25 Global Positioning System (GPS) The GPS is a sophisticated satellite-based navigation system using triangulation A GPS receiver listens for signals from four or more GPS satellites that carry extremely precise clocks The satellites transmit a signal that includes the time of transmission and the location of the satellite at the time of transmission If the receiver were to have an equally precise clock, then upon receiving such a signal from a satellite, it would be able to calculate its distance from the satellite using the speed of light Given three such distances, it would be able to calculate its own position However, such precise clocks are extremely expensive. Hence, the receiver uses a fourth such distance measurement to get a system of four equations with four unknowns, the three dimensions of its location and the error in its own local clock 26 Traditional Localization 𝑺𝟏 𝑥1 , 𝑦1 , 𝑑1 Aggregator 𝑺𝟐 𝑥2 , 𝑦2 , 𝑑2 𝐴𝑠 𝑏𝑠 T 𝑥3 , 𝑦3 , 𝑑3 𝑺𝟐 Target Position: 2 𝑧Ƹ 𝑇 = (𝑥ො 𝑇 , 𝑦ො 𝑇 ) = 𝑎𝑟𝑔 min 𝐴𝑠 𝑧Ƹ 𝑇 − 𝑏𝑠 𝑧Ƹ 𝑇 𝐴𝑠 , 𝑏𝑠 are functions of anchor location and ranging 27 Traditional Localization (cont.) Target Position 𝑧Ƹ 𝑇 = (𝑥ො 𝑇 , 𝑦ො 𝑇 ) = 𝑎𝑟𝑔 min 𝐴𝑠 𝑧Ƹ 𝑇 − 𝑏𝑠 2 𝑧Ƹ 𝑇 Method 1 (matrix inversion) 𝑧Ƹ 𝑇 = (𝐴𝑇𝑠 𝐴𝑠 )−1 𝐴𝑇𝑠 𝑏𝑠 Method 2 (gradient descent) 𝐴𝑠 , 𝑏𝑠 are functions of anchor 𝑧Ƹ 𝑇𝑖+1 = 𝑧Ƹ 𝑇𝑖 +µ𝐴𝑇𝑠 (𝑏𝑠 − 𝐴𝑠 𝑧Ƹ 𝑇𝑖 ) location and ranging 28 Gyroscope https://www.youtube.com/watch?v=V6XSsNAWg00 29 Dead reckoning Inertial Navigation Systems plus GPS. Dead reckoning starts from a known initial position and orientation, and then uses measurements of motion to estimate subsequent position and orientation Combinations of:

Document Details

Tags

Related

Full Transcript

Upgrade to continue