AA228V/CS238V
Validation of Safety-Critical Systems
Validation of Safety-Critical Systems
Lecture 06/07: Falsification Through Planning
Sydney Katz (smkatz@stanford.edu)
Sydney Katz (smkatz@stanford.edu)
Why do we save our work periodically?
SAVE
Sometimes, it is easier to iteratively build something up than to do it all at once.
From last lecture:
minimize
s, x
f(τ)
subject to
τ=Rollout(s,x)
minimize
s, x
f(Rollout(s,x))
This optimization problem typically involves searching over a very high-dimensional space.
e.g. inverted pendulum: s∈R2,x∈R2d
For depth d=21, the search space is 44-dimensional!
Planning algorithms allow us to iteratively build up a trajectory instead.
Plan for Today
1
Tree Search
2
Heuristic Search
3
Monte Carlo Tree Search
4
Reinforcement Learning
5
Simulator Requirements
Tree Search
Tree Search
The type of tree we are actually talking about in this lecture…
o,a,x
o,a,x
o,a,x
s
s
s
s
The type of tree we are actually talking about in this lecture…
o,a,x
o,a,x
o,a,x
s
s
s
s
Continuum World
A typical iteration of a tree search algorithm:
o,a,x
o,a,x
o,a,x
s
s
s
s
A typical iteration of a tree search algorithm:
o,a,x
o,a,x
o,a,x
o,a,x
s
s
s
s
s
A typical iteration of a tree search algorithm:
o,a,x
o,a,x
o,a,x
o,a,x
s
s
s
s
s
A typical iteration of a tree search algorithm:
Current Tree
o,a,x
o,a,x
o,a,x
s
s
s
s
Select
o,a,x
o,a,x
o,a,x
s
s
s
s
Extend
o,a,x
o,a,x
o,a,x
o,a,x
s
s
s
s
s
A typical iteration of a tree search algorithm:
Select
o,a,x
o,a,x
o,a,x
s
s
s
s
Extend
o,a,x
o,a,x
o,a,x
o,a,x
s
s
s
s
s
A typical iteration of a tree search algorithm:
Select
o,a,x
o,a,x
o,a,x
s
s
s
s
Extend
o,a,x
o,a,x
o,a,x
o,a,x
s
s
s
s
s
Tree search algorithms
differ from one another in
how they implement the
select and extend steps.
differ from one another in
how they implement the
select and extend steps.
Plan for Today
1
Tree Search
2
Heuristic Search
3
Monte Carlo Tree Search
4
Reinforcement Learning
5
Simulator Requirements
Heuristic Searchalgorithms use heuristics to explore the space of possible trajectories.
Rapidly Exploring Random Trees (RRT)
Rapidly Exploring Random Trees (RRT)
1
Select
2
Extend
A.Sample goal state
B.Compute objective for each node in
the current tree based on the goal
state
the current tree based on the goal
state
C.Select the node with the lowest
objective
objective
A.Select disturbance
B.Take a step from the selected node
using the selected disturbance
using the selected disturbance
C.Add result to the tree
Rapidly Exploring Random Trees (RRT)
1
Select
2
Extend
A.Sample goal state
B.Compute objective for each node in
the current tree based on the goal
state
the current tree based on the goal
state
C.Select the node with the lowest
objective
objective
A.Select disturbance
B.Take a step from the selected node
using the selected disturbance
using the selected disturbance
C.Add result to the tree
Rapidly Exploring Random Trees (RRT)
1
Select
2
Extend
A.Sample goal state
B.Compute objective for each node in
the current tree based on the goal
state
the current tree based on the goal
state
C.Select the node with the lowest
objective
objective
A.Select disturbance
B.Take a step from the selected node
using the selected disturbance
using the selected disturbance
C.Add result to the tree
Rapidly Exploring Random Trees (RRT)
1
Select
2
Extend
A.Sample goal state
B.Compute objective for each node in
the current tree based on the goal
state
the current tree based on the goal
state
C.Select the node with the lowest
objective
objective
A.Select disturbance
B.Take a step from the selected node
using the selected disturbance
using the selected disturbance
C.Add result to the tree
(e.g. distance to goal)
Rapidly Exploring Random Trees (RRT)
1
Select
2
Extend
A.Sample goal state
B.Compute objective for each node in
the current tree based on the goal
state
the current tree based on the goal
state
C.Select the node with the lowest
objective
objective
A.Select disturbance
B.Take a step from the selected node
using the selected disturbance
using the selected disturbance
C.Add result to the tree
Rapidly Exploring Random Trees (RRT)
1
Select
2
Extend
A.Sample goal state
B.Compute objective for each node in
the current tree based on the goal
state
the current tree based on the goal
state
C.Select the node with the lowest
objective
objective
A.Select disturbance
B.Take a step from the selected node
using the selected disturbance
using the selected disturbance
C.Add result to the tree
Rapidly Exploring Random Trees (RRT)
1
Select
2
Extend
A.Sample goal state
B.Compute objective for each node in
the current tree based on the goal
state
the current tree based on the goal
state
C.Select the node with the lowest
objective
objective
A.Select disturbance
B.Take a step from the selected node
using the selected disturbance
using the selected disturbance
C.Add result to the tree
Rapidly Exploring Random Trees (RRT)
1
Select
2
Extend
A.Sample goal state
B.Compute objective for each node in
the current tree based on the goal
state
the current tree based on the goal
state
C.Select the node with the lowest
objective
objective
A.Select disturbance
B.Take a step from the selected node
using the selected disturbance
using the selected disturbance
C.Add result to the tree
Rapidly Exploring Random Trees (RRT)
1
Select
2
Extend
A.Sample goal state
B.Compute objective for each node in
the current tree based on the goal
state
the current tree based on the goal
state
C.Select the node with the lowest
objective
objective
A.Select disturbance
B.Take a step from the selected node
using the selected disturbance
using the selected disturbance
C.Add result to the tree
Rapidly Exploring Random Trees (RRT)
1
Select
2
Extend
A.Sample goal state
B.Compute objective for each node in
the current tree based on the goal
state
the current tree based on the goal
state
C.Select the node with the lowest
objective
objective
A.Select disturbance
B.Take a step from the selected node
using the selected disturbance
using the selected disturbance
C.Add result to the tree
Rapidly Exploring Random Trees (RRT)
1
Select
2
Extend
A.Sample goal state
B.Compute objective for each node in
the current tree based on the goal
state
the current tree based on the goal
state
C.Select the node with the lowest
objective
objective
A.Select disturbance
B.Take a step from the selected node
using the selected disturbance
using the selected disturbance
C.Add result to the tree
We didn’t find any failures!
Rapidly Exploring Random Trees (RRT)
1
Select
2
Extend
A.Sample goal state
B.Compute objective for each node in
the current tree based on the goal
state
the current tree based on the goal
state
C.Select the node with the lowest
objective
objective
A.Select disturbance
B.Take a step from the selected node
using the selected disturbance
using the selected disturbance
C.Add result to the tree
We didn’t find any failures!
We could run for longer…
Or we could make some improvements to our algorithm!
Rapidly Exploring Random Trees (RRT)
Or we could make some improvements to our algorithm!
1
Select
2
Extend
Instead of sampling a goal state from anywhere in the state
space, we sample a goal state from the failure region.
space, we sample a goal state from the failure region.
Note: not all systems have an easily
identifiable failure region.
identifiable failure region.
Instead of sampling a random disturbance, select the
disturbance that will move us closest to the goal state.
disturbance that will move us closest to the goal state.
Rapidly Exploring Random Trees (RRT)
Or we could make some improvements to our algorithm!
1
Select
2
Extend
Instead of sampling a goal state from anywhere in the state
space, we sample a goal state from the failure region.
space, we sample a goal state from the failure region.
Note: not all systems have an easily
identifiable failure region.
identifiable failure region.
Instead of sampling a random disturbance, select the
disturbance that will move us closest to the goal state.
disturbance that will move us closest to the goal state.
Rapidly Exploring Random Trees (RRT)
Or we could make some improvements to our algorithm!
We found a failure!
Rapidly Exploring Random Trees (RRT)
Other Common Heuristics
Coverage Metrics
Alternative Objectives
Rapidly Exploring Random Trees (RRT)
Other Common Heuristics
Coverage Metrics
Alternative Objectives
Advanced Topic 🫤
Rapidly Exploring Random Trees (RRT)
We can incorporateAlternative Objectivesinto RRT by modifying how we compute the objectives in the select step.
1
Select
A.Sample goal state
B.Compute objective for each node in
the current tree based on the goal
state
the current tree based on the goal
state
C.Select the node with the lowest
objective
objective
Rapidly Exploring Random Trees (RRT)
We can incorporateAlternative Objectivesinto RRT by modifying how we compute the objectives in the select step.
1
Select
A.Sample goal state
B.Compute objective for each node in
the current tree based on the goal
state
the current tree based on the goal
state
C.Select the node with the lowest
objective
objective
From Before
Rapidly Exploring Random Trees (RRT)
We can incorporateAlternative Objectivesinto RRT by modifying how we compute the objectives in the select step.
Cost Function
c=current cost+cost to go
We don’t know this! If we did, our
problem would already be solved.
problem would already be solved.
We instead must estimate it using a
heuristic function h.
heuristic function h.
Rapidly Exploring Random Trees (RRT)
We can incorporateAlternative Objectivesinto RRT by modifying how we compute the objectives in the select step.
Cost Function
c=current cost+cost to go
Shortest Path to Failure
Rapidly Exploring Random Trees (RRT)
We can incorporateAlternative Objectivesinto RRT by modifying how we compute the objectives in the select step.
Cost Function
c=current cost+cost to go
Shortest Path to Failure
current cost=distance to current node in tree
Rapidly Exploring Random Trees (RRT)
We can incorporateAlternative Objectivesinto RRT by modifying how we compute the objectives in the select step.
Cost Function
c=current cost+cost to go
Shortest Path to Failure
current cost=distance to current node in tree
cost to go=distance to goal “as the crow flies”
1
2
3
4
5
6
🤔Which node would we extend next?
6
Rapidly Exploring Random Trees (RRT)
We can incorporateAlternative Objectivesinto RRT by modifying how we compute the objectives in the select step.
Cost Function
c=current cost+cost to go
Shortest Path to Failure
current cost=distance to current node in tree
cost to go=distance to goal “as the crow flies”
🤔Which node would we extend next?
Most Likely Failure
Rapidly Exploring Random Trees (RRT)
We can incorporateAlternative Objectivesinto RRT by modifying how we compute the objectives in the select step.
Cost Function
c=current cost+cost to go
Most Likely Failure
current cost=negative log likelihood of trajectory so far+C
Note: costs must be positive to
ensure that the search will terminate.
ensure that the search will terminate.
Rapidly Exploring Random Trees (RRT)
We can incorporateAlternative Objectivesinto RRT by modifying how we compute the objectives in the select step.
Cost Function
c=current cost+cost to go
Most Likely Failure
current cost=negative log likelihood of trajectory so far+C
cost to go=estimate of negative log-likelihood to go
e.g. could use distance to goal as a
proxy since shorter paths tend to
have higher likelihood
proxy since shorter paths tend to
have higher likelihood
Rapidly Exploring Random Trees (RRT)
We can incorporateAlternative Objectivesinto RRT by modifying how we compute the objectives in the select step.
Cost Function
c=current cost+cost to go
Shortest Path to Failure
current cost=distance to current node in tree
cost to go=distance to goal “as the crow flies”
Most Likely Failure
current cost=negative log likelihood of trajectory so far+C
cost to go=estimate of negative log-likelihood to go
Rapidly Exploring Random Trees (RRT)
We can incorporateAlternative Objectivesinto RRT by modifying how we compute the objectives in the select step.
Cost Function
c=current cost+cost to go
If the heuristic is admissible and the state and disturbances are
discrete, this algorithm turns into A* search!
discrete, this algorithm turns into A* search!
A heuristic is admissible if it is guaranteed to never overestimate the cost of reaching the goal state.
Rapidly Exploring Random Trees (RRT)
We can incorporateAlternative Objectivesinto RRT by modifying how we compute the objectives in the select step.
Cost Function
c=current cost+cost to go
If the heuristic is admissible and the state and disturbances are
discrete, this algorithm turns into A* search!
discrete, this algorithm turns into A* search!
A heuristic is admissible if it is guaranteed to never overestimate the cost of reaching the goal state.
Rapidly Exploring Random Trees (RRT)
We can incorporateAlternative Objectivesinto RRT by modifying how we compute the objectives in the select step.
Cost Function
c=current cost+cost to go
If the heuristic is admissible and the state and disturbances are
discrete, this algorithm turns into A* search!
discrete, this algorithm turns into A* search!
A heuristic is admissible if it is guaranteed to never overestimate the cost of reaching the goal state.
Rapidly Exploring Random Trees (RRT)
We can incorporateAlternative Objectivesinto RRT by modifying how we compute the objectives in the select step.
Cost Function
c=current cost+cost to go
If the heuristic is admissible and the state and disturbances are
discrete, this algorithm turns into A* search!
discrete, this algorithm turns into A* search!
A heuristic is admissible if it is guaranteed to never overestimate the cost of reaching the goal state.
Shortest Path
Most Likely Failure
Plan for Today
1
Tree Search
2
Heuristic Search
3
Monte Carlo Tree Search
4
Reinforcement Learning
5
Simulator Requirements
Monte Carlo Tree Search
Balances between exploration and exploitation
We will determine promising paths by maintaining a value estimate Q for each node in the tree.
Monte Carlo Tree Search
1
Select
Select a node to extend based on
a heuristic that balances between
exploration and exploitation.
a heuristic that balances between
exploration and exploitation.
2
Extend
Sample a disturbance, add it to the
tree, and propagate the results
back up the tree.
tree, and propagate the results
back up the tree.
Monte Carlo Tree Search
1
Select
Select a node to extend based on
a heuristic that balances between
exploration and exploitation.
a heuristic that balances between
exploration and exploitation.
2
Extend
Sample a disturbance, add it to the
tree, and propagate the results
back up the tree.
tree, and propagate the results
back up the tree.
Monte Carlo Tree Search
1
Select
Select a node to extend based on
a heuristic that balances between
exploration and exploitation.
a heuristic that balances between
exploration and exploitation.
2
Extend
Sample a disturbance, add it to the
tree, and propagate the results
back up the tree.
tree, and propagate the results
back up the tree.
N=8
Q=3
N=4
Q=2
N=2
Q=5
N=2
Q=11
N=3
Q=1
N=2
Q=1
N=2
Q=1
N=2
Q=13
number of children≤kNα?
yes
select it and go to
extend step
extend step
no
move to child node
that minimizes
that minimizes
Qchild−cNchildlogN
hyperparameters
Monte Carlo Tree Search
1
Select
Select a node to extend based on
a heuristic that balances between
exploration and exploitation.
a heuristic that balances between
exploration and exploitation.
N=8
Q=3
N=4
Q=2
N=2
Q=5
N=2
Q=11
N=3
Q=1
N=2
Q=1
N=2
Q=1
N=2
Q=13
number of children≤kNα?
yes
select it and go to
extend step
extend step
no
move to child node
that minimizes
that minimizes
Lower Confidence Bound (LCB)
Qchild−cNchildlogN
This is the part that balances
between exploration and
exploitation!
between exploration and
exploitation!
Monte Carlo Tree Search
Lower Confidence Bound (LCB)
Qchild−cNchildlogN
This is the part that balances
between exploration and
exploitation!
between exploration and
exploitation!
exploitation
exploration
exploration bonus
Monte Carlo Tree Search
1
Select
Select a node to extend based on
a heuristic that balances between
exploration and exploitation.
a heuristic that balances between
exploration and exploitation.
2
Extend
Sample a disturbance, add it to the
tree, and propagate the results
back up the tree.
tree, and propagate the results
back up the tree.
N=8
Q=3
N=4
Q=2
N=2
Q=5
N=2
Q=11
N=3
Q=1
N=2
Q=1
N=2
Q=1
N=2
Q=13
number of children≤kNα?
yes
select it and go to
extend step
extend step
no
move to child node
that minimizes
that minimizes
Qchild−cNchildlogN
Monte Carlo Tree Search
1
Select
Select a node to extend based on
a heuristic that balances between
exploration and exploitation.
a heuristic that balances between
exploration and exploitation.
N=8
Q=3
N=4
Q=2
N=2
Q=5
N=2
Q=11
N=3
Q=1
N=2
Q=1
N=2
Q=1
N=2
Q=13
number of children≤kNα?
yes
select it and go to
extend step
extend step
no
move to child node
that minimizes
that minimizes
Qchild−cNchildlogN
e.g. k=1, α=0.5
1(8)0.5=2.82
Monte Carlo Tree Search
1
Select
Select a node to extend based on
a heuristic that balances between
exploration and exploitation.
a heuristic that balances between
exploration and exploitation.
2
Extend
Sample a disturbance, add it to the
tree, and propagate the results
back up the tree.
tree, and propagate the results
back up the tree.
N=8
Q=3
N=4
Q=2
N=2
Q=5
N=2
Q=11
N=3
Q=1
N=2
Q=1
N=2
Q=1
N=2
Q=13
number of children≤kNα?
yes
select it and go to
extend step
extend step
no
move to child node
that minimizes
that minimizes
Qchild−cNchildlogN
11−(1)log2log8=9.26
2−(1)log4log8=0.78
13−(1)log2log8=11.26
Monte Carlo Tree Search
1
Select
Select a node to extend based on
a heuristic that balances between
exploration and exploitation.
a heuristic that balances between
exploration and exploitation.
2
Extend
Sample a disturbance, add it to the
tree, and propagate the results
back up the tree.
tree, and propagate the results
back up the tree.
N=8
Q=3
N=4
Q=2
N=2
Q=5
N=2
Q=11
N=3
Q=1
N=2
Q=1
N=2
Q=1
N=2
Q=13
number of children≤kNα?
yes
select it and go to
extend step
extend step
no
move to child node
that minimizes
that minimizes
Qchild−cNchildlogN
e.g. k=1, α=0.5
1(4)0.5=2
Monte Carlo Tree Search
1
Select
Select a node to extend based on
a heuristic that balances between
exploration and exploitation.
a heuristic that balances between
exploration and exploitation.
2
Extend
Sample a disturbance, add it to the
tree, and propagate the results
back up the tree.
tree, and propagate the results
back up the tree.
N=8
Q=3
N=4
Q=2
N=2
Q=5
N=2
Q=11
N=3
Q=1
N=2
Q=1
N=2
Q=1
N=2
Q=13
number of children≤kNα?
yes
select it and go to
extend step
extend step
no
move to child node
that minimizes
that minimizes
Qchild−cNchildlogN
e.g. k=1, α=0.5
1(4)0.5=2
Monte Carlo Tree Search
2
Extend
Sample a disturbance, add it to the
tree, and propagate the results
back up the tree.
tree, and propagate the results
back up the tree.
1
Select
Select a node to extend based on
a heuristic that balances between
exploration and exploitation.
a heuristic that balances between
exploration and exploitation.
N=8
Q=3
N=4
Q=2
N=2
Q=5
N=2
Q=11
N=3
Q=1
N=2
Q=1
N=2
Q=1
N=2
Q=13
When we add a new node to the
tree, we need to estimate its value Q.
tree, we need to estimate its value Q.
e.g. perform a bunch of rollouts and
take the average of their robustness.
take the average of their robustness.
Q=3
Monte Carlo Tree Search
2
Extend
Sample a disturbance, add it to the
tree, and propagate the results
back up the tree.
tree, and propagate the results
back up the tree.
1
Select
Select a node to extend based on
a heuristic that balances between
exploration and exploitation.
a heuristic that balances between
exploration and exploitation.
When we add a new node to the
tree, we need to estimate its value Q.
tree, we need to estimate its value Q.
e.g. perform a bunch of rollouts and
take the average of their robustness.
take the average of their robustness.
N=8
Q=3
N=4
Q=2
N=2
Q=5
N=2
Q=11
N=3
Q=1
N=2
Q=1
N=2
Q=1
N=2
Q=13
Q=3
N=1
Monte Carlo Tree Search
2
Extend
Sample a disturbance, add it to the
tree, and propagate the results
back up the tree.
tree, and propagate the results
back up the tree.
1
Select
Select a node to extend based on
a heuristic that balances between
exploration and exploitation.
a heuristic that balances between
exploration and exploitation.
When we add a new node to the
tree, we need to estimate its value Q.
tree, we need to estimate its value Q.
e.g. perform a bunch of rollouts and
take the average of their robustness.
take the average of their robustness.
N=8
Q=3
N=4+1=5
Q=2+(2−3)/5=1.8
N=2
Q=5
N=2
Q=11
N=3
Q=1
N=2
Q=1
N=2
Q=1
N=2
Q=13
Q=3
N=1
Monte Carlo Tree Search
2
Extend
Sample a disturbance, add it to the
tree, and propagate the results
back up the tree.
tree, and propagate the results
back up the tree.
1
Select
Select a node to extend based on
a heuristic that balances between
exploration and exploitation.
a heuristic that balances between
exploration and exploitation.
When we add a new node to the
tree, we need to estimate its value Q.
tree, we need to estimate its value Q.
e.g. perform a bunch of rollouts and
take the average of their robustness.
take the average of their robustness.
N=8+1=9
Q=3+(3−1.8)/9=3.13
N=4+1=5
Q=2+(2−3)/5=1.8
N=2
Q=5
N=2
Q=11
N=3
Q=1
N=2
Q=1
N=2
Q=1
N=2
Q=13
Q=3
N=1
Repeat!
Monte Carlo Tree Search
Plan for Today
1
Tree Search
2
Heuristic Search
3
Monte Carlo Tree Search
4
Reinforcement Learning
5
Simulator Requirements
Reinforcement Learning
System
Adversary
x
r
Reinforcement Learning
System
Adversary
x
r
🤔Does this set up remind you of anything?
We can use reinforcement learning
algorithms to train an adversary to
cause a system to fail!
algorithms to train an adversary to
cause a system to fail!
Reinforcement learning!
Why?Many reinforcement learning algorithms are designed to be sample efficient.
It can also generalize to different initial states.
Reinforcement Learning
Reinforcement Learning
2,500 Training Steps
35,000 Training Steps
50,000 Training Steps
65,000 Training Steps
Reinforcement Learning
Using MCTS or reinforcement learning to search for the most likely failure of a
system is often referred to as adaptive stress testing.
system is often referred to as adaptive stress testing.
Reinforcement Learning
Using MCTS or reinforcement learning to search for the most likely failure of a
system is often referred to as adaptive stress testing.
system is often referred to as adaptive stress testing.
Plan for Today
1
Tree Search
2
Heuristic Search
3
Monte Carlo Tree Search
4
Reinforcement Learning
5
Simulator Requirements
Simulator Requirements
How do I pick a falsification method?
Plan for Today
1
Tree Search
2
Heuristic Search
3
Monte Carlo Tree Search
4
Reinforcement Learning
5
Simulator Requirements