Safety Assurance for Automated Vehicles Beyond

Collision Avoidance
by
Charles J. Vorbach
B.S. Computer Science and Engineering
Massachusetts Institute of Technology, 2021
Submitted to the Department of Electrical Engineering and Computer
Science
in partial fulfillment of the requirements for the degree of
Master of Engineering in Electrical Engineering and Computer Science
at the
MASSACHUSETTS INSTITUTE OF TECHNOLOGY
May 2022
© Massachusetts Institute of Technology 2022. All rights reserved.

Author . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Department of Electrical Engineering and Computer Science
May 18, 2022

Certified by . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Daniela Rus
Deputy Dean of Research, CSAIL Director, Viterbi Professor
Thesis Supervisor

Accepted by . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Katrina LaCurts
Chair, Master of Engineering Thesis Committee
2
 Safety Assurance for Automated Vehicles Beyond Collision
Avoidance
by
Charles J. Vorbach

Submitted to the Department of Electrical Engineering and Computer Science

on May 18, 2022, in partial fulfillment of the
requirements for the degree of
Master of Engineering in Electrical Engineering and Computer Science

Abstract
Each year, automotive crashes cause thousands of deaths and injuries. Autonomous
safety systems have the potential to greatly reduce this tragic loss of life and improve
safety, but such systems must meet existing requirements for automotive certification.
Particularly, active safety systems must designed to comply with the Automotive
Safety Integrity Level risk classification scheme described in the ISO 26262 standard.
In this thesis, I design a system using redundant components to independently
enforce safety requirements across parallel software supervisors within an autonomous
vehicle planning pipeline. I use Hamilton-Bellman-Jacobi reachability analysis to
provide new guarantees for safe navigation on public roadways. I create new and
extend existing safety modules to independently verify collision avoidance, obedience
to traffic rules, and vehicle lane discipline. This project provides theoretical proof
of safety and implements control methods within Nvidia’s DriveWorks autonomous
vehicle framework.

Thesis Supervisor: Daniela Rus

Title: Deputy Dean of Research, CSAIL Director, Viterbi Professor

3
4
Acknowledgments
I deeply thank my family for their endless love and aid throughout my time in school.
There were many difficult times which I could not have overcome without you all.
You will forever be in my heart.
I want to thank my advisors Daniela Rus, Ramin Hasani, Saman Amarasinghe,
Julia Ng, and Rotem Aviv for providing the resources and mentoring necessary to
complete this Masters thesis. I have learned an incredible amount from your experi-
ence and guidance.
I deeply appreciate the generosity of my coworkers Yunfei Shi, Hon Leung Lee,
Tom Sun, and others for sharing their deep understanding of autonomous systems
and for their advice throughout this project. I thank you for the lifelong skills I have
developed working with you.
I am grateful to all my professors during my undergraduate and graduate pro-
grams, especially Russ Tedrake, John Tsitsiklis, William Freedman, Howard Schrobe,
Mauricio Karchmer, Zachary Abel, and many others for their tireless instruction.
Thank you to all the others I have learned from and grown with over the years.
Alexandra Upton, Aaron Ray, Alexander Amini, Nick Stathas, Max Halkenhauser,
Ethan Perrin, Kieran Strobel, Josh Smailes, Thomas Maldonado, Sijmen Huizenga,
and so many others too numerous to name.

5
6
Contents

1 Introduction 13
1.1 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.5 Thesis Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2 Background 17
2.1 ASIL Standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 ASIL Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3 Hamilton-Bellman-Jacobi Reachability Analysis . . . . . . . . . . . . 21
2.4 Additional Related Work . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.4.1 Lyapunov Analysis . . . . . . . . . . . . . . . . . . . . . . . . 23
2.4.2 Motion Planning under Traffic Regulations . . . . . . . . . . . 25
2.5 Definition of Safety . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.6 Previous Work at Nvidia . . . . . . . . . . . . . . . . . . . . . . . . . 26

3 System Representations and Design 29

3.1 Hyperion Vehicle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.1.1 Coordinate Systems . . . . . . . . . . . . . . . . . . . . . . . . 30
3.1.2 Obstacle Representation . . . . . . . . . . . . . . . . . . . . . 32
3.1.3 Lane Representation . . . . . . . . . . . . . . . . . . . . . . . 33
3.1.4 Wait Element Representation . . . . . . . . . . . . . . . . . . 35

7
 3.2 Unified Vehicle Model . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.2.1 Kinematic Bicycle Model . . . . . . . . . . . . . . . . . . . . . 36
3.2.2 Dynamic Bicycle Model . . . . . . . . . . . . . . . . . . . . . 37

4 Safety Architecture 41
4.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.1.1 Planning Pipeline . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.1.2 Safety Architecture . . . . . . . . . . . . . . . . . . . . . . . . 43
4.2 Safety Supervisor Modules . . . . . . . . . . . . . . . . . . . . . . . . 45
4.2.1 Safety Force Field . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.2.2 Control Projection Module . . . . . . . . . . . . . . . . . . . . 48
4.2.3 Collision Detector . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.3 Virtual Obstacle Generator . . . . . . . . . . . . . . . . . . . . . . . 50
4.3.1 Road Boundaries . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.3.2 Wait Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.4 Trajectory Selector Module . . . . . . . . . . . . . . . . . . . . . . . 54
4.4.1 Trajectory Selection . . . . . . . . . . . . . . . . . . . . . . . 55

5 Analyzing Safety and Results 57

5.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.1.1 Notes on Simulation Systems . . . . . . . . . . . . . . . . . . 57
5.1.2 Notes on Test Cases . . . . . . . . . . . . . . . . . . . . . . . 59
5.2 ASIL Decomposition Analysis . . . . . . . . . . . . . . . . . . . . . . 60
5.3 Correlation of Parallel Pathway Errors . . . . . . . . . . . . . . . . . 63
5.4 Profiling Safety Force Field Errors . . . . . . . . . . . . . . . . . . . . 65
5.5 Profiling Control Projection Errors . . . . . . . . . . . . . . . . . . . 70

6 Conclusion 77
6.1 Lessons Learned . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
6.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

A Safety Goals 81

8
List of Figures

2-1 ASIL decomposition of an ASIL D component using two ASIL B com-

ponents. In this situation, the independent and redundant ASIL B
components B1 and B2 are reduced by a logical OR. . . . . . . . . . 20

3-1 ISO 8855 intermediate axis coordinate system. Coordinate basis {𝑋, 𝑌, 𝑍}
is attached to the vehicle body. Coordinate basis {𝑋𝐸 , 𝑌𝐸 , 𝑍𝐸 } is
attached to the static environment. An additional coordinate basis
{𝑋𝑉 , 𝑌𝑉 , 𝑍𝑉 } is constructed from the projection of the 𝑋 and 𝑌 vec-
tors onto the ground plane [1] . . . . . . . . . . . . . . . . . . . . . . 31
3-2 A simple example of three polyline lanes projected onto a 𝑒ˆ3 normal
plane. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3-3 Bicycle Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

4-1 Safety Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4-2 ASIL Decomposition of Safety Architecture . . . . . . . . . . . . . . . 44

5-1 Matrix showing ASIL Rating of each safety goal at within each com-
ponent of the autonomous pipeline. The safety goals are those from
Table A.1. The modules are the World Model (WM), Safety Procedure
Generator (SPG), Behavior Planner (BP), Virtual Obstacle Generator
(VOG), Collision Detector (CD), Safety Force Field (SFF), Control
Projection (CP), and the Trajectory Selector (TS). . . . . . . . . . . 60

9
5-2 Backwards-traced ASIL dependency tree showing the modules required
to enforce Safety Goal 1. Dashed lines indicate redundant ASIL de-
composed dependencies. . . . . . . . . . . . . . . . . . . . . . . . . . 62
5-3 Number of road scenario tests passed by (1) the new safety architec-
ture, (2) the original planning architecture, (3) the Safety Force Field
alone pipeline, and (4) the Collision Detector alone pipeline. Note that
n=449 as 9 tests created after the original architecture are excluded. . 64
5-4 SFF scenario graphical interface. Note the colored non-expanded claimed
sets of each vehicle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5-5 Head-on collision false positive tolerance . . . . . . . . . . . . . . . . 67
5-6 Head-on collision false positive tolerance . . . . . . . . . . . . . . . . 68
5-7 Head-on collision false positive tolerance . . . . . . . . . . . . . . . . 69
5-8 Reference and predicted trajectories for the downstream controller in
sudden halt scenarios at different initial speeds. . . . . . . . . . . . . 71
5-9 Control Projection and downstream commanded accelerations in sud-
den halt scenarios at different initial speeds. . . . . . . . . . . . . . . 72
5-10 Reference and predicted trajectories for the downstream controller in
lane change scenarios at different initial speeds. . . . . . . . . . . . . 73
5-11 Control Projection and downstream commanded accelerations in lane
change scenarios at different initial speeds. . . . . . . . . . . . . . . . 74
5-12 Trajectory-based flat controller and downstream commanded acceler-
ations in lane change scenarios at different initial speeds. . . . . . . . 75

10
List of Tables

2.1 Previously determined maximum permissible failure rates for the au-
tonomous vehicle planning software components for each ASIL. . . . . 18

5.1 Number of test cases passed both pipelines, failed by only one pipeline,
and failed by both pipelines. . . . . . . . . . . . . . . . . . . . . . . . 63
5.2 Timeline for false positive tolerance measurement. . . . . . . . . . . . 66

A.1 Primary Safety Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

11
12
Chapter 1

Introduction

1.1 Motivations
Driving is one of the most dangerous activities undertaken on a daily basis. Figures
from the National Highway Traffic Safety Administration recorded 36,096 fatalities
and 2,740,000 injuries in motor vehicle traffic crashes in 2019 alone [2]. Despite
numerous efforts to improve safe driving practices, raise awareness, and install modern
safety systems, up to 94% of these crashes may be caused by driver error [3].
Developments in sensor and computational technology, which are deployed in ve-
hicles with autonomous or semi-autonomous driving features, raise the possibility
of developing active safety systems which are not affected by driver distraction or
error. The Nvidia DriveWorks system seeks to create autonomous software which
can operate in parallel with or independently of a driver to guarantee safety for all
road scenarios. This software must create a pipeline of processing from raw sensor
perception through state estimation, planning, and finally vehicle control. Addition-
ally, it must comply with existing standards for determining road safety of electronic
automobile components.
Developing an Automotive Safety Integrity Level (ASIL) certifiable safety archi-
tecture for this autonomous planning system will allow the software to be widely
deployed on existing and newly produced vehicles. The safety architecture created
for this thesis project will enable rigorous safety evaluation of the autonomous soft-

13
ware using safety analysis methods employed by existing standards. Finally, the
design of this safety architecture will speed the introduction of active safety systems
which have the potential to save lives.

1.2 Problem Statement

The focus of this work is to develop a new safety architecture which enables the
highest ASIL certification of the Driveworks autonomous planning software system.
This requires both organizing the modules of the system in a manner which permits
rigorous safety certification and creating new modules which guarantee additional
safety goals. This project must work within the existing patterns of ASIL analysis as
well as rely on the existing interfaces of the autonomy software.
Several existing safety monitors, namely the Safety Force Field and Collision De-
tector modules, must be modified and relocated in the planning pipeline to achieve
higher reliability through redundant operation of these components. New modules
must be created to broaden the safety guarantees enforced by the system. Particu-
larly, new safety goals must be added to prevent the violation of traffic wait signals
and to maintain lane discipline. These new modules must not compromise the overall
ASIL of the autonomous planning system.
The direct application of this problem is the certification and deployment of the
autonomous software in commercial vehicles. ASIL certification is an industry recog-
nised standard which allows car manufacturers to have greater confidence in the
safety of vehicles incorporating an ASIL certified system. Further, this project will
use reachability analysis to certify the planning system’s obedience to traffic rules.
It will be an implementation of methods using escape maneuvers and approximate
value functions to certify that the autonomous agent avoids unsafe states - including
states which break traffic wait rules or dangerously violate lane discipline.

14
1.3 Challenges
The ASIL analysis of an automotive electronic system is a rigorous process which
examines the failure modes of each component and the effects of component failures
on the safety goals for the system. Producing software which can achieve the highest
ASIL is difficult, especially for a task as complex as autonomous motion planning.
Further increasing the challenge of this project, existing safety monitors such as the
Safety Force Field and Collision Detector modules are only partially reliable. Due
to these modules’ occasional failures and because of the difficulty in certifying the
hardware these module execute on, these safety monitors cannot achieve the highest
ASIL rating independently.
Any new safety architecture which achieves the highest ASIL must employ re-
dundancy to maintain a higher level of reliability than its constituent parts. This
will require careful design to avoid single points of failure. Analyses in simulation
and using real-world data must justify the redundancy and safety of such an architec-
ture’s components. Additionally, the architecture must find a method of transforming
new traffic rule safety guarantees into forms which can be enforced by existing mod-
ules. This transformation cannot weaken the strong theoretical arguments for safety
grounded in reachability analysis performed by the current safety monitors nor limit
the ASIL of the combined planning system.

1.4 Contributions
In this thesis, I have designed and implemented a safety architecture which allows for
redundant verification of safety requirements. This architecture required the creation
of multiple new modules including the Virtual Obstacle Generator, Control Projec-
tion, and Trajectory Selector. These new modules perform tasks such as construction
of avoid sets for Hamilton-Bellman-Jacobi (HBJ) reachability analysis, understand-
ing and enforcing traffic signals, detection of drivable areas, and reduction of parallel
safety supervisors. The new Virtual Obstacle module also allows the transformation

15
of abstract lane data and wait conditions into constraints on the state space which
can be enforced with existing safety supervisors.
Several additional modules were altered or relocated in the planning pipeline,
including the Safety Force Field, Collision Detector, Behavior Planner, and the Safety
Procedure Generator. Changes to these modules allow for new safety guarantees on
collision avoidance, simulation of a set of evasive maneuvers designed to halt the
vehicle, and new methods for filtering unsafe trajectories.
Finally, I organize the new and existing modules in a manner which allows for the
highest ASIL certification of the autonomous planning system. This is performed via
ASIL decomposition wherein multiple redundant safety modules with independent
methods of enforcing safety goals are used to synthesis a single higher ASIL system.

1.5 Thesis Outline

This thesis is divided into six chapters. In this first chapter, I describe the motiva-
tions for this thesis project and its contributions to designing an autonomous safety
system. In the second chapter, I provide the necessary background information on
ASIL certification, ASIL decomposition, and HBJ reachability analysis. The third
chapter outlines the autonomous software system and how the new safety architec-
ture is incorporated into the planning pipeline. The fourth chapter documents the
new safety architecture with a particular focus on the Virtual Obstacle module and
on other modules which enable the autonomous planning system’s ASIL decomposi-
tion. The fifth chapter validates the ASIL design, justifies the independence of safety
monitors, and profiles the errors of several safety modules. In the sixth and final
chapter, I summarize the lessons learned from this project and improvements to the
system which can be implemented in the future.

16
Chapter 2

Background

This chapter describes the background and related work in both robust control HBJ
reachability analysis as well as in safety certification and decomposition. It also
documents previous work completed at Nvidia.

2.1 ASIL Standard

The ISO 26262 standard describes a method for evaluating the functional safety of
electronic systems in road vehicles. The standard uses a classification scheme called
Automotive Safety Integrity Levels (ASILs) which categorize a hazard analysis and
risk assessment. The ASILs of the standard are ASIL A, ASIL B, ASIL C, and ASIL
D which rate a component’s capability of meeting a safety goal from lowest to highest
respectively [4].
Each of these ASILs is qualitatively determined using three variables: severity,
exposure, and controllability of a component failure. The severity measures the phys-
ical danger of a failure to the occupants of the vehicle. The exposure captures the
likelihood of operating scenarios which could lead to a failure. The controllability
evaluates the ability of the driver to intervene to avoid danger in the case of a fail-
ure. These three variables are used to qualitatively evaluate potential hazards caused
by electrical component failures as well as to constrain the permissible likelihood of
failure by any component.

17
 The non-quantitative evaluations of the standard are informed by the precise
equation for expectation, ∫︁
E[X] = X𝜔 𝑑P(𝜔) (2.1)
Ω

where X is a random variable quantifying the injury to vehicle occupant over out-
comes 𝜔 drawn from sample space Ω with a probability density function P(𝜔). The
determination of ASIL level is a function,

ASIL = F(Severity, Exposure, Controllability) (2.2)

which can be compared to the ISO 26262 standard’s definition of risk,

Risk = Severity · Exposure · P(Failure | Exposure) (2.3)

In the context of an autonomous vehicle, failure of the planning software could lead
to the most severe injury to occupants via collision. The planning software could fail
whenever it is enabled which could be most operating conditions. Finally, at the SAE
vehicle autonomy levels 2 and 3 targeted by the planning system, the driver may be
inattentive and struggle to control a system failure.
For the listed reasons, the planning software must be designed to meet the highest
ASIL D. In an ASIL analysis completed prior to this thesis, the maximum allowable
probabilities of failure given exposure were found for the planning system. These are
listed in Table 2.1.

ASIL A B C D
Failures/Hours of Exposure 10−2 10−4 10−6 10−8
Table 2.1: Previously determined maximum permissible failure rates for the au-
tonomous vehicle planning software components for each ASIL.

18
2.2 ASIL Decomposition
The requirements to meet ASIL D certification of the planning system are stringent.
The required reliabilty of a component increases exponentially with its ASIL. As is
shown in Table 2.1, no more that one failure per 108 hours of operation of the planning
software can be tolerated to meet ASIL D. Given the numerous components of the
planning system and wide variety of road scenarios possible, demonstrating this high
degree of reliability from first principles or testing is difficult and expensive.
This thesis seeks to reduce the effort required to achieve ASIL D certification by
designing a software architecture for the autonomous planning system which uses in-
dependent, redundant modules. This design removes single points of failure from the
planning pipeline so that single failures do not lead to a complete loss of safety. The
redundant design enables limp-mode capability which permits higher ASIL certifica-
tion through ASIL decomposition.
As described in ISO 26262-1:2018, ASIL decomposition is defined as “Apportion-
ing of redundant safety requirements to elements, with sufficient independence, for
the same safety goal. The objective being reducing the ASIL of the redundant safety
requirements that are allocated to the corresponding elements.” ASIL decomposition
allows a higher ASIL to be enforced using independent and redundant lower ASIL
components. This is permitted so long as the design satisfies the following require-
ments:

1. The events of failure for each lower ASIL component are “sufficiently inde-
pendent.” Mutual independence is sufficient, but not necessary to meet this
requirement.

2. The output of the parallel evaluations of the lower ASIL components can be
reduced by a component certified at the higher ASIL such that if at least one
component does not fail then the reduced output does not violate the safety
goal.

3. The probability of failure for the whole system is less than the permissible

19
 probability of failure for the higher ASIL component using the multiplication
rule for probabilities under independence.

In the context of the autonomous planning system, the ASIL decomposition pro-
cess allows two independent ASIL B components to be synthesised into a single ASIL
D component. This is permitted where the probability of failure of both independent
ASIL B components (as listed in Table 2.1) is the same as the failure of a single
ASIL D component as computed using the multiplication rule for probabilities under
independence and where the system’s output is safe so long as one of the components
does not fail.

Figure 2-1: ASIL decomposition of an ASIL D component using two ASIL B compo-
nents. In this situation, the independent and redundant ASIL B components B1 and
B2 are reduced by a logical OR.

By performing ASIL decomposition on the safety supervision portions of the au-

tonomous planning pipeline, the software system can be divided into independent
and redundant pathways of ASIL B components. These ASIL B components may
be certified with respect the design’s safety goals with dramatically less effort than
equivalent ASIL D components since ASIL B components are permitted one failure
per 104 hours of operation. This allowable rate of failure is four orders of magni-
tude greater than for an ASIL D component. The parallel pathways of the designed
system may then be reduced in a manner which respects the requirements of ASIL
decomposition. The architecture designed in this project allows the whole planning
system to achieve ASIL D certification with substantially less testing effort.
The goal of the autonomous system is to achieve ASIL D certification of the safety
requirements summarized in Appendix A.1.

20
2.3 Hamilton-Bellman-Jacobi Reachability Analysis
Hamilton-Bellman-Jacobi (HBJ) reachability analysis is a important method for guar-
anteeing the safety of dynamical systems. The autonomous planner performs reach-
ability analysis in its Safety Force Field module. The Safety Force Field computes
the forward-reachable tube of states of all pairs of a road obstacle (including other
agents) and the ego vehicle given that both members of the pair execute a control
policy from a set of safety procedures. Each slice of this tube is the set of states which
the system can arrive at given the time-varying constraints at a time 𝑡.
This thesis project will extend the work of the original Safety Force Field system
from [5] as well as the reinterpreted control theoretic formulation of [6]. In compar-
ison to the original system, this project will increase the scope of the Safety Force
Field by including non-vehicle agents, guaranteeing important traffic safety rules, and
creating a wait condition controller. This is performed by transforming these safety
requirements into obstacles avoidance problems - that is constructing HBJ avoid sets
which do not permit the vehicle to violate any safety goal. The details of the process
are described in Section 4.2.1.
HBJ reachability is long-standing approach to constructing certificates of safety
for dynamical systems using dynamic programming. In [7], HBJ reachability analysis
is performed to certify safety for two-player differential games. For collision avoid-
ance, this is a pursuit-evasion game which prevents collision for any action taken by
the pursuing vehicle. This adversarial approach can lead to certifiably safe if pos-
sibly overly conservative planning. The use of a HBJ partial differential equation,
variational inequality, or mesh discretization in evaluation of unsafe sets causes an
exponential increase in the computational requirements with the dimension of the
state space. For autonomous vehicle planning, reachability analysis for pairs of road
agents is feasible for modest vehicle state representations. However, considering the
joint state of multiple road actors in the evaluation of avoid sets quickly becomes
computationally impossible.
Multiple recent works have developed techniques to improve the scaling of HBJ

21
reachability methods. [8] approaches the reachability in multi-agent motion planning
by prioritizing agents in planning. The trajectories of higher priority vehicles are
considered moving obstacles for lower priority vehicles. This relaxation allows the
HBJ reachability problem to be broken into sequential stages each of which is tractable
individually. The computational effort scales linearly with the number of vehicles
instead of exponentially. The work applies this approach to the planning of flight
trajectories for autonomous aircraft but the method can be applied almost directly
to autonomous road vehicles. Indeed, the pairwise composition of Safety Force Field
reachability set constraints is closely related to this approach.
[9] applies machine learning to solve reachability problems without requiring com-
putational effort which grows exponentially with the dimension of the state space.
Instead of solving a HBJ partial differential equation over a discretized state mesh,
a deep neural network is trained to learn a parameterized approximation of the so-
lution. This approach leverages self-supervised training methods from existing work
on neural partial differential equation solvers. The approximate solution can be used
to check control actions for safety or even reconstruct a tube of unsafe sets. Like
traditional reachability approaches, this method solve adversarial games to certify
safety no matter the actions of other road agents. [9] demonstrates this by evaluating
a trained network on a high dimensional multi-vehicle collision problem.
An issue with this adversarial safety certification used in many reachability analy-
ses is its poor representation of typical driving behavior. Adversarial games represent
collision avoidance as a pursuit-evasion game between two or more agents. Real-world
drivers do not behave in this way - they are not seeking a collision. This unrepresen-
tative modeling approach can lead to overly conservative or even unsolvable motion
plans. [10] examines a partial-cooperative model instead. Planning occurs over two
horizons: an adversarial phase and then a cooperative phase. This model of limited
cooperation attempts to avoid overly conservative planning.
One other approach to modeling limited cooperation uses an assumption of sym-
metric emergency maneuvers between road agents. In [11], only a single “escape pro-
cedure” is required to remain collision free between the ego and other road agents. By

22
simultaneous executing a reference trajectory tracking controller and a HBJ safety-
preserving controller, a combined planner can take the minimum intervention required
to avoid entering the unsafe set. The Safety Force Field can operate in a similar mode,
adjusting control actions to prevent entering an unsafe set. In the new safety archi-
tecture, the Safety Force Field is used as monitor on trajectories instead.
In comparison to these other works on HBJ reachability, this thesis project ex-
tends the safety guarantees of reachability analysis beyond collision avoidance by
transforming traffic signals and road boundaries into “virtual obstacles” which can be
added to the avoid set.

2.4 Additional Related Work

This thesis draws on other previous works from the well-developed field of safety cer-
tification of dynamical systems. The safety monitors such as the Safety Force Field
or Collision Detector modules as well as other components of the safety architec-
ture should be considered in the context of the many existing works on autonomous
planning, provable safety, and enforcement of traffic regulations.

2.4.1 Lyapunov Analysis

Much productive research on the safety of controlled dynamical systems relies on

Lyapunov analysis. The identification of a Lyapunov function for a dynamical system
provides a great deal of information about the future behavior of that system. The
properties of a Lyapunov function are a certificate of the local or global stability of the
system and can verify convergence to a fixed point. The sublevel set of a Lyapunov
function is an invariant set of the dynamical system. If avoid states are outside of
that sublevel set, then the safety of the system can be certified.
A great advantage of Lyapunov functions is that such functions can be searched for
numerically. [12] uses a relaxation on the positive definite requirement of a Lyapunov
function to perform this search. Instead, the Lyapunov function is required to be
a sum-of-squares polynomial which are more computationally tractable to identify.

23
[12] demonstrates how sum-of-squares Lyapunov functions can be constructed even
for nonlinear systems with equality, inequality, and integral constraints. Identifying
a sum-of-squares Lyapunov function 𝑝(𝑥) is equivalent finding a positive semidefinite
matrix 𝑄 for which 𝑝(𝑥) = 𝑍 𝑇 (𝑥)𝑄𝑍(𝑥) for a vector of monomial features 𝑍(𝑥) =
[𝑓1 (𝑥), ....𝑓𝑛 (𝑥)]𝑇 . Searching for such a 𝑄 can be performed by solving a semidefinite
program using one of the many open source or commercial available solvers.
Numerical searches for Lyapunov functions can be extended to time-varying prob-
lems, namely trajectory stabilization. In [13], sequentially composed linear controllers
are used to stabilize to a reference trajectory. For each controller, a sum-of-squares
optimization is solved to find a polynomial Lyapunov function with an invariant set
around the controller’s fixed point. These “funnels” of invariant sets are composed
and used to compute a backwards reachable set which maximizes the set of initial
states which reach a goal set. However, from a given initial state the funnels can also
be composed to compute the forward reachable set of the system. If this forward
reachable set has no collision with an avoid set, than the controlled trajectory is safe.
This technique allows for time-varying and uncertain dynamics.
The close relationship between reachability and Lyapunov analysis is shown in
[14]. This work generates motion plans by precomputing a library of trajectories for
a nonlinear dynamical system. In addition, sequential locally stabilizing controllers
are constructed to minimize the forward reachable sets using invariant funnels simi-
larly to [13]. These forward reachable sets are solved for under bounded disturbances
and uncertainty in the environment, model parameters, state, etc. Given the forward
reachable sets, each trajectory can be checked for collision against an unsafe set or
selected based on their vulnerability to disturbances. While this work only demon-
strates this method in simulation, it has many similarities to the use of a set of safety
procedures and forward reachability checking in the Safety Force Field module.
Funnel-based reachability motion planning techniques are subsequently employed
in [15] which develops safe motion plans in real time. Trajectories are selected from
a library of precomputed and composable controllers with known forward reachable
funnels. The method is validated in hardware experiments on fixed-wing flying robots.

24
The resulting motion planning system is shown to efficiently navigate through clut-
tered environments and follow complex reference trajectories in a manner which is
provably safe.
Even motion planning systems based on deep learning techniques admit Lya-
punov reachability analysis. Compared to traditional control techniques, deep rein-
forcement methods frequently lack provable guarantees of stability or reachability.
In [16], a neural-network controller is simultaneously trained with a neural-network
Lyapunov function certifying its stability. The verification of the Lyapunov condition
is performed using a mixed-integer linear program and allows the approximation of
the function’s region of attraction. The application of Lyapunov analysis to neural
networks is a productive area with other works such [17] which learns a Lyapunov
function for a controller maximizing the invariant set and verifying the Lyapunov
conditions using dense sampling that proves safety for a known Lipschitz constant of
the learned function.

2.4.2 Motion Planning under Traffic Regulations

In addition to the safety certification of trajectories, this project also draws inspira-
tion from important related work on optimal control under the constraints of traffic
rules. [18] develops a framework for the prioritization and implementation of traffic
rules in an optimal controller. The recursive rule priority structure used allows for
less important traffic regulations, such as maintaining a speed limit, to be enforced
only after more important rules such as avoiding collisions. The rule constraints are
directly incorporated into the optimal control problem. This work also develops a
technique for testing if a trajectory satisfies the traffic rules. Such a pass/fail evalu-
ation is employed in the filtering of the Trajectory Selector module.
Developing methods for enforcing and prioritizing traffic rules remains a difficult
problem with multiple approaches. [19] creates a planner for an autonomous vehicle
which trades off between completing scheduled rides on-time and obeying road rules.
By encoding these traffic rules in a temporal logic, a receding horizon planner can
evaluate a trajectory with the provably minimal number of rules violations. The work

25
combines a routing planner which selects road segments of a transportation network
with a local RRT* controller which plans motion through the local road segments.
Beyond specific and legally proscribed traffic regulations, there are additional so-
cially understood rules for driving. [20] develops a method of adapting autonomous
planning based on interaction with human road users. Driving is modeled as a non-
cooperative game in which agents attempt to maximize the sum of a reward function
over time. Human’s social preferences are estimated based on their driving behavior
using a learned model. Using these estimates of human driver’s social value orienta-
tion, the autonomous agent can take cooperative actions to avoid overly conservative
driving and improve the flow of traffic. Solving for the utility maximizing actions
based on the estimated decision-making model of human drivers requires finding a
Nash equilibrium for the optimal control policy.

2.5 Definition of Safety

As used in the safety architecture, the term safe indicates a state of the ego vehicle,
other road agents, and the world in which the safety goals listed in Table A.1 are not
violated. The most important safety goal is collision avoidance, but traffic signals,
road boundaries, and other safety requirements must also be respected to ensure
safety.

2.6 Previous Work at Nvidia

This thesis is completed at Nvidia Corporation. The project relies on previous work
performed at Nvidia. Particularly, it depends the creation of the DriveWorks au-
tonomous software pipeline including perception processing, state estimation, lane-
reconstruction, trajectory generation, and trajectory stabilization control [21].
Some pre-existing software modules were altered and incorporated into the safety
architecture, including the Safety Force Field, Collision Detector, Behavior Planner,
and Safety Procedure Generator components. Additionally, this thesis relies on pre-

26
vious safety concepts for the autonomous planning system developed at Nvidia.

27
28
Chapter 3

System Representations and Design

The safety architecture designed in this thesis was implemented for use in an existing
autonomous software system. This chapter describes the existing conventions, data
representations, and hardware available. It also explains how the safety architecture
is integrated into the autonomy software.

3.1 Hyperion Vehicle

The Hyperion hardware platform is a reference architecture specifying configurations
of sensors and computational resources compatible with the autonomous software.
The autonomous software is designed to function with subsets of the sensors available
in this specification with degraded performance. The perception and state estimation
portions of the autonomous software pipeline directly interface with hardware and
provide an application programming interface called the World Model. The planning
modules, which the new safety architecture organizes, consume the World Model
representations. This World Model allows the safety architecture to abstract away
many of the details of the specific hardware configuration.
Some configuration details, such as the specific computational hardware or those
affecting the vehicle dynamics, cannot be abstracted. The safety architecture is eval-
uated on 2018 Ford Fusion test vehicles. The Unified Vehicle Model described in
Section 3.2 is capable of simulating the dynamics of many common vehicles depend-

29
ing on the parameters selected. Careful clear-box system identification was previously
used to determine the parameters which best represent the 2018 Ford Fusion vehicle.
These parameters are used throughout the implementation of this thesis, though in
principle any Hyperion-compatible vehicle could be modeled.
Computation is performed on an Nvidia Drive AGX Pegasus board which incor-
porate two Xavier systems-on-chip and two Turing graphics processing units (GPUs).
Safety modules which perform computations on the GPU, including the Safety Force
Field and Collision Detector modules, use the Compute Unified Device Architecture
(CUDA) software interface to this hardware. A prior design choice to only certify
GPU hardware to ASIL B restricts any module which performs GPU computations
to at most an ASIL B certification. This constraint must be considered in the design
of the safety architecture.
The planning software considers the Hyperion vehicle which it is running on and
whose actions it can control to be the ego vehicle or the ego agent. Each complete
cycle of execution of the autonomous software pipeline is considered a single frame.
The frame rate is key performance metric as it limits the speed at which the planning
software can react to changing road conditions.

3.1.1 Coordinate Systems

All perceived World Model data structures are communicated in a vehicle body fixed
coordinate system. The 3D coordinate system is attached to the body frame of the
vehicle and therefore depends on the pose of the vehicle at a particular time. All
entities such as obstacles, trajectory points, and lane graph vertices are specified
relative to pose of the vehicle at the timestamp included in the entity representation
structure.
The coordinate system is a right-handed Cartesian coordinate system which has
its origin at the projection of the center of the rear axle on to the ground plane at
the lowest point of the tires. The 𝑒ˆ1 basis vector is aligned with the longitudinal axis
of the vehicle and points towards the front of the vehicle. The 𝑒ˆ2 basis vector points
towards the the left side of the vehicle. The final basis vector 𝑒ˆ3 points in the skyward

30
Figure 3-1: ISO 8855 intermediate axis coordinate system. Coordinate basis {𝑋, 𝑌, 𝑍}
is attached to the vehicle body. Coordinate basis {𝑋𝐸 , 𝑌𝐸 , 𝑍𝐸 } is attached to the
static environment. An additional coordinate basis {𝑋𝑉 , 𝑌𝑉 , 𝑍𝑉 } is constructed from
the projection of the 𝑋 and 𝑌 vectors onto the ground plane [1]
.

direction.
The coordinate system complies with the ISO 8855 vehicle coordinate system
definition such that the origin is located at the projection of the middle of the rear
axle on the ground plane when the vehicle is at rest. This reference point is assumed
fixed with respect to the vehicle body and does not move as the sprung mass of the
vehicle shifts during acceleration.
A consequence of the selection of a body-fixed coordinate system is that points
fixed to the static road move with respect to the World Model coordinate system as
the vehicle moves with respect to the road. After each planning frame, coordinates
must be updated by a filter combining the physically modeled motion of the vehicle
with new measurement data.
This body-fixed system of coordinates is preferred to a static world frame because

31
it avoids accumulation of errors, allows the highest accuracy incorporation of position
information, and is natural to use in the context of safety and motion planning. For
these reasons and to work within existing conventions the designed safety architecture
uses the same coordinates.

3.1.2 Obstacle Representation

Obstacles, including other vehicles, pedestrians, and physical obstructions, are rep-
resented by the planner using data structures. These structures include information
on the obstacle state, class, and metadata such as the time of detection. The data
structure also includes an obstacle boundary, a polyline composed of line segments
connected at three-dimensional vertices.
The ego vehicle is defined to have a bounding volume which is the volume of
the largest rectangular cuboid which (1) has faces having normal vectors which are
elements of the coordinate basis or their additive inverses and (2) contains every
point on the vehicle body. The safety systems consider a collision with an obstacle
to have occurred whenever this bounding volume has a non-empty intersection with
an obstacles’s boundary.
To minimize computational effort, collision checking is frequently performed after
projecting an obstacle’s boundary and the ego vehicle’s bounding volume onto the 𝑒ˆ3
normal plane. The projection of the bounding volume is called the vehicle footprint.
To remove spurious collisions, such as those which occur when the bounding volume
and the obstacle are separated along the 𝑒ˆ3 direction, this method pre-filters obstacles
by removing obstacles which have a vertical coordinate which is outside the interval
within the bounding volume. Since the 𝑒ˆ1 and 𝑒ˆ2 normal faces of the bounding volume
are orthogonal to the 𝑒ˆ3 vector, it can observed that any collision after projection is
also a collision before projection if there is no vertical separation.
These obstacles are generated from perception data by the state estimation system
and consumed by the planning and safety modules via the World Model. An obsta-
cle’s state is updated each frame, particularly as the obstacle moves with respect to
the body-fixed coordinate system. The modules designed for this project consume

32
obstacle information to make safety decisions.

3.1.3 Lane Representation

Like obstacles, lanes are represented using data structures produced by the upstream
state estimation system from perception data. Lane may additionally incorporate
information from prerecorded maps. These structures include a graph of all lane edge
positions, lane connections, and regions of contention.

Figure 3-2: A simple example of three polyline lanes projected onto a 𝑒ˆ3 normal plane.

A lane has left, right, and center curves which are represented as sequences of edges
or as polylines with three-dimensional vertices. The surface of the lane is composed of
convex combinations of lane edge points {𝑡·𝑙𝑙 (𝑠)+(1−𝑡)·𝑟𝑙 (𝑠) | ∀𝑡 ∈ [0, 1], ∀𝑠 ∈ [0, 𝑆]}
where 𝑙𝑙 (𝑠) and 𝑟𝑙 (𝑠) are the arc length parameterized left and right curves of a lane
𝑙 and 𝑆 is the total arc length. Other road data, such as curbs, traffic lines, or road
boundaries, may be included as single sequences of edges forming polyline curves.
The lane data structures also contain a classification of edge types including physical
barriers, curbs, gore areas, road boundaries, and painted traffic lines.
A positive aspect of this representation is that it makes few assumptions about
the nature of lane edges. This flexibility comes with trade-offs since it creates some

33
unexpected edge cases which must be handled. One such edge case, revealed in
testing, occurs when the ego vehicle changes lanes. Small errors in the estimates of
the position of lane edges create gaps between adjacent lanes. When the ego vehicle
moves from one lane to another, it can pass over one of the gaps and briefly pass out
of any lane. The planning software must be robust to this edge case and not assume
that the vehicle always exists in a lane. Similarly, lane edges may self-intersect or
form complex polygons when projected onto the 𝑒ˆ3 normal plane.
The discovery of these cases during testing required changing the lane detection
algorithm. Previously, polygons were constructed from lane’s left and right polyline
edges projected onto the 𝑒ˆ3 normal plane. Then the polygon containing the (0, 0, 0)
ego origin point was found using the crossing number ray casting point-in-polygon
algorithm [22]. The lane whose edges contained the ego origin was used in the planning
software as the “ego lane” for purposes such as lane-keeping. The existence of gaps
between lanes and complex polygon lane areas created bugs in this method.
During the creation of the safety architecture, the lane detection function was
reimplemented using the winding number ray casting point-in-polygon algorithm [22].
To minimize computational requirements, this check is cached for the duration of each
frame. When the vehicle is not in any lane, the lane whose edge is nearest to the ego
vehicle is selected by performing the following optimization,

arg min ||𝑐𝑙 (𝑠)||2 , ∀𝑠 ∈ [0, 𝑆] (3.1)

𝑙∈𝐿

where 𝐿 is the set of lanes and 𝑐𝑙 (𝑠) is the arc length parameterized center edge curve
of the lane 𝑙.
The final special case which needed to be handled for this project occurs when
lanes overlap in the 𝑒ˆ3 vertical direction. This scenario occurs in the common road
scenario of highway overpasses. When ego is found to be contained by multiple lanes,
then for each lane the nearest intersection with the 𝑡ˆ
𝑒3 , 𝑡 ∈ ℜ line is found through
a similar optimization to Equation 3.1. If the intersection 𝑑 is outside of a ball 𝐵
around ego, such that 0 ∈ 𝐵, then that lane is discarded. Any lanes inside that ball

34
are said to contain ego.
These lane representations and associated operations are used by the autonomous
system to support lane keeping, lane change, and other autonomous tasks. The
safety architecture uses the lane data to enforce important safety requirements, such
as remaining on the driveable surface of the road.

3.1.4 Wait Element Representation

Wait elements such as stop signs, traffic lights, and yield areas are represented using
an array of wait element data structures which augment the lane data. Each data
structure represents a separate wait element and is associated with a section of a
lane or lanes. These lane sections are closed intervals of lanes which cannot be safely
entered without obeying the traffic requirements of the wait.
From these lane sections, a wait area can be extracted. The wait area is the
polygon which encloses the surface of the lane in the section projected onto a 𝑒ˆ3
normal plane. These wait areas can be constructed from each projected lane edge
together with two additional edges connecting the left and right curves of the lane at
the beginning and end of the lane section which make the wait area a closed figure.
From these lane sections and wait areas, a wait line can be extracted. A wait line
is the edge at the beginning of the lane section which is perpendicular to the lane
center. This wait line is sometimes painted on the physical road and indicates the
position at which to halt in lane if necessary.
Each wait element also has a type indicating the behavior required to safely nego-
tiate it. These types include take-way, yield, stop-at-entry, and other kinds of traffic
signals. For example, a stop sign would be represented with a stop-at-entry type
wait element. An intersection where the autonomous vehicle has right of way would
represented with a take-way wait element since other vehicles are expected to yield.
This type information informs the safety architecture as to the required behavior at
the wait element.

35
3.2 Unified Vehicle Model
Letting 𝑥𝑖 ∈ 𝒳𝑖 ⊂ ℜ𝑛𝑖 be the state of the 𝑖th agent, the autonomous system models
the evolution of its state according to a time invariant ordinary differential equation
(ODE),
𝑥˙ 𝑖 (𝑡) = 𝑓𝑖 (𝑥𝑖 (𝑡), 𝑢𝑖 (𝑡)) (3.2)

where 𝑓𝑖 is uniformly continuous, bounded, and Lipschitz continuous [6].

Depending on application, on knowledge of the model parameters, and on com-
putational resources, a particular model and function 𝑓𝑖 (𝑥𝑖 (𝑡), 𝑢𝑖 (𝑡)) is selected. The
Unified Vehicle Model provides a common interface to these vehicle models and sup-
port for numerical evaluation using Euler’s method or the fourth order Runge-Kutta
method.

3.2.1 Kinematic Bicycle Model

Figure 3-3: Bicycle Model

This single-track planar model is commonly used to represent the vehicle in low
speed and low acceleration scenarios. As depicted in Figure 3.2.1, the vehicle is

36
modeled using a front and rear tire separated by a wheelbase 𝐿 = 𝑙𝐹 + 𝑙𝑅 , where 𝑙𝐹
and 𝑙𝑅 are the distance from center of mass to the front and rear tires respectively.
The static world frame coordinates (𝑋𝐸 , 𝑌𝐸 ) indicate the position of the center of
mass. The heading angle 𝜃 determines the rotation between the world and body
coordinate frame in the 𝑒ˆ3 normal plane. The front tire of the ego vehicle has world
frame coordinates (𝑋𝐸 + 𝑙𝐹 cos 𝜃, 𝑌𝐸 + 𝑙𝐹 sin 𝜃). In this kinematic model, inertia is
neglected so that the tires are constrained to never slip over the ground.
The control inputs are the front steering angle 𝛿 and a magnitude of velocity 𝑉 .
These assumptions yield equations of motion,
⎡ ⎤ ⎡ ⎤
𝑋 ˙ 𝑉 cos(𝛽 + 𝜃)
⎢ 𝐸⎥ ⎢ ⎥
(3.3)
⎢ ˙ ⎥ ⎢
⎢ 𝑌𝐸 ⎥ = ⎢ 𝑉 sin(𝛽 + 𝜃) ⎥
⎥
⎣ ⎦ ⎣ ⎦
˙𝜃 𝑣
sin(𝛽)
𝑙𝑅

where the vehicle side slip 𝛽, the angle between the vehicle heading and the vehicle
velocity vector, is,
𝑙𝑅 tan(𝛿)
tan(𝛽) = (3.4)
𝐿
In the Hyperion vehicle the rear wheels are fixed and there is only one front steer-
ing angle 𝛿. Magnitude of velocity 𝑉 = 𝑣𝑥2 + 𝑣𝑦2 is assumed to be independently
√︀

controllable using a low-level controller.

This kinematic bicycle model of the vehicles motion is used in performance-
constrained applications including the Safety Force Field and the Control Projection
modules. The kinematic bicycle model’s chief limitation is its inability to model tire
slip and therefore increasing inaccuracy at higher speeds and higher accelerations.

3.2.2 Dynamic Bicycle Model

Similarly to the kinematic bicycle model, this dynamic model is a single track model
using two tires separated by a wheelbase. Unlike the kinematic model, inertia is not
neglected and the tires are allowed to slip over the ground. This requires accounting
for complex tractive forces but is substantially more accurate at higher accelerations.

37
 The dynamic bicycle model derived and used has several simplifications and as-
sumptions, most notably (1) aerodynamic lift and drag are neglected, (2) the vehicle
drives on a flat surface with zero grade, (3) tire forces are proportional to slip ratio
and slip angle, (4) the rear tire slip angle 𝛼 is small enough to use the small angle
approximation for sin 𝛼 ≈ 𝛼, (5) the steering angle 𝛿 is small enough to use the small
angle approximation for sin 𝛿 ≈ 𝛿, and (6) load transfer can be neglected. These sim-
plifications are appropriate for highway driving applications of the dynamic bicycle
model.
The control inputs are the front steering angle 𝛿 and the slip ratios 𝜅𝐹 and 𝜅𝑅 .
Independent control of the slip ratios is assumed to be enabled by torque vectoring in
a low-level vehicle controller. The equation of motion for the dynamic bicycle model
is given by,
⎡ ⎤ ⎡ ⎤
𝑋˙ 𝑣𝑥 𝑐𝑜𝑠𝜃 − 𝑣𝑦 sin 𝜃
⎢ 𝐸⎥ ⎢ ⎥
⎢ ˙ ⎥ ⎢
⎢ 𝑌𝐸 ⎥ ⎢ 𝑣𝑥 𝑠𝑖𝑛𝜃 + 𝑣𝑦 cos 𝜃
⎥
⎥
⎢ ⎥ ⎢ ⎥
⎢ ˙ ⎥ ⎢
⎢ 𝜃 ⎥ ⎢ ˙𝜃 ⎥
(3.5)
⎥
⎢ ⎥=⎢ ⎥
1
(𝐶 𝜅 + 𝐶 𝜅 )
⎢ ⎥ ⎢ ⎥
⎢ 𝑣˙𝑥 ⎥ ⎢ 𝑚 𝑓 𝐹 𝑅 𝑅 ⎥
⎢ ⎥ ⎢ ⎥
⎢ ⎥ ⎢
⎢ 𝑣˙𝑦 ⎥ ⎢ 1 1 ˙
((𝐶𝐹 + 𝐶𝑅 )𝛼 + 𝑉 (𝑙𝐹 𝐶𝐹 − 𝑙𝑅 𝐶𝑅 )𝜃 − 𝐶𝐹 𝛿)
⎥
𝑚
⎥
⎣ ⎦ ⎣ ⎦
𝜃¨ 1
𝐼𝑒^3
((𝐶𝐹 𝑙𝐹 − 𝐶𝑅 𝑙𝑅 )𝛼 + 𝑉1 (𝑙𝐹2 𝐶𝐹 − 𝑙𝑅 2
𝐶𝑅 )𝜃˙ − 𝑙𝐹 𝐶𝐹 𝛿)

where the vehicle has mass 𝑚, rotational inertia 𝐼𝑒^3 , 𝐶𝐹 and 𝐶𝑅 are the front and
rear tire cornering stiffnesses respectively, 𝑉 is the magnitude of the velocity 𝑉 =
𝑣𝑥 + 𝑣𝑦2 , and 𝜅𝐹 and 𝜅𝑅 are the front and rear slip ratios respectively. The slip
√︀ 2

ratios are defined using the relative travel of the tires and the vehicle,

𝑅tire Ω𝐹
𝜅𝐹 = −1
𝑉 (3.6)
𝑅tire Ω𝑅
𝜅𝑅 = −1
𝑉

where 𝑅tire is the effective radius of the free-rolling tire, Ω𝐹 and Ω𝑅 are the angular
velocities of the front and rear tires respectively.
The dynamic bicycle model of vehicle motion is used in higher acceleration appli-

38
cations, especially during highway driving. The Collision Detector module specifically
uses the dynamic model to forward simulate the trajectory of the ego vehicle.

39
40
Chapter 4

Safety Architecture

In this chapter, I describe the design and implementation of the redundant safety
architecture used to minimize the requirements of ASIL certification. To implement
this architecture, several entirely new modules were created and several existing mod-
ules were repurposed. The architecture is designed to be flexible and to not constrain
future improvements to safety or planning functions.

4.1 Overview

Figure 4-1: Safety Architecture

41
4.1.1 Planning Pipeline

The Autonomous Vehicle (AV) Planner’s safety system is composed of the modules
shown in Figure 4-2. The planning pipeline begins with the consumption of World
Model state estimates. The Behavior Planner module then generates a set of candi-
date trajectories using lane data, road agent state estimates, and other World Model
information. Additionally, the Behavior Planner module scores each trajectory using
an approximate value function measuring the comfort of and progress toward the
destination of each trajectory. Each candidate trajectory is represented as a sequence
of [⃗𝑥, 𝑡]𝑇 spacetime points over a finite horizon 𝑡 ∈ (0, 𝑇𝑓 ]. This allows the trajectory
points to be interpolated to create a three-dimensional space curve parameterized by
the time 𝑡.
Linear interpolation between trajectory points is commonly used throughout the
planning software. This method yields a polyline trajectory. Higher-order splines, es-
pecially cubic splines, are used with appropriate boundary conditions where smooth
trajectory derivatives are required. Occasionally an estimate of local curvature is
computed by fitting a circular arc to a subsection of the trajectory. The fit is per-
formed using a either a three-point stencil, residual distance optimization, or random
sample consensus residual distance optimization depending on number of points and
noise in the candidate trajectory. The choice of an interpolation scheme is depends
on the specific module and use case.
In addition to this set of candidate trajectories constructed by the Behavior Plan-
ner module, the Safety Procedure Generator module constructs a set of special safety
procedures. These safety procedures are trajectories which halt the ego vehicle while
ignoring lane data and the state of other road actors. The safety procedures depend
only on the ego vehicle’s state and are constructed by numerically integrating the ve-
hicle model under evasive control actions such as sudden breaking or swerving turns.
The set of safety procedures is consumed by the Safety Force Field module later in
the pipeline and is used to guarantee the existence of at least one safe trajectory
which can bring the vehicle to a halt.

42
 Having obtained candidate trajectories and safety procedures, it is necessary to
also transform additional safety requirements into a representation enforceable by the
safety supervisor modules. The Virtual Obstacle module constructs virtual obstacles
which enforce traffic signals, road boundaries and other safety goals. This requires
consuming lane data and wait conditions as well as tracking the world state.
The set of candidate trajectories, the set of safety procedures, and all obstacles
perceived or virtual are passed to the safety supervisor modules. Safety Force Field
and Control Projection modules together and the Collision Detector module singly
check that each trajectory is safe. These independent checks are crucial to allow for
the ASIL decomposition of the safety architecture.
The Safety Force Field checks each trajectory using HJB reachability analysis.
The Collision Detector checks each trajectory by performing collision checking of the
ego vehicle footprint along the candidate trajectory with all obstacles traveling along
estimated obstacle trajectories. Both parallel safety supervisors produce an array of
Boolean values in which the 𝑖th value is true if and only if the 𝑖th trajectory is found
safe.
In the final stage of processing, the Trajectory Selector module consumes the set of
candidate trajectories, set of safety procedures, Boolean safety arrays, and the scores
for the candidate trajectories. The Trajectory Selector module selects the highest-
scoring candidate trajectory which is indicated to be safe by all passed safety result
arrays.

4.1.2 Safety Architecture

The goal of the AV Planner system is to select a trajectory which satisfies all safety
goals in Table A.1. To minimize the stringency of ASIL certification, ASIL decom-
position is performed so that each requirement is checked by two or more ASIL B
components at each stage it is enforced in the planning pipeline. The components
in the parallel paths shown in Figure 4-2 are ASIL B except for the final Trajectory
Selector module. The Trajectory Selector module combines the parallel safety checks
and chooses the highest-scoring, safe trajectory. Unlike the redundant components of

43
 Figure 4-2: ASIL Decomposition of Safety Architecture

the safety architecture, the Trajectory Selector is a single point of failure and therefore
must meet ASIL D certification.
Safety status of trajectories are passed between components using arrays of Booleans
for which the 𝑖th element is true if and only if the 𝑖 generated trajectory is indicated
to be safe by the originating safety monitoring component. To be safe, a trajectory
must be at least as safe as the least-safe safety procedure as measured by the collision
safety metric 𝑆(𝑖),

𝑡=𝑇𝑓
∑︁
𝑆(𝑖) = (𝐼(𝑖, 𝑡) · 𝐶Collision Energy · 𝑒−𝜆𝑡 ) (4.1)
𝑡=0

where 𝐼(𝑖, 𝑡) is an indicator variable which is 1 if and only if the 𝑖th trajectory has
a collision at a timestep less than or equal to 𝑡, 𝐶Collision Energy is a state-dependent
estimate of the severity of the collision, and 𝜆 is the time discount factor. The
indicator variable latches to 1 for timesteps after the initial collision to prevent cases
where the ego vehicle quickly passes through an obstacle from being rated more
favorably. Since distant timesteps are less certain due to replanning, exponential
time discounting is used to weight these less heavily. Since each possible trajectory

44
is compared to the safety procedure, a trajectory is safe if and only if,

˜ := 𝑆(𝑖) − min 𝑆(𝑗)

𝑆(𝑖) (4.2)
𝑗

˜ ≥0
𝑆(𝑖)

where each 𝑗 is an index of a safety procedure. Each safety monitor in the architecture
independently verifies 𝑆(𝑖)
˜ ≥ 0 for each trajectory in the candidate trajectory set.

The ASIL rating of the complete safety architecture can be verified by taking the
lower ASIL rating of two components at each serial stage of computation and by
attempting to perform ASIL decomposition over parallel stages of computation. By
examining Figure 4-2, it can be observed that the planning system can be synthesized
into a single ASIL D component.

4.2 Safety Supervisor Modules

The core pieces of the planning software’s safety architecture are the safety supervision
modules. The Safety Force Field, Control Projection, and Collision Detector modules
perform collision avoidance functions. Since the Virtual Obstacles module transforms
safety goals from Table A.1 into collision avoidance problems, these safety supervisors
can serve as redundant checks on all safety goals.
This section describes the mechanisms of operation of the Safety Force Field,
Control Projection, and Collision Detector modules as they relate to the safety archi-
tecture.

4.2.1 Safety Force Field

The Safety Force Field module seeks to guarantee the basic safety of the autonomous
vehicle. The system prevents the ego vehicle from colliding with other road users,
static obstacles, or virtual obstacles by computing control constraints which prevent
the system from arriving in an unsafe state. These control constraints can then
be used by the Control Projection module to evaluate the safety of the candidate

45
trajectories.
Additionally, the Safety Force Field protects trajectories from the set of safety
procedures such that at least one safety procedure may always be used to avoid
collision. Since each safety procedure trajectory is derived from a sequence of control
inputs, 𝑢𝑖 (𝑡) ∈ 𝒰safe
𝑖
may denote the 𝑖th agent’s instantaneous safe control input which
brings the agent to a halt over 𝑡 ∈ [0, 𝑡𝑓 ] and the control signal u𝑖 (·) ∈ U𝑖safe over a
time interval [0, 𝑡] where 0 ≤ 𝑡 ≤ 𝑡𝑓 .
For each agent 𝑖, the Safety Force Field solves for the set of forward reachable sets
(FRS), which is the set of all states the agent can reach from its initial state 𝑥0𝑖 by ex-
ecuting its safety procedures. For the ego agent, all of the safety procedures produced
by the Safety Procedure Generator may be used. For other road agents, fewer or a
single safety procedure may be used to minimize the computational requirements.
The FRS may be formally defined as,

𝐹 𝑅𝑆(𝑥0𝑖 , 𝑡) := {𝜉 𝑡 (𝑥0𝑖 , u𝑖 ) | ∃u𝑖 ∈ U𝑖safe (𝑡)} (4.3)

where 𝜉 𝑡 (·, ·) is the state obtained at 𝑡 from applying the control signal u𝑖 over the
horizon [0, 𝑡] from the initial state 𝑥0𝑖 to the system described in Section 3.2. In the
implementation, the future trajectories of each agent applying the safety procedures
are simulated using the kinematic bicycle model. The stationary trajectories of static
obstacles and virtual obstacles are also computed. The claimed set of an agent is the
set of all FRS (𝑥𝑖 , 𝑡) spacetime points for 𝑡 ∈ [0, 𝑡𝑓 ] where 𝑡𝑓 is the time the final actor
halts.

𝐶𝑖 (𝑥𝑖0 ) := {(𝑥𝑖 , 𝑡) | 𝑥𝑖 ∈ 𝐹 𝑅𝑆(𝑥0𝑖 , 𝑡), ∀𝑡 ∈ [0, 𝑡𝑓 ]} (4.4)

In the implementation, both the FRS and claimed sets are augmented using the
Minkowski sum of the vehicle footprint with the sampled states. This obtains all of
the 𝑥𝑖 state points the vehicle will occupy in the FRS at time 𝑡 or the (𝑥𝑖 , 𝑡) spacetime
points the vehicle will occupy while executing the safety procedure from [0, 𝑡𝑓 ].
At this point, an approximate value function can be defined which is: (1) strictly

46
positive when the ego vehicle’s claimed set intersects with that of an obstacle, (2) zero
elsewhere, (3) non-increasing along the safety procedures. This approximate value
function is called the safety potential function and is used to indicate the unsafe set of
states. From it properties (1) and (3), the value function is Lyapunov function for the
safety procedure trajectories. The implementation uses the smooth and differentiable
function,

𝑉 (𝑥A , 𝑥B ) = max{𝑡stop (𝑥A ) − 𝑡collision (𝑥A , 𝑥B ), 𝑡stop (𝑥B ) − 𝑡collision (𝑥A , 𝑥B )} (4.5)

where 𝑥A is the state of an agent A, 𝑡stop (𝑥A ) is the time at which the agent A
reaches a stop while executing a safety procedure, and 𝑡collision (𝑥A , 𝑥B ) is the time at
which agents A and B collide while executing their safety procedures. These values are
found by forward simulating the system as the agents execute their safety procedures
until the agents halt or collide.
Since the safety potential is non-increasing under a safety procedure, any control
policy which decreases the safety potential more than at least one safety procedure
is safe. That is,

𝜕𝑉 (𝑥A , 𝑥B ) 𝜕𝑉 (𝑥A , 𝑥B )
𝑓A (𝑥A , 𝑢A ) ≤ max 𝑓A (𝑥A , 𝑢¯A ) (4.6)
𝜕𝑥A A
¯A ∈Usafe
𝑢 𝜕𝑥A
Equation 4.6 can be used to find sets of safe controls such that if the agents begin
outside of the unsafe set, the agents will always remain outside the unsafe set so
long as both agents select controls from the set of safe controls. If the dynamics are
control affine, 𝑓 (𝑥, 𝑢) = 𝑓1 (𝑥) + 𝑓2 (𝑥)𝑢, then the set of safe controls is bounded by
hyperplanes [6].
The Safety Force Field outputs this set of safe controls, called the control con-
straints, to the rest of the safety architecture. Particularly, the Control Projection
module consumes the control constraints to detect unsafe trajectories. In this way,
the Safety Force Field system acts as an ASIL B safety supervisor. The Safety Force
Field is composed with the ASIL B Collision Detector to form a single ASIL D rated

47
safety system.

4.2.2 Control Projection Module

The Safety Force Field system can directly enforce the control constraints by project-
ing the planning system’s control output on to the nearest point inside the control
constraints. However, this method of enforcing the control constraints discards com-
fort scoring and path planning which occurred during trajectory generation. It also
cannot easily be combined with the checks performed by other safety supervisors. For
these reasons, the Control Projection module instead allows the Safety Force Field’s
constraints to checked against the whole set of candidate trajectories for safety.
The Control Projection module implements this functionality by mapping each
trajectory to a 𝑡 = 0 control output which can then be checked against the control
constraints. Directly obtaining a control output from the control optimization system
for each candidate trajectory would the most accurate method, but is computationally
infeasible. There are 𝑛 > 16 candidate trajectories and solving for a control output
can take up to 10 milliseconds of an approximately 30 millisecond frame. The Control
Projection module instead attempts to approximate the control output using simpler
and faster control methods.
The control projection module uses a simple pure pursuit controller to estimate
the control outputs. Given a trajectory 𝑟, look ahead time 𝑡𝑙 , and ego position 𝑝 this
controller has the following simple control law.

d
𝑉 =| r(𝑡)|
d𝑡

2𝐿 sin(ℓ)
tan(𝛿) =
|r(𝑡 + 𝑡𝑙 ) − 𝑝|
where ℓ is simply the angle from the vehicle heading to the look ahead point
r(𝑡 + 𝑡𝑙 ),

48
 (r(𝑡 + 𝑡𝑙 ) − 𝑝) · 𝑒ˆ2
ℓ=
|r(𝑡 + 𝑡𝑙 ) − 𝑝|

4.2.3 Collision Detector

Like the Safety Force Field, the Collision Detector module is responsible for avoiding
collision by detecting candidate trajectories which could result in a collision. Though
its method of collision checking is more straightforward compared to that of the Safety
Force Field, many implementation details and design decisions are shared between
the modules.
Each candidate trajectory is checked by the Collision Detector for collision with
another agent, static obstacle, or virtual obstacle. The operation begins with finding
the [⃗𝑥, 𝑡]𝑇 points occupied by the ego vehicle along the trajectory. Like in the Safety
Force Field, the trajectory is projected into a 𝑒ˆ3 normal plane and augmented using
the Minkowski sum taken with the vehicle footprint. The vehicle footprint may be
dilated to add “padding” and avoid near-collisions.
This occupancy set contains the spacetime points the ego vehicle will pass through
while following the trajectory. Intuitively, its difference from the claimed set or FRS
constructed by the Safety Force Field is that the occupancy set only contains space-
time points reachable along the tested trajectory instead of the points or spacetime
points reachable along any safety procedure. This also assumes perfect trajectory
tracking by the downstream control system.
The next stage of computation requires obtaining similar occupancy sets for ob-
stacles. This is trivial for stationary obstacles and virtual obstacles. Their occupancy
sets can be constructed using the Minkowski sum of their (possibly dilated) footprints
and their stationary trajectories with respect to the ego vehicle.
It is more difficult to obtain the future states of other agents. The Collision
Detector employs both a learned model and dynamics-informed heuristics to take a
maximum likelihood estimate of the future trajectory of each controlled agent. This
maximum likelihood trajectory is then used to obtain the occupancy sets.
The design decision to use a single point maximum likelihood estimate instead of

49
a probability distribution over future states by the Collision Detector means that it
can only consider the most likely modeled outcome. For this reason, the Collision
Detector module’s assurance of collision avoidance is substantially weaker than that of
the Safety Force Field. However, it may be reliable enough to meet the less stringent
ASIL B standard.

4.3 Virtual Obstacle Generator

Avoiding collision is a crucial, but not exclusive, safety requirement. Other impor-
tant safety goals listed in Table A.1 must also be enforced. Requirements such as
maintaining lane discipline or obeying wait conditions cannot be directly guaranteed
by the planning software’s safety supervisors which are limited to ensuring collision
avoidance.
The new Virtual Obstacle module is designed to transform more abstract safety
requirements into constraints on the world state. These constraints are represented
using virtual obstacles which can be consumed by the Safety Force Field and the Col-
lision Detector modules. Like other obstacles, the virtual obstacles have boundaries
composed of polylines of three dimension points. The virtual obstacles are constructed
by this module to create avoid sets for the Safety Force Field’s reachability analysis
which guarantee safety goals are enforced. Similarly, the obstacles transmitted to the
Collision Detector are constructed as to prevent the ego vehicle from entering unsafe
states.
The Virtual Obstacle module consumes state estimates, lane data, and wait ele-
ment information to create an array of virtual obstacles. This array includes virtual
obstacles covering the road boundary edges and surrounding active wait areas. The
module also performs heuristic tracking of each wait element’s applicability. Since
the module is a common input to both safety supervisors, it is a single point of fail-
ure and therefore must meet an ASIL D rating. For this reason, the design of the
Virtual Obstacle module emphasizes simplicity and seeks to transform World Model
data from the ASIL D rated state estimation system as directly as possible.

50
 The following subsections will outline the function of the Virtual Obstacle module,
particularly its implementation of the road bounding and wait element enforcing tasks.

4.3.1 Road Boundaries

An important safety requirement is that the ego vehicle does not leave the driveable
surface of the road. The driveable surface is not limited to lanes, which may be
crossed or exited, but includes any road area which is safe to drive. The road area is
defined by the lane data which provides a road boundary type edge. As with all World
Model estimates, this lane data is provided by an ASIL D rated system. The Virtual
Obstacle module must create virtual obstacles from the lane data which prevent the
ego vehicle from crossing the road boundaries.
Additionally, the Virtual Obstacle module supports the safety goal which requires
the ego vehicle to avoid crossing any ‘uncrossable’ lane edge. These edge types include
mapped road boundaries, physical dividers, curbs, fences, unpaved gore areas, and
other boundaries which the vehicle should never cross in autonomous operation. All
of these edge types are covered with virtual obstacles in a manner similar to the road
boundary edges.

Algorithm 1 Road Boundary Virtual Obstacle Generation

i←0
previousObstacle ← null
while i < laneVertexes.count do
if laneVertexes[i].type ∈ uncrossableTypes then
if previousObstacle = null then
previousObstacle ← Obstacle(laneVertexes[i])
else if previousObstacle.full then
previousObstacle ← Obstacle(previousObstacle.boundaryVertexes[-1])
previousObstacle.addBoundaryVertex(laneVertexes[i])
else
previousObstacle.addBoundaryVertex(laneVertexes[i])
end if
else
previousObstacle ← null
end if
end while

51
 The module constructs virtual obstacles using a method similar to the pseudocode
Algorithm 1. The software iterates over every lane edge, checking if the lane edge
type is in the set of uncrossable types. If this is the case, either a new obstacle is
created over the edge or the boundary of a previous obstacle is extended over the lane
edge. This algorithm runs in linear time in the number of lane edges and provides an
injective mapping from uncrossable lane edges to virtual obstacles. Additionally, the
algorithm minimizes the number of virtual obstacles created by extending boundary
of a previous obstacle whenever possible. This is a benefit since the virtual obstacle
array and each obstacle within it occupies a fixed amount of memory. If an obstacle
is extended instead of an new obstacle created, it reduces the number of virtual
obstacle array slots occupied and therefore the likelihood of filling the array before
every uncrossable edge is covered.
Several nuances not included in Algorithm 1 must be handled correctly. Despite
iterating over lane vertexes, the module must only cover pairs of vertexes forming
lane edges. This is implemented by setting the previous obstacle to null after breaks
in a lane polyline.
Additionally, Safety Force Field and the Collision Detector were modified to handle
the new road boundary virtual obstacles. Unlike the obstacles previous consumed by
the Safety Force Field and the Collision Detector, these virtual obstacles frequently
have long, open boundaries. The initial boundary vertex could be very distant from
other vertex points. This caused the previous method of filtering out distant obstacles
employed by those modules to fail. Obstacles which had their first boundary point
outside a velocity-dependent zone of the ego vehicle were not considered for collision
checking since it was assumed that all of their boundary edges would be distant from
the ego vehicle. This reduced computation in these modules, but could cause virtual
obstacles with edges near the ego vehicle to be improperly excluded. For this reason,
the modules were updated to check every edge for intersection with the ego vehicle’s
collision checking zone.

52
4.3.2 Wait Conditions

Several important safety goals for the autonomous system require that the ego vehi-
cle halts before entering lane segments associated with wait conditions. These wait
conditions may be created by stop signs, traffic lights, rail crossings, and other traffic
signals. The wait conditions are detected by the state estimation system and received
by the planning software via the World Model.
The Virtual Obstacle module is responsible for transforming the wait conditions
into constraints which can be enforced by the safety supervisors. The module creates
virtual obstacles which prevent the ego vehicle from entering the lane segment asso-
ciated with the wait condition. This is performed by identifying the lane segment
associated with the wait condition and then constructing virtual obstacles over its
left and right edges. Additional virtual obstacles are placed over the entry to the
lane segment, called the wait line, and the exit. Together, and when projected into
an 𝑒ˆ3 normal plane, these virtual obstacle enclose the wait area indicated by a wait
condition.
The Virtual Obstacle must also independently track which wait conditions cur-
rently apply to the ego vehicle. This is a relatively complex function which is imple-
mented via heuristics for each type of wait condition. Each wait element provided to
the module is checked to identify if it actively applies to the vehicle. For example,
if the element was created by a traffic light signal which has since changed then the
wait element might be marked inactive.
The main algorithmic loop is that of Algorithm 2.

Algorithm 2 Wait Element Virtual Obstacle Generation

𝑖←0
while i < waitArray.count do
updateWaitStatus(waitArray[i])
if waitArray[i].active then
waitAreaObstacle ← getWaitArea(waitArray[i])
virtualObstacles.append(waitAreaObstacle)
end if
𝑖←𝑖+1
end while

53
 Handling the various types of wait elements provided was a challenge with this
approach. Stop sign wait elements needed to be tracked using a unique identifier.
If the vehicle completed a full stop at the sign by halting within a specified range,
then the wait element was marked inactive. If the vehicle subsequently left that
range the stop sign’s wait element was restored to the active state. This bookkeeping
information is maintained using a hash set of completed stop-type wait element ids
for efficient lookup.
Wait elements created by traffic lights required tracking three states, an active,
inactive, and transitory state. These correspond to the red, green, and yellow states
of the light respectively. The safety requirement allows the vehicle to enter the in-
tersection in the inactive and transitory states. It also allows the vehicle to clear the
intersection in the active state if it has already entered it. This required adding func-
tionality to the virtual obstacle module preventing the creation of virtual obstacles if
the vehicle is in the intersection. This is important since if this case were not handled
correctly, there is the possible of trapping the vehicle in the intersection and causing
it to obstruct traffic.
Ideally, in a future revision to this safety architecture this complex wait condition
filtering may be moved out of the Virtual Obstacle module and into the state estima-
tion system. This would reduce the complexity of the behavior of the ASIL D Virtual
Obstacle module and reduce the effort required to test this module.

4.4 Trajectory Selector Module

The Trajectory Selector module is the final component of the safety architecture. It
is responsible for reducing the multiple safety result arrays and choosing a single,
safe trajectory. The module is a single point of failure in the planning pipeline,
and therefore must achieve an ASIL D certification. For this reason, the Trajectory
Selector’s design emphasizes simplicity of operation. The smaller the input space and
the functionality of the module, the more easily it can be tested and proven robust.
Additionally, the Trajectory Selector module is designed to allow for future alter-

54
ations to and expansions of the safety architecture. The module’s interface supports
adding new safety monitors providing parallel Boolean safety result arrays. Addi-
tional arrays of safety results can be processed without changing the implementation
of the Trajectory Selector.

4.4.1 Trajectory Selection

The Trajectory Selector module is a simple system. It consumes the set of safety
result Boolean arrays A containing the safety results arrays 𝐴1 and 𝐴2 provided by
the Control Projection and Collision Detector modules respectively. It eliminates the
𝑖th trajectory from the trajectory set if and only if ∃𝐴𝑗 : ¬𝐴𝑗 [𝑖] ∧ 𝐴𝑗 ∈ A. That is a
trajectory is eliminated if any safety result indicates that it is unsafe.
Of the trajectories which are not eliminated, the Trajectory Selector chooses the
𝑗 * trajectory where 𝑗 * = argmax𝑗 𝐶[𝑗] and 𝐶[𝑗] is the desirability score of the 𝑗th
trajectory computed by the Behavior Planner module’s reward function. Selecting
the highest scoring trajectory is preferred in order to maximize the comfort and
progress to the destination for the ego vehicle occupants, but is not necessary to
fulfill any of the safety goals listed in Table A.1. Since no safety-related functionality
depends on the correctness of the input trajectory scores, the Trajectory Selector is
not considered dependent on this input for the purposes of ASIL certification.
If no candidate trajectory is found to be safe, then a safety procedure is selected.
The safety procedures are generated by the ASIL D rated Safety Procedure Generator
module and are ‘protected’ each frame by both the ASIL B rated safety monitors. For
this reason, the Trajectory Selector can always select the Safety Procedure without
compromising its ASIL D rating.
The operation of the Trajectory Selector is composed of two operations: reduc-
ing the safety results and choosing the output trajectory. These functions perform
similarly to Algorithm 3 and Algorithm 4 respectively.
The Trajectory Selector is the final component of the planning pipeline. Its de-
scription concludes the specification of the safety architecture.

55
Algorithm 3 Combine Safety Results
combinedSafetyResults ← [1 ∀𝑖 ∈ (1, 2, ..., trajectorySet.count) ]
𝑖←0
while i < trajectorySet.count do
𝑘←0
while k < safetyResults.count do
combinedSafetyResults[i] = combinedSafetyResults[i] ∧ safetyResults[k][i]
𝑘 ←𝑘+1
end while
𝑖←𝑖+1
end while
return combinedSafetyResults

Algorithm 4 Select Trajectory

𝑗 * ← trajectorySet.count
𝑗←0
while j < trajectorySet.count do
if combinedSafetyResults[j] · 𝐶[𝑗] > 𝐶[𝑗 * ] then
𝑗* ← 𝑗
end if
𝑗 ←𝑗+1
end while

if 𝑗 * = trajectorySet.count then
return 𝑠 ∈ safetyProcedure
else
return trajectorySet[𝑗 * ]
end if

56
Chapter 5

Analyzing Safety and Results

5.1 Summary
In this chapter, I perform several analyses of the completed safety architecture. The
first section verifies that the ASIL decomposition of the system correctly supports
an ASIL D certification for each safety goal. This analysis produces a matrix show-
ing the ASIL required for each safety goal for each component in the pipeline. In
the second section, I use a suite of automated tests to justify the independence of
the parallel Safety Force Field and Collision Detector pathways in the autonomous
planning pipeline. This independence is a central structural design element which
allows for ASIL D synthesis of the planning system. In the third and fourth sections,
I profile the performance of the Safety Force Field module and the Control Projection
module respectively. The analysis of failures performed in this section provides an
initial basis for the lengthy ASIL certification process.

5.1.1 Notes on Simulation Systems

The experiments performed rely heavily on simulated testing in hand-crafted and

selected road scenarios. Due to the large input space for most of the planning modules,
exhaustive black box testing is infeasible. Instead, clear box testing is used to provide
insight into the planning software’s performance using tests informed by the design

57
of each module.
The evaluations in this chapter are performed using two different simulation sys-
tems. In Section 5.3, experiments are performed using the Drive Sim system. The
Drive Sim is an end-to-end simulation platform which generates synthetic environ-
ment data and simulates physical sensors in addition to the dynamics of the ego and
other road agents. Tests for this system can either be hand-crafted or generated from
recorded real-world driving sessions. The fidelity of the simulation is validated using
hardware-in-the-loop experiments. A drawback to the Drive Sim simulator is its large
compute requirements. Execution of the complete suite of behavior regression tests
is performed on a compute farm where the task can take up to a full day to complete.
The Pac Sim system is used for the experiments performed in Section 5.4 and
Section 5.5. The Pac Sim simulates the planning software in isolation by emulating
the World Model interface and evolving a vehicle dynamics model using the planning
outputs. It is substantially less compute intensive than the Drive Sim system. Since
it operates at a higher level of abstraction, Pac Sim scenarios are also easier to create
and more flexible. The lower compute requirements and simpler scenario design allows
for large scale testing to profile the behavior of individual planning modules as is done
in Section 5.4 and in Section 5.5.
The Pac Sim system is also substantially more modular than the Drive Sim. Any
vehicle dynamics model supporting the Unified Vehicle Model interface described in
Section 3.2 can be employed by the Pac Sim. These models are evolved using Runge-
Kutta fourth order methods and can have their parameters modified between or even
during a simulation episode. The Pac Sim system also allows for specific modules in
the planning pipeline to be replaced with fixed output during the simulation. This
allows very fine control during testing. By contrast, the Drive Sim is a monolithic
software system. It evolves a more complex but less easily modified dynamics model.
Software tests using the Drive Sim system are executed on a remote compute farm
or with hardware-in-the-loop. Tests are described using constraints on the measured
state during operation of the autonomous software. Due to the verisimilitude of the
Drive Sim, tests written for the system can be directly evaluated on the autonomous

58
test vehicle during real-world driving.

5.1.2 Notes on Test Cases

It is important to note that the tests performed in Section 5.3 are either hand-crafted
by developers of the autonomous software or selected by them from real-world driving
scenarios. The automated behavior regression tests are run against each released
version of the autonomous software and are a key metric of performance. Since the
test cases are time consuming to create and execute, no trivial tests are performed.
Many of the test cases validate the behavior of the autonomous system in difficult
driving scenarios or in scenarios where previous versions of the system have failed.
The distribution of road scenarios in these behavior regression tests is not identical
to real world driving but instead is a distribution of scenarios which are substantially
more difficult for the autonomous software. Some examples of road scenarios for
which the autonomous behavior is validated in these tests include the following:

• Lane change maneuvers performed at various speeds with other road actors.
Collision causes scenario failure.

• Unprotected yields at an intersection. Violation of right-of-way causes failure.

• Exiting a highway. Excessive jerk violates comfort metrics and causes failure.

• Computational stress tests. Too many dropped frames causes failure.

• Test case developed from real-world error. Test vehicle took a very wide turn
at a specific intersection requiring the driver to intervene.

Similarly, the test scenarios created in Section 5.4 and in Section 5.5 are specif-
ically constructed to lead to collisions and to illustrate particular dynamics respec-
tively. They certainly are not drawn from a distribution identical to that of real-world
driving. While results from the evaluation of tests performed in this chapter can sug-
gest similar results in real-world driving, they do not require it. Before drawing
final conclusions on the reliability or independence of planning modules, any analysis

59
based on simulation should be validated in real-world driving. With this caveat, our
evaluation of the safety architecture can be at least informed using the experiments
performed in this section.

5.2 ASIL Decomposition Analysis

Figure 5-1: Matrix showing ASIL Rating of each safety goal at within each component
of the autonomous pipeline. The safety goals are those from Table A.1. The modules
are the World Model (WM), Safety Procedure Generator (SPG), Behavior Planner
(BP), Virtual Obstacle Generator (VOG), Collision Detector (CD), Safety Force Field
(SFF), Control Projection (CP), and the Trajectory Selector (TS).

60
 The primary goal of the safety architecture is to develop a system which uses
ASIL decomposition to efficiently compose modules in a manner which can achieve
the highest ASIL certification level for all safety goals listed in Table A.1. This new
safety architecture can be analyzed with respect to each individual safety goal using
ASIL decomposition analysis.
The goal of ASIL decomposition analysis is to examine each module on which
the enforcement of a safety goal depends. The overall ASIL of a safety goal in the
autonomous planning pipeline is the minimum over the serially dependent modules
and the ASIL synthesis of parallel redundant modules. That is, redundant safety-
goal-enforcing modules have their ASILs combined into a higher ASIL if possible.
Serial safety-goal-enforcing modules use the lower ASIL of the modules. As described
in Section 2.2, two redundant ASIL B rated modules can be synthesised into a single
ASIL D system. The chain of dependencies can be discovered by exploring backwards
from the final module in the pipeline over each input module on which the correct
enforcement of a safety goal depends. This backwards exploration can be depicted as
a tree relationship like that shown in Figure 5-2 for each particular safety goal.
The overall ASIL enforced for each safety goal by each module in the pipeline
can be computed by finding the ASIL dependency tree for each safety goal and then
evaluating the synthetic ASIL forward from leaf to root. These enforced ASILs can
be summarized in a matrix as shown in Figure 5-1 which depicts the ASIL enforced
on each safety goal by each module in the planning pipeline. Since each safety goal
is enforced at ASIL D in the final module, the Trajectory Selector, the overall safety
architecture can be synthesized as an ASIL D system.
Additionally, Figure 5-1 shows the redundant pathways through the Safety Force
Field and Collision Detector modules can be synthesized into an ASIL D system.
The matrix also shows the dependency of some safety goals on the Virtual Obstacle
Generator to transform abstract traffic requirements into collision problems. Finally,
the matrix shows that every safety goal depends on the World Model inputs to the
planning safety architecture. Unsuprisingly, these inputs must be ASIL D rated to
achieve an ASIL D rating for the whole planning system.

61
Figure 5-2: Backwards-traced ASIL dependency tree showing the modules required
to enforce Safety Goal 1. Dashed lines indicate redundant ASIL decomposed depen-
dencies.

62
5.3 Correlation of Parallel Pathway Errors
The Safety Force Field and the Collision Detector modules are the principle safety
monitors in the planning pipeline. They are combined via two redundant pathways
to synthesize a single ASIL D system. For the modules to serve as redundant checks
for the purposes of ASIL certification, the events of failure for each module must be
“sufficiently independent.” This is a qualitative statement in the ASIL standard but
establishing statistical independence is sufficient to satisfy this requirement.
Validating statistical independence between the modules requires significant work
to translate each safety goal dependency into specific binary requirements on the
behavior of the module. Additionally, violations of these requirements must be tested
for across road scenarios drawn from a distribution identical to the distribution of
scenarios for real-world driving. This is a high bar which a conclusive ASIL analysis
must overleap. This design project can at least investigate the independence of the
parallel safety monitor pathways using a proxy for the distribution of road scenarios.

Safety Force Field Alone

Collision Detector Alone Passed Failed
Passed 415 23
Failed 17 3
Combined Architecture 455 3
Table 5.1: Number of test cases passed both pipelines, failed by only one pipeline,
and failed by both pipelines.

Previous work on the autonomous planning system developed a substantial num-

ber of end-to-end driving behavior tests. These automated regression tests validate
the simulated behavior of the autonomous software in many recorded real-world driv-
ing and hand-crafted scenarios. The collection of end-to-end tests can be used as
a proxy for real-world driving to justify the independence of failures in the paral-
lel planning safety modules. The experiment relies on the redundancy of the new
planning architecture. The entire autonomous software can be executed using (1)
the combined safety architecture, (2) the Safety Force Field pathway alone, or (3)
the Collision Detector pathway alone. This experiment evaluates the number of tests

63
Figure 5-3: Number of road scenario tests passed by (1) the new safety architecture,
(2) the original planning architecture, (3) the Safety Force Field alone pipeline, and
(4) the Collision Detector alone pipeline. Note that n=449 as 9 tests created after
the original architecture are excluded.

passed by the planning software using (1), (2), and (3) respectively. The results of
this experiment are summarized in Table 5.1. Defining two indicator variables for the
events of failure of the Safety Force Field alone and Collision Detector alone pipelines
respectively, the sampled estimate of covariance is 0.005 which can be normalized to
a correlation coefficient of 0.121. This value is quite close to zero, indicating that the
events of failure of the modules are substantially independent.
In addition to using these drive behavior tests to measure the correlation of parallel
processing pipelines in the safety architecture, we can use them as a proxy for the
increased safety of the system overall. The number of tests passed by the original
planning architecture is compared to the number of tests passed by the new safety
architecture as well as both the Collision Detector alone and Safety Force Field alone

64
pathway systems. To avoid bias in tests created to challenge the new architecture,
automated tests created after the original architecture are excluded.
The results of the experiment are shown in Figure 5-3. This figure shows that the
new safety architecture is an improvement on both the original planning system and
on a safety pipeline which relies on either safety monitor alone.

5.4 Profiling Safety Force Field Errors

Figure 5-4: SFF scenario graphical interface. Note the colored non-expanded claimed
sets of each vehicle.

The Safety Force Field determines the unsafe sets and can intervene to prevent
unsafe control actions. It is one of the two key safety monitors in the new architecture.
The Safety Force Field consumes trajectories and obstacle state estimates produced
by the World Model and Virtual Obstacle Generator.
In this experiment, I profile the operation of the Safety Force Field module with
regard to ASIL false positive and false negative errors over a large number of simulated

65
 1 Time of Event Event
2 SFF triggers Execute safety procedure and check for
false positive (Abort if no false positive)
3 All actors complete safety procedure Reset to SFF trigger time
4 SFF triggers + F.P. Tolerance Execute Safety Procedure
5 All actors complete safety procedure, Increase F.P. Tolerance, reset to SFF
but no collision trigger time, and return to (4)
or
All actors complete safety procedure, Correct F.P. Tolerance is found
and collision occurs
Table 5.2: Timeline for false positive tolerance measurement.

random road scenarios. For the Safety Force Field, a false positive error occurs
whenever the software wrongly detects that a control action is unsafe, that is that
an action leads to a state for which a collision is inevitable no matter which safety
procedure is executed. A false negative error occurs whenever the software fails to
detect that a control action is unsafe, that is that an action leads to an inevitable
collision.
Due to discretization of the unsafe set, some error is impossible to avoid. Addi-
tionally, conservative design decisions favoring false positive errors over false negative
errors cause the system as implemented to almost never encounter false negatives.
False negative errors could lead to a collision and therefore are more dangerous that
false positives which only cause overly conservative driving. Any ASIL requirement
on the Safety Force Field should specify a tolerance for false positives representing
the margin of safety for the module’s unsafe set computations.
In this experiment, only false positives and no false negatives were encountered
in over 104 randomized road scenarios. I therefore conducted additional experiments
to measure the tolerance for false positives built into the module. That is, the size of
the implicit buffer in time between the system having a false positive error and a false
negative error. As it depends on a counterfactual, this metric is difficult to measure
in real-world operation but can be evaluated in reproducible simulations.
This experiment evolves the state of an ego agent and one other agent forward
using the dynamic bicycle model from Section 3.2.2. The starting state and control

66
 Figure 5-5: Head-on collision false positive tolerance

signals are generated randomly but constrained such that a collision between agents
will eventually occur. Simultaneously with the forward evolution of the dynamic
system, the Safety Force Field module is evaluated at each time step. If the Safety
Force Field detects a control action will move the agent into the unsafe set, then both
vehicles execute a safety procedure.
If a collision occurs between the vehicle footprints, then a false negative error
has occurred since the Safety Force Field did not detect the collision until it was
already inevitable. Otherwise, the state can be reset to one time step after taking the
control action determined by Safety Force Field to be unsafe. Both vehicles execute a
safety procedure. If no collision occurs before the safety procedure is completed then
the detection by Safety Force Field was a false positive. Due to conservative design
choices, these types of false positives were universal, occurring in over 104 randomized
scenarios.

67
 Figure 5-6: Head-on collision false positive tolerance

An additional slate of experiments were performed to measure false positive errors

by executing safety procedures one time step after taking a control action that the
Safety Force Field determined to be unsafe. If no collision occurs before the safety
procedure is completed then the detection by Safety Force Field was a false positive.
Due to conservative design choices, these false positives were universal.
Since there is a design trade-off between dangerous false negatives and performance-
hampering false positives, some tolerance for false positives is preferable. Too much
of a tolerance however might lead to the selection of overly conservative trajectories.
I designed an additional experiment to measure the false positive tolerance as the
buffer in time between detecting an unsafe control action and the agents actually
entering the unsafe set.
The false positive tolerance for a specific collision scenario is measured by sim-
ulating forward until a false positive first occurs. Then, the scenario is simulated

68
 Figure 5-7: Head-on collision false positive tolerance

repeatedly with an increasing delay between detecting an unsafe control action and
switching from the initial control signal to a safety procedure. The smallest de-
lay found which leads to a false negative error, that is a simulated collision, is the
false positive tolerance. That is the distance in time between the first detection of
a collision by Safety Force Field and that collision becoming inevitable. The exact
procedure is summarized in Table 5.2.
For ease of debugging, several model parameters were exposed and the claimed
sets were illustrated by a graphical user interface depicted in Figure 5-4. The false
positive tolerance was profiled for a head-on moving collision, a rear collision with
one stationary agent, and a T collision scenario between two moving agents. The
sweep of false positive tolerances is shown in Figure 5-5 for model parameter mass,
in Figure 5-6 for relative collision velocity, and in Figure 5-7 for safety procedure
curvature. Other model parameters were set to the defaults for the 2018 Ford Fusion

69
test vehicle.
The immediate observation from these figures is that the false positive tolerance
is small, consisting of less than two tenths of a second for all scenarios and parameter
combinations. Additionally, by examining the sensitivities of the metric to various pa-
rameters, we can observe road scenarios and parameter combinations in which Safety
Force Field might be overly or insufficiently conservative. For example, observing
the decrease in false positive tolerance with speed recovers the intuitive result that
reaction times are more important at high speeds. Depending on the desired margin
of error, the Safety Force Field might be overly conservative for rear-end collisions
and for speeds under 15 m/s.
Additionally, by varying the curvature of a circular safety procedure it can be
observed that the Safety Force Field is symmetric with respect to chirality and that
higher curvatures are associated with a bigger false positive buffer. Continuing to
profile the sensitivities of the Safety Force Field to various parameters and road
scenarios could be a productive area for tuning and understanding the safety monitor.

5.5 Profiling Control Projection Errors

The Safety Force Field’s enforcement of the safety goals relies on the Control Pro-
jection module’s mapping from trajectories to current time control actions. This
mapping is performed using a simplistic pure pursuit controller. Any ASIL certifica-
tion of the planning system would need to justify that the estimates produced by the
Control Projection module are sufficiently close to the actual control actions taken by
the downstream model predictive controller later in the autonomous software process.
Developing rigorous tolerances for the control projection estimates would require
analyzing the tolerances inside the Safety Force Field module to determine binary
requirements for ASIL certification. Instead, I analyze the Control Projection module
as a feasible method for mapping input trajectories to current time control actions.
Specifically, I compare the outputs of the Control Projection module to the outputs
of the downstream predictive controller in hand-crafted road scenario simulations.

70
For the purposes of this experiment, it is assumed that the low-level model inverse
controller downstream of both the Control Projection module and the predictive
controller enables close tracking of commanded accelerations.

Figure 5-8: Reference and predicted trajectories for the downstream controller in
sudden halt scenarios at different initial speeds.

I analyze the performance of the Control Projection module in two simulated

scenarios: one to investigate longitudinal dynamics and one to investigate lateral
dynamics. The longitudinal scenario is a sudden halt trajectory which transitions
from constant velocity to a halt via a constant breaking acceleration. This is a
frequent road scenario encountered at stop signs and other wait conditions. The speed
control from the simple pure pursuit law is equal to the magnitude of the second time
derivative of the trajectory at the current time. By contrast, the speed control of the
downstream controller performs an optimization over future states using a complex
loss function which optimizes for passenger comfort and other factors.
The longitudinal reference trajectory and predicted trajectory produced by the

71
Figure 5-9: Control Projection and downstream commanded accelerations in sudden
halt scenarios at different initial speeds.

72
downstream controller are depicted in Figure 5-8. The longitudinal accelerations
commanded by the Control Projection module and the downstream controller are de-
picted in Figure 5-9. Some observations are immediate. In this sudden halt scenario,
there is a constant braking acceleration and so the control signal from the Control
Projection module is a square wave at the constant breaking acceleration. By contrast
the downstream controller both anticipates the sudden stop and continues controlling
the trajectory of the vehicle after it is completed. Due to the predictive aspects of
the downstream controller, the difference in control signals are sometimes substan-
tial, reaching up to 2.5 m/s2 for one scenario. The ASIL requirements on the Control
Projection module must either admit this error in the Control Projection’s estimates
or else a different method of control projection must be employed.

Figure 5-10: Reference and predicted trajectories for the downstream controller in
lane change scenarios at different initial speeds.

73
Figure 5-11: Control Projection and downstream commanded accelerations in lane
change scenarios at different initial speeds.

74
Figure 5-12: Trajectory-based flat controller and downstream commanded accelera-
tions in lane change scenarios at different initial speeds.

75
 The lateral experiment is conducted similarly for a lane change scenario at various
speeds. The reference trajectories and predicted trajectories are depicted in Figure
5-10. The lateral accelerations commanded by the Control Projection module and
the downstream controller are depicted in Figure 5-11. This lane change scenario
reveals a flaw in the use of a simple pure pursuit controller to estimate the control
action of a trajectory. Since the lateral acceleration produced by the pure pursuit
control law depends on the angle between the vehicle heading and a look ahead point,
the pure pursuit controller cannot execute a lane change without overshoot error.
This overshoot creates an error signal to steer back to the reference trajectory. The
predictive downstream controller does not overshoot to nearly the same extent and
so the control signal produced by the Control Projection module is a poor fit for the
accelerations of a lane change maneuver. This result would need to be accounted for in
a final ASIL certification analysis or else this method of control projection improved
- perhaps by directly inverting the trajectory using the differential flatness of the
kinematic bicycle model. An example of flatness-based control is shown for the same
inputs in Figure 5-12. Indeed the flat controller is a better fit to the downstream
control commands and does not exhibit the asymmetry or asymptotic relationship
between control and speed present in the pure pursuit controller.

76
Chapter 6

Conclusion

6.1 Lessons Learned

Developing the new safety architecture for this autonomous planning software was a
lengthy project. It involved numerous design choices and reincorporation of existing
modules and interfaces. The final system design reflects two core conclusions:

1. Complex and partially reliable modules can be composed using ASIL decompo-
sition to produce a more reliable overall system.

2. The safety guarantees provided by existing modules can be extended by trans-

forming abstract traffic rules into constraints on the state of the vehicle.

Redundant pathways are used to combine the parallel checks performed by the
Safety Force Field and the Collision Detector modules. Both modules are only par-
tially reliable but with ASIL decomposition, the modules can be synthesized into
a ASIL D system. This decomposition requires independence between the modules
which is an assumption supported by testing.
Multiple new safety guarantees on lane discipline, wait signal obedience, and other
traffic rules are added to the autonomous planning system by transforming these
requirements. The Virtual Obstacle Generator creates state space restrictions which
enable existing safety supervisors to enforce these safety goals.

77
 Together, ASIL decomposition and safety goal transformation are used to create
a planning architecture which can provide broader and stronger guarantees on safety.
The new design prepares the autonomous system for rigorous ASIL certification.

6.2 Future Work

The development of a new safety architecture for an autonomous driving system in this
thesis has several natural extensions. Firstly, finalizing the safety architecture enables
the lengthy process of ASIL certification to begin. This is an industry-standard
engineering and regulatory process which establishes the ASIL of the autonomous
system. This certification process is currently on-going for the Driveworks hardware
and software package.
Secondly, the analysis and justifications provided in Chapter 5 rely heavily on
simulated and hand-crafted testing scenarios. However, the performance of the safety
modules depends on the distribution of scenarios encountered in real-world driving.
This distribution is certainly not identical to that used in testing. Future work should
focus on gathering real-world driving data using this planning architecture as well as
developing metrics which can be evaluated without requiring counterfactual simula-
tion.
A third line of improvements could focus on the performance of the safety modules
themselves. The ASIL of components is a minimum standard, not a maximum. This
project’s analyses revealed that the tuning and design assumptions of modules like
the Safety Force Field and Control Projection module can be improved. In the case
of the Control Projection module, perhaps substantially. Additional improvements
could add cost-based risk minimization to the Collision Detector module which may
improve over the maximum likelihood estimates used for agent trajectories currently.
A fourth and final line of future work could focus on reducing the computational
costs of safety monitoring in the planning software. Currently, the computational re-
sources used to forward simulate and collision check multiple trajectories in both the
Safety Force Field and the Collision Detector modules is substantial. It is possible,

78
given the limited state and that safety evaluations are performed pairwise between
the ego and other road agents, to memoize many of these evaluations using offline
computation and a lookup table. While it could require computing a Lipschitz con-
stant for the safety potential to ensure sufficiently dense sampling, this optimization
could reduce costs and allow greater accuracy than online evaluation.
Given the active development of this autonomous software, I few doubts that
many of these improvements will eventually be implemented.

79
80
Appendix A

Safety Goals

There are many safety goals for the autonomous planning software. Several of the
most important requirements, and those focused on by this thesis are reproduced
here. Any component responsible for ensuring theses safety requirements are met,
that is whose failure could result in the violation of one of these safety goals, must
be ASIL D certifiable.

Table A.1: Primary Safety Goals

Count Safety Requirement

1 Ego-vehicle shall stay on active roadway when driving.
2 Ego-vehicle shall avoid collision with vehicles.
3 Ego-vehicle shall avoid collision with pedestrians.
4 Ego-vehicle shall avoid collision with non-human obstacles.
5 Ego-vehicle shall yield to vehicles with right-of-way at intersections.
6 Ego-vehicle shall halt before stop signals and signs.
7 Ego-vehicle shall wait at wait signals and signs.
8 Ego-vehicle shall avoid operation post collision.

81
82
Bibliography

[1] ISO 8855: Road vehicles - Vehicle dynamics and road-holding ability. Interna-
tional Standards Organization, 2 ed., 2011.

[2] N. C. for Statistics and Analysis, 2019 Summary of Motor Vehicle Crashes Traffic
Safety Fact Sheet. National Highway Traffic Safety Administration, 2021.

[3] S. Singh, Critical Reasons for Crashes Investigated in the National Motor Vehicle
Crash Causation Survey. National Center for Statistics and Analysis, 2015.

[4] ISO 26262: Road vehicles — Functional safety. International Standards Orga-
nization, 2 ed., 2018.

[5] J. N. David Nistér, Hon-Leung Lee and Y. Wang, “Safety force field deep dive,”
2019.

[6] E. S. Andrea Bajcsy, Karen Leung and M. Pavone, “A control theorist’s guide to
the safety force field,” 2021.

[7] I. Mitchell, A. Bayen, and C. Tomlin, “A time-dependent hamilton-jacobi formu-

lation of reachable sets for continuous dynamic games,” IEEE Transactions on
Automatic Control, vol. 50, no. 7, pp. 947–957, 2005.

[8] M. Chen, J. F. Fisac, S. Sastry, and C. J. Tomlin, “Safe sequential path planning
of multi-vehicle systems via double-obstacle hamilton-jacobi-isaacs variational
inequality,” in 2015 European Control Conference (ECC), pp. 3304–3309, 2015.

[9] S. Bansal and C. Tomlin, “Deepreach: A deep learning approach to high-

dimensional reachability,” 2020.

[10] D. Fridovich-Keil and C. J. Tomlin, “Approximate solutions to a class of reacha-

bility games,” in 2021 IEEE International Conference on Robotics and Automa-
tion (ICRA), pp. 12610–12617, 2021.

[11] K. Leung, E. Schmerling, M. Zhang, M. Chen, J. Talbot, J. C. Gerdes, and

M. Pavone, “On infusing reachability-based safety assurance within planning
frameworks for human-robot vehicle interactions,” CoRR, vol. abs/2012.03390,
2020.

83
[12] A. Papachristodoulou and S. Prajna, “On the construction of lyapunov func-
tions using the sum of squares decomposition,” in Proceedings of the 41st IEEE
Conference on Decision and Control, 2002., vol. 3, pp. 3482–3487 vol.3, 2002.

[13] A. Majumdar, A. A. Ahmadi, and R. Tedrake, “Control design along trajectories

with sums of squares programming,” CoRR, vol. abs/1210.0888, 2012.

[14] A. Majumdar, “Robust online motion planning with reachable sets by anirudha,”
2013.

[15] A. Majumdar and R. Tedrake, “Funnel libraries for real-time robust feedback
motion planning,” CoRR, vol. abs/1601.04037, 2016.

[16] H. Dai, B. Landry, L. Yang, M. Pavone, and R. Tedrake, “Lyapunov-stable

neural-network control,” CoRR, vol. abs/2109.14152, 2021.

[17] S. M. Richards, F. Berkenkamp, and A. Krause, “The lyapunov neural network:

Adaptive stability certification for safe learning of dynamic systems,” CoRR,
vol. abs/1808.00924, 2018.

[18] W. Xiao, N. Mehdipour, A. Collin, A. Y. Bin-Nun, E. Frazzoli, R. D. Tebbens,

and C. Belta, Rule-Based Optimal Control for Autonomous Driving, p. 143–154.
New York, NY, USA: Association for Computing Machinery, 2021.

[19] C.-I. Vasile, J. Tumova, S. Karaman, C. Belta, and D. Rus, “Minimum-violation

scltl motion planning for mobility-on-demand,” in 2017 IEEE International Con-
ference on Robotics and Automation (ICRA), pp. 1481–1488, 2017.

[20] W. Schwarting, A. Pierson, J. Alonso-Mora, S. Karaman, and D. Rus, “Social

behavior for autonomous vehicles,” Proceedings of the National Academy of Sci-
ences, vol. 116, no. 50, pp. 24972–24978, 2019.

[21] “Nvidia driveworks.” NVIDIA Corporation. Version 3.5. 2021.

[22] D. Sunday, Practical Geometry Algorithms. 2001.

84