Stanford AA228V I Validation of Safety Critical Systems I Reachability for Linear Systems

Key Concepts

• Failure Analysis vs. Formal Methods: Shifting from estimating failure probabilities to proving the absence of failure.
• Reachability Analysis: Computing the set of states a system can reach over time.
• Mass Spring Damper System: A common model used to illustrate reachability concepts.
• Bounded Sets: Defining initial states and disturbances within specific limits.
• Reachable Set (R_d): The set of all states reachable at a specific depth (time step) d.
• Reachable Set up to Horizon (R_1:h): The union of all reachable sets from time step 1 to h.
• Avoid Set: The set of states the system should not enter.
• Linear Systems: Systems where sensor, agent, and environment are linear functions of state, action, observation, and disturbance.
• Set Propagation Techniques: Methods for computing reachable sets by applying operations to sets.
• Linear Transformation (Matrix Multiplication) for Sets: Applying a matrix to every point in a set.
• Minkowski Sum (Addition) for Sets: Adding every point in one set to every point in another set.
• Finite Representation: Representing a set without listing all its points.
• Closed Under Set Operations: Applying an operation to a set and getting a set of the same type.
• Convex Set: A set where a line between any two points in the set is entirely within the set.
• Polytope: A bounded intersection of half-spaces.
• H-Polytope: A polytope represented as a set of half-spaces (linear inequalities).
• V-Polytope: A polytope represented as the convex hull of a set of vertices.
• Convex Hull: The smallest convex set containing a given set of points.
• Zonotope: A special type of polytope represented as the Minkowski sum of line segments centered at a point.
• Overapproximation: Creating a set that contains the true reachable set.

Main Topics and Key Points

Introduction to Formal Methods and Reachability

• The lecture transitions from failure analysis to formal methods, specifically reachability analysis.
• Goal: To prove the absence of failure under certain assumptions, rather than just estimating failure probabilities.
• Reachability: Aims to compute the set of states a system can reach over time.
• Disclaimer: A humorous acknowledgment of the difficulty in making the topic entertaining.

Illustrative Example: Mass Spring Damper System

• A mass spring damper system is introduced as a simple example.
• System Description: A mass attached to a wall via a spring and damper, with the ability to move back and forth.
• Failure Condition: The mass entering a defined "red region" (getting too close to the wall or extending too far).
• Agent/Controller: An agent applies force to the mass to counteract the spring and damper, ideally reducing oscillation.
• Sensor Noise: The agent receives noisy observations of the mass's position, making control more challenging.
• Question: Given a bound on the maximum possible noise, can we prove the system will never fail? Or can we provide a counterexample?

Assumptions for Reachability Analysis

• To obtain guarantees, certain assumptions must be made.
• Initial State Set: The mass starts with a position between -0.2 and 0.2 (relative to its resting point) and zero velocity.
• Disturbance Set: The maximum absolute observation noise on position and velocity is bounded by 1.
• Generalization: These assumptions define a bounded set of initial states and disturbances.
• Distributions to Bounded Sets: Distributions over initial states and disturbances can be converted to bounded sets using their support (or selecting a region containing most probability mass).

Reachable Sets: Definition and Computation

• Reachable Set (R_d): The set of all states reachable at depth d, given the initial state set and disturbance sets.
• Mathematical Definition: R_d = {s' | s' = reach(s, x), s ∈ S, x ∈ X}, where reach is a rollout function, S is the initial state set, and X is the disturbance set.
• Reachable Set up to Horizon (R_1:h): The union of all reachable sets from time step 1 to h.
• Safety Verification: Check if the reachable set intersects with the avoid set (set of bad states). If it doesn't, the system is guaranteed to be safe up to the horizon h.
• Liveness Verification: Check if the reachable set is contained within a goal region.

Linear Systems: Definition and Properties

• Definition: Systems where the sensor, agent, and environment are linear functions of the state, action, observation, and disturbance.
• Mathematical Representation: Observation model, agent, and transition model are defined using matrices and vectors.
• Mass Spring Damper as a Linear System: The mass spring damper system can be represented as a linear system.

Set Propagation Techniques for Linear Systems

• Goal: To compute reachable sets by applying operations to sets instead of individual points.
• Key Operations: Matrix multiplication (linear transformation) and addition (Minkowski sum).
• Linear Transformation for Sets: A * P = {A * p | p ∈ P}, where A is a matrix and P is a set.
• Minkowski Sum for Sets: P ⊕ Q = {p + q | p ∈ P, q ∈ Q}, where P and Q are sets.
• Set-Based Reachability Equation: Deriving an equation for the next state in terms of the current state and disturbances, then replacing point operations with set operations.
• Implementation in Code: Using the LazySets.jl Julia package to perform set operations.

Nice Set Representations: Convex Sets and Polytopes

• Desirable Properties: Finite representation, efficient set operations, closed under set operations.
• Convex Set Definition: A set where a line between any two points in the set is entirely within the set.
• Polytope Definition: A bounded intersection of half-spaces.
• H-Polytope Representation: Defined by a set of linear inequalities (A * x ≤ b).
• V-Polytope Representation: Defined as the convex hull of a set of vertices.
• Equivalence of H and V Representations: A polytope can be represented in both H and V forms.

V-Polytopes: Linear Transformation and Minkowski Sum

• Linear Transformation of a V-Polytope: Multiply each vertex by the matrix, then take the convex hull of the resulting vertices.
• Minkowski Sum of V-Polytopes: Take the convex hull of all combinations of sums of vertices from each polytope.
• Complexity Analysis: Linear transformations don't change the number of vertices, but Minkowski sums can lead to exponential growth in the number of vertices.

Zonotopes: A Special Type of Polytope

• Definition: The Minkowski sum of a set of line segments centered at a point.
• Representation: Defined by a center point and a list of generators (vectors).
• Linear Transformation of a Zonotope: Multiply the center and each generator by the matrix.
• Minkowski Sum of Zonotopes: Add the centers and concatenate the lists of generators.
• Complexity Analysis: Linear growth in the number of generators for Minkowski sums, making zonotopes more computationally tractable than general polytopes.
• Hyperrectangles as Zonotopes: Hyperrectangles are a special case of zonotopes where the generators are aligned with the axes.

Overapproximation: Trading Accuracy for Computational Efficiency

• Definition: Creating a set that contains the true reachable set.
• Notation: Using a bar over the set symbol to denote overapproximation (e.g., ̄P).
• Guarantee Implications: If the overapproximated reachable set does not intersect with the avoid set, the system is guaranteed to be safe. If it does intersect, no conclusion can be drawn.
• Practical Implementation: Overapproximate the reachable set every few iterations to reduce the number of vertices.
• LazySets.jl Support: The LazySets.jl package provides an overapproximate function.

Step-by-Step Processes, Methodologies, or Frameworks Explained

1. Reachability Analysis Process:

   • Define the system and its dynamics.
   • Define the initial state set and disturbance sets.
   • Define the avoid set (or goal region).
   • Compute the reachable set at each time step using set propagation techniques.
   • Check if the reachable set intersects with the avoid set (or is contained within the goal region).
   • Draw conclusions about the system's safety or liveness.

2. Set Propagation for Linear Systems:

   • Start with the initial state set.
   • For each time step:
     • Apply the set-based reachability equation: R_d = A * R_{d-1} ⊕ B * X, where A and B are matrices derived from the system dynamics, and X is the disturbance set.
     • Use linear transformation and Minkowski sum operations for sets.
   • Repeat until the desired horizon is reached.

3. Linear Transformation of a V-Polytope:

   • Multiply each vertex of the V-polytope by the transformation matrix.
   • Compute the convex hull of the resulting set of points.

4. Minkowski Sum of V-Polytopes:

   • For each combination of vertices from the two V-polytopes, add the vertices together.
   • Compute the convex hull of the resulting set of points.

5. Linear Transformation of a Zonotope:

   • Multiply the center of the zonotope by the transformation matrix.
   • Multiply each generator of the zonotope by the transformation matrix.

6. Minkowski Sum of Zonotopes:

   • Add the centers of the two zonotopes together.
   • Concatenate the lists of generators from the two zonotopes.

Key Arguments or Perspectives Presented, with Their Supporting Evidence

• Formal methods provide guarantees that failure analysis cannot. While failure analysis can identify potential failures and estimate their probabilities, it cannot prove the absence of failure. Formal methods, specifically reachability analysis, aim to provide such guarantees under certain assumptions.
• Assumptions are crucial for obtaining guarantees. Reachability analysis requires defining bounded sets for initial states and disturbances. The validity of the guarantees depends on the accuracy and appropriateness of these assumptions.
• Set-based reachability is more powerful than sampling-based methods. Sampling-based methods (e.g., Monte Carlo simulations) can provide insights into system behavior, but they cannot guarantee that all possible states have been explored. Set-based reachability aims to compute the full set of reachable states, providing stronger guarantees.
• Different set representations have different computational properties. Polytopes are a general class of sets that can be used for reachability analysis, but they can suffer from exponential growth in the number of vertices. Zonotopes are a special type of polytope that offer more computationally tractable operations, but they are not always applicable.
• Overapproximation can trade accuracy for computational efficiency. Overapproximating the reachable set can reduce the computational burden of reachability analysis, but it can also lead to less precise guarantees.

Notable Quotes or Significant Statements with Proper Attribution

• "So instead of trying to find failures or estimate probabilities of failure, here we're actually trying to prove the absence of failure." - This highlights the core difference between failure analysis and formal methods.
• "Now we're going to get guarantees, but we have to make some assumptions in order to actually get those guarantees." - This emphasizes the trade-off between guarantees and assumptions in formal methods.
• "A set is just a collection of points." - This provides a fundamental understanding of what a set is in the context of reachability analysis.
• "If the overapproximate reachable set does not intersect with the avoid set, we can still make a guarantee. We can still conclude that the system is safe." - This summarizes the key implication of using overapproximation for safety verification.
• "Assumptions matter." - This is the moral of the story about the hot pink chair covers, emphasizing the importance of carefully considering assumptions in any analysis.

Technical Terms, Concepts, or Specialized Vocabulary with Brief Explanations

• Falsification: A method for finding failures in a system by searching for counterexamples.
• Failure Distribution: A probability distribution that describes the likelihood of failure over time.
• Failure Probability Estimation: Estimating the probability of a system failing within a given time period.
• Formal Methods: Techniques for formally specifying, verifying, and validating systems.
• Reachability: The set of states a system can reach over time, given its initial state and dynamics.
• Agent: A component that interacts with the environment and influences the system's behavior (also referred to as a controller).
• Sensor Noise: Errors or uncertainties in the measurements provided by sensors.
• Bounded Set: A set with defined limits or boundaries.
• Support (of a distribution): The region where the probability density function is non-zero.
• Rollout: Simulating the system's behavior over a period of time, starting from a given initial state.
• Depth: The number of steps in a trajectory or rollout.
• Avoid Set: The set of states the system should not enter (also referred to as the set of bad states).
• Linear Inequality: An inequality of the form a^T * x ≤ b, where a and b are vectors and x is a variable.
• Half-Space: The region of space defined by a linear inequality.
• Polyhedron: The intersection of half-spaces.
• Convex Hull: The smallest convex set containing a given set of points.
• Generator (of a zonotope): A vector that defines a line segment used to construct the zonotope.
• Overapproximation: Creating a set that contains the true set.

Logical Connections Between Different Sections and Ideas

• The lecture begins by contrasting failure analysis with formal methods, setting the stage for the introduction of reachability analysis.
• The mass spring damper system is introduced as a concrete example to illustrate the concepts of reachability, initial states, disturbances, and avoid sets.
• The discussion of assumptions leads to the definition of bounded sets and the conversion of distributions to bounded sets.
• The definition of reachable sets is followed by a discussion of how to compute them, leading to the introduction of linear systems and set propagation techniques.
• The explanation of set propagation techniques motivates the need for efficient set representations, leading to the discussion of convex sets, polytopes, and zonotopes.
• The complexity analysis of polytope operations motivates the use of zonotopes and overapproximation techniques.

Data, Research Findings, or Statistics Mentioned

• No specific data, research findings, or statistics are mentioned in the transcript.

Synthesis/Conclusion of the Main Takeaways

The lecture provides a comprehensive introduction to reachability analysis as a formal method for verifying the safety of dynamic systems. It covers the fundamental concepts, assumptions, and techniques involved in computing reachable sets for linear systems. The lecture emphasizes the importance of carefully considering assumptions and the trade-offs between accuracy and computational efficiency. It also highlights the usefulness of the LazySets.jl Julia package for performing set-based reachability analysis. The key takeaway is that reachability analysis can provide guarantees about system safety, but it requires careful modeling, appropriate assumptions, and efficient computational techniques.