Stanford AA228V I Validation of Safety Critical Systems I Falsification through Planning

Key Concepts

• Robustness: A measure of how close a trajectory is to failure.
• Likelihood: The probability of a trajectory occurring, based on the probabilities of the initial state and subsequent disturbances.
• Objective Function: A function that is minimized by an optimization algorithm to find failures.
• Population Methods: Optimization algorithms that maintain a population of samples and iteratively move them towards optimizing the objective.
• Local Descent Methods: Optimization algorithms that start from an initial guess and move it slowly towards a minimum.
• Zero Order Methods (Direct Methods): Optimization algorithms that only require function evaluation and do not need gradients.
• Tree Search: A category of planning algorithms that iteratively build up a trajectory by selecting and extending nodes in a tree.
• Heuristic Search (RRT - Rapidly Exploring Random Trees): A type of tree search that uses heuristics to explore the space of possible trajectories.
• Monte Carlo Tree Search (MCTS): A type of tree search that balances exploration and exploitation by maintaining a value estimate for each node in the tree.
• Exploration vs. Exploitation: The trade-off between exploring the space of possible trajectories and exploiting known promising paths.

Finding Failures Using Optimization

• Problem Setup: The goal is to find failures by optimizing an objective function that represents closeness to failure, subject to the constraint that the trajectory is a rollout given the initial state and sequence of disturbances.
• Objective Function: Initially, robustness is considered as the objective function. However, minimizing only robustness can lead to unlikely trajectories.
• Incorporating Likelihood: To address the issue of unlikely trajectories, likelihood is incorporated into the objective function.
  • The likelihood of a trajectory is the product of the likelihood of the initial state and the likelihood of all subsequent disturbances.
  • Mathematically, p(τ) = p(initial state) * p(disturbance 1) * p(disturbance 2) * ... * p(disturbance n).
  • In code, this is implemented as the product of the probability density function (PDF) of each disturbance at each time step, given the state, action, and observation.
  • The log PDF is used for numerical stability, as multiplying many small numbers can lead to very small numbers that are difficult to work with.
• New Objective Function: A new objective function is defined that considers both robustness and likelihood.
  • If the trajectory is a failure (τ ∉ Ψ), the objective is to minimize the negative likelihood of the trajectory.
  • If the trajectory is not a failure, the objective is to minimize the robustness.
• Gridworld Example: A Gridworld example is used to illustrate the difference between minimizing robustness and minimizing the new objective function.
  • Minimizing robustness leads to trajectories that go straight to the obstacle.
  • Minimizing the new objective function leads to trajectories that stay close to the nominal path and only deviate at the end to fall into the obstacle.
• Notes on Using the Objective:
  • Failures should never have a higher objective value than successes.
  • Numerical stability can be an issue due to multiplying many small numbers together.
  • Taking the log can break the requirement that failures have a lower objective value than successes.
• Practical Approach: In practice, a combined objective function is often used, trading off between minimizing robustness and minimizing the negative log likelihood.
  • Objective = Robustness + λ * (-Log Likelihood)
  • λ is a weighting parameter that needs to be tuned.
• Optimization Algorithm: The problem is formulated as an optimization problem, and off-the-shelf optimization algorithms can be used.
  • Examples include optim.jl and JMP in Julia.
• Categories of Optimization Methods:
  • Local Descent Methods: Start from an initial guess and move it slowly towards a minimum.
    • Examples: Gradient Descent, Adam, LBFGS.
    • Require gradients of the objective function.
  • Zero Order Methods (Direct Methods): Do descent based on function evaluation.
    • Examples: Hooke-Jeeves, Nelder-Mead.
    • Can work for black box systems.
• Gradient Descent Example: An example of gradient descent is shown for the pendulum, where each dot represents a disturbance.
  • The algorithm starts with an initial state of 0 and all disturbances are 0.
  • The disturbances are perturbed slightly to move the trajectory towards a failure.
• Population Methods Example: An example of population methods is shown for the pendulum, where a full population of possible samples is maintained.
  • The samples are updated to try to move them towards failure.
  • Population methods can find multiple failure modes.

Falsification Through Planning (Tree Search)

• Motivation: Iteratively building up a trajectory can be easier than doing it all at once.
• Tree Search: A category of planning algorithms that iteratively build up a trajectory by selecting and extending nodes in a tree.
• Tree Structure: Each node in the tree is a state for the system, and each edge represents a transition between nodes.
• Continuum World Example: A continuous version of a grid world problem is used to illustrate the concepts.
  • The agent can move around in a continuous space and needs to reach a goal while avoiding an obstacle.
  • The agent can take actions of up, down, left, and right, but it can slip in other directions.
• Tree Search Algorithm:
  1. Select: Select a node in the tree to extend.
  2. Extend: Sample a new disturbance, which gives a new observation, action, and brings to a different state.
• Heuristic Search (RRT - Rapidly Exploring Random Trees):
  • Uses heuristics to explore the space of possible trajectories.
  • Select Step:
    1. Sample a goal state.
    2. Compute an objective for each node in the current tree based on the goal state.
    3. Select the node with the lowest objective.
  • Extend Step:
    1. Select a disturbance.
    2. Take a step from the selected node using the selected disturbance.
    3. Add the result to the tree.
• Improvements to RRT:
  • Sample goal states from the failure region instead of the entire state space.
  • Select a disturbance that steers towards the goal.
• Other Common Heuristics:
  • Coverage Metrics: Use coverage metrics to guide the search and explore the space of possible trajectories as much as possible.
  • Alternative Objectives: Incorporate alternative objectives, such as finding the most likely failure or the shortest path to a failure.
• Incorporating Alternative Objectives:
  • Cost Function: Specify a cost function that consists of two things:
    • Current Cost: The cost required to get to the node that is currently at.
    • Cost to Go: The estimated cost to get to the goal.
  • Shortest Path to Failure:
    • Current Cost: Distance to the current node in the tree.
    • Cost to Go: Distance to the goal.
  • Most Likely Failure:
    • Current Cost: Negative log likelihood of the trajectory so far.
    • Cost to Go: Estimated negative log likelihood to go.
• A* Search: If the heuristic is admissible and the state space and disturbance space are discrete, then the algorithm turns into A* search.
  • A heuristic is admissible if it is guaranteed to never overestimate the cost of reaching the goal state.
• Monte Carlo Tree Search (MCTS):
  • Balances exploration and exploitation.
  • Maintains a value estimate (Q) for each node in the tree.
  • Select Step: Select a node to extend based on a heuristic that balances exploration and exploitation.
  • Extend Step: Sample a disturbance, add it to the tree, and propagate the results back up.
  • Progressive Widening: A technique used to control the number of children of each node.
  • Lower Confidence Bound (LCB): A formula used to balance exploration and exploitation.
  • Backpropagation: The process of updating the value estimates of the nodes in the tree after a new node has been added.

Conclusion

The lecture covers methods for finding failures in systems using optimization and planning. It begins by discussing how to set up an optimization problem to minimize closeness to failure, incorporating likelihood to avoid unlikely trajectories. It then introduces tree search algorithms, specifically heuristic search (RRT) and Monte Carlo tree search (MCTS), as methods for iteratively building up trajectories and exploring the space of possible failures. The lecture emphasizes the importance of balancing exploration and exploitation, and provides practical guidance on how to implement these algorithms and tune their parameters.