Stanford AA228V I Validation of Safety Critical Systems I Discrete Reachability

Key Concepts

• Interval Arithmetic: Performing arithmetic operations on intervals to bound the range of a function's output.
• Inclusion Functions: Functions that, given an interval input, return an interval that is guaranteed to contain the range of the original function over that input.
• Natural Inclusion Function: A simple inclusion function where each elementary function in a nonlinear function is replaced with its interval counterpart.
• Mean Value Inclusion Function: An inclusion function based on the mean value theorem to provide tighter bounds than the natural inclusion function.
• Taylor Inclusion Function: A generalization of inclusion functions using Taylor series expansions to achieve higher-order accuracy.
• Taylor Models: Representing sets as a polynomial (Taylor polynomial) plus an interval remainder to capture non-hyperrectangular shapes.
• Conservative Linearization: A second-order Taylor model, resulting in a polytope representation.
• Jacobian: A matrix containing the partial derivatives of a vector-valued function, used in conservative linearization.
• Minkowski Sum: The sum of two sets, where each element of the first set is added to each element of the second set.
• Symbolic Reachability: Computing reachable sets by considering the entire rollout function at once.
• Concrete Reachability: Computing reachable sets one step at a time, concretizing the reachable set at each time step.
• Wrapping Effect: The compounding of overapproximation error in concrete reachability due to concretizing the reachable set at each time step.
• Partitioning: Dividing the initial set into smaller subsets and performing reachability analysis on each subset to reduce overapproximation.
• Discrete Reachability: Reachability analysis for systems with discrete states and disturbances, represented using directed graphs.
• Forward Reachable Set: The set of states reachable from an initial set by following forward edges in the graph.
• Backward Reachable Set: The set of states that can reach a target set by following backward edges in the graph.
• Invariant Set: A set of states that, once entered, the system will remain within for all future time steps.
• Satisfiability: Checking if a system satisfies a property, such as avoiding a specific set of states.
• Probabilistic Reachability: Analyzing the likelihood of reaching a particular state or set of states.
• Probability of Occupancy: The distribution over reachable states at each time step.
• Discrete State Abstraction: Converting continuous systems into discrete systems by partitioning the state space and representing each cell as a node in a graph.

Taylor Models

• Definition: A Taylor model represents a set by applying a polynomial to an input set and adding an interval remainder: TaylorModel = p(x) + alpha, where p(x) is the Taylor polynomial of degree n-1 for a Taylor model of order n, and alpha is an interval remainder.
• Taylor Polynomial: The Taylor polynomial consists of terms up to degree n-1.
• Interval Remainder (Lagrange Remainder): An interval that bounds the error of the Taylor polynomial approximation, derived using the inclusion function for the n-th derivative of the function.
• Approximation and Error Bounding: The polynomial approximates the function, and the interval remainder bounds the error of this approximation.
• Connection to Taylor Inclusion Function: If the polynomial p(x) is replaced with the natural inclusion function for the polynomial, the Taylor model recovers the Taylor inclusion function.
• Flexibility: Taylor models allow passing arbitrary sets through the Taylor polynomial, unlike inclusion functions which are limited to intervals.
• Example: Applying Taylor models of increasing order to a function with an interval input shows improved overapproximation. A second-order Taylor model results in a polytope, while a third-order model can produce non-convex sets.
• Limitations: Working with non-convex sets (e.g., third-order Taylor models) is computationally challenging, especially in higher dimensions, due to the difficulty of performing operations on them (e.g., intersection checks).

Conservative Linearization

• Definition: A second-order Taylor model, resulting in a polytope representation.
• Multi-Dimensional Functions: For a function f(x) that inputs a vector x and outputs a vector, conservative linearization involves breaking f into sub-functions f1 to fn, each outputting one component of the result.
• First-Order Taylor Polynomials: The first-order Taylor polynomial is computed for each sub-function.
• Jacobian Matrix: The gradients of the sub-functions are stacked to form the Jacobian matrix J.
• Linearization Formula: The function is approximated as f(c) + J(x - c), where c is the center point.
• Taylor Model Application: The Taylor model is then f(c) + J(x - c) + alpha, where alpha is the interval remainder.
• Linear Reachability: The linear function f(c) + J(x - c) allows using linear reachability techniques to pass polytopes through the function.
• Minkowski Sum and Matrix Multiplication: Addition is replaced with the Minkowski sum, and standard matrix multiplication is used.
• Intuition: The function is linearized, a set is passed through the linearized portion, and the error due to linearization is calculated and added on as the interval remainder.
• Julia Implementation: Julia handles the Jacobian calculation and Minkowski sums efficiently.
• Limitations: If the function is highly non-linear, the linearization will result in a large overapproximation (large interval remainder).

Concrete vs. Symbolic Reachability

• Symbolic Reachability: Computes reachable sets by considering the entire rollout function at once. For example, to compute the reachable set at time step 3 from time step 1, it uses a reach function that takes the state at time step 1 and disturbances for the next time steps until time step 3.
• Concrete Reachability: Computes reachable sets one step at a time, concretizing the reachable set at each time step. For example, to compute the reachable set at time step 3 from time step 1, it first computes the reachable set at time step 2, then uses that to compute the reachable set at time step 3.
• Trade-offs:
  • Symbolic Reachability:
    • Computationally expensive due to considering the entire rollout function.
    • Nonlinearities compound over time.
    • No wrapping effect.
  • Concrete Reachability:
    • More computationally efficient (one step at a time).
    • Decreased compounding of nonlinearities.
    • Suffers from the wrapping effect (overapproximation error compounds).
• Problem Dependence: Whether symbolic or concrete reachability performs better is problem-dependent.
• Hybrid Approaches: Combining symbolic and concrete reachability (e.g., a few symbolic steps, then concretize, then a few more symbolic steps) can be effective.

Partitioning

• Process:
  1. Divide the initial set into smaller subsets.
  2. Perform reachability analysis on each subset.
  3. Take the union of the reachable sets from each subset to obtain an overapproximation of the reachable set.
• Benefits:
  • Propagating smaller sets results in less overapproximation error.
  • Non-convex sets can be represented as a union of convex sets.
• Trade-offs:
  • More subsets increase computational costs.
• Application: Particularly useful when the set has a shape that is not well-represented by hyperrectangles.
• Implementation: Typically, only the input set is partitioned.

Discrete Reachability

• Representation: Discrete systems are represented using directed graphs, where nodes represent states and edges represent potential transitions between states. Edge weights represent the probability of transition.
• Graph Construction:
  1. Enumerate all states.
  2. Create a graph with these states as nodes.
  3. For each state, determine the possible next states and their transition probabilities using a "successors" function.
  4. Add weighted edges to the graph representing these transitions.
• Analysis Types:
  • Reachable sets
  • Satisfiability
  • Probabilistic reachability
• Reachable Sets:
  • Forward Reachable Set: Computed by starting at the initial set of states and following forward edges in the graph.
  • Backward Reachable Set: Computed by starting at the target set and following backward edges in the graph.
  • Equivalence to Breadth-First Search: Computing reachable sets is equivalent to breadth-first search of the graph.
• Invariant Sets:
  • Definition: A set of states that, once entered, the system will remain within for all future time steps.
  • Checking for Invariant Sets: If the reachable set from time step 1 through d is a subset of the reachable set of the previous time steps, then the reachable set is an invariant set.
• Satisfiability:
  • Definition: Checking if a system satisfies a property, such as avoiding a specific set of states.
  • Forward Reachability: Check if the forward reachable set intersects with an avoid set.
  • Backward Reachability: Check if the backward reachable set (starting from the avoid set) intersects with the initial set.
  • More Efficient Methods: If only satisfiability is needed, more efficient methods exist (e.g., heuristic search, Boolean satisfiability).
• Probabilistic Reachability:
  • Motivation: To understand the likelihood of reaching a particular state or set of states.
  • Probability of Occupancy: The distribution over reachable states at each time step.
    • Computed recursively using the formula: P(s, t+1) = sum(P(s', t) * P(s -> s')) for all possible previous states s'.
  • Probability of Reaching a Target Set: The probability of reaching a state in the target set within a given time horizon.
    • Computed recursively.
• Discrete State Abstraction:
  • Purpose: To convert continuous systems into discrete systems.
  • Process:
    1. Partition the continuous state space into cells.
    2. Each cell becomes a node in the graph.
    3. For each cell, determine the set of reachable states using continuous reachability algorithms (e.g., conservative linearization).
    4. Overapproximate the reachable set by including all cells that the reachable set overlaps with.
    5. Draw edges between the original cell and all overlapping cells.
  • Benefits: Allows applying discrete reachability algorithms to continuous systems.
  • Finer Partitions: Result in less overapproximation.

Conclusion

The lecture explores various techniques for reachability analysis, focusing on non-linear and discrete systems. It begins by addressing the limitations of interval arithmetic and inclusion functions for non-linear systems, leading to the introduction of Taylor models as a more flexible representation. Conservative linearization, a specific type of Taylor model, is presented as a way to obtain polytope representations. The lecture then contrasts symbolic and concrete reachability, highlighting their trade-offs and potential for combined approaches. Partitioning is introduced as a method to reduce overapproximation by dividing the initial set into smaller subsets. Finally, the lecture transitions to discrete reachability, covering graph-based representations, forward and backward reachable sets, invariant sets, satisfiability, and probabilistic reachability. Discrete state abstraction is presented as a way to apply discrete reachability techniques to continuous systems. The lecture emphasizes the importance of choosing the appropriate technique based on the specific problem and the trade-offs between computational cost and accuracy.